41.Закони булевої алгебри

Булава алгебра – це алгебраїчна структура (А,,+, -,0,1) з бінарними операціями ,А: А²А, унарною операцією “ ”: АА і виділеними елементами 0, 1 в носії А, які задовольняють властивості: 1)комутативність: XvY =YvX, XY=YX; 2)асоціативність: Xv(YvZ)=(XvY)vZ, (X^Y)^Z=X^(Y^Z), 3)дистрибутивність: Xv(Y^Z)=(XvY)^(XvZ), X^(YvZ)=(X^Y)v(X^Z) 4) ідемпотентність кон’юнкції та диз’юнкції: XvX=X, X^X=X 5)закон виключення третього: Xv ¬X=1; 6)закон протиріччя: X^¬X=0; 7) дії з константами: Xv0 =X, Xv1=1, X^0=0, X^1=X 8) закон елімінації: X^(XvY)=X, Xv(X^Y)=X 9)подвійне заперечення: ¬ ¬ Х=Х 10)закон де Моргана: ¬(XvY)= ¬X^ ¬Y, ¬(X^Y)= ¬Xv ¬Y 11) X  Y = ¬Xv Y 12) X xor Y = X·¬Y v ¬X·Y 13) X~Y=X·Yv¬X·¬Y. Це набір незалежних властивостей, які можна вважати аксіомами або незалежними законами булевої алгебри.

42.Поняття двоїстої та самодвоїстої функцій

Функція, двоїста сама собі, тобто f=f^k, називається самодвоїстою. Функція f*(x₁,x₂…,x_n) називається двоїстою до функції f(x₁,…,x_n), якщо f*(x₁,…,x₂)=f(¬x₁,…, ¬x_n). Відношення двоїстості між функціями симетрично. Із визначення двоїстості маємо, що для будь – якої функції двоїста їй визначається однозначно. Функція, яка двоїста сама собі, назив. самодвоїстою.

43. Правило розкладаня булевої ф-ї за всіма або декількома змінними.

Серед множин еквівалентних формул, що зображують булеву функцію f виділяється одна формула, досконала нормальна форма(ДНФ).

ДНФ має регламентовану логічну структуру, а її побудову заснована на рекурентному застосуванні теорем спец.розкладання Булевих функцій про змінні.

Будь-яку булеву функцію f(x1,x2..xN)

Можна зобразити у такій формі

=багатократна диз’юнкція, яка береться за всіма можливими наборами значень для будь-якого к-кількість змін.

44.Поняття досконалої диз’юнктивної нормальної форми (дднф) та досконалої кон’юнктивної нормальної форми (дкнф).

Досконалою диз’юнктивною нормальною формою (ДДНФ) називається формула, що зображена у вигляді диз’юнкції елементарних кон’юнкцій даної функції. Досконалою кон’юнктивною нормальною формою (ДКНФ) функції називається формула, що зображена у вигляді кон’юнкції конституент нуля (макстермів) даної функції. Елементарною диз’юнкцією, що містить нуль змінних, будемо вважати константу 0.

45.Алгоритм переходу від таблиці істинності до дднф.

1.Виключити константи, використовуючи закони дій з константами;

2.Опустити закони заперечення безпосередньо на змінні, використовуючи закони де Моргана;

3.Використовуючи дистрибутивний закон, розкрити дужки;

4.Побудувати конституанти одиниці функції введенням у кожну елементарну кон’юнкцію відсутніх змінних, використовуючи закон виключення третього;

5.За допомогою дистрибутивного закону розкрити дужки і звести подібні, використовуючи закон ідемпотентності. Одержана формула відповідає ДДНФ функції.

Алгоритм переходу від довільної формули алгебри логіки до ДКНФ.

1.Виключити константи, використовуючи закони дій з константами

2.Опустити знаки заперечення безпосередньо на змінні, використовуючи закони де Моргана.

3.За допомогою використання дистрибутивного закону, звести функцію до виду кон’юнкції елементарних диз’юнкцій. До одержаних елементарних диз’юнкцій застосувати закони ідемпотентності й виключення третього, спростити їх і звести подібні.

4.Побудувати конституанти нуля функції введенням у кожну елементарну диз’юнкцію відсутніх змінних, використовуючи закон протиріччя.

5.Зо допомогою дистрибутивного закону звести функцію до виду кон’юнкції конституант нуля і спрстити формулу, використовуючи закон ідемпотентності. Одержана формула є ДКНФ функції.