Алгебра Буля

     Приклад. Побудуємо ДДНФ для  функції, заданою так: 

    

     Функція приймає значення 1 на наборах 00 і 11. Отже, .

     Будь-яку ДНФ можна звести до  ДДНФ розщепленням кон’юнкцій, які містять не всі змінні:якщо кон’юнкція не містить змінної , то

.

     Приклад. Перетворимо диз’юнктивну  нормальну форму  у досконалу. Застосувавши розщеплення для кон’юнкції і закон ідемпотентності для диз’юнкції, отримали

.

     Будь- яке тотожне перетворення можна обернути.

     Теорема. Для довільних рівносильних  формул алгебри Буля  і існує еквівалентне перетворення в за допомогою основних законів алгебри Буля.

     Доведення. Перетворимо  і у ДДНФ. Оскільки і рівносильні, то їхні ДДНФ збігаються. Обертаючи друге перетворення, отримаємо ряд перетворень :

  ДДНФ .

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

     2.3. Кон’юнктивні  нормальні форми

     Нехай,як і в попередньому пункті, зафіксуємо множину змінних .

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

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

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

     Приклад. Знайдемо КНФ для формули  .Використовуючи алгоритм, одержимо:

.

     Елементарну диз’юнкцію рангу називають конституентою нуля. Тобто, конституента нуля – це елементарна диз’юнкція, у яку входять всі змінні з множини Х.

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

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

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

( )= .

     Візьмемо тотожність для двоїстих  формул

( )= .

     Ліва частина рівна ƒ( ), а праву перетворюємо далі

= =

     Отже,

ƒ(

)= .

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

     Приклад. Побудувати ДКНФ функції, заданої у такому вигляді: 

 

     Функція приймає значення 0 на наборах 01 та 10. Отже ,

.

     Слід зазначити, що на основі тотожних перетворень будь-яку КНФ можна перетворити у ДКНФ. Якщо в деяку елементарну диз’юнкцію не входить змінна , то потрібно записати рівносильний вираз і скористатись дистрибутивним законом: . Після тривіальних перетворень отримаємо ДКНФ.

     Приклад. Перетворимо КНФ у досконалу КНФ. Використовуючи розщеплення диз’юнкції, можемо записати

     Зазначимо,що ДКНФ єдина. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Висновок 

     Булева функція – це така функція, значення і кожний аргумент якої можуть дорівнювати одному з двох чисел: 0 або 1. Вона тісно пов'язані з логікою. Елементами булевої алгебри множин є не числа, а певні об'єкти, природа яких ігнорується. Істотним при цьому є лише те, що всі елементи алгебри, які називаються множинами, являють собою частини однієї і тієї самої множини.     Спеціальними формами зображення булевих функцій в алгебрі Буля є диз’юнктивні нормальні форми і кон’юнктивні нормальні форми.

     Над елементами булевої алгебри можна виконувати певні операції. Результатом кожної такої операції, що виконується над множинами (елементами алгебри), буде також множина (елемент алгебри). Ця обставина визначає назву булевої алгебри — алгебра множин.

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

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

Література

     1. Нікольський Ю.В. Дискретна математика. − Л.: Магнолія-Плюс, 2006.

     2. Новиков Ф.А. Дискретная математика  для програмистов. – С.Пб.: Питер, 2001.

     3. Бардачов Ю.М. Дискретна математика. – К.: Вища школа, 2002.

     4. Акимов О.Е. Дискретная математика, логика, группи, графи. – М.: Мир, 2001.

     5. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики. – К.: Наукова думка, 2002.

     6. Андерсен Д. Дискретна математика  і комбінаторика. – С.Пб.: Вільямс, 2003.

     7. Яблонский С.В. Введение в дискретную  математику. – М.: Наука, 1986.

      8. http://studentu5.com. 

     10. http://referatu.net.ua/referats/119/6203/?page=0. 

     11. http://ukrkniga.org.ua/ukrkniga-text/books/_book-85.htm. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Додотки 

     I. Історичні аспекти розвитку теорії булевих функцій.

     Алгебра логіки як одна із  складових математичної логіки, що заснована на використанні алгебраїчних методів у логіці, була сформована у працях Дж. Буля, де Моргана, Ст. Джевонса. Саме праці цих науковців вважаються першими дослідженнями, присвяченими саме алгебрі логіки. Де Морган та Дж. Буль будували свої системи не дедуктивно, а відповідно до традицій алгебри свого часу – алгоритмічно: визначали операції, правила їх застосування, прийоми отримання висновків. Пізніше вирішення задач алгебраїчної логіки графічними (метод кіл Ейлера, діаграми Венна, діаграми де Моргана) та механічними (логічна дошка, логічна машина Ст.Джевонса) способами було поштовхом не тільки до подальшого розвитку математичної логіки, а й до ідей виникнення обчислювальних пристроїв, що механізують процеси міркування.

     Систему Дж. Буля його сучасники вважали штучною та довільною. Наприклад, П.Порецький вказував на ту обставину, що Дж. Буль іноді взагалі підганяв логічні операції під арифметичні, не розкриваючи секрет успіху свого методу і не аналізуючи причин використаної ним аналогії. М.Стяжкін вказував на те, що всі, без винятку, представники російської загальної логіки негативно ставились до результатів Дж. Буля. 
     Першим в Україні та й одним з перших у Російській імперії, хто звернув увагу на розвиток логічної думки на Заході, на думку М.Стяжкіна, був Федір Козловський. Саме він на відміну від своїх сучасників позитивно оцінював систему Дж. Буля.

     Зацікавлення новим напрямом у логіці в Російській імперії розпочалось із праць відомого логіка П. Порецького, який у 1880 р., на засіданні секції фізико-математичних наук Казанського університету зробив доповідь “Про основи математичної логіки”, яка за своїм змістом була рефератом роботи німецького математика і логіка Е. Шрьодера, послідовника Дж.Буля. У 1881р. П.Порецький опублікував роботу під назвою “Виклад основних начал математичної логіки в найбільш наочній та загальнодоступній формі”, де автор критично оцінював деякі результати Дж.Буля та Е.Шрьодера. 
     З-поміж численних українських логіків, що працювали у 80 х рр. ХІХ ст. (О.Новицький, П.Ліницький, С.Гогоцький, П.Юркевич та інші), згадку про новий напрям логіки знаходимо лише у М.Грота. У своїй праці “До питання про реформу логіки” (1882) він акцентує увагу на відокремлення математичної логіки від старої метафізичної та пов’язує це з працями де Моргана, Дж.Буля, Ст.Джевонса. Але сам вчений не підтримує поглядів представників школи математичної логіки та пропонує називати булеву логіку математичною, а не логічною теорією.      

Хоча  логічні та математичні символи  відрізняються (в математиці однакові символи означають не тотожні об’єкти, а тільки рівні за величиною; в логіці однакові символи представляють тотожні об’єкти), Дж.Буль зводить дії над логічними символами до математичних дій. Уся система Дж.Буля спрямована на те, щоб вирішити логічну задачу в найбільш загальному вигляді: при заданому числі засновків виключити довільне число термінів і знайти усі можливі логічні відношення між отриманими термінами. “Таким чином, Дж.Буль виходить з вузьких рамок Аристотелевої логіки і розширює логічну задачу до можливих меж. Природно, що ця задача розкладається на дві частини: 1) визначення логічних відношень між термінами одного судження і 2) між термінами якого завгодно числа суджень. Перша частина відповідає безпосереднім умовиводам, друга частина – опосередкованим умовиводам” .

      Порівнюючи системи Дж.Буля та Ст.Джевонса, Ф.Козловський стверджував, що головні основи обох систем однакові: позначення тотожності, синтезу співналежних термінів та поєднання термінів неспівналежних однакове в обох системах; відмінність розкладу функцій у системі Дж.Буля відповідає логічний алфавіт Ст.Джевонса; загальна постановка логічної задачі одна і та сама в обох системах.  
     Однією із головних відмінностей систем Дж.Буля та Ст.Джевонса є погляд на розподільні судження, що виключають один одного. У системі Ст.Джевонса формальний закон логіки не передбачає необхідного взаємовиключення альтернатив та посилання у доведенні на розмовну мову.  
     Отже, можна дійти висновку, якщо систему Дж.Буля розглядати як частковий випадок теорії ймовірності, то система Ст.Джевонса є таким же частковим випадком теорії з’єднання, на якій ґрунтується теорія ймовірності: замість математичних обчислень над числами – нулем та одиницею Ст.Джевонс пропонує підібрати комбінації із термінів, що задовольняють основні закони формальної логіки. Таким чином, основа системи Ст.Джевонса є глибшою, ніж основа системи Дж.Буля, що є головною перевагою символів Ст.Джевонса.