Принцип двойственности

Определение. Функция f^*(x₁, …, x_n) = называется двойственной функции f(x₁, …, x_n).

Пример: (построение функции, двойственной к исходной)

x	y	z	f(x, y, z)

Таблица для двойственной функции f^*(x, y, z) при упорядоченном наборе значений переменной получается из таблицы для функции f(x, y, z) построением функции отрицания и переворачиванием столбца значений от функции .

Таблица функций, двойственным к элементарным:

		0*			1*		x		x*

0^* = 1 1^* = 0 x^* = x

x	y	x & y		(x & y)*		x	y	x Ú y		(x Ú y)*

(x & y)^* = x Ú y (x Ú y)^* = (x & y)

Из определения двойственности вытекает:

f^** = (f^*)^* = = = f Þ f^** = f

Функция f двойственна к f^*

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

Теорема двойственности

Если j(x₁, …, x_n) = f(f₁(x₁₁, …, ), …, f_m(x_m1, …, )), где (x₁, …, x_n) – переменные, входящие в наборы (x₁₁, …, ), …, (x_m1, …, ), то j^*(x₁, …, x_n) = f(f₁^*(x₁₁, …, ), …, f_m^*(x_m1, …, )).

Доказательство: j^*(x₁, …, x_n) º [по определению] º = [по условию] =

= = =

= = [по определению двойственной функции] =

=

Пример: f₁(x, y) = x & y, f₂(x, y) = x Ú y, f₃(x) = .

j = = f₂(f₁(x₁, x₂), f₁(f₃(x₃), x₄))

j^* = f₂^*(f₁^*(x₁, x₂), f₁^*(f₃^*(x₃), x₄)) = f₁(f₂(x₁, x₂), f₂(f₃(x₃), x₄)) = .

Принцип двойственности

Если формула A = C[f₁, …, f_s] реализует формулу f(x₁, …, x_n), то формула C[f₁, …, f_s], полученная из формулы f₁, …, f_s на f₁^* …, f_s^* , реализует f^*(x₁, …, x_n). Эту формулу называют двойственной к А и обозначают А^*. Для формулы А над множеством P = {0, 1, x, , &, Ú} принцип двойственности записывается так:

«Для получения двойственной формулы надо заменить 0 на 1, 1 на 0, & на Ú, Ú на & и сохранить функции x и .»

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

МАТЕРИАЛ ЭКЗАМЕНА

(Лекция 9)

Разложение булевых функций по переменным

Введем обозначение:

x	d	xd
			Þ xd = 1 Û x = d
			xx = 1

Обозначение:

Теорема (О разложении булевых функций по переменным)

Каждую функцию алгебры логики f(x₁, x₂, …, x_n) для "m Î {1, 2, …, n} можно представить в виде , где дизъюнкция берется по всевозможным наборам значений d₁, …, d_m переменных x₁, …, x_m. Такое представление функции f называется разложением этой функции по m переменным.

Доказательство: Рассмотрим произвольный набор значений переменных (a₁, …, a_n) и вычислим f(a₁, …, a_n) сначала стандартным образом, а затем так: = [По ранее доказанному, если a_i ¹ d_i, то ] = = f(a₁, …, a_n).

Следствия:

1) m = 1. Тогда f(x₁, …, x_n) = = .

2) m = n. Тогда f(x₁, …, x_n) = , остались лишь те наборы d, при которых f(d₁, …, d_n) = 1.

f(x1, …, xn) = , f(d1, …, dn) = 1

Такое различие называется Совершенной Дизъюнктивной Нормальной Формулой (СДНФ).

Пример:

x1	x2	x3	f	f1	f2	f3		f = f1Ú f2 Ú f3   - СДНФ

Существует еще и Совершенная Конъюнктивная Нормальная Формула (СКНФ):

f(x1, …, xn) = , f(d1, …, dn) = 1

Только для функции «0» мы не можем составить СДНФ.

По аналогии, не существует СКНФ для функции «1».

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

Если формула алгебры логики составлена исключительно из функций 0, 1, &, Å, то после несложных преобразований ее можно записать в виде полинома по «Сумме по модулю 2».

Определение. Полиномом Жегалкина от n переменных x₁, …, x_n называется «Сумма по модулю 2»: .

Пример: ПЖ(x₁, x₂) = a₁₁x₁x₂Å a₁x₁Å a₂x₂Å a_o

Слагаемых в этой сумме столько, сколько подмножеств (j₁, …, j_s) из n чисел, то есть 2ⁿ, при этом значения коэффициентов . Таким образом, число полиномов Жегалкина от n переменных равно , то есть |ПЖ(n)| = .

Теорема Жегалкина

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

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

Замечание. Если у функции есть фиктивные переменные, то они не должны входить в полином Жегалкина.

Способы нахождения Полинома Жегалкина:

1) Через законы Алгебры Логики.

a) Из формулы.

b) Из СДНФ.

2) Метод неопределенных коэффициентов.

Способ 1(а): x Ú y = = = (x Å 1) (y Å 1) Å 1 = = xy Å x Å y

Способ 2:

x	y	x ® y					(x ® y) = a12xy Å a1x Å a2y Å a0
			a0 = f(0, 0) = 1
			a0 Å a1 = f(1, 0), 1 Å a1 = 0 Þ a1 = 1
			a2 Å a0 = f(0, 1), 1 Å a2 = 1 Þ a2 = 0
			a12 Å a1 Å a2 Å a0 = f(1, 1), a12 Å 1 Å 0 Å 1 = 1 Þ a12 = 1

ПЖ(x ® y) = xy Å x Å 1

Определение. Если полином Жегалкина не содержит конъюнкций, то есть имеет вид a₁x₁ Å a₂x₂ Å … Å a_nx_n Å a₀, то соответствующая ему функция называется линейной.

Полнота и замкнутость

Определение. Система функций {f₁, f₂, …, f_s}называется полной (функционально полной), если любая булева функция может быть записана в виде формул через функции этой системы ({f₁, f₂, …, f_s} Ì P₂).

Пример:

1) P₂ – полная.

2) {Ø, &, Ú} – полная Þ Если f(x₁, …, x_n) º 0, то f(x₁, …, x_n) = x₁ & .

3) {0, 1} – неполная.

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

Пусть даны 2 системы булевых функций R = {f₁, f₂, …, f_r} (I) и S = {g₁, g₂, …, g_s} (II), причем система I – полная и каждая функция системы I выражается в виде формул системы II. В этом случае система II является полной.

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

Следствие. Полными являются следующие системы: {Ø, Ú}, {Ø, &}, {¤}, {Ø, ®}, {0, 1, &, Å}.

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

а) (I) {Ø, &, Ú}. x & y = = . Аналогично: x Ú y = .

б) (I) {Ø, &}. = x / x. Тогда: x & y = = (x / y) / (x / y).

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

Определение. Пусть М – некоторое подмножество булевых функций. Замыканием М (обозначается [M]) называется множество всех булевых функций, являющихся суперпозицией функций из М.

Пример:

1) М = Р₂, [M] = P₂.

2) M = {1, x Å y}, f Î M, f = a₀ Å a₁x₁ Å … Å a_nx_n (f – линейная функция).

Свойства замыкания:

1) M Í [M]

2) [[M]] = [M]

3) M₁ Í M₂ [M₁] Í [M₂]

4) [M₁ È M₂] Ê [M₁] È [M₂]

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

(Лекция 10)

Примеры:

1) M = P₂, [M] = P₂ =M – замкнутое

2) M = L (множество линейных функций), [M] = L = M – замкнутое

3) M = {Ø, &, Ú} Þ [M] =P_­­­2 Þ M – замкнутое

4) M = {0, 1}Þ M – неполное, [M] = {0, 1} – замкнутое.

5) M = {1, }Þ [M] = {0, 1, x, } Þ M – незамкнутое

6) [M] – замкнутый класс по свойству 2.