Дискретная математика Вариант №2

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

№ 2 f: 1,2,6

Решение

Наборы значений переменных

Номер

набора Набор

0 0 0 0 1

1 0 0 1 0

2 0 1 0 0

3 0 1 1 1

4 1 0 0 1

5 1 0 1 1

6 1 1 0 0

7 1 1 1 1

Таким, образом, искомая функция:, и .

Алгоритм получения СДНФ по таблице истинности

1. Отметить те строки ТИ, в последнем столбце которых стоят 1:

2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =1, то в конъюнкцию включают саму эту переменную, если =0, то ее отрицание:

3. Все полученные конъюнкции связать в дизъюнкцию.

Алгоритм получения СКНФ по таблице истинности

1. Отметить те строки ТИ, в последнем столбце которых стоят 0:

2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму эту переменную, если =1, то ее отрицание:

3. Все полученные дизъюнкции связать в конъюнкцию: