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