Формы записи высказываний. Алгоритмические способы решения логических задач

Для упрощения логических высказываний могут быть использованы следующие равносильности (свойства):

Свойства конъюнкции и дизъюнкции

Коммутативные (переместительные) законы

Ассоциативные (сочетательные) законы

Дистрибутивные (распределительные) законы

Законы поглощения

Законы склеивания

Свойства с отрицанием

Законы Де Моргана

Закон двойного отрицания ;

Закон противоречия ;

Закон исключения третьего .

Свойства с логическими константами

, ;

Связь между логическими операциями

;

, ;

, ;

;

Нормальные формы. Совершенные нормальные формы

Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Примеры элементарных конъюнкций

.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) и выглядит следующим образом:

где и - различные элементарные конъюнкций.

Примеры ДНФ:

Алгоритм приведения к ДНФ может быть описан с привлечением приведенных выше равносильностей:

1. Используя закон двойного отрицания и законы Де Моргана все отрицания "спускаются" до переменных;

2. Раскрываются скобки по распределительному закону;

3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние конъюнкции и повторение переменных;

4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.

Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Примеры элементарных дизъюнкций:

Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) и выглядит следующим образом:

где и - различные элементарные дизъюнкции.

Примеры КНФ:

Алгоритм приведения к КНФ может быть описан с помощью тех же соотношений и законов, которые использовались и в алгоритме для ДНФ.

1. Используя закон двойного отрицания и законы Де Моргана все отрицания "спускаются" до переменных;

2. Раскрываются скобки по распределительному закону;

3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние дизъюнкции и повторения переменных;

4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.

Совершенной дизъюнктивной нормальной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой: 1) все слагаемые содержат сомножителем все переменные - без отрицания либо с отрицанием, но не вместе. 2) отсутствуют повторения слагаемых и сомножителей.

Совершенной конъюнктивной нормальной формой формулы алгебры высказываний (СКНФ) называется КНФ, в которой: 1) каждый сомножитель содержит слагаемым каждую переменную, без отрицания либо с отрицанием, но не вместе; 2) отсутствуют повторения сомножителей и слагаемых.

Статьи по теме:

Особенности зрительного восприятия детей с нормой и нарушениями зрения
зрительный восприятие анализатор амблиопия Развитие и использование зрительного восприятия в обучении слепых детей с остаточным зрением и слабовидящих является в настоящее время коренной проблемой тифлопсихологии и тифлопедагогики. Исследовав и изучив множество источников и работ таких исследовател ...

Формы записи высказываний. Алгоритмические способы решения логических задач
Элементарные высказывания в логике высказывания рассматриваются как не расчленяемые "атомы", а составные высказывания - как "молекулы'', образованные из "атомов" применением к ним логических операций. Логика высказываний интересуется единственным свойством элементарных выск ...

Особенности изучение педагогического процесса
Характерная черта педагогических процессов – неоднозначность их протекания. Результаты обучения, образования, воспитания, развития зависят от одновременного воздействия очень многих причин. Достаточно изменить влияние даже одного-двух факторов, чтобы эти результаты существенно отличались между собо ...