Булеви функции. Теорема на Пост-Яблонски за пълнота


Категория на документа: Информатика


Дефинираме двоична функция f (x, ) = x по следния начин:
x = x, ако  = 1 и x = , ако  = 0.

Лема: 0 = , 1 = .

Формули от вида , където при j  s, j  { 0, 1}, наричаме елементарни конюнкции.

Теорема (Бул): Множеството { x  y, xy, } е пълно.
Доказателство: Ако f =, можем да представим f = x и тогава
f  [{ x  y, xy, } ].
Нека f . Тогава f (x1, x2, …, xn) = , което е формула над { x  y, xy, }.

В означенията на доказателството, когато f , формулата се нарича съвършена дизюнктивна нормална форма на f.

Теорема: Нека F  F2 е пълно множество, G  F2 и за всяка функция f  F имаме f  [G]. Тогава G е пълно множество.

Следствие: { xy, } е пълно, { x  y, } е пълно,
{ , , xy, x  y } е пълно.
Доказателство: От теоремата на Бул и законите на Де Морган , и от = x  .

Да се спрем на последното пълно множество от следствието.
Нека f  F2. Тогава f има формула над { , , xy, x  y }. Разкриваме скобите във формулата, като прилагаме дистрибутивния закон на конюнкцията спрямо събирането по модул 2, използваме идемпотентността на умножението (xx = x) и факта, че f  f = . Накрая получаваме многократна сума по
модул 2 от елементарни конюнкции без отрицания, като една елементарна конюнкция участва най-много веднъж. При това, от аналогията на конюнкцията с умножението по модул 2, получената формула може да разглеждаме като полином над полето GF (2) (полето с два елемента). Наричаме я полином на Жегалкин.

Теорема: Всяка булева функция има и то единствен полином на Жегалкин.
Доказателство: Всяка функция има полином, различните функции имат различни полиноми и броят на полиномите е = |F2n|.

Казваме, че множеството F  F2 е затворено, ако [F] = F.
Например F2 е затворено, тъй като [F2] = F2.
Множествата {}, {}, { x, } също са затворени.

Теорема (критерий за затвореност): Нека F  F2 е такова, че
1. f (x) = x  F;
2. за всяка функция f (x1, …, xn)  F и g1, …, gn  F имаме
h = f (g1, …, gn)  F.
Тогава F е затворено множество.

Kазваме, че функцията f (x1, …, xn)  F2 запазва нулата, ако
f (0, …, 0) = 0. Kазваме, че функцията f (x1, …, xn)  F2 запазва единицата, ако f (1, …, 1) = 1.

Oзначаваме с T0 множеството от всички булеви функции, които запазват нулата. Tези от тях които са на n променливи
означаваме с T0n. Oзначаваме с T1 множеството от всички булеви функции, които запазват единицата и с T1n тези от тях, които са на n променливи.
Например xy  T0, x  y  T0, xy  T1, x  y  T1, x  T0, x  T1,

 T0,  T1, x  y  T0, x  y  T1.
Така T0  F2 и T1  F2.
Очевидно, |T0n| = = |T1n|, тъй като всяка функция запазваща коя да е от константите се дефинира по произволен начин върху всички вектори освен един.

Теорема: Множествата T0 и T1 са затворени множества от булеви функции.
Доказателство: Директно от критерия за затвореност.




Сподели линка с приятел:





Яндекс.Метрика
Булеви функции. Теорема на Пост-Яблонски за пълнота 9 out of 10 based on 2 ratings. 2 user reviews.