НОРМАЛЬНЫЕ ФОРМЫ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Элементарная конъюнкция (ЭК), элементарная дизъюнкция (ЭД) от высказывательных переменных. Свойство ЭК (ЭД) принимать значение 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.   (Задача Кислера.) Браун, Джонс и Смит обвиняются в подделке сведений о подлежащих налоговому обложению доходах. Они дают следующие показания под присягой:

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

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

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

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

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

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

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

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

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