Задача 3.1 Построить СДНФ и СКНФ для функции, таблица истинности которой имеет следующий вид:
х | y | z | f(x,y,z) |
Решение.
Построение СДНФ. Функция принимает значение 1 на кортежах (001), (010), (101). Кортежу (001) соответствует элементарная конъюнкция . Кортежу (010) соответствует элементарная конъюнкция . Кортежу (101) соответствует элементарная конъюнкция . Получаем СДНФ f(x,y,z)= .
Построение СКНФ. Функция принимает значение 0 на кортежах (000), (011), (100), (110), (111). Кортежу (000) соответствует элементарная дизъюнкция . Кортежу (011) - , кортежу (100) - , кортежу (110) - , кортежу (111) - .
Получаем СКНФ f(x,y,z)=( )()()()().
Практические задания
4.1 Построить СДНФ и СКНФ.
Вариант 1 а) ; б) ; в) . | Вариант 2 а) ; б) ; в) . |
Вариант 3 а) б) в) | Вариант 4 . а) б) в) . |
Контрольные вопросы
1) Дайте определение ДНФ и КНФ.
2) Дайте определение СДНФ и СКНФ.
3) Каков алгоритм построения СДНФ?
4) Каков алгоритм построения СКНФ?