Нормальные формы формул алгебры высказываний

Элементарная конъюнкция (ЭК), элементарная дизъюнкция (ЭД) от высказывательных переменных. Свойство ЭК (ЭД) принимать значение 1 (0) ровно на одном наборе значений переменных. Конъюнктивная нормальная форма (КНФ) и дизъюнктивная нормальная форма (ДНФ) формулы алгебры высказываний. Критерии существования КНФ и ДНФ. Алгоритмы построения различных КНФ и ДНФ для заданной формулы. Критерий тождественной истинности (ложности) формул алгебры высказываний, основанный на свойствах ЭД и КНФ (ЭК и ДНФ).

13.1. Указать элементарные конъюнкции и элементарные дизъюнкции среди следующих формул:

1) ; 5) ;

2) ; 6) ;

3) ; 7) ;

4) ; 8) .

13.2. Доказать, что каждая элементарная конъюнкция истинна, а каждая элементарная дизъюнкция ложна только на одном наборе истинностных значений входящих в нее переменных.

13.3. Установить, какие из данных формул являются элементарными конъюнкциями, элементарными дизъюнкциями, КНФ и ДНФ:

1) ; 6) ;

2) ; 7) ;

3) ; 8) ;

4) ; 9) ;

5) ; 10) .

13.4. В упражнении 13.3. определить для элементарных конъюнкций и ДНФ наборы значений переменных, на которых они принимают значение 1; для элементарных дизъюнкций и КНФ – наборы, на которых они принимают значение 0.

13.5. Построить различные элементарные конъюнкции, содержащие

а) одну; б) две; в) три

из переменных , , и являющиеся истинными на каждом из следующих наборов:

1) , , ;

2) , , ;

3) , , .

13.6. Построить различные элементарные дизъюнкции, содержащие

а) одну; б) две; в) три

из переменных , , и являющиеся ложными на каждом из следующих наборов:

1) , , ;

2) , , ;

3) , , .

13.7. Построить различные КНФ, являющиеся ложными на следующих наборах значений переменных , , :

1) , ;

2) , , ;

3) .

13.8. Построить различные ДНФ, являющиеся истинными на наборах значений переменных , , , приведенных в упражнении 13.7.

13.9. Следующие формулы преобразовать так, чтобы они содержали только операции :

1) ;

2) ;

3) ;

4) ;

5) .

13.10. Следующие формулы преобразовать так, чтобы они содержали только операции :

1) ;

2) ;

3) ;

4) .

13.11. Следующие формулы преобразовать так, чтобы они содержали только операции :

1) ;

2) ;

3) ;

4) .

13.12. Доказать, что следующие системы связок являются полными, то есть для любой формулы существует эквивалентная ей формула, содержащая логические связки только из заданной системы:

1) ;

2) ;

3) .

13.13. Доказать, что системы связок

1) ;

2)

где – штрих Шеффера (или дизъюнкция отрицаний): ,

– стрелка Пирса (или конъюнкция отрицаний): ,

являются полными.

13.14. Доказать, что следующие системы связок не являются полными, то есть, не достаточны для выражения любой формулы:

1) ;

2) ;

1) .

13.15. Следующие формулы преобразовать так, чтобы отрицание относилось только к высказывательным переменным:

1) ;

2) ;

3) ;

4) .

13.16. Следующие формулы преобразовать так, чтобы они содержали только операции , , , при этом относилось только к высказывательным переменным:

1) ;

2) ;

3) ;

4) .

13.17. Приведите следующие формулы к различным КНФ и различным ДНФ с помощью равносильных преобразований:

1) ; 7) ;

2) ; 8) ;

3) ; 9) ;

4) ; 10) ;

5) ; 11) ;

6) ; 12) .

13.18. Показать, что для любой формулы существует бесконечное множество различных КНФ и ДНФ.

13.19. Указать тип формул упражнения 13.17., используя критерии тождественной истинности и тождественной ложности формул, основанные на свойствах элементарной дизъюнкции и КНФ; элементарной конъюнкции и ДНФ.

13.20. Может ли Андрей получить 3, а Миша 4, если известно, что каждое из приведенных ниже высказываний истинно:

а) Коля получил 5 или Нина не получила 4;

б) Нина получила 4 или Андрей не получил 3;

в) Маша не получила 4 или Даша получила 2;

г) Даша не получила 2 или Володя не получил 4;

д) Коля не получил 5 или Володя получил 4.

13.21. При составлении расписания уроков на один день учителя математики, истории и литературы высказали следующие пожелания: математик просил поставить ему или первый, или второй урок; историк – или первый, или третий; учитель литературы – или второй, или третий. Как составить расписание уроков, чтобы учесть все пожелания?

13.22. (Задача Венна.) Существовал финансовый клуб с такими правилами:

а) Члены финансового комитета должны избираться среди членов общей дирекции.

б) Нельзя быть одновременно членом общей дирекции и членом библиотечного совета, не будучи членом финансового комитета.

в) Ни один член библиотечного совета не может быть членом финансового комитета.

Упростить правила.

13.23. (Задача Кислера.) Браун, Джонс и Смит обвиняются в подделке сведений о подлежащих налоговому обложению доходах. Они дают следующие показания под присягой:

Браун: Джонс виновен, а Смит невиновен.

Джонс: Если Браун виновен, то виновен и Смит.

Смит: Я невиновен, но хотя бы один из них двоих виновен.

Ответить на вопросы:

а) Совместимы ли показания всех троих одновременно?

б) Показания одного из обвиняемых следуют из показаний другого; о чьих показаниях идет речь?

в) Если все трое невиновны, то кто совершил лжесвидетельство?

г) Предполагая, что показания всех обвиняемых верны, указать, кто виновен, а кто невиновен?

д) Если невиновный говорит истину, а виновный лжет, то кто невиновен, а то виновен?

Дата добавления: 2015-06-27