Лекции по дискретной математике

Соответствие элементарных функций f 0, 1, x, x , x1& x2 , x1 x2

f* 1, 0, x, x , x1 x2 , x1& x2

Из определения двойственности следует, что

γ** = (γ* )* = γ

Теорема || Пусть

Φ(x1,..., xn ) = γ(γ1(x11,..., x1p1 ),..., γm (xm1,..., xm pm ))

Тогда

Φ*(x1,..., xn ) = γ*(γ1*(x11,..., x1p1 ),..., γ*m (xm1,..., xm pm ))

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

Φ*(x1,..., xn ) = Φ(x1,..., xn ) = f (f1(x11,..., x1p1 ),...,fm (xm1,..., xm pm )) =

=f (f1(x11,..., x1p1 ),...,f m (xm1,..., xm pm )) =

=f (f1*(x11,..., x1p1 ),...,f *m (xm1,..., xm pm )) =

=f *(f1*(x11,..., x1p1 ),...,fm* (xm1,..., xm pm ))

Отсюда вытекает принцип двойственности: двойственной к формуле U = C(f1,..., fn ) является формула U* = C(f1*,..., fn* ).

Пусть формула содержит только символы &, , ¬. Тогда для получения U* из U нужно заменить:

0 1 &

b b b b

1 0 &

Из принципа двойственности вытекает, что

U(x1 ,..., xn ) = B(x1 ,..., xn )

U* (x1 ,..., xn ) = B* (x1 ,..., xn )

Вчастности,

x1 & x2 = x1 x2

c .

x1 x2 = x1 & x2

Лекция №15

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

Возникают вопросы:

1)всякая ли функция может быть записана с помощью формулы?

2)как это сделать?

Совершенная дизъюнктивная нормальная форма.

Обозначим xδ = xδ + xδ, где δ равен либо 0, либо 1. Тогда

xδ = x, δ = 0 .x , δ =1

Поскольку

αα = αα + α α = α + α =1

,

αα = αα + αα = 0

то xδ=1 x=δ.

Теорема о разложении функции по переменным || Каждую функцию Булевой алгебры f (x1,..., xn ) при любом m (1 ≤ m ≤ n) можно

представить в следующей форме: f (x1,..., xm , xm+1,..., xn ) =

где дизъюнкция берется по всем наборам значений переменных x1 ,..., x n . ||

опр || Это представление называется разложением функции по m переменным x1,…xm.||

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

1) Рассмотрим произвольный набор значений (α1,..., αn ) . Левая часть равенства имеет вид f (α1,..., αn ) . Правая часть

(в сумме только одно произведение отлично от нуля: то в котором δj = αj )

= f (α1,...,αm ,αm+1,...,αn ) .

Теорема доказана.

Разложение по одной переменной

1) f (x1,..., xn −1, xn ) = xn & f (x1,..., xn −1,1) xn & f (x1,..., xn −1,0)

Разложение по всем n переменным

Опр. Это разложение называется совершенной дизъюнктивной нормальной формой.

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

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

γ(x1, x2 , x3) = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 = = x1x2 (x3 + x3) + x1x3(x2 + x2 ) = x1x2 + x1x3

f (x1, x2 , x3) = (x1 + x2 ) → x3 = x1x2 + x3 = x1x2 (x3 + x3) + x3(x1 + x1) = = x1x2x3 + x1x2 x3 + x1x2x3 + x1x2x3 + x1x2x3 =

~

γ(x4 ) = (0100100011000010)

x1x2 x3x4 + x1x2 x3 x4 + x1x2 x3 x4 + x1x2 x3x4 + x1x2x3 x4

f = (x1 + x2 )(x1 + x2 ) = x1x2 + x1x2 + x1x2 + x2x2 = x1x2 + x1x2

~

~

γ(x3 ) = (x1 + x2 + x3 )(x1 + x2 + x3 ) =

= x1x1x3 + x2 x1x2 + x3 x3 + x1x3 + x2 x3 + x3 x1x2 = = x1x3 (x2 + x2 ) + x2 x3 (x1 + x1 ) + x3 x1x2 =

= x1x2 x3 + x1 x2 x3 + x1 x2 x3 + x1x2 x3

~

γ(x3 ) = (x1 + x2 x3 )(x1 x2 + x3 )(x1x 2 + x3 ) =

= (x1 x2 + x2 x3 x1 x2 + x1x3 + x2 x3 x3 )(x1 + x2 + x3 ) =

= x1 x2 + x1 x2 x3 + x1 x2 x3 + x1x3 = x1 x2 (x3 + x3 ) + x1 x2 x3 + x1x3 (x2 + x2 ) = = x1 x2 x3 + x1 x2 x3 + x1x2 x3 = x1 x2 x3 + x1 x 2 x3 + x1x2 x3

~

γ(x4 ) = (x1 → x4 )(x2 → x3 )(x3 → x1 x4 ) =

= (x1 + x2 )(x2 + x3 )(x3 + x1 x4 ) = x1 x2 x3 + x2 x3 + x1x2 x4 + x1x2 x3 x4 = = x1 x2 x3 (x4 + x4 ) + x2 x3 (x1 + x1 )(x4 + x4 ) + x1x2 x3 x4 = x1 x2 x3 x4 + + x1 x2 x3 x4 + x1x2 x3 x4 + x1x2 x3 ......

Лекция № 9 (11.04.00)

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

Опр || система функций {f1,f2 ,...,fn } из P2 (множества всех булевых

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

Пример: 1) Само множество P2 ;

2)B ={x1, x1 & x2 , x1 x2};

3)B ={0,1} - не полна.

Теорема || Пусть даны две системы функций из P2

B={f1,f2 ,...}, (I)

C={g1 ,g2 ,...}. (II)

Известно, что система I полная и каждая функция системы I выражается через функции системы II. Тогда система II является полной.

Доказательство || Пусть h P2 . В силу полноты сист. I функцию h можно выразить в виде формулы h = C[f1,f2 ,....]. По условию теоремы

f1 = C1[g1,g2 ,...]

f2 = C2[g1,g2 ,...]

.........................

Поэтому

h = C[C1[g1,g2 ,...],C2[g1,g2 ,...],...] = C′[g1,g2 ,...] ч. и т.д.

Примеры ||

1) B0 ={x1 , x1 & x2 , x1 x2 } - полная.

2) B1 ={x1 , x1 & x2 } - тоже полная, так как x1 x2 = x1 & x2 .

3)B2 ={x1 , x1 x2 } - тоже полная.

4)B3 ={x1 | x 2 } - тоже полная, так как

x | y = x & y = x y , x | x = x & x = x ,

(x1 | x2 ) | (x1 | x2 ) = x1 | x2 = x1 x2 = x1 & x2 .

(3) – I)

5) B ={0,1, x1 x2 , x1 x2} x = x 1

x1x 2 = x1 & x 2 тогда взяв в качестве сист. I сист. 2 можно заключить, сист. функций 5) – полная. Тем самым, справедлива

Теорема Жегалкина || Каждая функция из P2 может быть выражена при помощи полинома по модулю 2 – (полинома Жегалкина):

Имеем: число разных сочетаний xi1 ,..., xis равно числу подмн-в мн-ва из n элементов. Каждое aik может принимать одно из 2-х значений {0,1}.

Тогда число разных пол. Жег. равно 22n , т.е. равно числу различных булевых функций.

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

Жег.

Примеры

x1 x 2 = a x1x 2 b x1 c x 2 d x1 = 0, x2 = 0 0 = d,

x1 = 0, x2 =1 1 = c, x1 =1, x2 = 0 1 = b,

x1 =1, x2 =1 1 = a b c a =1,

Следовательно,

x1 x2 = x1x2 x1 x 2

Пока опустим

2 способ T-преобразов. вектора функции

T(α0 ,α1 ) = (α0 ,α0 α1 )

T(γ0 ) = (0,0 0) = (0,0)

T(γ1 ) = (0,0 1) = (0,1)

T(γ2 ) = (0,1)

T(γ3 ) = (1,1 1) = (1,0)

T(γ0 , γ1 ) = T(T(γ0 ),T(γ0 ) T(γ1 )) = ((0,0),(0,0) (0,1)) = (0,0,0,1) T(γ2 , γ3 ) = T(T(γ2 ),T(γ2 ) T(γ3 )) = ((0,1),(0,1) (1,0)) = (0,1,1,1)

T(γ0 , γ1 , γ2 , γ3 ) = Tγ0 γ1 ,T(γ1 , γ1 ) + T(γ2 , γ3 ) = (0,0,0,1),(0,0,0,1) (0,1,1,1) =

~

= (0,0,0,1,0,1,1,0) = B

~

γ(x) = 0 K0 0 K1 0K2 1 K3 0K4 1 K5 1 K6 0K7 =

= 0 1 0 x3 0 x3 1 x2 x3 0x1 1 x1x3 1 x1x2 0 x1x2 x3 = = x1x3 x1x3 x1x2

3 способ – алгебраических преобразований x = x 1

f (x, y) = x → y = x y = xy = x(y 1) 1 = xy x 1

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

Замечание. Замыкание инвариантно относ. операций введения и удаления фиктивных перем.

Примеры.

1)M=P2, [M]=P2.

2)M={1,x1 x2}, [M] – мн-во L всех линейных ф-й вида

(x1,..., xn )= c0 c1x1 ... cn xn , (ci=0,1).f

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

1)[M]=M;

2)[[M]]=[M];

3)M1 M2 [M1] [M2];

4)[M1 M2] [M1] [M1].

Опр. Класс (мн-во) M называется (функционально) замкнутым, если

[M]=M.

Примеры.

1)Класс M=P2 функционально замкнут;

2)Класс {1,x1 x2} не замкнут;

3)Класс L замкнут (линейное выражение, составленное из линейных выражений линейно).

Новое определение полноты. M – полная система, если [M]=P2.