Теоретичні положення

1.Основи булевоъ алгебри.Математичний апарат, що описує роботу дискретних пристроїв, базується на алгебрі логiки, або булевiй алгебрі (Джордж Буль, 1815-1864 р., англiйський математик). Булева алгебра оперує двiйковими змiнними, якi умовно позначаються 0I 1.В її основi лежить поняття булевої функцiї, функцiї виду f(x1,x2,...,xn)стосовно арґументiв x1,x2,...,xn, яка, як i її арґументи, може набувати тiльки два значення - 0i 1. Логiчна функцiя може бути задана алгебраїчним виразом або таблицею, яка називається таблицею iстинностi.

Дiї над двiйковими змiнними вiдбуваються за правилами виконання логiчних операцiй. Найпростiших логiчних операцiй є три: заперечення (або iнверсiя, або операцiя НІ), логiчне множення (або кон'юнкцiя, або операцiя I) та логiчне додавання (або диз'юнкцiя, або операцiя АБО). Cкладнiші логiчнi перетворення можна звести до вказаних операцiй.

Операцiя заперечення виконується над однiєю змiнною та характеризується такими властивостями: функцiя y=1, якщо арґумент x=0, i y=0, якщо x=1. Заперечення позначається рискою над змiнною, з якою проводиться операцiя: y = x . Вiдповiдноy = x. Операцiя логiчного множення (кон'юнкцiя) для двох змiнних описана у табл.1.1 та позначається y = x1•x2. Нульове значення одного з арґументiв забезпечує нульовий результат операцiї.

Операцiя логiчного додавання (диз'юнкція) для двох змiнних описана табл.1.2 та позначається y = x1+x2. Рiвнiсть хоча б одного арґумента логiчнiй одиницi визначає одиничне значення всiєї функцiї.

Диз'юнкцiя та кон'юнкцiя може здiйснюватися з багатьма змiнними. Сукупнiсть рiзних значень змiнних називається набором. Булева функцiя nарґументiв може мати до N=2nнаборiв. Оскiльки функцiя набуває тiльки два значення, то

загальне число булевих функцiй nарґументiв дорiвнює

2^N= 2²ⁿ. Два арґументи дають 16 значень функцiї (табл.1.3). Закони булeвої алгебри випливають з аксiом та мають двi форми вираження: (табл. 1.2.(а))

КНФ - кон'юнктивна нормальна форма та ДНФ - диз'юнктивна нормальна форма[3].