Функционально полные системы функций

В разделе логика высказываний рассматриваются булевы функции, то есть функции, принимающие только два значения: истина или ложь. Булевы функции можно подразделить на классы функций (группы функций), относительно определенного признака. Класс булевых функций называется замкнутым, если комбинация функций из данного класса содержится в нем же. Под комбинацией булевых функций будем понимать функцию, состоящую из других булевых функций, соединенных знаками логических операций.

Существует несколько замкнутых классов функций:

1) Класс функций, сохраняющих ноль: .

2) Класс функций, сохраняющих единицу: .

3) Класс S самодвойственных функций составляют функции, на противоположных наборах принимающие противоположные значения.

.

4) Класс линейных функций L составляют функции, которые представляются полиномом Жегалкина первой степени.

5) Класс М монотонных функций: для двоичных векторов и , где , , вводится следующее отношение частичного порядка. Считается, что , если для . Класс M определяется следующим образом:

.

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

Функция алгебры логики называется монотонной, если для любых n мерных двоичных наборов ,из того, что , следует, что

Теорема о монотонных функциях:всякая булева функция в сигнатуре алгебры логики, не содержащая отрицаний, является монотонной функцией, для любой монотонной функции алгебры логики, отличной от 0 и 1, найдется равносильная ей булева функция без отрицаний.

Пример 1. Определить, является ли функция монотонной.

Решение:

– не содержит отрицаний, является монотонной.

Функция называется двойственнойфункцией к функции . Функция называется самодвойственной, если .

Самодвойственными являются функции

Проверку на самодвойственность функции можно осуществлять по таблице истинности, для чего в последнем столбце: первый 0 или 1 заменяют на 1 или 0, ставят на последнее место, если на последнем месте стоит 1 или 0, проверку ведут дальше – сравнивают вторую строку и предпоследнюю, и так далее до середины. Если же получились два одинаковых значения хотя бы на двух симметричных относительно середины строчках последнего столбца таблицы истинности, то функция не является самодвойственной.

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

Решение:

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

Если двойственная функция к исходной равна исходной, то исходная функция самодвойственная.

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

Теорема Поста о функциональной полноте: для того чтобы система функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из следующих замкнутых классов T₀, T₁, L, M и S.

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

Пример 1. Проверить функциональную полноту системы булевых функций .

Решение:

Проверим принадлежность замкнутым классам функции . Построим таблицу истинности данной функции:

, следовательно ;

, следовательно ;

, следовательно, .

, следовательно, .

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

Построим таблицу Поста:

			S	M	L
	+	–	–	–	+
	+	+	–	+	–
	–	+	–	+	+

В каждом столбце таблицы имеется минус, следовательно, система A функционально полна.

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

Системы функций { , } – штрих Шеффера и стрелка Пирса являются полными, так как , , , .

Система функций является полной, так как .

Свойства полных наборов

№ п/п	Полные наборы	Свойства
1.		Булева Алгебра
2.		Переход к дизъюнкции
3.		Переход к конъюнкции
4.
5.
6.
7.
8.

Пример 2.Определить, каким классам Поста принадлежит функция

f = .

Решение:

Построим таблицу истинности:

x	y	z

f (0, 0, 0) = 0, fÎT₀ (класс булевых функций сохраняющих нуль);

f (1, 1, 1) = 0, fÏT₁ (класс булевых функций сохраняющих единицы);

f (0, 0, 1) > f (1, 1, 1), fÏM (класс монотонных функций);

f (0, 1, 1) ¹ , fÏS (класс самодвойственных функций).

= –полином Жегалкина.

Функция линейная, fÎ L (класс линейных функций).

Пример 3.Определить, является ли полной система функций и образует ли она базис.

Решение:

;

= ;

x	y

Проверяем, принадлежат ли функции к классу сохраняющих ноль:

, ,

, .

Проверяем, принадлежат ли функции к классу сохраняющих единицу:

, .

, .

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

, , ,

, , .

Проверяем, принадлежат ли функции к классу монотонных:

, f₁ Î M,

, f₂ Ï M.

Проверяем, являются ли данные функции линейными:

,

= =

= .

Составляем таблицу Поста:

Функция	Классы
P0	P1	S	M	L
	Да	Нет	Нет	Да	Да
	Нет	Да	Нет	Нет	Нет

Система функций Á образует полную систему, так как для каждого из классов Поста в системе есть функции, не принадлежащие этому классу. Система функций Á является базисом, так как полна и при удалении одной из функций система становится неполной.

Пример 4. Определить, является ли полной система функций F = {Øx ® y, x Ù Øy} и образует ли она базис.

Решение:

Øx ® y « x Ú y, F = {x Ú y, x Ù Øy},

Для x Ù Øy:

1) f(0,0) = 0;

2) f(1,1) = 0;

3) f(0,0) ≠ f(1,1);

4) Так как f(0,0) = f(1,1), следовательно, функция f(x Ù Øy) монотонна;

5) Полином Жегалкина: x+xy.

Для x Ú y:

1) f(0,0) = 0;

2) f(1,1) = 1;

3) f(0,1) ≠ f(1,0);

4) Так как f(0,0) < f(1,1), следовательно, функция f(x Ú y) монотонна;

5) Полином Жегалкина: x+y+xy.

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

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

{f₁(x, y, z)=(xy~(y~ z)), f₂(x, y) = x + y x, f₃(x, y, z) = x ~ (y z), f₄(x, y)= x + , f₅(x, y, z) = = x y←z}.

Решение:

Составляем таблицу истинности для каждой из этих пяти функций (для f₂и f₄таблицу можно составить отдельно).

f₁(x, y, z) принадлежит Т_0, и f₁ не принадлежит Т₁, f₁ не принадлежит M, S, f₃не принадлежит T₀, M, S и f₃принадлежит Т₁, f₅ принадлежит Т₁,и f₅ не принадлежит Т₀, М, S. Осталось проверить линейность этих функций:

f₃ = x ~ (y z) = = x + yz + 1 – нелинейна;

f₅ = x y ← z = = (x y + 1) z + 1 = x y z + z + 1 – нелинейна.

x, y	x y	f2 = x + x y	f4 =

Составим таблицу Поста:

Таким образом, базисами являются: f₁и f₃; f₁и f₄; f₂и f₄; f₁и f₅, f₂и f₅. Полными наборами будут любые наборы, содержащие какой-нибудь базис.

Пример 6.Определить, полна ли система функций .

Решение:

Построим таблицу Поста:

f(x,y)			L	M	S
xy	+	+	–	+	–
x 1	–	–	+	–	+

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

Упражнения

1. Определить, являются ли функции монотонными:

b) f(x,y)=(x ;

c) f(x,y)=(xy );

d) f(x,y,z)=xyz ;

e) f(x,y,z)=(xy ;

f) f(x,y)=(x y)(y );

g) f(x,y)=(x ;

h) f(x,y)=(x y);

i) f(x,y,z)=(xy ;

j) f(x,y,z)=(xy ;

k) f(x,y)=(xy x) y;

l) f(x,y)=(xy .

2. Определить, являются ли функции самодвойственными:

a) f(x,y,z)=(xy ;

b) f(x,y)=(xy );

c) f(x,y)=(x y);

d) f(x,y)=(x y) ;

e) f(x,y)=(xy ;

f) f(x,y)=(xy ;

g) f(x,y,z)=(xy ;

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

3. Определить, полны ли системы функций:

a) {x y, x 1};

b) {x y, x y};

c) {x y, x 1};

d) {x y, x 1};

e) {xy, x|1};

f) {x y, x 1};

g) {xy, x 1};

h) {x y, x 1}.