Типи булєвих функцій

Задачі

Визначити всі елементарні ФАЛ, що належать класам P₀ і P₁.

Визначити, чи є задані булєві функції лінійними:

елементарні ФАЛ двох перемінних;

x₁+x₂+x₃;

x₁x₂+x₂x₃+x₁x₃;

(x₁x₂+ùx₁ùx₂)Åx₃;

x₁x₂(x₂Åx₃);

x₁x₂+ùx₂x₃+ùx₃x₄+ùx₄x₁;

(1010, 1010, 0110, 1000);

(1010, 0110, 1001, 0110).

Визначити, які з елементарних ФАЛ є монотонними.

Визначити, які з приведених ФАЛ є монотонними:

xy+xz+ùxz;

x®(x®y);

ù(x+y)~(xÅy);

xy(xÅy);

xyÅyzÅxzÅz;

(00110111);

(0001010101010111).

Довести, що для кожної монотонної ФАЛ, відмінної від конституенти, існують ДНФ і КНФ, не утримуючі заперечень перемінних.

Чи є функція f₂ двоїстою до функції f₁, якщо:

f₁ = xÅy; f₂ = x~y;

f₁ = x®y; f₂ = y®x;

f₁ = xy+xz+yz; f₂ = xyÅxzÅyz;

f₁ = xÅyÅz; f₂ = xÅy+z;

f₁ = ùxùyz+x(y~z); f₂ (x, y, z)= (01101101).

Які з приведених функцій є самодвоїстими?

xy+xz+yz;

(ùx+y+ùz)t+ùxyùz;

(0001001001100111);

x₁Åx₂Å... Åx_2m+1Å b; bÎ{0,1}.

Функціональна повнота

Задачі

Нехай Т - деяка безліч ФАЛ. Обґрунтувати властивості замикання:

[[T]] = [T];

якщо T₁ Í T_2, то [T₁] Í [T₂];

[T₁ ÈT₂] Ê [T₁] È [T₂];

[Æ] = Æ.

Довести чи спростувати:

перетинання ф.з.класів є ф.з.класом;

об'єднання ф.з.класів є ф.з.класом;

різниця ф.з.класів є ф.з.класом;

доповнення ф.з.класу (тобто сукупність функцій, у нього не вхідних) не є ф.з.класом;

сукупність функцій, подвійних функціям з ф.з.класу, утворить ф.з.клас.

Які з зазначених систем ФАЛ є функціонально замкнутими класами?

функції однієї перемінної;

функції двох перемінних;

усі ФАЛ;

монотонно убутні функції;

функції, що зберігають і нуль, і одиницю;

функції, що зберігають нуль, або зберігають одиницю.

Використовуючи критерій функціональної повноти (теорема Поста), з'ясувати повноту наступних систем ФАЛ:

x/y;

x¯y;

ùx, 1;

xy, ùx;

x+y, ùx;

xy, xÅy;

xy+yz+xz, ùx;

xy, x+y;

xÅy, x+y.

Показати неповноту наступних систем ФАЛ і зробити висновки про істотність умов теореми Поста:

0, xy, xÅyÅz;

1, x+y, xÅyÅz;

ùxùy+ùxùz+ùyùz;

0, 1, xÅy;

0, 1, xy.

Довести, що жоден із класів P₀, P₁, L, M, S не міститься в іншому.

Довести, що усякий власний функціонально замкнутий клас міститься в одному з класів P₀, P₁,L, M, S.

Довести, що ф.з.класи P₀, P₁,L, M, S є передповними й інших передповних класів немає.

Довести, що базис не може містити більш чотирьох функцій.

Використовуючи теорему Поста, з'ясувати чи повна система Ф0:

Ф₀ = {(01101001), (10001101), (00011100)};

Ф₀ = (S\M)È(L\(P₀ÈP₁));

Ф₀ = (SÇM)È(L\M)È(P₀\S);

Ф₀ = (M\(P₀ÇP₁))È(L\S).

Виразити всі елементарні ФАЛ через наступні функції, що утворять функціонально повну систему:

стрілку Пірса;

штрих Шеффера;

інверсію, кон’юнкцію;

інверсію, диз'юнкцію;

кон’юнкцію, суму по mod 2, константу 1;

імплікацію, константу 0.