Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгебри логіки
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут прикладної математики та фундаментальних наук
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2006
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Група:
ПМ-32
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет ”Львівська політехніка”
Інститут прикладної математики та фундаментальних наук
кафедра прикладної математики
КУРСОВА РОБОТА
з курсу: „Дискретна метематика”
на тему: „Алгебри логіки”
Анотація
У роботі розглянуто основні властивості булевих функцій. Перевірено виконання законів булевої алгебри для двохелементної алгебраїчної структури . Розглянуто основні закони алгебри Жегалкіна, Шеффера та Пірса.
У середовищі програмування С++ реалізується перевід логічних виразів у кожну розглянуту алгебру логіки. Текст програми містить додаток.
Зміст
Вступ
Розділ 1. Булеві змінні і функції
1.1. Двійкові інтерпретації, істотні та фіктивні змінні
1.2. Способи задання булевих функцій
1.2.1. Таблиці істинності
1.2.2. Номери булевих функцій і інтерпретацій
1.2.3. Булеві алгебри: загальна, двохелементна і логічна
1.2.4. Булеві формули і пріоритет операцій
1.2.5 Перехід від формули до таблиці істиності
Розділ 2. Алгебри логіки
2.1. Алгебра Буля
2.2. Алгебра Жегалкіна
2.2.1. Тотожності алгебри Жегалкіна
2.2.2. Поліном Жегалкіна
2.3. Алгебра Шеффера
2.4. Алгебра Пірса
Висновок
Список використаної літератури
Вступ
В історії логіки виділяють два етапи:
1. Від логіки Давнього світу до виникнення у другій половині XIX ст. сучасної логіки.
2. Від другої половини XIX ст. до наших днів.
На першому етапі логіка переважно вирішувала проблеми, поставлені ще Арістотелем. В останні півтора століття в ній відбулись якісні зміни. Щоправда, передумови цих змін з'явилися ще тоді, коли Лейбніц запропонував ідею числення і відповідну формалізовану мову. Цю ідею, як зазначалось, сучасники не зрозуміли і зрештою забули. Проте в другій половині XIX ст., а тим більше в XX ст. на людство чекала ціла злива ідей, завдяки яким сучасна логіка перейшла наукову революцію. Назвемо лише деяких видатних учених, які зробили істотний внесок у її розвиток.
Джордж Буль (1815—1864) — один із засновників математичної логіки. Поклавши в основу своїх досліджень аналогію між алгеброю і логікою, він розробив відповідне логічне числення, в якому застосував закони й операції математики (додавання класів, множення тощо). Алгебро-логічний метод дав можливість Булю виявити нові типи висновків, які не враховувались у традиційній силогістиці. Він детально проаналізував закони комутативності, асоціативності, дистрибутивності .
Огастес де Морган (1806—1871) — засновник логічного аналізу відношень. Він сформулював основні принципи логіки висловлювань і логіки класів. У розробленій ним алгебрі відношень аналізував операції додавання, множення тощо. У математичній логіці Морган сформулював закони, які носять його ім'я — «закони де Моргана».
Готліб Фреге (1848—1925) заклав основи логічної семантики. У своїй фундаментальній праці «Основні закони арифметики» він побудував систему формалізованої арифметики на основі розробленого ним розширеного числення предикатів з метою обґрунтування ідеї про зведення математики до логіки. Ідеї Фреге багато в чому наперед визначили розвиток логіки XX ст.: він увів поняття логічної функції й розрізнення властивостей речей і відношень (а відповідно одномісних і багатомісних логічних функцій); вперше увів символи для позначення кванторів; увів поняття істиннісного значення тощо. Фреге систематично досліджував відношення між мовними виразами і предметами, які позначаються цими виразами; розкрив відмінність між значенням і смислом мовних виразів. Його праці розцінюються як початок нового етапу в розвитку математичної (символічної) логіки.
Чарлз-Самдерс Пірс (1839—1914) — родоначальник семіотики (загальної теорії знаків). У своєму численні він використовував як строгу, так і нестрогу диз'юнкції. Пірс сформулював закони матеріальної імплікації. Тривалий час його праці не були відомі широкій науковій громадськості.
Давид Гільберт (1862—1943) досяг значних успіхів у застосуванні методу формалізації в тлумаченні логічних умовиводів, у розробці числення висловлювань і предикатів, у дослідженні аксіоматизації знань. Він здійснив строго аксіоматичну побудову геометрії Евкліда, що наперед визначило подальший розвиток досліджень з аксіоматизації наукового знання, запропонував розгорнутий план обґрунтування математики шляхом її повної формалізації. Щоправда, ця програма виявилась нездійсненною, проте її ідеї спричинили виникнення метаматематики (теорії доведень).
Альфред-Норт Уайтхед (1861—1947) у співавторстві з Б. Расселом написав тритомну працю «Принципи математики», яка зробила значний внесок у розвиток математичної логіки.
Джузеппе Пеано (1858—1932) запропонував ідеї, завдяки яким було здійснено перехід від старої алгебри логіки до математичної в її сучасному вигляді. Він увів прийняті в сучасній математичній логіці символи (— знак входження елемента до тієї чи іншої множини; — знак включення множини; — знак об'єднання множин; — знак перетину множин), сформулював систему аксіом для арифметики натурального ряду.
Платон Порецький (1846—1907) першим у Росії розробив і читав курс математичної логіки. Він узагальнив і розвинув досягнення Дж. Буля, У. С. Джевонса, Е. Шредера у сфері алгебри логіки. Значне місце у працях Порецького займала «теорія наслідків». Ним узагальнена теорія силогістики традиційної логіки, проаналізовані деякі несилогістичні міркування тощо.
Значним є внесок у розвиток сучасної логіки і деяких інших учених, зокрема представників львівсько-варшавської школи, до якої належали К.Твардовський, Я.Лукасевич, С.Лесьневський, А.Тарський, Т.Котарбіньський, К.Айдукевич та ін. Вони багато зробили для розвитку логічної семантики, теорії множин, модальної й багатозначної, математичної логіки, для розв'язання металогічних і методологічних проблем тощо.
Розділ 1. Булеві змінні і функції
1.1. Двійкові інтерпретації, істотні та фіктивні змінні
Для зображення інформації в комп'ютерах викориcтовуєтья двійкова система числення. Таким чином, всі операції, які виконує комп'ютер, проводяться на множині . Ці перетворення зручно формально зображати за допомогою апарата двійкової логіки, який був розроблений Джорджем Булем у середині XIX століття. Ця алгебраїчна структура є алгеброю і називається булевою. Булева алгебра використовується при розв'язанні різних задач обробки інформації, при роботі з базами даних, в логічному програмуванні, при проектуванні інтелектуальних систем, конструювання та аналізу роботи комп'ютерів та інших електронних пристроїв. У цьому розділі розглянуто основні властивості булевих функцій з аргументами з множини і її способом зображення булевих функцій у вигляді виразів булевої алгебри. Булева функція може мати велику кількість логічних знаків операцій, у той час, як може існувати інше, еквівалентне зображення даної функції, що має меншу кількість змінних і операцій. У главах розділу описано методи одержання виразів з мінімальною кількістю змінних і знаків операцій.
Розглянемо двохелементну множину, елементи якої будемо позначати через і 1:.
Означення
Змінні, які можуть приймати значення тільки з множини В, називаються логічними або булевими змінними. Самі значення 0 і 1 булевих змінних називаються булевими константами.
В мовах програмування для роботи з такими змінними, як правило, вводиться спеціальний логічний (булевський) тип (наприклад, у мовах Pascal і Java — boolean, у С+ — bool). Змінна цього типу приймає два значення: true і false.
Означення
Функція виду , аргументи і значення у якої належать множині В, називається n-місною булевою функцією. Такі функції також називають логічними або перемикальними функціями.
Означення
Кортеж конкретних значень булевих змінних називається двійковим словом (п-словом) або булевим набором довжини п. Для булевої функції конкретне (індивідуальне) значення булевого набору називається також інтерпретацією булевої функції. Множина всіх двійкових слів, що позначаєься через , називається п-вимірним булевим кубом і містить елементів-слів:.
Дійсно, для п = 1 є всього слова— (0) і (1), а за рахунок збільшення довжини слова на один символ кількість слів збільшується в два рази, оскільки додатковий символ може приймати два значення — 0 або 1. Для наочності зобразимо в одному рядку набори булевих змінних зростаючої довжини, у другому рядку — кількості різних наборів відповідної довжини:
Покажемо, що кількість всіх можливих булевих функцій дорівнює . Позначимо n-слово одним символом і пронумеруємо всі різні слова: , де . Дві булеві функції і співпадають, якщо для всіх . Оскільки може мати два значення (0 або 1), то число різних функцій дорівнює кількості різних булевих слів (наборів) довжини р, тобто числу .
Функції кількох незалежних змінних можна розглядати як функції від більшої кількості змінних. При цьому значення функції не змінюється при зміні значення цих «додаткових» змінних.
Означення
Змінна у функції називається неістотною (або фіктивною), якщо
при будь-яких значеннях решти змінних, тобто якщо зміна значення у будь-якому наборі значень не змінює значення функції.
В цьому випадку функція фактично залежить від змінної, тобто зображує функцію . Стверджують, що функція g одержана з функції видаленням фіктивної змінної, а функція одержана з g введенням фіктивної змінної, причому ці функції за визначенням рівні.
1.2. Способи задання булевих функцій
Булеві функції можуть бути задані такими способами:
За допомогою таблиці істинності (значеннями на кожній з інтерпретацій).
Порядковим номером, який має ця функція.
Аналітично (у вигляді формули).
Розглянемо кожний із зазначених способів докладніше.
1.2.1. Таблиці істинності
Таблиці, в яких кожній інтерпретації (тобто набору аргументів) функції поставлено у відповідність її значення, називаються таблицями істинності булевої функції.
В таблиці істинності кожній змінній та значенню самої функції відповідає по одному стовпчику, а кожній інтерпретації — по одному рядку. Кількість рядків у таблиці відповідає кількості різних інтерпретацій функції. Булеві функції , які залежать від однієї змінної, наведено в таблиці 1.
Таблиця 1. Булеві функції однієї змінної
0
0
0
1
1
1
0
1
0
1
Кожній функції відповідно до значень, що вона приймає, можна привласнити такі назви: — функція константа 0, — функція повторення аргументу, — функція інверсії або заперечення аргументу, — функція константа 1.
Різні булеві функції двох змінних f(x, у) зображено в таблиці 2, їх кількість дорівнює .
Таблиця 2. Булеві функції двох змінних
Більшість із шістнадцяти булевих функцій f(x, у) часто застосовуються на практиці. Оскільки дані функції використовуються як у математиці, так і в програмуванні, вони можуть мати різне позначення. Позначення, назви і прочитання булевих функцій від двох змінних зображено її таблиці 3.
Таблиця 3. Позначення булевих функцій двох змінних
Функція
Позначення
Назва
Інші позначення
Прочитання
1
2
3
4
5
0
константа 0
будь-яке 0, константа 0
кон'юнкція (логічне «і»)
AND, І, , min, ,
&, &&, *
х і у
заперечення імплікації
\
х і не
повторення першого аргументу
як х
1
2
3
4
5
заперечення оберненої імплікації
\
не х і у
у
повторення другого аргументу
як у
ху
що виключає «або» (сума за модулем 2)
, <>, >, <, !=, XOR
і не як у
диз'юнкція (логічне «або»)
OR, АБО,
+, max
х або у
заперечення диз'юнкції (стрілка Пірса)
,
не х і не у
еквівалентність
, , Eqv, =
х як у
заперечення другого аргументу
у
не у
обернена імплікація
x, якщо y
(x або не y )
заперечення першого аргументу
не x
імплікація
, =>, Imp
якщо x, то у (не x або у)
заперечення кон'юнкції (штрих Шеффера)
ху,х&у
не x або не у
1
константа 1
будь-яке 1, константа 1
Позначення Not, And, Or, Xor, Imp, Eqv використовуються у мові програмування Basic; позначення !, &, ! = використовуються умові С; позначення , , використовуються в системі Mathcad. Для стислості у прикладах та викладеннях ми будемо опускати знак кон'юнкції і писати ху замість х у.
1.2.2. Номери булевих функцій та інтерпретацій
Кожній функції привласнюється порядковий номер у вигляді натурального числа, двійковий код якого зображує стовпчик значень функції у таблиці істинності. Молодшим розрядом вважається самий нижчий рядок (значення функції на інтерпретації (1, 1, ..., 1)), а старшим — самий верхній (значення функції на інтерпретації (0, 0, ..., 0)). Вказаний порядковий номер функції, як двійковий, так і десятковий, повністю визначає булеву функцію.
Кожній інтерпретації булевої функції також привласнюється свій номер — значення двійкового коду, який зображує інтерпретація. Інтерпретації, що записана у верхньому рядку таблиці істинності, привласнюється номер 0, потім йде інтерпретація номер 1 тощо. В самому нижчому рядку розташована інтерпретація за номером , де п — кількість змінних, від яких залежить булева функція.
Приклад. Знайдемо порядковий номер функції f(x, у), що приймає такі значення: (0, 0) = 1, (0, 1)=1, (1,0) = 0, (1, 1) = 1. Побудуємо таблицю істинності для цієї функції (таблиця 4).
Таблиця 4. Таблиця істинності f(x, у)
x
у
f(x, у)
0
0
1
0
1
1
1
0
0
1
1
1
Двійковий код, що відповідає значенням цієї функції, — 1101. Переведемо двійкове число у десяткову систему числення. Для цього кожному розряду двійкового числа привласнимо ваговий коефіцієнт, що кратний відповідному степеню числа 2, починаючи з нижчого рядку: , , 22 тощо. Помноживши ваговий коефіцієнт на відповідну двійкову цифру і додавши одержані значення, знайдемо порядковий номер функції:
11012 = 123+122 + 021+ 1 = 8 + 4 + 0 + 1 = 1310.
Таким чином, десятковий номер даної функції — 13, тобто розглянута функція імплікації f13(x, у) = х у (див. f13(x, у) в таблиці 4). Таким чином, функцію f13(x, у) можна задати за допомогою двійкового коду, що відповідає її двійковому номеру: f13(x,y) відповідає двійковому числу (1101)2.
Приклад. Побудуємо таблицю істинності для бінарної функції з порядковим номером 14. Для цього знайдемо двійкове число, яке відповідає десятковому числу 14. Зобразивши це число як суму степенів числа 2, одержимо:
1410 = 8 + 4 + 2=123 + 122+121 + 0= 11102.
Таким чином, відповідає двійковому числу (1110)2.
Побудуємо шукану таблицю істинності, розташувавши одержане число у стовпчику значення функції таким чином, щоб молодший розряд виявився у нижчому рядку (таблиця 5).
Таблиця 5. Таблиця істинності
x
у
1
2
3
0
0
1
1
2
3
0
1
1
1
0
1
1
1
0
1.2.3. Булеві алгебри: загальна, двохелементна і логічна
Означення
Частково упорядкована множина – алгебраїчна структура (А, ), в якій кожна пара елементів має найменшу верхню і найбільшу нижню грані, називається граткою.
Означення
Гратка називається дистрибутивною якщо операції і дистрибутивні одна відносно одної:
Означення
Гратка з 0 і 1 називається граткою з доповненням, якщо для кожного її елемента є обернений елемент відносно обох операцій і : для будь-якого справедливо
Означення
Дистрибутивна гратка з доповненням називається булевою граткою або булевою алгеброю , де - унарна операція знаходження оберненого елемента, 0, 1 – нуль і одиниця гратки.
Аналізуючи алгебраїчну форму всіх властивостей і та заміняючи позначення операцій , , на +, •, ~ відповідно, ми виділяємо такий набір незалежних властивостей, які можна вважати аксіомами або незалежними законами булевої алгебри:
Комутативність:
Асоціативність:
3. Дистрибутивність:
4. Закони для нуля, одиниці та заперечення:
Всі інші відношення (деякі з них також називаються «законами» булевої алгебри) є наслідком зазначених вище. Зокрема, з 1-4 виходять:
Закони ідемпотентності:
Інші властивості одиниці і нуля:
Закони поглинання:
Закон інволюції (подвійного заперечення):
Закони де Моргана (подвійності):
Означення
Булева алгебра — це алгебраїчна структура (А, •, +, ~, 0, 1) з бінарними операціями •, +: А2А, унарною операцією : і виділеними елементами 0, 1 в носії А, які задовольняють властивості 1-4.
Позначення операцій , замість +, • у спеціальних булевих алгебрах запозичене з логіки, в якій Дж. Буль вперше виділив алгебраїчну структуру з властивостями 1-4. Носій цієї структури В = {0, 1} складається з двох елементів.
Означення
Алгебраїчна структура, В = {0, 1}, де операція є кон'юнкція , є диз'юнкція (див. таблиці 2, 3), є заперечення або інверсія (див. таблицю 1), називається двохелементною буле-вою алгеброю.
Виконання законів булевої алгебри 1-4 у структурі , а також законів 5-9 виходить з визначення операцій кон'юнкції, диз'юнкції та заперечення через таблиці істинності 1, 2 .
Означення
Алгеброю логіки називається двохелементна булева алгебра , В = {0, 1}, в якій множину операцій доповнено двома бінарними операціями: імплікацією та еквівалентністю ~ (див. таблиці 2, 3).
1.2.4. Булеві формули і пріоритет операцій
Булеві функції можуть бути задані аналітично, тобто формулами.
Означення
Формула — це вираз, що містить булеві функції та їхні суперпозиції.
Означення
Суперпозицією називається спосіб одержання нових функцій шляхом підстановки значень одних функцій замість значень аргументів інших функцій. Точніше, суперпозицією булевої функції і функцій називається функція , де кожна з функцій співпадає з однією з функцій , . При цьому деякі з функцій, а значить і можуть тотожно співпадати з однією із змінних , .
Приклад. Розглянемо формулу, що задає функцію таким чином:
.
Ця формула містить функції: — заперечення, — кон’юнкція і — диз’юнкція. Дану формулу можна зобразити у вигляді суперпозиції вказаних функцій таким чином:
.
У формулі використано інфіксний запис, коли знаки функцій (операцій) розташовані між операндами. Для запису виразів у інфіксній формі необхідно визначити порядок виконання операцій, що виконується за допомогою дужок або задання пріоритету операцій.
Якщо у формулі відсутні дужки, то операції виконуються у такій послідовності: заперечення, кон'юнкція, диз'юнкція, імплікація та еквівалентність: .
Приклад. Попередню формулу з урахуванням пріоритету операцій можна записати без дужок:
.
Зворотно з урахуванням пріоритету операцій розставимо
дужки:
.
Необхідно відзначити, що знак операції заперечення може розміщатися не тільки над окремими змінними, але й над формулами або їхніми частинами. В цьому випадку операції виконуються так, як наче б то вираз, що знаходиться під знаком заперечення, було вкладено в дужки.
Приклад. У формулі дужки можна розставити таким чином:
.
На відміну від табличного завдання, зображення функції формулою не єдине. Наприклад, функцію штрих Шеффера можна зобразити за допомогою основних операцій булевої алгебри формулами:
або
а функцію стрілка Пірса таким чином:
або .
Означення
Формули, що зображують одну й ту ж функцію, називаються еквівалентними або рівносильними.
Еквівалентність формул позначається знаком рівності. Один із способів встановити еквівалентність формул складається з такого: для кожної формули будується таблиця істинності, а потім одержані таблиці порівнюються, тобто фактично для кожного набору змінних перевіряється, чи дорівнюють на ньому значення функцій. Існують й інші способи перевірки еквівалентності формул, які буде розглянуто нижче.
1.2.5. Перехід від формули до таблиці істинності функції
Побудуємо таблицю істинності для функції, що задана такою формулою:
.
Функція залежить від чотирьох змінних і, отже, для неї є 24=16 інтерпретацій. Для побудови таблиці істинності необхідно визначити значення функції на всіх інтерпретаціях:
. . .
Розмістимо в таблиці істинності інтерпретації в порядку збільшення відповідних їм двійкових номерів і запишемо одержане значення функції на кожній інтерпретації. Одержимо таблицю істинності функції (таблиця 6).
Таблиця 6. Таблиця істинності f(x, у, z, t)
y
z
t
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
0
1
0
1
1
0
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
Розділ 2. Алгебри логіки
2.1. Алгебра Буля
У цьому розділі буде перевірено виконання законів булевої алгебри 1-4, а також 5-9 з п. 1.2.3 для двохелементної алгебраїчної структури .
1. Комутативність кон'юнкції та диз'юнкції
.
Таблиця 7. Таблиця істиності
0
0
0
0
0
1
1
1
1
0
1
1
1
1
1
1
Сумістимо таблиці істинності для обох частин першої рівності (таблиця 7).
Стовпці і у таблицях істинності містять однакові значення, що доводить комутативність операції диз'юнкції. Знайдемо тотожність, двоїсту даній, для чого замінимо всі функції на двоїсті їм:
, .
2. Асоціативність кон'юнкції та диз'юнкції
Створимо таблиці істинності для лівої та правої частин другої рівності (таблиця 8).
Таблиця 8. Доведення асоціативності кон'юнкції
2)
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
1
0
0
0
1
0
1
1
1
1
1
1
1
Стовпчики, що відповідають лівій та правій частинам другої рівності, містять однакові значення, що доводить справедливість тотожності. Тотожність, що виражає асоціативність диз'юнкції, двоїста доведеній, оскільки може бути одержана з неї шляхом заміни всіх функцій на двоїсті їм, і, отже, вона теж правильна.
3. Дистрибутивність кон'юнкції та диз'юнкції відносно одна одній
.
Доведемо дистрибутивність кон'юнкції щодо диз'юнкції, використовуючи таблицю істинності (таблиця 9).
Таблиця 9. Дистрибутивність кон'юнкції щодо диз'юнкції
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
Стовпчики, які відповідають лівій та правій частинам першої рівності, містять однакові значення, що і доводить справедливість рівності . Двоїста тотожність виражає дистрибутивність диз'юнкції відносно кон'юнкції.
4. Ідемпотентність кон'юнкції та диз'юнкції
.
Побудуємо таблиці істинності функцій з лівих частин рівності (таблиця 10).
Таблиця 10. Закон ідемпотентності.
0
0
0
1
1
1
В таблиці значення всіх стовпців однакові і співпадають із значенням змінної , що і доводить обидві тотожності. Дані тотожності так, як і розглянуті вище, є двоїстими одна одній.
5. Закон виключеного третього
Доведемо цей закон, використовуючи таблицю істинності (таблиця 11).
Таблиця 11. Закон виключеного третього
0
1
1
1
0
1
Стовпчик таблиці істинності, який зображує ліву частину тотожності, що доводиться, дорівнює константі одиниці, що і треба було довести.
6. Закон протиріччя
Цей закон є двоїстим до доведеного вище закону виключеного третього.
7. Тотожності з константами
Побудуємо таблиці істинності для лівих частин тотожностей (таблиця 12).
Таблиця 12. Таблиці істинності тотожностей
0
0
0
1
0
1
1
1
1
0
Одержана таблиця доводить справедливість даних тотожностей.
8. Закони елімінації
Доведемо цей закон аналітично, використовуючи тотожності з константами і дистрибутивний закон:
9. Закон подвійного заперечення
Побудуємо відповідну таблицю істинності (таблиця 13). Одержана таблиця істинності доводить справедливість тотожності.
Таблиця 13. Закон подвійного заперечення
0
1
0
1
0
1
Наслідок. Якщо до деякої частини А формули F булевої алгебри операція
заперечення застосована більше одного разу, то можна видалити будь-яке парне число даних операцій і значення формули F не зміниться.
10. Закони де Моргана
.
Доведемо першу з наведених тотожностей за допомогою таблиці істинності (таблиця 14).
Таблиця 14. Доведення закону де Моргана
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
0
0
1
0
1
1
1
0
0
0
0
Побудована таблиця істинності доводить справедливість тотожності. Другий закон де Моргана є двоїстим першому і, отже, також є правильним.
2.1. Алгебра Жегалкіна
Означення
Алгебра , що утворена множиною В = {0, 1} разом з операціями кон'юнкції, (сума за модулем 2) і константами 0, 1, називається алгеброю Жегалкіна.
Приклад. Формула , де х, у, z — булеві змінні, є прикладом формули алгебри Жегалкіна, тому що вона містить операції кон'юнкції і XOR.
В алгебрі Жегалкіна операція кон'юнкції повністю ідентична множенню, а операція XOR зображує додавання за модулем для скінченних множин.
2.1.1. Тотожності алгебри Жегалкіна
Нагадаємо властивості операції кон'юнкції:
1) — асоціативність.
2) — комутативність.
3) — ідемпотентність.
4), — дії з константами.
Властивості операції XOR (додавання за модулем 2):
5) — асоціативність операції XOR. Для доведення будуємо таблицю істинності (таблиця 15).
Таблиця 15. Доведення асоціативності операції XOR
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
0
1
0
1
0
0
0
1
1
1
1
0
1
1
0
1
0
1
1
0
1
0
0
0
1
1
1
0
1
0
1
Ліва та права частини тотожності мають однакові таблиці істинності, таким чином, тотожність 5 доведена.
6) — комутативність операції XOR виходить з таблиці істиності (таблиця 16).
Таблиця 16. Доведення тотожності 6
0
0
0
0
0
1
1
1
1
0
1
0
1
1
0
1
7) — закон зведення подібних доданків.
Як видно з таблиці істинності для операції XOR (таблиця 17), якщо операнди однакові, то функція дорівнює нулю, а якщо операнди різні, то значення функції — одиниця.
Таблиця 17. Доведення тотожностей 7 і 8
0
0
0
1
0
1
8) — операція з константою 0 (таблиця 17).
9) — дистрибутивність відносно виходить з таблиці істинності (таблиця 18).
Таблиця 18. Дистрибутивності відносно
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
1
0
1
1
1
1
0
0
1
1
0
Операція XOR (сума за модулем 2) відіграє важливу роль у програмуванні, при обробці та кодуванні інформації. Вона має важливу властивість — наявність оберненого елемента х' для кожного (операції диз'юнкції і кон'юнкції такої властивості не мають). У цій алгебрі кожний елемент є оберненим до самого себе: .Це дозволяє розв'язувати рівняння шляхом додавання до обох частин однакових елементів. Наприклад, рівняння виду розв'язується так:
Можливість розв'язку подібних рівнянь, що відсутня у булевій алгебрі, обумовила широке застосування операції XOR, зокрема, при кодуванні інформації.
Алгебра Жегалкіна не є ґраткою, оскільки в ній не виконуються всі необхідні для цього властивості, наприклад, ідемпотентність обох операцій.
Будь-яка булева функція може бути зображена через операції кон'юнкції, диз'юнкції, заперечення. Для доведення зображення будь-якої булевої функції формулою алгебри Жегалкіна достатньо виразити диз'юнкцію і заперечення через кон'юнкцію і XOR — операції алгебри Жегалкіна.
Зображення заперечення в алгебрі Жегалкіна формулою виходить з таблиці істинності (таблиця 19):
Таблиця 19. Операція заперечення
0
1
1
1
0
0
Зображення диз'юнкції в алгебрі Жегалкіна реалізується формулою: .
Доведемо цю формулу аналітично:
Таким чином, будь-яка логічна функція може бути зображена формулою в алгебрі Жегалкіна.
2.1.2. Поліном Жегалкіна
Серед всіх еквівалентних зображень функції в алгебрі Жегалкіна виділяється особливий вид формул, що називаються поліном Жегалкіна.
Означення
Поліномом Жегалкіна називається скінченна сума за модулем 2 попарно різних елементарних кон'юнкцій над множиною змінних . Кількість змінних, що входять до елементарної кон'юнкції, називається рангом елементарної кон'юнкції.
Кількість попарно різних елементарних кон'юнкцій у поліномі називається довжиною полінома.
Зображення у вигляді поліному існує та єдине для кожної булевої функції.
Для побудови поліному Жегалкіна функції, що задана деякою формулою алгебри Жегалкіна, необхідно розкрити всі дужки в даній формулі за законом дистрибутивності і виконати всі можливі спрощення з використанням законів дій з константами, ідемпотентності і зведення подібних доданків.
Приклад. Зобразити поліномами Жегалкіна логічні функції імплікацію і еквівалентність .
Розв'язок. Спочатку запишемо ДДНФ даних функцій, потім виразимо операції диз'юнкції та заперечення через операції кон'юнкції та XOR. Одержавши формулу алгебри Жегалкіна, користуючись описаним вище правилом, одержимо поліном Жегалкіна для кожної з даних функцій:
За видом полінома Жегалкіна визначається така важлива властивість булевих функцій, як лінійність.
Означення
Булева функція називається лінійною, якщо її поліном Жегалкіна не містить кон'юнкцій змінних.
Чи є лінійними операції булевої алгебри? Заперечення — лінійна функція, оскільки її поліном Жегалкіна не містить кон'юнкцій змінних. Диз'юнкція — нелінійна функція, оскільки її поліном Жегалкіна містить кон'юнкцію імінних х і у. Імплікація є нелінійною функцією, а еквівалентність — функція лінійна.
Приклад. Дослідити на лінійність функцію .
Розв'язок. Побудуємо поліном Жегалкіна функції , використовуючи такі тотожності:
Функція не є лінійною, оскільки її поліном Жегалкіна містить кон'юнкції змінних.
Теорема [Бондаренко М.Ф. Комп’ютерна дискретна математика, ст. 142]
Для будь-якої булевої функції існує єдиний поліном Жегалкіна.
Доведення. Доведемо існування полінома. Для будь-якої функції існує зображення у вигляді формул булевої алгебри. Від формул булевої алгебри завжди можна перейти до формул алгебри Жегалкіна, а потім до поліному Жегалкіна, використовуючи тотожності зображення операцій диз'юнкції та заперечення в алгебрі Жегалкіна, а також правило побудови полінома. Таким чином, для будь-якої булевої функції існує поліном Жегалкіна.
Підрахуємо кількість різних поліномів Жегалкіна від п змінних. Спочатку знайдемо кількість різних елементарних кон'юнкцій без заперечень від п змінних. У загальному випадку таку кон'юнкцію можна записати у такому вигляді:
де — булеві константи, причому = 0, якщо присутнє в кон'юнкції і = 1, якщо не присутнє в кон'юнкції. Набір повністю визначає елементарну кон'юнкцію, отже кількість таких наборів дорівнює кількості елементарних кон'юнкцій без заперечень від змінних. Кількість двійкових наборів (кодів) довжини п дорівнює . Тому кількість елементарних кон'юнкцій від п змінних без заперечень дорівнює . Поліном Жегалкіна, за визначенням, є сумою за модулем 2 n-місних елементарних кон'юнкцій. Перенумеруємо всі можливі елементарні кон'юнкції без заперечень від п змінних і позначимо їх . Запишемо поліном Жегалкіна у вигляді:
де — булеві константи, причому = 1, якщо кон'юнкція присутня у поліномі і = 0, якщо кон'юнкція не присутня у поліномі. Набір повністю визначає вид полінома, отже кількість таких наборів довжини дорівнює кількості поліномів Жегалкіна від п змінних, тобто дорівнює . Кількість різних булевих функцій від п змінних також дорівнює . Оскільки одному поліному не можуть відповідати дві різні функції, кожній булевій функції відповідає єдиний поліном Жегалкіна. Теорему доведено.
На цій теоремі засновано метод невизначених коефіцієнтів, який можна використовувати для знаходження полінома Жегалкіна заданої функції. Розглянемо цей метод на прикладі.
Приклад. Побудувати поліном Жегалкіна для функції — імплікації, використовуючи метод невизначених коефіцієнтів.
Розв'язок. Запишемо поліном для даної функції у вигляді суми за модулем 2 всіх можливих елементарних кон'юнкційдля х, у з невизначеними коефіцієнтами:
де коефіцієнти приймають значення з множини і визначають присутність або відсутність елементарної кон'юнкції в поліномі. Шукаємо послідовно значення коефіцієнтів, підставляючи значення змінних і функції на різних інтерпретаціях:
Отже, .
Далі
звідки маємо, що .
На такій інтерпретації
звідки маємо, що .
Нарешті,
Підставивши одержані значення коефіцієнтів , одержуємо поліном Жегалкіна для функції :
2.3. Алгебра Шеффера
Реалізується функцією Шефера (“і-не”):
.
Аксіоми алгебри Шефера:
Алгебра Шефера володіє тільки властивістю комутативності.
2.4. Алгебра Пірса
Реалізується функцією Пірса (“або-не”):
.
Аксіоми алгебри Пірса:
Алгебра Пірса володіє тільки властивістю комутативності.
Висновок
Булева алгебра відображає певні логічні закономірності об’єктів та систем реального світу. Засади алгебри логіки були сформульовані британцем Джорджем Булем в 1847 році і з тих пір ця система застосовується для вирішення широкого спектру проблем математичної логіки та теорії множин, та особливо конструювання цифрової електроніки (початок використання булевої алгебри для синтезу перемикальних (релейних) схем був покладений в 1938 році роботами відомого американського вченого Клода Шеннона).
Булева алгебра використовується при розв'язанні різних задач обробки інформації, при роботі з базами даних, в логічному програмуванні, при проектуванні інтелектуальних систем, конструювання та аналізу роботи комп'ютерів та інших електронних пристроїв.
Додаток
// converter.cpp : Основна програма, визначає головну точку входу main.
#include "stdafx.h"
#include "parser.h"
// Максимальна кількість символів вводу
const size_t MAX_COUNT = 100;
const size_t BUF_SIZE = 10000; // Максимальна довжина вхідного виразу в символах
// Функція виводу допомоги при помилковому вводі
void usage()
{
using namespace std;
cout<<" Pru vukluky prohramu vukorustovyjte nastypnuj suntaksus:"<<endl;
cout<<" converter.exe VuxidnujBazus KincevujBazus NazvaVxidnohoFajly "<<endl;
cout<<" VuxidnujBazus - nazva bazusy vxidnux danux, dopystumi nazvu: Sheffer, Boolean, Zhegalkin, Pirs "<<endl;
cout<<" KincevujBazus - nazva kincevoho bazusy, dopystumi nazvu: Sheffer, Boolean, Zhegalkin, Pirs "<<endl;
cout<<" NazvaVxidnohoFajly - nazva fajly z vxidnojy stri4kojy "<<endl;
}
void help_symbols()
{
using namespace std;
cout<<"Bazus Boolja (& - i , ! - ne, | - abo )" <<endl;
cout<<"Bazus Zhegalkina (& - i , + - dodavannja po modyljy dva)" <<endl;
cout<<"Bazus Pirsa (^ - fynkcija Pirsa )" <<endl;
cout<<"Bazus Sheffera (~ - wtrux Sheffera )" <<endl;
cout<<endl;
}
int main(int argc, char* argv[])
{
using namespace std;
stoune::Basis cur_basis, target_basis; // Змінні
char buf[BUF_SIZE], *cha = buf;
cout<<"Uvaga!!! Y vxidnuj fajl vvod'te dani, rozdiljajy4u operand vid operaciji probilom. "<<endl;
cout<<"Z vxidnoho fajly z4utyjet'sja til'ku odun vuraz. "<<endl;
cout<<"Dlja perevody inwoho vurazy zaminit' dani y fajli i zapystit' prohramy znovy. "<<endl;
cout<<"Kil'kist' arhymentiv vxidnoho vurazy - ne bilwa 2 "<<endl;
if (argc == 2)
{
if (!strncmp(argv[1], "-h", MAX_COUNT))
usage();
return 0;
}
else if (argc < 3)
{
help_symbols(); // Функція яка виводить пояснення значків
cout<<"-----------------------"<<endl;
cout<<" Vvedit' vhidnyj vyraz "<<endl;
cout<<"-----------------------"<<endl;
cin.getline(buf,BUF_SIZE-1) ;
cout<<"-----------------------"<<endl;
cout<<" Vvedit' nomer vhidnogo bazysu (Sheffer - 1 , Boolean - 2, Zhegalkin - 3, Pirs - 4): ";
unsigned basis = 0;
cin >> basis; // Вводимо номер вхідного базису
cur_basis =static_cast<stoune::Basis> (basis);
if (cur_basis > stoune::Pirs)
{
cout<<"Vy vvely nedopustymyj nomer bazysu"<<endl;
return 4;
}
cout<<endl;
cout<<endl<<" Vvedit' nomer vihidnogo bazysu (Sheffer - 1 , Boolean - 2, Zhegalkin - 3, Pirs - 4): ";
cin >> basis; // Вводимо номер вихідного базису
target_basis =static_cast<stoune::Basis> (basis);
if (target_basis > stoune::Pirs)
{
cout<<"Vy vvely nedopustymyj nomer bazysu"<<endl;
return 4;
}
cout<<endl;
}
else
{
if (!strncmp(argv[1],"Sheffer", MAX_COUNT))/// Перевіряємо який вхідний базис
{
cur_basis = stoune::Sheffer;
cout<<" Vhidnyj Basis Sheffer"<<endl;
}
else if (!strncmp(argv[1],"Boolean", MAX_COUNT) )
{
cur_basis = stoune::Boolean;
cout<<" Vhidnyj Basis Boolean"<<endl;
}
else if (!strncmp(argv[1],"Zhegalkin", MAX_COUNT) )
{
cur_basis = stoune::Zhegalkin;
cout<<" Vhidnyj Basis Zhegalkin"<<endl;
}
else if (!strncmp(argv[1],"Pirs", MAX_COUNT) )
{
cur_basis = stoune::Pirs;
cout<<" Vhidnyj Basis Pirs"<<endl;
}
else
{
cout<<" Nedopustuma nazva "<<argv[1] <<" vxidnoho bazusy!!! "<<endl;
usage();
return 4;
}
if (!strncmp(argv[2],"Sheffer", MAX_COUNT) )/// Перевіряємо який вхідний базис
{
target_basis = stoune::Sheffer;
cout<<" Kincevyj Basis Sheffer"<<endl;
}
else if (!strncmp(argv[2],"Boolean", MAX_COUNT) )
{
target_basis = stoune::Boolean;
cout<<" Kincevyj Basis Boolean"<<endl;
}
else if (!strncmp(argv[2],"Zhegalkin", MAX_COUNT) )
{
target_basis = stoune::Zhegalkin;
cout<<" Kincevyj Basis Zhegalkin"<<endl;
}
else if (!strncmp(argv[2],"Pirs", MAX_COUNT) )
{
target_basis = stoune::Pirs;
cout<<" Kincevyj Basis Pirs"<<endl;
}
else
{
cout<<" Nedopustuma nazva "<<argv[2] <<" vuxidnoho bazusy!!! "<<endl;
usage();
return 4;
}
ifstream file;
file.open(argv[3]);
file.seekg(ios_base::beg); // Перейти на початок файлу
if (!file.good())// Перевіряємо чи вдалося відкрити файл
{
cout<<" Vxidnuj fajl ne isnyje abo vunukla pomulka dostypy do fajlovoji sustemu."<<endl;
return 2;
}
file.getline(buf,BUF_SIZE-1);
}
if (!stoune::parse
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора