Примеры заданий по теме

1. Определите истинностные значения следующих высказываний.

1) 5 – простое число и 8 – простое число;

2) 5 – простое число или 8 – простое число;

3) Если 4 делится на 2, то 4 делится на 3;

4) Если 5 делится на 2, то 4 делится на 3; 

5) Если 15 делится на 3, то 8 делится на 4;

6) Если 15 делится на 4, то 8 делится на 4;

7) 15 делится на 3 тогда и только тогда, когда 8 делится на 4.

2. Составьте истинностные таблицы для следующих формул и укажите, какие из формул являются тавтологиями, какие – выполнимыми, какие – опровержимыми, какие – тождественно ложными.

1) ( )  (С & );

2) А  (В  А);

3) (А В) & (В С) & .

Тема 2. Равносильность.

Содержание. Определение равносильных формул. Критерий равносильности. Основные равносильности. Равносильные преобразования формул.

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

Контрольные вопросы

1. Какие пропозициональные формулы называются равносильными?

2. Сформулируйте критерий равносильности формул.

3. Напишите список основных равносильностей.

4. Какими методами можно доказывать равносильность формул алгебры высказываний?

Примеры заданий по теме

1. Приведите формулу к возможно более простой форме.

2. Докажите, что формула является тавтологией.

Тема 3. Нормальные формы

Содержание. Элементарная конъюнкция. Дизъюнктивная нормальная форма (ДНФ). Теорема о приведении к ДНФ. Элементарная дизъюнкция. Конъюнктивная нормальная форма (КНФ). Теорема о приведении к КНФ. Проблема разрешения.

Цель. Освоение алгоритмов получения дизъюнктивной и конъюнктивной нормальных форм (ДНФ и КНФ).

Контрольные вопросы

1. Какая пропозициональная формула называется элементарной конъюнкцией?

2. Дайте определение дизъюнктивной формулы.

3. Сформулируйте теорему о приведении формулы к ДНФ.

4. Сформулируйте алгоритм приведения формулы к ДНФ.

5. Какая пропозициональная формула называется элементарной дизъюнкцией?

6. Дайте определение конъюнктивной нормальной формы.

7. Сформулируйте теорему о приведении формулы к КНФ.

8. Сформулируйте алгоритм приведения формулы к КНФ.

9. Как формулируется проблема разрешения в алгебре высказываний?

10. Как используются ДНФ и КНФ для решения проблемы разрешения?

Примеры заданий по теме

1. Является ли тавтологией формула ?

2. Является ли тождественно ложной формула ?

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

Содержание. Определение совершенных дизъюнктивных и конъюнктивных нормальных форм (СДНФ и СКНФ). Теоремы существования и единственности совершенных нормальных форм.

Цель. Освоение алгоритмов получения совершенных дизъюнктивной и конъюнктивной нормальных форм (СДНФ и СКНФ).

Контрольные вопросы

1. Сформулируйте определение совершенной дизъюнктивной нормальной формы.

2. При каких условиях существует совершенная дизъюнктивная нормальная форма для пропозициональных формул?

3. Сформулируйте теорему о единственности совершенной дизъюнктивной нормальной формы.

4. Сформулируйте определение совершенной конъюнктивной нормальной формы.

5. При каких условиях существует совершенная конъюнктивная нормальная форма для пропозициональных формул?

6. Сформулируйте теорему о единственности совершенной конъюнктивной нормальной формы.