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

⇐ ПредыдущаяСтр 3 из 7Следующая ⇒

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

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

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.

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

= =

= .

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

Функция	Классы
P₀	P₁	S	M	L
	Да	Нет	Нет	Да	Да
	Нет	Да	Нет	Нет	Нет

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

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

Решение:

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

x	y	x Ú y	x Ù Ø y

Функция	Классы
P₀	P₁	S	M	L
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₄таблицу можно составить отдельно).

x, y, z	xy	y ~ z	f₁=(xy~(y~ z))	yz	f₃= x~ y z	f₅= xy← z

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	f₂ = x + x y	f₄ =

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

	Т₀	Т₁	L	M	S
f₁ f₂ f₃ f₄ f₅	+ + – – –	– – + + +	– – – + –	– – – – –	– – – – –

Таким образом, базисами являются: 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}.

Индивидуальное задание

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

17.1 ;

17.2 ;

17.3 ;

17.4 ;

17.5 ;

17.6 ;

17.7 ;

17.8 ;

17.9 ;

17.10 ;

17.11 ;

17.12 ;

17.13 ;

17.14 ;

17.15 .

ЛОГИКА ПРЕДИКАТОВ

Предикаты и кванторы

Пусть А – множество объектов произвольной природы (предметная область предиката), n-местный предикат – произвольное отображение

, .

Пример 1. Предикат A(x) =«x ≤ 2» на множестве X = R – одноместный. Предикат B(x, y) =«xy > 0» на множестве X = – двуместный.

Если X = {0, 1}, то n-местный предикат является n-местной булевой функцией. Нульместный предикат представляет собой высказывание.

Поскольку множество значений любого предиката лежит во множестве {0, 1}, то с предикатами можно производить все операции алгебры логики, и все известные свойства логических операций обобщаются для предикатов. Рассмотрим эти свойства (для удобства в свойствах записываются одноместные предикаты):

1. Коммутативность:

P(x) Q(x) = Q(x) P(x), P(x) Q(x) = Q(x) P(x).

2. Ассоциативность:

P(x) (Q(x) R(x))=(P(x) Q(x)) R(x),

P(x) (Q(x) R(x))=(P(x) Q(x)) R(x).

3. Дистрибутивность:

P(x) (Q(x) R(x))=(P(x) Q(x)) (P(x) R(x)),

P(x) (Q(x) R(x))=(P(x) Q(x)) (P(x) R(x)).

4. Идемпотентность: P(x) P(x) = P(x), P(x) P(x) = P(x).

5. Закон двойного отрицания: P(x) = P(x).

6. Закон исключения третьего: P(x) P(x) = 1.

7. Закон противоречия: P(x) P(x) = 0.

8. Законы де Моргана:

(P(x) Q(x)) = P(x) Q(x),

(P(x) Q(x)) = P(x) Q(x).

9. Свойства операций с логическими константами:

P(x) 1 = 1, P(x) 0= P(x), P(x) 1= P(x), P(x) 0 = 0.

Здесь P(x), Q(x) и R(x) – любые предикаты,

– объединение предикатов,

– пересечение предикатов,

– следствие предикатов,

– эквиваленция предикатов.

Для предикатов определены операции специального вида, которые называются кванторами.

Пусть дан n-местный предикат на множестве X, означающий, что для набора выполнено свойство A, и пусть – одна из переменных. Тогда запись означает, что для всех значений переменной свойство A выполнено. Символ называется квантором всеобщности (общности). Предикат является (n-1)-местным. Он зависит от переменных . Если дан одноместный предикат P(x), то утверждение xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.

Для n-местного предиката на множестве X и переменной запись означает, что существует значение переменной , для которойсвойство A выполнено. Символ называется квантором существования. Предикат является (n-1)-местным, зависит от переменных , для одноместного предиката P(x) утверждение xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.

Пример 2. На множестве X = R дан предикат A(x) =«x≤ 2». Высказывание x(x ≤ 2) – ложно, x(x ≤ 2) – истинно.

Запись xA ( xA) не подразумевает, что в формуле A есть переменная x.

Переменная x называется переменной в кванторе, а A – областью действия квантора.

Имеют место эквивалентности:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) x(P(x) Q(x)) = xP(x) xQ(x);

10) x(P(x) Q(x)) = xP(x) xQ(x);

11) xP(x) xQ(x) = xP(x) yQ( y) = x(P(x) yQ( y)) =

= x y (P(x) Q( y));

12) xP(x) xQ(x) = xP(x) yQ( y) = x(P(x) yQ( y)) =

= x y (P(x) Q( y)).

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

Пример 3.

Предложение – одноместный предикат, определенный на множестве N.

– «существует х, для которого верно » – истинное высказывание;

– «для всех x верно » – ложное высказывание.

Предложение – двухместный предикат, определенный на множестве А.

Предикат называется выполнимым, если при некоторых значениях переменных он принимает значение истина.

Пример 4. Найти значение высказывания .

Трехместный предикат определен на множестве N. Решение:

Пусть = 1. Эквивалентность имеет место тогда и только тогда, когда для некоторого , и предикат является тождественно истинным относительно y, то есть исходное высказывание истинно.

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

В формуле вхождения обеих переменных свободные, в формуле вхождение переменной x связано, а вхождение переменной у свободно.

Для каждого предиката A областью истинности называется множество Y = {x X, A(x) = 1}, на котором предикат принимает значение 1.

Множество истинности предиката ,

Для предиката A(x) =«x ≤ 2» на множестве X= областью истинности является множество Y = {x R, x ≤ 2}.

Для предиката B(x, y) =«xy > 0» на множестве X = область истинности Y = {(x, y) , xy > 0}.

Для области истинности пересечения и объединения предикатов верны соотношения:

, .

Следующие предложения означают: – «для всех m верно: m делится на n» или «любое натуральное ненулевое число делится на n» – одноместный предикат, зависит от n, выполнимый предикат, область его истинности – {n=1}, так как все числа делятся на 1;

– «существует m, для которого верно: m делится на n» или «найдется натуральное ненулевое число, которое делится на другое натуральное ненулевое число» – одноместный предикат, зависит от n, тождественно истинный предикат, область его истинности – А;

– «для всех n верно: m делится на n» или «натуральное ненулевое число делится на любое натуральное ненулевое число» – одноместный предикат, зависит от m, тождественно ложный предикат, область его истинности –пустое множество;

– «существует n, для которого верно: m делится на n» или «натуральное ненулевое число делится на некоторое натуральное ненулевое число» – одноместный предикат, зависит от m, тождественно истинный предикат, область его истинности – А.

Упражнения

1. Выделить предикаты, для каждого предиката установить местность и область истинности, если X = R. Для двуместных предикатов изобразить область истинности графически.

1) x + 2 = 0;

2) При x =0 выполняется равенство x − 2 = 0;

3) - 8 = 0;

4) (x - 8 = 0);

5) однозначное число x является простым.

2. На множестве M = {1, 2, 3, …, 20} заданы предикаты:

A(x): «x не делится на 5»;

B(x): «x – четное число»;

C(x): «x – число простое»;

D(x): «x кратно 3».

Найдите множество истинности следующих предикатов:

a) ;

b) ;

c) ;

d) .

3. Записать предикаты, полученные в результате логических операций над предикатами P(x), Q(x) и R(x), множества истинности которых (E) заштрихованы на следующих рисунках:

Рис. 3

Рис. 2

Рис. 1

Рис. 9

Рис. 8

Рис. 7

Рис. 6

Рис. 5

Рис. 4

Индивидуальное задание

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

1.1 x y z (xz = y), X = N;

1.2 z x y (xz = y ), X = Z;

1.3 z y x (xy > xz), X = N;

1.4 x y z (xyz < yz), X = Z;

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒