Для упрощения логических высказываний могут быть использованы следующие равносильности (свойства):
Свойства конъюнкции и дизъюнкции
Коммутативные (переместительные) законы
Ассоциативные (сочетательные) законы
Дистрибутивные (распределительные) законы
Законы поглощения
Законы склеивания
Свойства с отрицанием
Законы Де Моргана
Закон двойного отрицания ;
Закон противоречия ;
Закон исключения третьего .
Свойства с логическими константами
,
;
Связь между логическими операциями
;
,
;
,
;
;
Нормальные формы. Совершенные нормальные формы
Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Примеры элементарных конъюнкций
.
Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) и выглядит следующим образом:
где и
- различные элементарные конъюнкций.
Примеры ДНФ:
Алгоритм приведения к ДНФ может быть описан с привлечением приведенных выше равносильностей:
1. Используя закон двойного отрицания и законы Де Моргана все отрицания "спускаются" до переменных;
2. Раскрываются скобки по распределительному закону;
3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние конъюнкции и повторение переменных;
4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.
Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Примеры элементарных дизъюнкций:
Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) и выглядит следующим образом:
где и
- различные элементарные дизъюнкции.
Примеры КНФ:
Алгоритм приведения к КНФ может быть описан с помощью тех же соотношений и законов, которые использовались и в алгоритме для ДНФ.
1. Используя закон двойного отрицания и законы Де Моргана все отрицания "спускаются" до переменных;
2. Раскрываются скобки по распределительному закону;
3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние дизъюнкции и повторения переменных;
4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.
Совершенной дизъюнктивной нормальной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой: 1) все слагаемые содержат сомножителем все переменные - без отрицания либо с отрицанием, но не вместе. 2) отсутствуют повторения слагаемых и сомножителей.
Совершенной конъюнктивной нормальной формой формулы алгебры высказываний (СКНФ) называется КНФ, в которой: 1) каждый сомножитель содержит слагаемым каждую переменную, без отрицания либо с отрицанием, но не вместе; 2) отсутствуют повторения сомножителей и слагаемых.
Статьи по теме:
Специальное формирование как алгоритмических, так и
эвристических приемов умственной деятельности
Исследование процесса усвоения и применения знаний показали, что обычно учащиеся усваивают содержательную сторону знаний и непосредственно с ней связанные конкретные приемы решения довольно узкого круга задач. Лишь у школьников с высокой обучаемостью на основе решения единичных задач формируются об ...
Экологическая психология и образование
Традиционно в педагогической практике процесс экологического образования детей связывается в первую очередь с их экологическим, а чаще просто биологическим просвещением и порой вовсе отождествляется с последним. При этом экологическая воспитанность рассматривается как некое обязательное следствие э ...
Механизм творческого воображения. Понятие воображения
Наряду с образами памяти, которые являются копиями восприятия, человек может создавать и совершенно новые образы. В образах может предстать и то, чего мы непосредственно не воспринимали, и то, чего в такой именно форме в действительности не существует. Это образы воображения. Итак, «воображение – э ...