Задача 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. Все полученные дизъюнкции связать в конъюнкцию:
