Алгоритм представления функции в виде СДНФ

1. Выписываем носитель функции N_f.

2. Для каждого булева вектора носителя выписываем элементарную конъюнкцию.

3. Выписываем дизъюнкцию всех конъюнкций.

Алгоритм представления функций в виде СКНФ.

1. Выписываем дополнение носителя функции.

2. Для каждого вектора из выписываем полную дизъюнкцию литералов, над каждым литералом ставим отрицание значения компоненты вектора.

3. Выписываем конъюнкцию всех элементарных дизъюнкций.

Проблема разрешимости формул решается СДНФ, СКНФ и СПНФ.

Понятия тавтологии, противоречия и выполнимости формул – критерии.

Лекция 10

Минимизация булевых функций