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

1. Привести к совершенной конъюнктивной нормальной форме относительно переменных , и  формулу .

2. По данному набору значений переменных постройте элементарную конъюнкцию, принимающую значение 1 только на наборе (0, 0, 1, 1) значений переменных.

Тема 5. Булевы функции.

Содержание. Понятие булевой (истинностной) функции. Представление истинностных функций формулами. Метод Блейка – Порецкого. Полные системы булевых функций. Неполные системы функций. Применение алгебры высказываний к описанию релейно-контактных схем.

Цель. Усвоение понятия булевой (истинностной) функции и способов её задания. Понятие полной системы булевых  функций.

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

1. Дайте определение булевой функции.

2. Как задать булеву функцию таблицей?

3. Как найти формулу в СДНФ булевой функции, которая задана таблично?

4. Как найти формулы в СКНФ булевой функции, которая задана таблично?

5. Как можно упростить формулы булевых функций методом Блейка – Порецкого?

6. Какие системы булевых функций называются полными?

7. Как установить полноту системы булевых функций?

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

1. Упростите  методом Блейка – Порецкого  булеву функцию  f (X, Y, Z, V),  которая задана следующей формулой:

2. Докажите полноту следующих систем функций: {,  ¯ }, {&,  ¯ }, {,  ¯ }.

Тема 6. Логическое следование формул

Содержание. Логическое следствие. Признаки логического следствия. Правила логических умозаключений. Закон контрапозиции.

Тема 7. Виды теорем и методы математических доказательств

Содержание. Прямая и обратная теоремы. Противоположная и обратная противоположной теоремы. Необходимые и достаточные условия. Методы математических доказательств. Доказательство от противного. Метод приведения к абсурду.

Тема 8. Аксиоматическое определение логики высказываний

Содержание. Алфавит, формулы и аксиомы исчисления высказываний. Вывод из аксиом – доказуемость формул. Выводимость из гипотез. Правила вывода. Построение выводов.

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

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

1. Как определяются формальные (аксиоматические) теории в математической логике?

2. Дайте определение одной из формальных теорий, являющейся исчислением высказываний.

3. Приведите примеры формул, являющихся аксиомами по всем схемам аксиом определения формальной теории.

4. Что такое вывод из аксиом и вывод из гипотез?

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

1. Является ли данная последовательность формул выводом из аксиом:

а)  А₁   В (А В),

А₂   (В (А В)) (В (В (А В)),

А₃   В (В (А В));         

б)  А₁   (А А)  (В (А А)),

А₂    А А,

А₃   В  (А А);

в)  А₁   А  (В С).

2. Является ли данная последовательность формул выводом из гипотез:

А₁   А В,

А₂   А,

А₃   В,         

А₄   В (С В),

А₅    С В.

Тема 9. Теорема дедукции.

Содержание. Теорема дедукции. Следствия. Применения теоремы дедукции. Метод резолюций в исчислении высказываний.

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