4.8. Полнота и замкнутость алгебраических систем

Любую логическую функцию, как простую так и сложную, можно представить двумя способами – табличным и формульным. Таблица задает функцию непосредственно как соответствие между двоичными наборами и значениями функции на этих наборах. Этот способ универсален, т.е. пригоден для любой функции, однако громоздок. Формула – гораздо более компактный способ задания функции, однако она задает функцию через другие функции. Поэтому для любой системы функций S возникает естественный вопрос: всякая ли логическая функция представима формулой над S? В настоящем параграфе будет показано, какими свойствами должны обладать операции, с помощью которых можно выражать любое сложное высказывание.

Система функций S называется функционально полной системой в P_k, если любая логическая функция f (fÎP_k) может быть представлена формулой над S, т. е. является суперпозицией функций из S и базисом, если теряется полнота S при удалении хотя бы одной функции, где P_k – k-значная логика. Ранее уже указывалось, что система S₀ ={Ù, Ú,` }, состоящая из операций конъюнкции, дизъюнкции и отрицания функционально полна. Функционально полной будет и любая система S, через функции которой можно выразить дизъюнкцию, конъюнкцию и отрицание. Действительно, для любой логической функции f представляющую ее формулу над S можно построить так: взять булеву формулу для f (такая формула обязательно найдется) и все булевы операции в ней заменить формулами над S, представляющими эти операции. Аналогично доказывается и более общее утверждение: если все функции функционально полной системы S* представимы формулами над системой S, то S также функционально полна. В этом случае говорят, что S сводится к S*.

В общем случае для установления полноты системы S булевых функций f_i (S в P₂) используют критерий полноты Поста – Яблонского.

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

Классом К₀ булевых функций f_i(x₁, x₂, ..., x_n), сохраняющих константу 0, называется множество функций вида { f_i (x₁, x₂, ..., x_n)/ f_i (0, 0, ..., 0) = 0}.

Классом К₁ булевых функций f_i(x₁, x₂, ..., x_n), сохраняющих константу 1, называется множество функций вида { f_i (x₁, x₂, ..., x_n)/ f_i (1, 1, ..., 1) = 1}.

Классом К_л линейных булевых функций f_i(x₁, x₂, ..., x_n) называется множество функций вида { f_i (x₁, x₂, ..., x_n)/ f_i (x₁, x₂, ..., x_n) = с₀ Å с₁х₁ Å с₂х₂ Å ...
Å с_nх_n}, где с₀, с_i = 0, 1; i = 1, 2, ..., n, Å – знак операции «сложение по модулю 2».

Классом К_с самодвойственных булевых функций f_i(x₁, x₂, ..., x_n) называется множество функций вида { f_i (x₁, x₂, ..., x_n)/ f_i (x₁, x₂, ..., x_n) = `f<sub>i</sub>(`x₁,`x<sub>2</sub>, ..., `x_n)}.

Функция f₁(x₁, x₂, ..., x_n) называется двойственной к функции f₂(x₁, x₂, ..., x_n), если f₁(x₁, x₂, ..., x_n) = `f<sub>2</sub>(`x₁, `x<sub>2</sub>, ..., `x_n). Отношение двойственности между функциями симметрично. Из определения двойственности ясно, что для любой функции двойственная функция определяется однозначно. В частности, может оказаться, что функция двойственна самой себе. В этом случае она называется самодвойственной. Функция самодвойственна, если на любой паре противоположных наборов аргументов (наборов, сумма десятичных эквивалентов которых равна 2ⁿ –1) функция принимает противоположные значения.

Классом К_м монотонных булевых функций f_i(x₁, x₂, ..., x_n) называется множество булевых функций, для которых выполняется условие: для любых двоичных наборов s и t длины n (s₁, s₂, ..., s_n; t₁, t₂, ..., t_n) из того, что s ³ t, следует, что f_i(s₁, s₂, ..., s_n) ³ f_i(t₁, t₂, ..., t_n).

Константы 0, 1 и функция x монотонны, отрицание`x немонотонно. Дизъюнкция и конъюнкция любого числа переменных являются монотонными функциями.

Критерий полноты.Система S булевых функций f_i является полной тогда и только тогда, когда выполняются следующие условия:

1) существует функция f_iÎ S, не сохраняющая константу 0: f_i Ï K₀;

2) существует функция f_iÎ S, не сохраняющая константу 1: f_i Ï K₁;

3) существуют нелинейная функция, несамодвойственная функция и немонотонная функция в системе S.

Для порождения всех базисов в двузначной логике P₂ строится двумерная таблица 4.7, каждой строке которой взаимно однозначно сопоставляется одиннадцать функций из табл. 4.3 (функции f₃, f₄, f₅, f₁₀, f₁₁ не используются), а столбцам – классы функций (K₀, K₁, K_л, K_с, K_м). На пересечении строк i и столбцов j ставится 1, если i-тая функция не принадлежит j-тому классу, в противном случае клетка (i,j) оставляется пустой.

Таблица 4.7

Методом Петрика, преобразуя мультипликативно-аддитивную форму в аддитивно-мультипликативную, получают все покрытия столбцов строками табл. 4.7:

Каждое из полученных покрытий порождает базис В_i:

B₁ = { ° } – базис Вебба;

B₂ = { | } – базис Шеффера;

B₃ = { D, ~ };

B₄ = {®, 0} – импликативный базис;

B₅ = {®, D};

B₆ = {®, Å};

B₇ = { D,` } – коимпликативный базис;

B₈ = { ®,` } – импликативный базис;

B₉ = { Ù,` } – конъюнктивный базис Буля;

B₁₀ = { Ú,` } – дизъюнктивный базис Буля;

B₁₁ = { D, 1 } – коимпликативный базис;

B₁₂ = {~, Ù, 0};

B₁₃ = {~, Ú, 0 };

B₁₄ = { Å, Ù, ~ };

B₁₅ = { Å, Ú, ~ };

B₁₆ = { Å, Ù, 1} – базис Жегалкина;

B₁₇ = { Å, Ú, 1}.

Получено 17 базисов, в каждом из которых нельзя вычеркнуть ни одну функцию без потери полноты в P₂.

Каждому сложному высказыванию в базисе {Ù, Ú,` } (И, ИЛИ, НЕ) соответствует эквивалентное высказывание в любом из этих базисов.

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

Согласно ГОСТу базисные элементы графически изображают в виде прямоугольников, в которых инверсные входы и выход изображают в виде
незаштрихованных кружков и внутри прямоугольников ставят «1», если внешняя связка «дизъюнкция», и «&», если внешняя связка «конъюнкция», за исключением сложения по модулю два (тогда обозначают «М2») и эквивалентности (обозначают «=») (табл. 4.8). Более сложные элементы графически изображают в виде композиций перечисленных элементов на основе представления реализуемой им булевой функции в виде дизъюнктивной нормальной формы (ДНФ) или конъюнктивной нормальной формы (КНФ).