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