Представление булевой функции в виде дизъюнктивной нормальной формы. Выражение всех логических операции в формуле через конъюнкции, дизъюнкции и отрицания. Сокращение количества слагаемых, входящих в формулу и количества переменных, входящих в слагаемое.
Здесь ?j = {0, 1} и переменная xij входит в конъюнкцию с отрицанием, если ?j = 0, и без отрицания, если ?j = 1. Отметим, что любая функция может быть представлена в виде ДНФ, вообще говоря, не единственным образом. Алгоритм состоит в следующем: 1) Выразить все логические операции в формуле через конъюнкции, дизъюнкции и отрицания. Конъюнкция всех таких дизъюнкций образует КНФ - выражение вида Рассмотрим конъюнкции заданной ДНФ слева направо: 1) Пусть выбрана конъюнкция Ki.
Список литературы
· С. В. Яблонский - Введение в дискретную математику (6-е изд, 2010 г.)
