dm_tema_3

С помощью законов алгебры логики можно выполнять преобразования булевых функций.

Пример Рассмотрим булеву функцию f (x; y) = x _ y _ x. Применяя законы де

Моргана, дистрибутивности, исключенного третьего, коммутативности, получим

f (x; y) = (x ^ y) _ x = (x _ x) ^ (y _ x) = 1 ^ (x _ y) = x _ y:

3. Алгебра логики 3.3 Классы булевых функций

3.3 Классы булевых функций

Все множество булевых функций f (x1; : : : ; xn) обозначим через P2. Число переменных может быть любым.

Определение Суперпозицией двух булевых функций

f (x1; : : : ; xk ; : : : ; xn); g(y1; : : : ; ym)

называется булева функция

f (x1; : : : ; xk 1; g(y1; : : : ; ym); xk ; : : : ; xn):

Пример

Пусть f (x1; x2) = x1 ^ x2, g(x1; x2) = x1 x2. Тогда

f (g(x1; x2); x2) = (x1 x2) ^ x2; g(f (x1; x2); x2) = (x1 ^ x2) x2:

Определение

Замыканием множества булевых функций F P2 называется множество [F ] всех булевых функций, получаемых из F с помощью операции суперпозиции.

Определение

Множество булевых функций F называется замкнутым, если [F ] = F .

Определение Система булевых функций

F = ff1; : : : ; fmg

называется функционально полной, если [F ] = P2.

Следующие классы булевых функций будем называть основными.

Определение

Булева функция f сохраняет константу 0, если

f (0; : : : ; 0) = 0:

Класс булевых функций, сохраняющих константу 0, обозначим через

K0.

Определение

Булева функция f сохраняет константу 1, если

f (1; : : : ; 1) = 1:

Класс булевых функций, сохраняющих константу 1, обозначим через

K1.

Определение

Функция f (x1; : : : ; xn) называется двойственной к функции f и обозначается f .

Пример Двойственной для конъюнкции является дизъюнкция

x1 ^ x2 = x1 _ x2:

Определение

Булева функция f называется самодвойственной, если f = f . Класс самодвойственных функций обозначим через S.

Определение

Булева функция f называется линейной, если она может быть записана в следующем виде

f (x1; : : : ; xn) = c0 c1x1 c2x2 cnxn;

ãäå ci 2 f0; 1g. Множество всех линейных функций обозначим через L.

Пример Эквивалентность является линейной функцией

x1 x2 = 1 x1 x2:

Пусть x = (x1; : : : ; xn), y = (y1; : : : ; yn) два булевых вектора длины n. Будем говорить, что x y, åñëè xi yi , i = 1; : : : ; n. В противном случае x è y несравнимы.

Определение

Булева функция f называется монотонной, если для любых x y выполняется неравенство f (x) f (y). Множество всех монотонных функций обозначим через M.

Теорема

Классы булевых функций K0, K1, S, L, M и все множество булевых функций P2 замкнуты.

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

Докажем [S] = S. Пусть f ; g 2 S. Тогда

f(x1; : : : ; g(y1; : : : ; ym); : : : ; xn) =

f(x1; : : : ; g(y1; : : : ; ym); : : : ; xn) =

f(x1; : : : ; g(y1; : : : ; ym); : : : ; xn):

Теорема (теорема Поста)

Система булевых функций F является функционально полной тогда и только тогда, когда для любого класса K 2 fK0; K1; S; L; Mg найдется функция f 2 F такая, что f 2= K .

Таблица принадлежности булевых функций классам K0, K1, S, L, M

Из таблицы видно, что системы булевых функций: fx; x1 ^ x2g, fx; x1 _ x2g являются функционально полными.

3. Алгебра логики 3.4 Нормальные формы булевых функций

3.4 Нормальные формы булевых функций

Рассмотрим множество булевых функций n переменных x1; : : : ; xn. Обозначим: xi ^ xj = xi xj , xi1 = xi , xi0 = xi . Под литералом будем понимать xi èëè xi .

Определение Элементарной конъюнкцией называется конъюнкция литералов

x1 1 : : : xmm ; m n;

ãäå i 2 f0; 1g.

Элементарная конъюнкция равна 1 только на наборе значений аргументов x1 = 1; : : : ; xm = m.