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