Совершенные и нормальные формы

Теперь мы имеем способ задания булевых функций формулами и можем по каждой формуле построить равную ей булеву функцию. В связи с этим возникают несколько вопросов.

Во-первых (не в порядке важности, разумеется), не много ли набралось элементарных булевых функций, не сократить ли их число? – Действительно, пример алгебры подмножеств, перенесенный на алгебру Буля, подсказывает, что трёх операций – дизъюнкции, конъюнкции и отрицания должно вроде бы хватить на все случаи жизни. И более того, как выяснится в дальнейшем, можно обойтись двумя и даже одной операцией – но мы, начиная с настоящего момента, будем работать с перечисленными операциями или, как говорят, «в дизъюнктивном базисе Буля» – или стандартном.

Во-вторых, мы установили соответствие: формула ” функция. Спрашивается, а имеет ли место обратное соответствие формула ’ функция? Смысл вопроса в том, нет ли «дырок» среди формул, каждой ли функции соответствует какая-то (следовательно, и не одна) функция? В математике это свойство формул называют полнотой. Фактически эти два вопроса оба о полноте, но один в узком смысле, как полнота формул среди элементарных булевых функций, второй – в широком, как полнота формул среди всех булевых функций.

В-третьих, предположим, что нам предъявлены две формулы, представляющие одну функцию (т.е. равносильные). Можем ли мы последовательными преобразованиями с использованием тождеств алгебры Буля, преобразовать одну из них в другую? Существует ли алгоритм преобразования? – Эта проблема носит в математике название проблемы разрешимости. К решению этих проблем мы и приступим.

Обращаясь за аналогиями к элементарной математике, мы без труда замечаем, что наши проблемы схожи с проблемами представления чисел в виде произведения простых сомножителей или, наоборот, представления алгебраических выражений в виде суммы по степеням переменных. Решение этих проблем осуществляется процедурой: а) сновала выражение приводят к какому-то стандартному виду; б) затем приведенные формулы сравнивают между собой. Для того чтобы процедура работала, должно существовать стандартное представление формул, в котором формулы записываются однозначно: так, разложение на простые множители единственно, как и разложение многочлена по степеням.

Такие стандартные формы существуют и для формул алгебры логики. Их называют нормальные совершенные формы. Используются совершенные дизъюнктивная, конъюнктивная и полиномиальная нормальные формы (СДНФ, СКНФ и СПНФ).

· Литералом называется переменная или ее отрицание.

· Элементарной конъюнкцией (дизъюнкцией) ранга r называется конъюнкция (дизъюнкция) r литералов. Произвольная конъюнкция может содержать несколько одинаковых литералов, но их всегда можно сократить, пользуясь идемпотентностью, так что она будет состоять из разных литералов.

· ЭК (ДК) называется полной, или конституентой, если в нее входят все литералы, рассматриваемые в контексте задачи.

Дизъюнктивной нормальной формой (ДНФ) называется произвольная дизъюнкция элементарных конъюнкций. Конъюнктивной нормальной формой (КНФ) называется произвольная конъюнкция элементарных дизъюнкций.

Пример:

D = x₁x₂Úx₁x₃Úx₂x₃

K = (x₁Úx₂)(x₁Úx₃)(x₂Úx₃)

По случайному совпадению оказалось, что эти две формы реализуют одну и ту же функцию – функцию голосования. Для проверки можно построить таблицу истинности или раскрыть скобки в КНФ.