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

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

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

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

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

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

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

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

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

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

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

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

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

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

, ;

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

;

, ;

, ;

;

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

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

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

.

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

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

Примеры ДНФ:

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

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

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

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

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

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

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

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

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

Примеры КНФ:

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

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

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

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

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

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

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

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

Современная языковая ситуация и проблемы речевой культуры
Культурологами, психологами, лингвистами, а также писателями и журналистами отмечается заметное снижение общего уровня речевой и коммуникативной культуры на рубеже XX и XXI вв. Состояние русской речи, особенно речи молодежи, вызывающее глубокую озабоченность не только у лингвистов и преподавателей- ...

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

Содержание среднего образования
В 1870-1872 гг. были созданы три основных и наиболее распространённых типа общеобразовательной средней школы, которые просуществовали в Сибири с известными изменениями до их ликвидации в 1920-1921 гг. Классическая гимназия являлась привилегированной средней школой с восьмилетним курсом обучения, ре ...