Важнейшие замкнутые классы Алгебры Логики

Класс Т₀ – класс булевых функций, сохраняющих константу «0», то есть это такие функции от f(x₁, …, x_n), что f(0, …, 0) = 0.

Пример:

1) Принадлежащие Т₀: &, Ú, x.

2) Не принадлежащие Т₀: x ® y, .

x1	…	xn		f		Þ
	…
	…			2n - 1
…………
	…

Теорема.

Т₀ – замкнутый класс.

Доказательство: T₀ = |T₀| Û

Докажем: [T₀] Í T₀, Ф Î [T₀] Ф Î T₀. Ф = f(f₁, …, f_s) = f(f₁(x₁, …, x_n), …, f_s(x₁, …, x_n)), f₁, …, f_s Î T₀. Следовательно, Ф(0, …, 0) = f(f₁(0, …, 0), …, f_s(0, …, 0)) = f(0, …, 0). Так как каждая функция f₁, …, f_s сохраняет «0», то Ф Î T₀.

Класс Т₁ – класс всех булевых функций, сохраняющих константу «1», то есть Т₁: f(1, …, 1) = 1.

Пример:

1. Принадлежащие Т₁: x & y, x Ú y, x, x ® y.

2. Не принадлежащие Т₁: x Å y, .

(T₀ Ç T₁ ¹ Æ)

Класс S – класс самодвойственных функций, то есть f^* = f Þ f – самодвойственная.

Пример:

1) Принадлежащие S: x, .

2) Не принадлежащие S: x & y, x Ú y, x ® y.

f Í S: f^*(x₁, …, x_n) = [f Í S] = f(x₁, …, x_n).

Определение. Наборы (a₁, …, a_n) и – противоположные. На таких наборах самодвойственная функция принимает противоположные значения. Самодвойственная функция полность определяется на первых n / 2 строках таблицы.

Теорема.

S – замкнутый класс.

Доказательство: S – замкнутый класс.

Доказательство: S = |S| Û

Ф Î [S] Ф Î S, f₁, …, f_l Î S. Ф = f(f₁, …, f_n) = f(f₁(x₁, …, x_n), …, f_l(x₁, …, x_n)). Рассмотрим Ф*( x₁, …, x_n) = f^*(f₁^*(x₁, …, x_n), …, f_l^*(x₁, …, x_n)) = [x_i^* = f_i, i = 1, 2, …, n, f^* = f] = f(f₁(x₁, …, x_n), …, f_l(x₁, …, x_n)) = Ф*( x₁, …, x_n) Þ Ф – самодвойственная.

Лемма ( О не самодвойственных функциях).

Если функция f(x₁, …, x_n) – не является самодвойственной, то из нее путем подстановки функций x и можно получить не самодвойственную функцию от одной переменной, то есть константу ( ).

Доказательство: Так как f Ï S Þ $(a₁, …, a_n): f(a₁, …, a_n) = , , x₁ ~ , x_n ~ . Заметим, что , то есть и 1^a = a. Рассмотрим функцию . Докажем, что g(x) º Const. Для этого рассмотрим g(0) и g(1): g(0) = = = f(a₁, …, a_n) = = g(1) Þ g(0) = g(1) Þ g(x) º Const.

Класс М – класс монотонных функций.

Определение. Пусть набор = (a₁, …, a_n), f( ) = f(a₁, …, a_n). Для любых = (b₁, …, b_n) выполнено отношение предшествования, если a_i ≤ b_i, для "i = 1, 2, …, n ( ) или b_i ≤ a_i, для "i = 1, 2, …, n ( ).

Пример: Наборы:

(0, 1, 0, 1) (1, 1, 0, 1)

(0, 1, 0, 1) ? (1, 0, 0, 1) – не находятся в отношении предшествования.

Определение. Если , Þ (Свойство транзитивности).

Определение. Функция f(x₁, …, x_n) принадлежит классу монотонных функций, если для " имеет место неравенство f( ) f( ).

Пример:

1) Принадлежит М: 0, 1, x & y, x Ú y.

2) Не принадлежит М: , x ® y, x Å y.

В Алгебре логики монотонная функция является только монотонно-возрастающей.

Теорема.

Класс М – замкнутый.

(без доказательства)

Лемма (О немонотонной функции).

Если немонотонная, то из нее путем подстановки констант «0» и «1» и функции x можно получить немонотонную функцию от одной переменной, ( ).

Доказательство: Так как f Ï М Þ $ и , : f( ) > f( ). Рассмотрим = (a₁, …, a_i-1, 0, a_i+1, …, a_n) и = (a₁, …, a_i-1, 1, a_i+1, …, a_n). Рассмотрим функцию g(x) = f(a₁, …, a_i-1, x, a_i+1, …, a_n), g(0) = f( ) > g(1) = f( ) Þ Þ g(x) = .

Класс L – класс линейных функций, то есть L = { C₀ Å C₁x₁ Å … Å C_nx_n }.

Пример:

1) Принадлежащие L: 0, 1, x, .

2) Не принадлежащие L: x& y, x Ú y, x ® y.

[L] = L

Для каждого n (число переменных) существует по 2 линейных функции, то есть x₁ Å … Å x_n и x₁ Å … Å x_n Å 1.

|L| = 2n

Лемма (О нелинейной функции).

Если f(x₁, …, x_n) не является линейной, то из нее путем подстановки констант «0» и «1» функций x и , а также, может быть, путем навешивания отрицаний к функции f, можно получить нелинейную функцию от двух переменных, то есть x & y.

Доказательство: Так как f Ï L, то есть полином Жегалкина обязательно содержит конъюнкцию (x & y) Þ получить x & y. Доказательство: без ограничения общности можно считать, что в этих конъюнкциях можно читать существенным x₁ & x₂, то есть ПЖ(f) = x₁x₂f₁(x₃, …, x_n) Å x₁f₂(x₃, …, x_n) Å x₂f₃(x₃, …, x_n) Å f₄(x₃, …, x_n). Так как Полином Жегалкина – единственный, то f₁(x₃, …, x_n) ¹ 0. Выберем набор значений (x₃, …, x_n), f(x₃, …, x_n) = 1. Пусть j(x₁, x₂) = f(x₁, x₂, a₃, …, a_n) = x₁x₂ Å ax₁ Å bx₂ Å g, где a = f₂(x₃, …, x_n), b = f₃(x₃, …, x_n), g = f₄(x₃, …, x_n) (a, b, g = 0 или 1). Сделаем подстановку: x₁ ~ x₁ Å C₁, x₂ ~ x₂ Å C₂. j(x₁ Å C₁, x₂ Å C₂) = (x₁ Å C₁)( x₂ Å C₂) b a(x₁ Å C₁) Å b(x₂ Å C₂) Å g = x₁x₂ Å C₂x₁ Å C₁x₂ Å C₁C₂ Å ax₁ Å aC₁ Å bx₂ Å bC₂ Å g = [C₂ = a, C₁ = b] = x₁x₂ Å ab Å ab Å ab Å g = x₁x₂ Å ab Å g = . Вывод: x₁x₂ = j(x₁ Å C₁, x₂ Å C₂) Å d = f(x₁ Å C₁, x₂ Å C₂, a₃, …, a_n) Å .

(Лекция 11)

Существует два способа определения f Î L:

1) Записать Полином Жегалкина для f и выяснить – есть ли конъюнкция. Тогда f Î L.

2) а) Исключить фиктивные переменные из f;

б) Построить диаграмму для полученной функции.

Для функции двух переменных (x Å y):

Функция является линейной, если на противоположных слоях разные значения.

Для функции трех переменных:

f Î L значения функции на слоях чередуются.

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

Пример:

	T0	T1	S	M	L
	+	-	-	+	+
	-	+	-	+	+
	-	-	+	-	+

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

Фундаментальная теорема Алгебры логики

(Критерий полноты системы булевых функций)

(Теорема Поста о функциональной полноте)

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

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

1) Необходимость. Пусть F – полная система булевых функций. Доказываем методом «от противного». Допустим, F содержится в одном из пяти замкнутых классов (F Í X) Þ [по свойству замыкания] Þ [F] Í [X] = X (так как Х – замкнутый класс) Þ Замыкание этой системы совпадает с множеством булевых функций (P₂ = [F] Í X), то есть P₂ Í X, но X Í P₂ (изначально), то есть X = P₂, что неверно из определения одного из замкнутых классов. Значит, наше допущение неверно и F целиком содержится в одном из пяти замкнутых классов.

2) Достаточность. Пусть F не содержится ни в одном из пяти замкнутых классов. Тогда, из системы F можно выделить подсистему F’, содержащую не более пяти функций, которые также обладают этим свойством, то есть F’ = {f₁, f₂, f₃, f₄, f₅}, причем f₁ Ï T₀, f₂ Ï T₁, f₃ Ï S, f₄ Ï M, f₅ Ï L. Докажем, что F содержит и & (Известно, что {Ø, &} – полная система). Поскольку f₁ Ï T₀ Þ f₁(0, …, 0) = 1 Þ f₁(1, …, 1) =

В случае (а) есть . Берем функцию f₃ Þ [по лемме о не самодвойственной функции] Þ получаем константу. Так как есть , то получаем вторую константу. Таким образом, у нас есть (0, 1, , f₅) Þ [по лемме о нелинейной функции] Þ x₁ & x₂. Получим {Ø, &}. Пункт (а) доказан.

Докажем пункт (б). f₂(1, …, 1) = 0 Þ f₁(1, …, 1) = 1. (0, 1, f₄) Þ [по лемме о немонотонной функции] Þ получим . Теперь получим конъюнкцию аналогично пункту (а).

Таким образом, мы выразили функции Ø и & через функции системы F’. Но известно, что система {Ø, &} – полная. Значит, по теореме о сведении вопроса о полноте системы одной функции к вопросу о полноте другой. Отсюда F’ – полная Þ F – полная.

Пример: x ® y, x ~ y.

x

y

x ® y

x ~ y

T0

T1

S

M

L

x ~ y = = x Å y Å 1 x ® y = xy Å x Å1

®

–

+

–

–

+

~

–

+

–

–

+

–

–

+

–

+

Данная система содержится в Т₁. Следовательно, по критерию полноты эта система неполная.

Можно ли добавить к этой системе такую функцию, чтобы система стала полной?

Система {Ø, ®, ~}- полная, то есть [{Ø, ®, ~}] = P₂.

Можно ли исключить из этой системы такую функцию, чтобы система стала полной?

[{Ø, ®}] = P₂ Þ {Ø, ®} – полная.

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

Примеры базисов:

1) {x / y}

2) {x & y, }, {x Ú y, }

3) {1, x & y, x Å y}

Из примера (2) следует, что система {x & y, x Ú y, } – полная, но не базис.

Система:

	T0	T1	S	M	L		Найдем базис: {0, 1, &} Ì М Þ неполная {0, 1, Å} Ì L Þ неполная {0, &, Å} Ì T0 Þ неполная {1, &, Å} Þ полная и является базисом
	+	--	--	+	+
	--	+	--	+	+
&	+	+	--	+	--
Å	+	--	--	--	+

Следствие 1 из Теоремы Поста.

Каждый базис в алгебре логики состоит не более чем из 4-х функций.

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

Пусть f₁ Ï T₀, f₂ Ï T₁, f₃ Ï S, f₄ Ï M, f₅ Ï L Þ {f₁, f₂, f₃, f₄, f₅} – полная по теореме Поста. Докажем, что из этой системы можно удалить одну функцию и система останется полной.

(а) f₁(1, …, 1) = 0 Þ f₁ Ï M Þ Удаляем f₄ Þ {f₁, f₂, f₃, f₅} – полная.

(б) f₁(1, …, 1) = 0 Þ f₁ Ï S Þ Удаляем f₃ Þ {f₁, f₂, f₄, f₅} – полная.

Следствие доказано.

Определение. Класс А называется предполным, если А – неполный, но при добавлении любой f Ï A он становится полным.

Следствие 2 из Теоремы Поста.

В алгебре логики пять предполных классов.

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

1) Докажем, что в алгебре логики нет других предполных классов, методом «от противного». Допустим Х – предполный класс, не совпадающий ни с одним из этих пяти. Х – неполный, но содержится в одном из пяти замкнутых классов (Y) по Теореме Поста. X ¹ Y Þ X Ì Y Þ $f Î Y: f Ï X. но после добавления к классу Х {f È X} Í Y Þ [По Теореме Поста] Þ f È {X} – неполная. Получили противоречие с тем, что Х – предполный. Таким образом, других предполных классов в алгебре логики нет.

2) Докажем. Что рассмотренные нами замкнутые классы – предполные. Эти классы не полны по Теореме Поста, так как каждый их них содержится сам в себе. Докажем, что при добавлении любой булевой функции они станут полными, методом «от противного». Пусть Z – один их этих пяти классов. Рассмотрим функцию f Ï Z. Предположим, что Z – не предполный. Тогда после добавления функции f он становится неполным. Если он неполный, то по Теореме Поста Z È {f} Í W, где W – другой из этих пяти классов. Отсюда получается, что Z Í W. Это противоречит определению одного из пяти замкнутых классов. Перебирая последовательно все пять замкнутых классов докажем, что все они предполные.