Алгебра Буля

   

    Функцію будують також за три кроки (див.табл.3):

- ;

- ;

- .

Таблиця 3

    

     Складанні логічного висловлення із простих використовується принцип суперпозиції, тобто підстановка у функцію замість її аргументу інших функцій. Замість будь-якої змінної використовується як власне незалежна змінна, аргумент, так і змінна, що є функцією інших змінних. Також цей принцип є правильним у звичайній алгебрі дійсних чисел. За допомогою принципу суперпозиції з двомісних мулевих функцій можна побудувати будь-яку булеву функцію.

     Принцип суперпозиції дає можливість  на основі трьох основних елементарних  функцій (заперечення, кон’юнкція, диз’юнкція) отримати складене логічне висловлення, яке описує функціонування цифрових систем і автоматів. Покажемо це стосовно операцій кон’юнкції, диз’юнкції та інверсії.

     Якщо і - формули, то , , , , - також формули.

     При перетворенні формул використовують  такі операції підстановки змінних  і без повторної підстановки  функцій:

- операцію підстановки змінних

,

яка дає  змогу виконати підстановку змінних у функцію ƒ( ) і в результаті отримати функцію . Очевидно, підстановка змінних включає їх перейменування, перестановку і ототожнення;

- операцію  без повторної підстановки функцій, що дає змогу будувати вирази , де - або формула, або змінна з , причому хоча б одне з A відмінне від змінної, а множини змінних, які входять в і , не перетинаються .

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

     1.5. Рівносильність формул

     Формули і називаються рівносильними, якщо при будь-яких значеннях змінних , які входять у ці формули, вони набувають однакових значень.

     Приклади.

- рівносильне ;

- рівносильне ;

- рівносильне ;

- рівносильне .

     Між поняттями еквівалентності  і рівносильності існує зв’язок: якщо формули і - рівносильні, то формула (еквівалентність) набуває значення істини при всіх значеннях змінних, і навпаки: якщо формула отримує значення істини при всіх значеннях змінних, то формули і - рівносильні.

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

     Приклади важливих рівносильних формул:

- рівносильне ;

- рівносильне ;

- рівносильне ;

- рівносильне ;

- рівносильне ;

- рівносильне ;

- рівносильне . 
 
 
 
 
 
 
 
 

Розділ II. Алгебра Буля

     2.1. Закони алгебри Буля

     Булевою алгеброю називається алгебра , якщо складається з:

• двох бінарних операцій – (або) і (і);
• однієї унарної операції – (заперечення);
• двох унарних операцій – 0(нуль) і 1(одиниця),

і для виконується така сукупність співвідношень :

-  - комутативність;

- - асоціативність;

- - дистрибутивність;

- - закони для нуля, одиниці і заперечення.

Закони асоціативності:

Закони комутативності:

Дистрибутивний  закон для кон’юнкції відносно диз’юнкції:

Дистрибутивний  закон для  диз’юнкції відносно кон’юнкції:

.

Закон подвійного заперечення:

= .

Закони  де Моргана:

Закони  ідемпотентності:

Закони  поглинання:

Співвідношення  для констант:

Закон виключеного третього:

Закон протиріччя:

  

     2.2. Диз’юнктивні нормальні форми

     Спеціальними формами зображення булевих функцій в алгебрі Буля є диз’юнктивні нормальні форми і кон’юнктивні нормальні форми.

     Введемо позначення  - параметр, який дорівнює 0 або1. Очевидно, що

     Зазначимо, що

     Закріпимо множину змінних .

     Елементарна кон’юнкція – це формула ,де змінні з множини Х, причому всі різні. Число r називають рангом кон’юнкції. У випадку r=0 кон’юнкцію називають порожньою і покладають рівною 0.

     Приклад. Елементарними кон’юнкціями  є 1, а формули 0, елементарними кон’юнкціями не є.

     Елементарну кон’юнкцію, яка містить усі змінні з множини Х, називають конституентою одиниці. Тобто, конституента одиниці – це елементарна кон’юнкція рангу n. Легко побачити, що всіх різних конституент одиниці для фіксованої множини n змінних є стільки, скільки є двійкових наборів з n компонентами, тобто .

     Диз’юнктивна нормальна форма (ДНФ) – диз’юнкція елементарних кон’юнкцій , у яких попарно різні.

    Існує алгоритм, який дає можливість для будь-якої формули булевої алгебри тотожними перетвореннями знайти рівносильну їй диз’юнктивну нормальну форму.

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

     На другому етапі досягають, щоб усі кон’юнкції виконувались раніше диз’юнкцій, для цього розкривають дужки на основі дистрибутивного закону для кон’юнкції відносно диз’юнкції. Потім, на основі співвідношень для констант і закону протиріччя виключають нулі і, на основі законів ідемпотентності, об’єднують рівні члени. Цим процес побудови диз’юнктивної нормальної форми закінчують.

     Приклад. Зведемо  до диз’юнктивної нормальної форми.

Використовуючи  алгоритм побудови диз’юнктивної нормальної форми, можемо записати

      

  .

     Досконала диз’юнктивна нормальна форма – це диз’юнктивна нормальна форма, у якої кожна елементарна кон’юнкція є конституентою одиниці.

     Теорема. Будь-яку булеву функцію  ƒ( ) можна єдиним способом зобразити в досконалій диз’юнктивній нормальній формі.

     Доведення. Нехай задано деяку функцію ƒ( ) . Кожному двійковому набору =( ,…, ) значень змінних відповідає єдина конституента одиниці,яка перетворюється на цьому наборі в 1 і визначена так: . Усі інші конституанти одиниці на цьому наборі перетворюються в 0. Наприклад, набору 0101 відповідає конституанта .

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

ƒ(

)= .

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

ƒ(

)= .

     Для доведення єдності ДДНФ  знайдемо кількість ДДНФ від  n змінних . Для цього будь-яким способом занумеруємо конституанти одиниці, їх . Кожній ДДНФ від змінних можна таким взаємно однозначним способом поставити у відповідність набір із нулів і одиниць. Компоненти з номерами конституант одиниці, які входять у ДДНФ, дорівнюють одиниці, а решта компонент – нулю. Нульовий набір при цьому не отримаємо, тому що він відповідав би порожній ДДНФ. Отже, різних ДДНФ буде стільки, скільки існує наборів довжини , відмінних від набору із самих лише нулів, тобто 2 . Функцій (за виключенням тотожного нуля) від змінних також є 2 . Кожну із цих функцій можна зобразити ДДНФ, отже, це зображення єдине.

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