Содержание

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

Похожие записи