5.4. Полные системы в классах т0, т1, м, s, l.

Утверждение 1:

Полной системой в классе Т₀ является система

Доказательство:

Обе функции принадлежат Т₀. Осталось показать, что , то есть любуюможно представить суперпозицией функций

Рассмотрим и полином ЖегалкинаТогда свободное слагаемое данного полинома равно 0 в силу того, что.Поэтому данный полином есть суперпозиция только. Это и есть требуемая суперпозиция.

Утвеждение 2:

В классе Т₁ полной является система .

Доказательство:

Рассмотрим . Покажем, что ее можно получить суперпозицией. В дальнейшем потребуются функции:

Рассмотрим функции (k+1 – число наборов, на которыхf равна единице), которые получаются из по правилу:

для каждой функции оставляем соответствующий единичный набор, а на остальных (кроме 1…1) приравниваем к нулю.

Например:

0 0 0 0 0 0 0

0 0 1 0 0 0 0

0 1 0 1 1 0 0

0 1 1 0 0 0 0

1 0 0 1 0 1 0

1 0 1 1 0 0 1

1 1 0 0 0 0 0

1 1 1 1 1 1 1

В результате дополнительных функций будет столько, сколько единичных наборов без последнего. Очевидно

Поэтому, чтобы найти представление функциичерездостаточно найти представление каждой из добавочных функций через

Если f имеет один единичный набор, то это есть элементарная конъюнкция переменных без отрицания. В противном случае рассмотрим дополнительную функцию f_i . Не теряя общности будем считать, что соответствующий единичный набор имеет вид: . Тогда справедливо:

Например: f₁ равна 1 на наборах 010 и 111, поэтому

Утверждение 3:

В классе S полной является система

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 1

1 0 0 0 0

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

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

Самодвойственных функций, существенно зависящих от двух переменных нет:

0 0 01 0 1 1 0

0 1 01 0 1 0 1

1 0 10 1 0 1 0

1 1 10 1 0 0 1

Функции, не имеющие существенных переменных – константы, т.е. не самодвойственные функции от одной переменной есть .

коммутативные операции, относительно второй и третьей переменных при фиксированной первой:

и ассоциативны относительно второй и третьей переменных при фиксированной первой:

Будем обозначать:

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

Например:

Выражение, в котором присутствует символ на наборах, в которыхравно 1, тогда и только тогда, когда все переменные выражения равны 1:=0 и

Значение выражения, в котором присутствует не зависит от расположения скобок и это выражение на наборах в которыхравно 1, когда хотя бы одна из переменных равна 1.

Утверждение:

Например:

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

Доказательство:

Рассуждения в этом случае аналогичны случаю представления функции в виде СДНФ.Формальное доказательство следующее.

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

Рассмотрим набор

Покажем, что значение правой части на данных наборах равен 1 соответственно 0.

1) Рассмотрим слагаемые правой части, которые соответствуют набору .

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

А поэтому значение всей дизъюнкции равно 1, т.к. существует слагаемое, равное 1.

2) . Рассмотрим произвольное слагаемое в правой части. Пусть оно соответствует единичному наборутогда наборыиразличны, поэтому, тогдаi-ый множитель на наборе будет равен 0, таким образом все слагаемые равны 0. Тогда значение всей правой части равно 0 на наборе. Утверждение доказано.

4) В классе монотонных функций полной является система .

Определение:

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

Пример:

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

набор 001 для монотонной функции является нижней единицей набор 110 тоже нижняя единица функции.

Утверждение:

Пусть для монотонной функции :,. Тогда справедливо представление:

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

В данном примере разложение следующее:

Доказательство:

1) тогда рассматриваем тот нижний набор, который меньше либо равен чем рассматриваемый, тогда в силу того, чтов тех местах, где в наборестоит 1, втакже должна стоять 1.

Поэтому слагаемое, соответствующее набору равно 1 на наборе, а поэтому и вся дизъюнкция равна 1.

2)

Рассмотрим произвольное слагаемое, которое соответствует нижней единице , на набореи покажем, что значение этого слагаемого равно 0 на наборе. Допустим противное,, что соответствующее слагаемое на набореравно 1.Тогда в тех местах , где в наборестоит 1 в наборетакже стоит 1, то есть. Но в силу того, чтополучаем противоречие, т.к. значение, в то время как

5) В классе L полной системой является следующая .

Доказательство:

а это и есть все линейные функции.