Закон двойственности

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

Из этого закона следует, что суперпозиция самодвойственных функций – функция самодвойственная.

В булевой алгебре принцип двойственности звучит так: если в формуле F, представляющей функцию f, все конъюнкции заменить на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу F*, представляющую двойствен-ную функцию f*.

Пример. Применить принцип двойственности к функции: f( x,y,z ) = x y & z.

Сделав замену дизъюнкции на конъюнкцию, а конъюнкции на дизъюнкцию, получим следующую функцию:

f₁( x,y,z ) = x & (y z).

Составим следующую таблицу.

Таблица 1.17

x	y	z	y&z	F	y z	f1
0	0	0	0	0	0	0
0	0	1	0	0	1	0
0	1	0	0	0	1	0
0	1	1	1	1	1	0
1	0	0	0	1	0	0
1	0	1	0	1	1	1
1	1	0	0	1	1	1
1	1	1	1	1	1	1

Из табл. 1.17 видно, f₁ = f*, т.е. f₁, полученная по принципу двойственности является двойственной функцией к f.

Очевидно, что если логические функции равны, то и двойственные им функции также равны, т.е. если f₁ = f₂, то f₁* = f₂*. Это позволяет с помощью принципа двойственности получать новые эквивалентные соотношения.

Пример. С помощью принципа двойственности доказать свойство поглощения:

x & ( x y ) = x .

По принципу двойственности получим: x & ( x y ) = x x & y = x( 1 y ) = x.

Пример. Рассмотрим две функции:

f₁( x,y ) = x x & y и f₂( x,y ) = x & ( x y ).

Из предыдущего примера видно, что они равные. Тогда из равенства их двойственных функций получим следующее эквивалентное соотношение:

S – класс всех самодвойственных функций.

Для самодвойственной функции справедливо равенства (1.12), т.е. на наборах

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

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

Докажем, что класс S замкнут. Поскольку класс S содержит тождественную функцию, достаточно показать, что функция Ф = f( f₁, …, f_m ) является само-двойственной, если f₁, …, f_m - самодвойственные.

Последнее устанавливается непосредственно:

Ф* = f*( f₁*, …, f_m* ) = f( f₁, …, f_m ) = Ф.

Определение. Для двух наборов значений переменных a = ( a₁, … , a_n ) и b = ( b₁, … , b_n ) выполнено отношение предшествования a ≤ b,

если

a₁ ≤ b₁, … , a_n ≤ b_n, где a_i, b_i { 0,1 }.

Например, для a = ( 0,1,0,1 ) и b = ( 1,1,0,1 ) выполнено отношение a ≤ b.

Очевидно что если a≤ b и b≤ c, то a ≤ c. Следует отметить, что не любые пары наборов значений переменных находятся в отношении предшествования, например, наборы ( 0,1 ) и ( 1,0 ) в таком отношении не находятся.

Определение. Функция f( x₁, …, x_n ) называется монотонной, если для любых двух наборов значений переменных a и b таких, что a ≤ b, имеет место неравенство:

f( a ) ≤ f( b ). (1.13)

Нетрудно заметить, что функция, равная монотонной функции, так же является монотонной. Легко проверить, что монотонными функциями будут следующие функции: 0, 1, x, x & y, x y. Функция не является монотонной.

Пример. Проверить на монотонность функции f₁ и f₂, заданные следующей таблицей:

Таблица 1.18

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

Для функции f₁ вторую строку ( f₁ = 1 ) можно сравнивать с третьей, шестой и седьмой строками, где f₁ = 0. Набор значений переменных второй строки не нахо-дится в отношении предшествования с набором третьей строки, а с набором шестой строки находится в отношении предшествования, т.е.

( 0, 0, 1 ) ≤ ( 1, 0, 1 ). Сравнивая значения функции f₁ для этих строк, получим:

f₁( 0, 0, 1 ) > f₁( 1, 0, 1 ).

Следовательно, функция f₁ не является монотонной.

Для функции f₂ наборы значений переменных третьей и четвертой строк, где f₂ = 1, можно сравнивать с наборами пятой строки, для которой f₂ = 0. Наборы значе-ний переменных этих строк не находятся в отношении предшествования с набором пятой строки, поэтому эти строки не следует сравнивать. Другие строки так же не следует сравнивать, т.к. значение функции в предшествующей строке не больше значения функции в последующей строке. Следовательно, условие (1.13) не нарушается для функции f₂, а это и означает, что данная функция монотонная.

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

Теорема. Любая булева формула, не содержащая отрицаний, представляет монотонную функцию, отличную от 0 и 1, и наоборот, для любой монотонной функции, отличной от 0 и 1, найдется представляющая ее булева формула, не содержащая отрицаний.

Пример. Проверить на монотонность следующие функции:

x y, x & y, x & ( y z ).

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

M - класс всех монотонных логических функций. Можно показать, что класс M является замкнутым классом.

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

f( x₁, …, x_n ) = a₀ a₁ x₁ a₂ x … a_n x_n , (1.14)

где a_i {0,1}.

Легко видеть, что константы 0, 1 и функции x, , x y являются линейными функциями. Функциzя x y не является линейной, т.к. она представляется следующим полиномом Жегалкина:

x y = 1 x x y .

Для проверки функции на линейность полезна следующая теорема.

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

L – класс всех линейных логических функций.

Этот класс так же замкнут, т.к. выражение, составленное из линейных выражений, является линейным.

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

Предполными классами будут классы Т , T , S, M и L. Других предполных классов нет.

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

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

Пример. Проверить на полноту следующую систему функций: { x → y, x & y ).

Для проверки составим следующую таблицу.

Таблица 1.19

f	To	T1	S	M	L
→	–	+	–	–	–
&	+	+	–	+	–

В данной таблице знак «+» означает, что функция принадлежит соответствующему классу, а знак «–», что не принадлежит. Из таблицы видно, что все функции данной системы принадлежат классу Т₁. Следовательно, по теореме о полноте данная система функций не является полной.

Пример. Проверить на полноту следующую систему функций: { , x y }.

Функция не сохраняет 0, не сохраняет 1 и не является монотонной. Функция х y не является самодвойственной и нелинейная. Из этого следует, что в данной системе функций есть хотя бы одна функция не принадлежащая каждому из пяти замкнутых классов. Следовательно, данная система функций функционально полная.

Замечание. Можно показать, что если функция не принадлежит классам T , T и S , то она не принадлежит и классам M и L.

Следующие системы не являются полными

{ ,1 }, { xy, x y }, { x y, }, { xy yz xz, },

{ xy yz xz, 0, 1 }, { 0, xy, x y z }, { 1, xy, x y z },

{ }, { 0, 1, x y }, { 0, 1, xy }.

Для проверки систем на полноту удобно пользоваться следующей таблицей Поста

f	T	T	S	L	M
	-	-	+	+	-
xy	+	+	-	-	+
x y	+	+	-	-	+
1	-	+	-	+	+
0	+	-	-	+	+
x y	+	-	-	+	-
x ↓ y	-	-	-	-	-
x ∕ y	-	-	-	-	-
x y z	+	+	+	+	-
x → y	-	+	-	-	-
	-	-	+	-	-

Определение. Пусть К – некоторое подмножество функций из Р₂. Замыканием множества К называется множество всех логических функций, представимых в виде формул через функции множества К. Замыкание множества К обозначается [K].

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

Примеры.

1). Пусть К = Р₂. Тогда очевидно, что [K] = P₂.

2). Пусть K = { , x y, x & y }. Тогда [K] = P₂.

3). Пусть K = { 1, x y }. Замыканием этого множества будет класс L.

4). Пусть K = { 0, 1, x y, x & y }. Замыканием данного множества будет класс М, т.к. любая монотонная функция может быть представлена в виде формул через функции множества К.

В терминах замыкания можно дать другое определение полноты: K- полная система функций, если [K] = P₂.

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

Пример. Множество K = { 1, x y } не является замкнутым классом, т.к. [K] = L, а константа 1 не является линейной функцией.

2. К – значная логика