Содержание
6 задач
СКНФ, СДНФ, таб. метод, метод Карно, метод Квайна, полнота системы, кратчайший путь орграф, мксимальный поток в транспортной сети, задача об оптимальном назначении
Выдержка из текста
Задача 1. Найти СДНФ, СКНФ, а также сокращенную, ядровую и все минимальные дизъюнктивные нормальные формы булевой функции . Функция задана указанием номеров наборов значений переменных, на которых она равна нулю. Наборы нумеруются числами от 0 (набор (0,0,0)) до 7 (набор (1,1,1)).
№2 f: 1,2,6
Решение
Наборы значений переменных
Номер
набораНабор
00001
10010
20100
30111
41001
51011
61100
71111
Таким, образом, искомая функция: , и .
Алгоритм получения СДНФ по таблице истинности
1.Отметить те строки ТИ, в последнем столбце которых стоят 1:
2.Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =1, то в конъюнкцию включают саму эту переменную, если =0, то ее отрицание:
3.Все полученные конъюнкции связать в дизъюнкцию.
Алгоритм получения СКНФ по таблице истинности
1.Отметить те строки ТИ, в последнем столбце которых стоят 0:
2.Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму эту переменную, если =1, то ее отрицание:
3.Все полученные дизъюнкции связать в конъюнкцию: