pdm_02

Доказательство замкнутости на примере T0

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

Базис : f1 , f2 ,..., fn T0

Предположение : V f ( f1 (x1 , x2 ,..., xn ),..., fn (x1 , x2 ,..., xn ))

Шаг : V (0,0,...,0)				f ( f1 (0,0,...,0),..., fn (0,0,...,0))			f (0,0,...,0) 0.
ч.т.д.
	Пример. Пример предполных функций
	Функция		T0	T1	T*	TM	TL
	0		да	нет	нет	да	да
	1		нет	да	нет	да	да
	x		нет	нет	да	нет	да
	x	y	да	да	нет	да	нет
Также говорят о предполноте одного замкнутого класса в другом. Класс A
предполон		в	классе B,	если замыкание	класса A	с любой функцией,

принадлежащей B, но не принадлежащей A, порождает класс B.	11

Полная система функций, базис

Определение. Система G функций из замкнутого множества функциональных символов F полна в F (является порождающей системой для F), если множество замыканий класса [G]=F. Система функций H полна (в Pn), если [H]= Pn. Полная в F система функций G называется базисом в F, если никакая собственная подсистема в G не является полной в F.

Полны в Pn следующие системы функций: -основной базис набор операторов «и», «или», «не»; -оператор «штрих Шеффера»; -оператор «стрелка Пирса»;

-операторы «сумма по модулю два», «и», «или».

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

«и», «не» или «или», «не».

12

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

Теорема. Пусть заданы две системы функций:
	F	{ f1, f2 ,..., fn } и G					{g1, g2 ,..., gk }.
Тогда, если система F полна и все функции из
	F	реализуемы формулами над G,							то система G
также					полна:
([F ]			Pn		i	1...n( fi	func i [G]))		[G] Pn
Доказательство. Пусть h							произвольная функция, h			Pn .
Тогда [F ]			Pn		h	func [F ]		{ i // fi }	формула над G.
Следовательно, h						func [G]. ч. т. д.
Запись			{		i // fi }	означает замену в			всех fi на	i .

Пример.

Система { , , } полная, следовательно :

система { , } полная, т.к. x y (x y).

13

Теорема Поста

Теорема. Чтобы система функций алгебры логики F была функционально полной, необходимо и достаточно, чтобы эта система содержала:

-функцию, не сохраняющую 0;

-функцию, не сохраняющую 1;

-несамодвойственную функцию;

-немонотонную функцию;

-нелинейную функцию.

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

Пусть

система

Пример.

функций F из Pn полна в Pn. Допустим, что в F нет одной из указанных функций, например, нелинейной. Тогда все функции в F линейны, а т.к. класс линейных

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

суперпозиция над F не даст нелинейной функции.

Далее предположением, что система

F= {x, x y}

1отрицание не сохранят 0; 2 отрицание не сохранят 1;

3	x y	не самодвойственна;
4 x y не монотонна;
5	x y	не линейна.

F содержит все указанные в теореме функции можно показать, что

	суперпозицией F можно получить	14
	полную систему.

Двойственные функции

Определение. Пусть функция алгебры логики f (x1, x2 ,..., xn ) Pn .

Тогда функция f * (x1, x2 ,..., xn ), называемая двойственной

к f , определяется как : f * (x1, x2 ,..., xn ) f (x1, x2 ,..., xn ).

Следствие: f ** f .

Если в	таблице	истинности
			x	y	x→y		x	y	(x→y)*
инвертировать все значения (в
			0	0	1		1	1	0
том числе аргументы), то получим
			0	1	1		1	0	0
таблицу	истинности	функции
			1	0	0		0	1	1
двойственной исходной.
			1	1	1		0	0	0

Теорема. Функция, двойственная суперпозиции функций, равна суперпозиции функций, двойственных к функциям, составляющим эту суперпозицию.

Функция двойственная самой себе, называется самодвойственная функция. Например: ¬x.

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

15

Полином Жегалкина

Определение. Полином Жегалкина называют:

a	ai1,..., ik xi1 ... xik , где : k 0,..., n; a, ai1,..., ik E2 .
1 i1 ... ik	n

Теорема (Жегалкина). Всякую функцию алгебры логики возможно представить единственным полином Жегалкина.

Полином Жегалкина можно получить с помощью таблицы истинности функции алгебры логики и треугольника Паскаля.

x	y	z	f(x,y,z)	N							треугольник Паскаля
0	0	0	1	1	1			0				0				1			0			1			0				1
0	0	1	0	z		1				0				1		1					1			1				1
0	1	0	0	y				1				1				0			0			0			0
0	1	1	1	yz						0				1		0					0			0
1	0	0	0	x								1				1			0			0
1	0	1	1	xz										0			1				0
1	1	0	0	xy												1			1
1	1	1	1	xyz													0

f (x, y, z) =1 z y x xy

16

Линейные функции

Определение. Функцию f (x1, x2 ,..., xn ) называют линейной, если полином Жегалкина для неѐ имеет линейный

относительно	переменных вид:
f (x1, x2 ,..., xn )	a0 a1x1 ... an xn , ai E2 .

Теорема. Класс линейных функций замкнут относительно суперпозиции.

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

f (x1, x2 ,..., xn )	a0
g(x1, x2 ,..., xm )	b0

f (g1, g2 ,..., gn ) a0

...

a1 x1	...	an xn ,	ai E2	и
b1x1	...	bm xm .
a1 (b0		b1x1 ...	bm xm ) ...
an (b0		b1x1 ...	bm xm ).	линейная ф.
				ч. т. д.

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

17

		Монотонные функции
Определение. Функция			f (x1, x2 ,..., xn ) называется монотонной,
если всяких наборов			A и B	условие A	B влечѐт	f ( A) f (B).
Где A	a1, a2 ,..., an		и B	b1,b2 ,..., bn	наборы длины n,
из 0 и	1, будем считать			A B, если	a1 b1, a2	b2 ,..., an bn .

Теорема. Класс монотонных функций замкнут относительно суперпозиции.

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

Лемма. Функция монотонна тогда и только тогда, когда еѐ сокращѐнная ДНФ не содержит отрицаний.

18

Конъюнктивно нормальная форма (КНФ)

Определение. Элементарным дизъюнктивным термом называется терм составленный из попарно различных переменных или их отрицаний соединѐнных операцией дизъюнкция.

Пример. x, x, x y, x y x

Определение. Конъюнктивно нормальная форма называется конъюнкция попарно различных дизъюнктивных термов.

Пример. x, x, x y, x (x y z) ( y m)

Лемма. Всякая функция алгебры логики допускает представление в виде КНФ.

Терм – выражение формального языка системы. Понятие терм определяется индуктивно. Терм есть символьное выражение: t(x1,x2,…,xn), где t – имя терма или функтор, а x1,x2,…,xn – термы структурированные или простейшие.

19

Дизъюнктивно нормальная форма (ДНФ)

Определение. Элементарным конъюнктивным термом называется терм составленный из попарно различных переменных или их отрицаний соединѐнных операцией конъюнкция.

Пример. x, x, x y, x y x

Определение. Дизъюнктивно нормальная форма называется дизъюнкция попарно различных конъюнктивных термов.

Пример. x, x, x y, x y z, x (x y) (x z)

Лемма. Всякая функция алгебры логики допускает представление в виде ДНФ.

20