1.7. Полнота и замкнутость

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

Определение. Система функций из Р₂ { f₁, … , f_n } называется (функциональ-но) полной, если любая логическая функция может быть представлена в виде формулы через функции этой системы.

Пример. Система функций { , x₁ & x₂, x₁ x₂ } является полной.

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

Теорема. Пусть система функций F₁ = { f₁, … ,f_n } полная, а каждая ее функция выражается в виде формулы через функции системы F₂ = { h₁, … , h_m }. Тогда система F₂ так же полная.

Доказательство данной теоремы приведено в [1]. Опираясь на эту теорему, можно установить полноту других систем.

Пример. Доказать, что система функций { , x₁ & x₂} будет полной.

Согласно закону де Моргана имеем: x₁ x₂ = , т.е. функция x₁ x₂ выражается через функции данной системы. Следовательно, каждая функция системы предыдущего примера выражается через функции данной системы. Поэтому по представленной теореме эта система тоже будет полной.

Пример. Доказать полноту системы { , x₁ x₂ }.

Доказательство проводится аналогично предыдущему примеру, учитывая, что:

x₁ & x₂ = _.

Замечания:

1). С точки зрения функциональной полноты систему функций первого примера можно считать избыточной, т.е. она сохраняет свойство полноты и при удалении из нее операции & или .

2). Однако за не избыточностью полученных при этом систем приходится платить избыточностью формул.

Пример. Доказать полноту систем F₁ = { x₁ / x₂ } и F₂ = { x₁↓ x₂ }.

Данные системы будут полные, т.к. отрицание, дизъюнкция и конъюнкция выражаются через функции этих систем следующим образом:

= x / x = x ↓ x, x₁ x₂ = = ( x₁ ↓ x₂ ) ↓ ( x₁ ↓ x₂ ),

x₁ & x₂ = = ( x₁ / x₂ ) / ( x₁ / x₂ ).

Пример. Доказать полноту системы { x & y, x y, 1 }.

Так как = x 1 получим, что функции полной системы { , x & y } выражаются через функции данной системы. Следовательно, эта система так же полная

.

Определение. Минимальная полная система функций ( т.е. такая полная сис-тема функций, удаление из которой любой функции делает систему не полной ) называ-ется базисом.

Базисами будут следующие полные системы функций:

{ xy, x y, 1 }, { x ↓ y }, { x ∕ y }, { x y , x y , 1 },

{ x y z , xy, 0, 1 }, { x → y, }, { x → y, 0 }.

Замечание. Можно показать, что базис не может содержать более четырех функций.

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

С понятием полноты тесно связано понятие замыкания и замкнутого класса.

Определение. Множество логических функций называется замкнутым классом, если любая суперпозиция функций из этого множества снова принадлежит ему.

Рассмотрим основные замкнутые классы логических функций:

Т_o – класс всех логических функций f( x₁,…, x_n ), сохраняющих ноль, т.е. для которых выполняется равенство:

f( 0, …, 0 ) = 0.

Легко видеть, что функции 0, x, x & y, x y, x y принадлежат классу T_o, а функции 1, не принадлежат ему. В таблице задания функции из класса T_o значение функции равно 0 для первой строки. Из таблицы 1.2 видно, что таких функций двух переменных ровно половина. Следовательно, логических функций от n переменных принадлежащих этому классу будет / 2.

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

Ф = f( f₁, … , f_m ) принадлежит T_o, если f₁, … , f_m принадлежат T_o. Последнее соотношение вытекает из следующей цепочки равенств:

Ф( 0, … , 0 ) = f( f₁( 0, … , 0 ), …, f_m( 0, … , 0 ) ) = f ( 0, … , 0 ) = 0.

T₁ – класс всех логических функций f ( x₁, …, x_n ), сохраняющих единицу, т.е.для которых выполняется равенство:

f( 1, …, 1 ) = 1.

Легко видеть, что функции 1, x, x & y, x y принадлежат данному классу, а функции 0, не принадлежат ему. Класс T₁ так же содержит / 2 функций n переменных.

Доказательство того, что класс T₁ является замкнутым классом, проводится аналогично.

Определение. Функция f*( x₁, … , x_n ) называется двойственной функцией к функции f( x₁, … , x_n ), если она определяется равенством

. f*( x₁, … , x_n ) = ( ₁, …, _n).

Очевидно, что таблица для двойственной функции получается из таблицы функции f( x₁, … , x_n ) инвертированием ( т.е. заменой 0 на 1 и 1 на 0 ) столбца зна-чений функции и его переворачиванием. Это видно из следующей таблицы:

Таблица 1.17

x1	x2	x3	f	f*
0	0	0	1	0
0	0	1	1	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	1
1	0	1	1	1
1	1	0	0	0
1	1	1	1	0

Легко проверить, что: функция 0 двойственна к 1, функция 1 двойственна к 0, функция x двойственна к , функция двойственна к x, функция x & y двойственна к x y, функция x y двойственна к x & y. Из этого следует, что отношение двойственности между функциями f и f* симметрично.

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

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

Определение. Функция f( x₁, …, x_n ) называется самодвойственной, если она равносильна своей двойственной, т.е. выполняется следующее условие:

f( x₁, … , x_n ) = f*( x₁, … , x_n ) или f( x₁, … , x_n ) = ( , …, ). (1.12)

Легко заметить, что для того чтобы функция была самодвойственной нужно чтобы ее значения были “ антисимметричны “, т.е. чтобы значения функции на противоположных наборах переменных ( т.е. на наборах равно удаленных от начала и конца таблицы ) были противоположны.

Например, f = ( 0, 1, 1, 0, 1, 0, 0, 1 ) будет самодвойственной.

Действительно, инвертируя заданную функцию получим

f = ( 1, 0, 0, 1, 0, 1, 1, 0 ).

Переворачивая значения функции f₁, получим двойственную функцию к f , т.е.

f* = ( 0, 1, 1, 0, 1, 0, 0, 1 ).

Сравнивая значения функций f и f* видим, что f = f*. Следовательно,

согласно (1.12) заданная функция самодвойственная.

Функции x и самодвойственные функции, т.к. у них выполняется “антисимметричность“, а функции x y и x & y не являются самодвой-ственными.

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

Пример. Проверить на самодвойственность функцию:

f( x,y,z ) = x y x z y z.

Найдем двойственную к f функцию:

В результате преобразований получили, что двойственная функция к заданной представляется такой же формулой, как и заданная функция. Следовательно, заданная функция является самодвойственной.