Diskretnaya_matematika_1_semestr

Класс s.

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

fSf=f*

ЄS	x,¬x
∉S	→,│,↓,1,0,≡,⨁,&,∪

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

α=(α1,α2,…,αn) ¬α=(¬α1,¬α2,…,¬αn)

На противоположных наборах самодвойственная функция принимает противоположные значения. То есть, в общем случае:f(x1,x2,...,xn)=f(x1,x2,...xn), поэтому для задания самодвойственной функции от n переменных достаточно (2^n)/2 или(2^n-1) наборов. Тогда числа самодвойственных ф-ций =2^2^(n-1).

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

f0,f1,…fkЄS

ФЄS-?

Ф*(y1,…,yn)=f0*(f1*(x11,…,x1i,…),…,fk*(xk1,…,xkik))=f0*(f1(x1,…,x1i1),fk(xk1,…,xkik))=f0(f1(x11,…,x1i,..),…,fk(xk1,…,xkik))=Ø

Лемма о несамодвойственнs[ функции. Если функция (f∉S) несамодвойственна, то из нее путем подстановки вместо переменных тождественных функций и отрицания, можно получить константу.

Доказательство. Пусть f≠f*. Тогда найдутся два противоположных набора: (α1,α2,…,αn) и (¬α1,¬α2,…,¬αn), на которых ф-ция принимает одинаковые значения: f(α1,α2,…,αn)=¬f(¬α1,¬α2,…,¬αn).

По набору (α1,α2,…,αn) и ф-ции а построим ф-цию φ по одной переменной: φ(х)=f(x^α1, x^α2,…,x^αn)

Она получена в результате подстановки вместо переменных ф-ции x^αi. В зависимости от значения αi подставляется тождественная ф-ция или отрицание.

П окажем, что φ-константа.φ(0)=f(0^α1,0^α2,…,0^αn)=f(¬α1,¬α2,…,¬αn)=0^α=

1,α=0 = f(α1,α2,..,αn)=f(1^α1,1^α2,…,1^αn)=φ (1)

0,α=1 =¬α;

1 ^α= 1, α=1

0, α=0 =α

Что и требовалось доказать.

Содержание