Формы записи высказываний. Алгоритмические способы решения логических задач

Для упрощения логических высказываний могут быть использованы следующие равносильности (свойства):

Свойства конъюнкции и дизъюнкции

Коммутативные (переместительные) законы

Ассоциативные (сочетательные) законы

Дистрибутивные (распределительные) законы

Законы поглощения

Законы склеивания

Свойства с отрицанием

Законы Де Моргана

Закон двойного отрицания ;

Закон противоречия ;

Закон исключения третьего .

Свойства с логическими константами

, ;

Связь между логическими операциями

;

, ;

, ;

;

Нормальные формы. Совершенные нормальные формы

Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Примеры элементарных конъюнкций

.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) и выглядит следующим образом:

где и - различные элементарные конъюнкций.

Примеры ДНФ:

Алгоритм приведения к ДНФ может быть описан с привлечением приведенных выше равносильностей:

1. Используя закон двойного отрицания и законы Де Моргана все отрицания "спускаются" до переменных;

2. Раскрываются скобки по распределительному закону;

3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние конъюнкции и повторение переменных;

4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.

Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Примеры элементарных дизъюнкций:

Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) и выглядит следующим образом:

где и - различные элементарные дизъюнкции.

Примеры КНФ:

Алгоритм приведения к КНФ может быть описан с помощью тех же соотношений и законов, которые использовались и в алгоритме для ДНФ.

1. Используя закон двойного отрицания и законы Де Моргана все отрицания "спускаются" до переменных;

2. Раскрываются скобки по распределительному закону;

3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние дизъюнкции и повторения переменных;

4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.

Совершенной дизъюнктивной нормальной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой: 1) все слагаемые содержат сомножителем все переменные - без отрицания либо с отрицанием, но не вместе. 2) отсутствуют повторения слагаемых и сомножителей.

Совершенной конъюнктивной нормальной формой формулы алгебры высказываний (СКНФ) называется КНФ, в которой: 1) каждый сомножитель содержит слагаемым каждую переменную, без отрицания либо с отрицанием, но не вместе; 2) отсутствуют повторения сомножителей и слагаемых.

Статьи по теме:

Обучающий эксперимент и анализ его результатов
Следующим этапом нашей работы было проведение серии экспериментальных занятий с учащимися 7-х классов средней школы г. Астрахани. Мы не приводим в нашей работе описание каждого проведенного урока. Останавливаемся лишь на некоторых методических приемах, использовавшихся нами на уроках алгебры для ак ...

Рекомендации по работе с детьми-сиротами и детьми, оставшимися без попечения родителей на уроках естественно-географического цикла
Исходя из изученного и представленного в данной работе теоретического материала и результатов диагностики, можно определить ряд рекомендаций для учителя по работе с детьми-сиротами и детьми, оставшимися без попечения родителей на уроках естественно-географического цикла. Повышение мотивации обучени ...

Понятие — продуктивное мышление. Общая характеристика видов мышления
Предмет нашего исследования — творческое (продуктивное) мышления. Хотя это понятие давно употребляется в психологической литературе, его содержание дискуссионно. Обращаясь к анализу литературы, мы ставили перед собой задачу выяснить, как крупнейшие представители психологических теорий определяют по ...