Алгоритм приведения к СКНФ c помощью таблицы истинности

1. Строим таблицу значений формулы.

2. Рассматриваем только те строки таблицы, где формула принимает значение 0.

3. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием.

4. Образуем конъюнкцию полученных дизъюнкций.

Пример.

Построить СКНФ для данных формул логики высказываний.

1. .

2.

Решение.

1. Строим таблицу значений, используя предыдущий пример.

Рассматриваем только наборы, на которых формула принимает значение ноль.

СКНФ (0): № 0, 1, 2, 3, 6:

2. Строим таблицу значений, используя предыдущий пример.

СКНФ (0): № 0, 1, 2:

Определение. Формулы, в которых имеются только операции Ø, Ù, Ú над простыми переменными называются приведенными формулами.

Теорема. Для каждой формулы существует равносильная ей приведенная формула.

Варианты заданий

Вариант 1

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 2

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 3

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 4

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 5

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 6

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

а)

б)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 7

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a) хÚ ( Ù z)Ú (yÙ )

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

а)

б)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 8

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b) ( Ú z)Ù yÙ ( Ú z)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 9

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 10

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 11

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 12

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a) ;

b) .

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a) ;

b) .

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 13

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 14

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вариант 15

Задание 1. С помощью равносильных преобразований привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 2. С помощью таблицы истинности привести формулу к а) СДНФ; б) СКНФ.

a)

b)

Задание 3. Записать формулы в приведенном виде (содержащем только операции Ø, Ù, Ú над простыми переменными).

a)

b)

Вопросы к защите практической работы №3

1. Сформулируйте определение СКНФ

2. Сформулируйте определение СДНФ

3. Опишите алгоритм построения СКНФ аналитическим способом

4. Опишите алгоритм построения СДНФ аналитическим способом

5. Опишите алгоритм построения СКНФ табличным способом

6. Опишите алгоритм построения СДНФ табличным способом

7. Какая формула называется приведенной?