Пример 3. Покажем, что функция х1х2 двойственна к x1&x2, функция х1х2 двойственна к функции x1|x2.

x1x2	f=х1х2	f*	g=x1|x2	g*=x1x2
0 0 0 1 1 0 1 1	0 1 1 1	0 0 0 1	1 1 1 0	1 0 0 0

Теорема о двойственных функциях

Если f* двойственна кf, тоfдвойственна кf*.

Доказательство.f*(x₁, ...,x_n) = (₁, ..., _n). Найдем двойственную функцию кf*, т.е. (f*(x₁, ...,x_n))* = ((₁, ..., _n))* = (₁, ..., _n) =f(x₁, ..,x_n).

Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.

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

Теорема: Пусть функцияh(x₁, ...,x_n) реализована формулойh(x₁, ...,x_n) = =g(G₁, ...,G_m) =g(f₁(x₁, ...,x_n), ...,f_m(x₁, ...,x_n)), где какие-то переменные могут быть фиктивными. Тогдаh*( x₁, ...,x_n) =g*(f₁*(x₁, ...,x_n), ...,f_m*(x₁, …,x_n)), это означает, что если функция задана некоторой формулой, то чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные, 0 на 1, 1 на 0.

Доказательство.h*(x₁, ...,x_n) = (₁, ..., _n) = (f₁(₁, ..., _n), ...,f_m(₁, ..., _n)) = __.. _n. _. _ng..g*(f₁*(x₁, ...,x_n), ...,f_m*(x₁, ...,x_n)), что и требовалось доказать.

Если функция h(x₁, ...,x_n) реализуется формулойN[f₁, ...,f_n], то формулу, полученную изNзаменойf_i, входящих в нее, наf_i* и реализующую функциюh*(x₁, ...,x_n), будем называть двойственной и обозначатьN*(x₁, ...,x_n).

Пример 4.Построить формулу, реализующуюf*, еслиf= ((xy)z) (y(xyz)). Покажем, что она эквивалентна формулеN=z(xy).

Найдем (xy)* и (xy)*.

x y	xy	(xy)*	x y	(xy)*
0 0 0 1 1 0 1 1	0 1 1 0	1 0 0 1	1 1 0 1	0 1 0 0

Из таблиц видно, что

(xy)* = x ~ y = = xy1, xy =yx,

(xy)* =y xy =y.

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

f* = yz((x(yz)1)) = yzz(x(yz)1) =z(y(xz)) =z(y(xz1)) =z(y(x)) =zy(zxz) =z(yx) =z(xy).

Тогда f= (f*)* = [z(xy)]* =z(x~y).

Пример 5.Найти формулу для f* и показать, что она эквивалентна формулеN= (x(zt)), еслиf= (xyz~(tx))t.

f* = ((xyz)t(y))(t) = (t(y)(xyz))(t) =

= (t(xyz)(x))(t) = t(xyz)(xtx) =

= t(xyz)(x) = (xtzxxz) =(txzxz)

= (x(zt)).

Лемма о несамодвойственной функции

Подстановкой функций ив несамодвойственную функцию можно получить одну из констант.

Доказательство. Пусть– несамодвойственная функция. Тогда существует набор, для которого. Построим функцию, заменив единицы вна, а нули – на. Так как, то. Заметим, что.

Тогда , т.е.. Следовательно, функцияесть одна из констант.

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

Обозначим x^=

Посмотрим, чему равно x^при разных значенияхxи.

x\	0	1
0	1	0
1	0	1

Из таблицы следует: x^=1 тогда и только тогда, когда x=.

Теорема о разложении функции по переменным

Пустьf(x₁, ..., x_n) P₂. Тогда для любого m: 1 ≤ m ≤ n допустимо представление:

f(x₁, ..., x_m, x_m+1, ..., x_n) = ,

где дизъюнкция берется по всем наборам из 0 и 1, которое называется разложением функции f по переменным x₁, ...,x_n.

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

Пример 1.m= 1, запишем разложение по переменнымх:

f(x₁, ...,x_n) = = f(0,x₂ , …,x_n)x₁f(1,x₂, ...,x_n). (1)

Пример 2. m=2, запишем разложение по переменнымхи:

f(x₁,x₂,…x_n) = =

.

Если f(x_,x_) =x_x_, то последняя формула даетx_x_= x_x_.

Доказательство.Для доказательства возьмем произвольный набор_,,_n) и покажем, что левая и правая части формулы (1) принимают на этом наборе одинаковые значения. Слева имеемf_._n. Cправа :.

Дизъюнкция берется по всевозможным наборам (_, ...,_m). Если в этих наборах хотя бы одно_i_i (1≤i≤m), то= 0 и , следовательно, ненулевой член будет только на наборе (_, ...,_m) = (_, ...,_m), тогда f_._n.

Следствие 1. Любую функцию f(x₁, ..., x_n) не равную тождественно нулю можно представить в виде: , причём единственным образом. Этот вид называется совершенной дизъюнктивной нормальной формой функции f(x₁, ..., x_n) и записывается СДНФ.

Доказательство. Существование СДНФ для функции не равной тождественно нулю вытекает из предыдущей теоремы. Покажем, что эта СДНФ единственная. В самом деле, имеетсяn-местных функций, не равных нулю тождественно. Подсчитаем число различных СДНФ отnпеременных. Путьозначает число сочетаний изnэлементов поk. Тогда число одночленных СДНФравно. Числоk-членных СДНФ равно. Числоn-членных СДНФ равно. Число всех различных СДНФ

Итак, функций реализуются посредствомСДНФ, т.е. каждой функции соответствует единственная СДНФ.

Замечание. – элементарная конъюнкция ранга n по числу входящих переменных, предполагается, что приij,х_i х_j. СДНФ дляf(x₁, ..., x_n)–дизъюнкция элементарных конъюнкций рангаn. Если функция представлена в виде дизъюнкций элементарных конъюнкций, где ранг хотя бы одной элементарной конъюнкции меньшеn, то такая форма называетсядизъюнктивной нормальной формой(ДНФ).

Cледствие 2.Любая функция алгебры логики может быть представлена в виде формулы через отрицание, & и.

а) Если f≡ 0, тоf(x₁, ...,x_n) =&.

б) Если f(x₁, ...,x_n)0 тождественно, тогда ее можно представить в виде СДНФ, где используются только связки , &,. СДНФ дает алгоритм представления функции в виде формулы через &,, .

Пример 3.Пусть функцияf(x₁,x₂,x₃) задана таблицей истинности. Запишем ее в виде СДНФ. Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и

(1, 1, 1), поэтому f(x₁,x₂,x₃) =x₁⁰ &x₂¹ &x₃⁰ x₁¹ &x₂⁰ &x₃⁰ x₁¹&x₂¹ &x₃¹=

=&x₂&x₁&&x₁&x₂&x_3.

x1	x2		x3		f
0 0 0 0 1 1 1 1		0 1 1 1 0 0 1 1		0 1 0 1 0 1 0 1		0 0 1 0 1 0 0 1

Следствие 3. Мы умеем представлять функцию в виде . Нельзя ли представить ее в виде . Пусть функция f(x₁, ..., x_n) 1 тождественно. Тогда функция f* 0 тождественно, и ее можно представить в виде СДНФ:

.

По принципу двойственности заменим & на и наоборот, получим

(2)

называется элементарной дизъюнкцией ранга n. Представление функции в виде (2) называетсясовершенной конъюнктивной нормальной формой или в краткой записи –СКНФ. СКНФ дляf(x₁, ...,x_n) – конъюнкция элементарных дизъюнкций рангаn. КНФ дляf(x₁, ...,x_n) – конъюнкция элементарных дизъюнкций, где ранг хотя бы одной элементарной дизъюнкции меньшеn.

Пример 4.Пустьf(x₁,x₂,x₃) =x₁ (x₂(x₃ ~x₁)). Представим ее в виде СКНФ, для этого получим таблицу истинности.

x1	x2	x3	x3~x1	x2 (x3~x1)	f
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	1 0 1 0 0 1 0 1	1 1 1 0 1 1 0 1	1 1 1 1 1 1 0 1

Функция равна нулю только на наборе (1, 1, 0), поэтому

f(x₁x₂x₃)=x₁x₂x₃=x₁⁰x₂⁰x₃¹=x₃.