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

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

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

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

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

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

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

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

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

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

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

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

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

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

, ;

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

;

, ;

, ;

;

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

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

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

.

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

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

Примеры ДНФ:

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

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

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

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

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

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

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

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

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

Примеры КНФ:

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

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

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

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

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

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

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

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

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

Психолого - педагогические принципы развития мышления школьников
В соответствии с требованиями, предъявляемыми современной школой, обучение в ней должно ориентироваться на развитие продуктивного, творческого мышления, обеспечивающего возмож­ность самостоятельно приобретать новые знания, применять их в многообразных условиях окружающей действительности. Мы беремс ...

Инструменты управления изменениями. Этапы изменений
Инструменты управления изменениями в организации представляют собой приемы и методы, которыми может пользоваться менеджер при осуществлении изменений. Управляет изменением менеджер. Ему надо не только спланировать изменение, но и убедить исполнителей в целесообразности нововведения, в том, что оно ...