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

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

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

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

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

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

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

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

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

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

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

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

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

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

, ;

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

;

, ;

, ;

;

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

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

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

.

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

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

Примеры ДНФ:

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

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

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

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

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

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

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

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

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

Примеры КНФ:

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

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

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

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

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

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

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

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

Изучение развития художественного восприятия старших дошкольников
Художественное восприятие существенно отличается не только от перцепции предметов действительности, но и от постижения знаковых предметов, функционирующих в науке. И связано это с практически-действенным характером искусства: ведь как раз в ходе восприятия художественного произведения и протекает д ...

Определение логико-психологической, дидактической и методической структуры учебного занятия. Технологическая схема учебного занятия
Урок – педагогическое произведение, и поэтому он должен отличаться целесообразностью, внутренней взаимосвязанностью частей, единой логикой развёртывания деятельности педагога и учащихся. Соблюдая основные требования к уроку, учитывая индивидуальные особенности учащихся, преподаватель должен вносить ...

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