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