. Цю ф-цію часто називають логічним перетворенням або логічним множенням;
f8 (x1,x2) =x1 х2 - функція Вебба (стрілка Пірса);f9 (x1,x2) =x1~х2 - еквівалентність;
f13 (x1,x2) =x1 х2 - імплікація;
f14 (x1,x2) =x1/x2 - штрих Шеффера;
f15 (x1,x2) =1 - тотожна одиниця (константа 1);
Розглянуті простіші булеві ф-ції дозволяють будувати нові булеви ф-ції з допомогою узагальненої операції, що називається операцією суперпозиції. Фактично операція суперпозиції заключається в тому, що існує підстановка замість аргументів інших булевих функцій (в деякій мірі аргументів).
Зауважимо, що суперпозиція функцій одного аргументу породжує функції одного аргументу. Суперпозиція ф-цій двох аргументів дає можливість будувати функції будь-якої кількості аргументів.
Суперпозиція булевих ф-цій представляється у виді логічних формул. Однак слід відмітити:
одна і та ж функція може бути представлена різними формулами;
кожній формулі відповідає своя суперпозиція і своя своя схема з’єднання елементів;
між формулами представлення булевих ф-цій і схемами, які їх реалізують, існує взаємнооднозначна відповідність.
Очевидно, що серед схем, які реалізують дану функцію є найбільш проста. Пошук логічної формули, що відповідає цій схемі, предствляє великий практичний інтерес, а перетворення формул булевих функцій грунтується на використанні співвідношень булевої алгебри.
Для булевої алгебри визначена одна одномісна (унарна) операція, дві двохмісні (бінарні) операції кон’юнкції і диз’юнкції (позначаються відповідно “*", “
”).В цій алгебрі справедливі три аксіоми:
закон комутативності - x
y=y x, x*y=y*x; закон асоціативності - (x y) z=x (y z), (x*y) *z=x* (y*z);закон дистрибутивності - x* (y
z) = x*y x*z, x y*z= (x y) * (x z);Перетворення формул булевих функцій використанням тільки аксіом булевої алгебри малоефективне. Для спрощення формул використовують цілий ряд співвідношень. Приведемо деякі з них.
= * , * = (Теореми де Моргана) (1)x
x*y=x, x* (x y) =x; (2)x
x=x, x*x=x, =x; (3)x
y =x y; (4)x
=1, x* =0; (5)x
1=1; x*0=0; (6)xy
x =x, (x y) (x ) =x; (7)В ряді випадків, перетворення над формулами булевих функцій зручно виконувати в алгебрі Жегалкіна. Алгебра Жегалкіна включає дві двохмісні операції: кон’юнкцію і додавання за модулем 2 (*,
), а також константу 1. Тут мають місце ті ж закони:x
y=y x, x*y=y*xx
(y z) = (x y) z, x* (y*z) = (x*y) *zx* (y
z) =x*y x*zДля спрощення формул можуть бути використані такі співвідношення:
x
0=x; x*1=x; x*0=0; x x=0; x*x=x.Із комутативності і асоціативності слідує, що диз’юнкція кількох змінних може виконуватися послідовно, причому порядок взяття дизьюнкції не впливає на результат. Тобто, диз’юнкція сукупності змінних може бути виражена співвідношенням
x1 x2 … xn=
xiАналогічно для кон’юнкції
x1*x2*…*xn=
xiі суми по модулю 2
x1
x2 … xn= Теореми де Моргана для кількох змінних мають вигляд:
= = Вище згадувалося про існування аналітичних форм представлення булевих ф-цій. Тут розглянемо універсальні (канонічні) форми представлення, які дають можливість отримати аналітичну форму безпосередньо по таблиці істиності для довільної булевої ф-ції. Ця форма в дальшому може бути спрощена. Найбільш широке поширення отримала досконала нормальна форма (ДНФ). Перед тим як перейти до вивчення, приведемо визначення конституєнти одиниці - поняття, яким будемо широко користуватися дальше.
Визначення: Конституєнтою одиниці називається функція f (x1, x2, …, xn), яка приймає значення 1 тільки на одному наборі.
Якщо згадати, що диз’юнкція рівна 1, коли хоча б одна з змінних приймає значення 1, то можна легко виразити, будь-яку булеву функцію як диз’юнкцію конституєнт одиниці, які відповідають тим наборам, на яких функція рівна 1. В більш загальному вигляді це можна записати таким чином: