Функции алгебры логики

Тогда f ( x1 ,x2 ,x3 ) 1 x3 x2 x1x3 x1x2 x1x2 x3 .

Доказательство. Любая функция из Р2 может быть представлена формулой над {x1 & x2, x1 x2, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции f(x1, ..., xn) от n переменных. Мы знаем, что всего таких функций, т.е. их таблиц истинности , 2n. Подсчитаем число различных полиномов Жегалкина от n переменных, т.е. число вариаций вида:

множества { x1, ..., xn }, сюда входит и пустое множество (если s = 0). Число подмножеств множества из n элементов равно 2n , а так как каждый набор входит с коэффициентом ai1i2...is , принимающим два значения: 0 или 1, то число

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

Определение. Функция f(x1, ..., xn), полином Жегалкина для которой имеет следующий линейный относительно переменных вид: f = а0 а1х1 а2х2 ...

аnхn, называется линейной.

41

Лемма о нелинейной функции. Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

Доказательство. Пусть f(x1, ..., xn) – нелинейная функция. Тогда полином Жегалкина содержит для нее слагаемое, в котором присутствует произведение xixj. Будем считать для простоты, что x1x2 в многочлене Жегалкина является этим произведением. Произведя группировку слагаемых, функцию f представим в виде f ( x1 ,...,xn ) x1x2h0( x3 ,...xn ) x1h1( x3 ,...,xn ) x2h2( x3 ,...,xn ) h3( x3 ,...,xn ).

Функция h0 не есть тождественный нуль, иначе в полиноме Жегалкина отсутствует слагаемое с произведением x1x2. Тогда существует набор ( 3, …, n) из 0 и 1, для которого h0( 3, …, n) = 1. Пусть h1( 3, …, n) = a, h2( 3, …, n) = b, h3( 3, …, n) = c. Тогда g( x1 ,x2 ) f ( x1 ,x2 , 3 ,..., n ) x1x2 ax1 bx2 c.

Построим функцию:

h( x1 ,x2 ) g( x1 b,x2 a ) ( x1 b )( x2 a ) a( x1 b ) b( x2 a ) c x1x2 ax1 bx2 ab ax1 ab bx2 c x1x2 d ,

где d = ab c. Если d = 0, то h(x1, x2) = x1x2. Если d = 1, то h(x1, x2) = x1x2 1 и тогда x1x2 h( x1 ,x2 ). Лемма доказана.

Функция f(x1, ..., xn) сохраняет константу a {0, 1}, если f(a, …, a) = a. Пример 4. Функция xy сохраняет 0, сохраняет 1. Функция x y сохраняет 1

и не сохраняет 0.

2.6. Замыкание и замкнутые классы

Определение 1. Пусть M Р2. Замыканием М называется множество всех функций из P2, которые можно выразить формулами над М. Замыкание М обозначается [M].

Определение 2. Множество функций М называется замкнутым классом, если [M]=M.

Пример 1.

1)P2 – замкнутый класс.

2)Множество {1,x1 x2} не является замкнутым классом. Его

замыканием будет класс линейных функций: [{1, x1 x2}] = {f(x1, ..., xn) = c0c1x1 cnxn}. Действительно, по определению формулы над М, функция f(G1, x3), где f – есть сумма по модулю 2, G1 – функция х1 х2, будет формулой над М: f(G1, x3) = (x1 x2) x3.

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

М– полная система, если [M] = P2.

3)A = {f(x1, ..., xn) f(1, 1, ..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g1, ..., gn A, т.е. f(1, 1, ..., 1) = 0, g1(1, 1, ..., 1) = 0,

42

тогда f(g1, ..., gn) [A]. Посмотрим, принадлежит ли функция f(g1, ..., gn)

множеству А. f(g1(1, ..., 1), g2(1, ..., 1), ..., gn(1, ..., 1) = f(0, ..., 0)), но f(0, ..., 0) не

обязано быть равным 0. Действительно, пусть g1(x1, x2) = x1 x2, g2(x) = x A. Возьмем g2(g1(x1, x2)) = x1 x2 [A], g2(g1(1, 1)) = 1 1 = 0, следовательно,

g2(g1(x1, x2)) A, отсюда [A] A и А – незамкнутый класс.

Важнейшие замкнутые классы в Р2

1) Т0 - класс функций, сохраняющих константу 0.

Т0 = { f(x1, ..., xn f(0, ..., 0) = 0, n = 1, 2, ...}. Покажем, что Т0 является собственным подмножеством Р2, т.е. Т0 и Т0 Р (не совпадает с Р2). Для этого достаточно привести примеры функций, входящих в Т0, и примеры функций из Р2,

[Т0] = Т0. Вложение Т0 [ Т0] очевидно, так как по определению формулы любая функция из Т0 является формулой над Т0 и, следовательно, принадлежит [Т0].

Покажем, что [Т0] Т0. Для этого надо показать, что Ф = f(f1, ..., fm) [ Т0], если все функции f, f1, f2, f3, ..., fm Т0. Надо заметить, что в формуле в качестве функции f1 могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т0,

поэтому достаточно показать, что Ф = f (f 1, ..., fm) Т0. Для этого рассмотрим следующую функцию: Ф(0, ..., 0) = f (f 1(0, ..., 0), f 2(0, ..., 0), ...) = f(0, ..., 0) = 0.

Число функций, зависящих от n переменных и принадлежащих Т0, будет равно T0( n ) 22n 1.

2) T1 – класс функций, сохраняющих константу 1.

следовательно Т1 – собственное подмножество Р2. T1( n ) 22n 1.

Покажем, что [T1] T1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т1, можно рассмотреть Ф = f(f1, ..., fn) [T1], где f, f1, ..., fn T1. Найдем Ф(1, ..., 1) = f(f1(1, ..., 1), ..., fn(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f1, ..., fn) T1, отсюда следует [T1] = T1.

43

3) S – класс самодвойственных функций.

S = {f(x1, ...) f* = f }; x, x , x1 x2 x3 S, x1&x2, x1 x2, x1 x2 S, следовательно,

S – собственное подмножество Р2. |S(n)| = 22n 1 . Покажем, что [S] S. Ф = f(f1, ..., fn)[S], если f, f1, ..., fn S, а также, что Ф S. По принципу двойственности, Ф* = f*(f1*, ..., fn*) = f(f1, ..., fn) = Ф, отсюда S – замкнутый класс.

например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования ( ) является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.

x1 x2 M, x1 x2, x1 x2, x1 ~ x2 M.

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

замкнутый класс. Рассмотрим функцию Ф [M], Ф = f(f1, ..., fm), где f, f1, ..., fm M,

причем можем считать, что все они зависят от n переменных. Пусть набор ~ =

~

1, ..., n), = ( 1, ..., n). Рассмотрим Ф 1, ..., n) = f(f1 1, ..., n), …, fm 1, ...,n)) и Ф( 1, ..., n) = f(f1( 1, ..., n), ..., fm( 1, ..., n)). Здесь f1( ) f1( ), ..., fm( )

fm( ), тогда набор (f1( ), ..., fm( )) (f1( ), ..., fm( )), но тогда Ф( ) Ф( ), так как f M, отсюда Ф = f(f1, ..., ) – монотонная функция.

Определение. Функция f есть суперпозиция над M, если f реализуется некоторой формулой над M.

Лемма о немонотонной функции. Отрицание можно получить суперпозицией констант 0 и 1, тождественной функции и немонотонной функции.

44

следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.

A={x, x , 0, 1, x1x2) не является полной системой функций так как всегда есть функции Р2 не входящие в эти классы.

Задачи

1.Доказать, что пересечение любых двух замкнутых классов замкнуто.

2.Доказать, что объединение двух замкнутых классов не всегда замкнуто.

Теорема Поста о полноте

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T0, T1, L, S, M.

Доказательство. Докажем необходимость этого условия. Пусть система

N = {f1, f2, ...fs, ...} полна в Р2, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T0, T1, L, S, M. Докажем от противного, пусть N Q, очевидно, [N] [Q] = Q, но [N] = P2, т.к. N – полна в Р2, отсюда Р2=Q, но это не так. Необходимость доказана.

45

Докажем достаточность. Пусть F = {f0, f1, fL, fm, fs}, где f0 T0, f1 T1, fL L, fs S и fm M. Покажем, что суперпозицией функций системы F можно получить

полную систему G = {x1&x2, x }.

1. Пусть g(x) = f0(x, …, x). Тогда g(0) = f( 0, …, 0) = 1. Далее возможны два случая:

g(1) = 1. Тогда g(x) 1. Функция h(x) = f1(g(x), …, g(x)) = f1(1, …, 1) = 0, т.е. h(x) 0. Получили константы 0 и 1;

g(1) = 0. Тогда g(x) = x . По лемме о несамодвойственной функции суперпозицией над {fs, x } можно получить одну из констант, например, 0. Тогда f0(0, …, 0) = 1 есть другая константа.

В обоих случаях получили обе константы.

2.По лемме о немонотонной функции суперпозицией над {fm, 0, 1} можно получить отрицание.

3.По лемме о нелинейной функции суперпозицией над {fL, 1, x } можно получить конъюнкцию. Теорема доказана.

Следствие. Всякий замкнутый класс функций из Р2, не совпадающий с Р2 содержится, по крайней мере, в одном из замкнутых классов T0, T1, L, S, M. Действительно, если N не является подмножеством Q, то [N] = P2, что неверно.

Примеры использования теоремы Поста.

1.Покажем, что система функций {f1 =x1x2, f2 =0, f3 =1, f4 = x1 x2 x3} полна в Р2. Составим таблицу, которая называется критериальной :

46

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

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной,

действительно, {f2, f3, f4} L, {f1, f3, f4} T1, {f1, f2, f4} T0, {f1, f2, f3} M.

2. Мы знаем, что система {x1|x2} – полна в Р2. Какова для нее

Согласно критериальной таблице, полной является и система {1, x1x2, x1 x2}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где а i1i2...is равны 0, если члены х i1 х i2 ...х ik , в полиноме

1)=0, следовательно, f M, f T1. Рассмотрим функцию h = x1x2 x2x3 x1x3=1,

набор ее значений (11101000), h S\T0, но h L. Следовательно, критериальная таблица имеет вид:

и А – полная система функций.

47

Определение. Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система

функций {x1&x2, 0, 1, x1 x2 x3} – базис.

Теорема о достаточности четырех функций.

Из любой полной в Р2 системы функций можно выделить полную подсистему, состоящую не более чем из четырех функций.

Доказательство. Пусть {f0, f1, fL, fM, fS} – полная система функций, тогда она не лежит целиком ни в одном из классов T0, T1, L, M, S. Следовательно, в системе есть функции f0 T0, f1 T1, fL L, fS S и fm M. Система {f0, f1, fL, fM, fS} P2 и образует полную систему в Р2. Рассмотрим функцию f0: f0(0, ..., 0) = 1.

Если f0(1, ..., 1) = 0, то f0 T1 и f0 M, тогда {f0, fS, fL} – полная система из трех функций.

Если f0(1, ..., 1) = 1, то f0 S и {f0, f1, fL, fM } образует полную систему из четырех функций.

Пример 1, приведенный выше, показывает, что цифру 4 в общем случае уменьшить нельзя, из полной системы {x1x2,0,1,x1 x2 x3} нельзя выделить полную подсистему.

Следствие. Базис в Р2 может состоять максимум из четырех функций.

2.7. Функции k - значной логики

Введем обозначение: Eк={0, 1, 2, ..., k–1}.

Функция k-значной логики, зависящая от n переменных, – это закон, отображающий Ekn Ek . Множество функций k-значной логики обозначается как

Рk. Функция из Рk полностью определена, если задана ее таблица истинности, т.е. заданы значения на всех наборах. Наборы можно рассматривать как записи в k- ичной системе счисления чисел от 0 до k–1, всего наборов kn. Функций из Рk, зависящих от n переменных, будет kn. |P3(n)|, например, будет 3, если n = 2, то

|P3(2)| = 39 = 19683 (k=3, n=2).

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

1.Циклический сдвиг или отрицание Поста: x = x+1(mod k).

2.Зеркальное отображение или отрицание Лукосевича: Nx = k–1–x.

48

Эти две функции являются обобщением отрицания.

3. Ji(x)= x = i, I = 0, 1, 2, ..., k–1}.

4.min(x1,x2) – обобщение конъюнкции;

5.x1 x2(mod k) – второе обобщение конъюнкции;

6.max(x1,x2) – обобщение дизъюнкции;

7.x1+x2(mod k) – сумма по mod k.

Принято min(x1,x2) обозначать x1&x2, max(x1,x2) обозначать x1 x2.

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

Теорема о полной в Рk системе функций

Cистема функций {max(x1,x2), min(x1,x2), 0, 1, ..., k–1, J0(x), J1(x), ..., Jk-1(x)}

является полной в Рk и любая функция f(x1, ..., xn) Pk выражается формулой над

Эта формула есть своеобразный аналог СДНФ.

49

равенство на нем справедливо, то формула верна. В этой формуле использованы функции Ji(x), (i = 0, ..., k–1), min(x1x2), max(x1x2) и константы 0, ..., k–1, так как функция f(i1, ..., in) есть число из {0, 1, ..., k–1}.

2.8. Задачи и упражнения по функциям алгебры логики

При оперировании с функциями алгебры логики бывают полезны следующие

эквивалентности (большинство из них называют обычно основными

эквивалентностями алгебры логики). Построив таблицу для соответствующих

функций, убедитесь в справедливости следующих эквивалентностей:

1. x y y x – коммутативность связки , где символ является общим

обозначением для связок &, , , ~, |, .

2. x y z x y z – ассоциативность связки , где – общее обозначение

для связок &, , ,~. 3. Дистрибутивность

а) x & y z x & y x & z – дистрибутивность конъюнкции

относительно дизъюнкции;

б) x y & z x y & x z – дистрибутивность дизъюнкции

относительно конъюнкции;

50