Алгебра логіки (Булева алгебра, Булева логіка, двійкова логіка, двійкова алгебра, англ. Boolean algebra) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями. В алгебрі логіки значенням змінних є значення істинності істина або хиба, які зазвичай визначаються як 1 і 0 відповідно. На відміну від елементарної алгебри, у якій значеннями змінних є числа, а основними операціями є додавання і множення, основними операціями булевої алгебри є кон'юнкція операція І (англ. AND) позначається як ∧, диз'юнкція АБО (англ. OR) позначається як ∨, і заперечення НІ (англ. NOT) позначається як ¬. Таким чином, формалізм для описання логічних відношень є аналогічним тому, як описуються числові відношення в елементарній алгебрі.
Алгебра логіки | |
Названо на честь | Джордж Буль |
---|---|
Тема вивчення/дослідження | булева алгебра і булева функція |
Алгебра логіки у Вікісховищі |
Булеву алгебру запропонував Джордж Буль у своїй книзі Математичний аналіз логіки (1847), і більш детально в наступній книзі [en] (1854). Відповідно до [en], термін «Булева алгебра» вперше запропонував Шеффер у 1913, хоча Чарлз Сандерс Пірс у 1880 дав назву «Булева алгебра з однією сталою» першій главі своєї книги «Найпростіша математика». Булева алгебра є фундаментальною основою для розвитку цифрової електроніки, і втілена в усіх мовах програмування. Вона також використовується в теорії множин і статистиці.
Визначення
Базовими елементами, якими оперує алгебра логіки, є висловлювання.
Висловлювання будуються над множиною {B, , , , 0, 1}, де B — непорожня множина, над елементами якої визначені три операції:
- заперечення (унарна операція),
- кон'юнкція (бінарна),
- диз'юнкція (бінарна),
- а логічний нуль 0 і логічна одиниця 1 — константи.
Так само використовуються назви
- диз'юнкт — пропозиціональна формула, що є диз'юнкцією одного або більше літералів (наприклад ).
- кон'юнктив — пропозиціональна формула, що є кон'юнкцією одного або більше літералів (наприклад ).
Унарна операція заперечення в тексті формул оформляється або у вигляді значка перед операндом (), або у вигляді риски над операндом (), що компактніше, але загалом менш помітно.
Значення
Тоді як в елементарній алгебрі вирази зазвичай виражаються в числах, в алгебрі логіки вони виражають значення істинності істина і хиба. Ці значення задають за допомогою бітів (або двійкових чисел), а саме 0 та 1. Вони не поводять себе так само як цілі числа 0 та 1, для яких 1 + 1 = 2, а можуть визначатися як елементи [en], що є цілочисельною арифметикою за модулем 2, для якої 1 + 1 = 0. Алгебра логіки також вивчає функції, що приймають значення в множині {0, 1}.
Предмет вивчення
Спочатку проблематика алгебри логіки перетиналася з проблематикою алгебри множин (теоретико-множинні операції).
Проте із закінченням формування теорії множин (70-і роки 19 ст.), до складу якої входила алгебра множин, і подальшим розвитком математичної логіки, предмет алгебри логіки значно змінився.
Сучасна алгебра логіки розглядає операції над висловлюваннями (див. Числення висловлень) як булеву функцію і вивчає відносно них такі питання, як:
- таблиці істинності;
- функціональна повнота;
- замкнені класи;
- представлення у вигляді: ДНФ, КНФ, полінома Жегалкіна.
Операції
Базові операції
Як уже зазначалося, базовими операціями булевої алгебри (алгебри логіки) є такі логічні операції:
- І (кон'юнкція), позначається x∧y (іноді x І y), задовольняє x∧y = 1, якщо x = y = 1 та x∧y = 0 в інших випадках.
- АБО (диз'юнкція), позначається x∨y (іноді x АБО y), задовольняє x∨y = 0, якщо x = y = 0 та x∨y = 1 в інших випадках.
- НІ (заперечення), позначається ¬x (іноді НЕ x або !x), задовольняє ¬x = 0, якщо x = 1 та ¬x = 1, якщо x = 0.
Альтернативним способом значення x∧y, x∨y, та ¬x можна представити в табличному вигляді для всіх можливих значень за допомогою таблиць істинності таким способом.
-
0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 0
Якщо значення істинності 0 та 1 інтерпретувати як цілі числа, ці операції можна було задати як звичайні операції арифметики (де x + y використовує додавання, а xy використовує множення), або як функції мінімуму/максимуму:
Можна вважати, що лише заперечення і одна з двох операцій, що залишилися, є базовими, оскільки наступні рівняння дозволяють визначити кон'юнкцію через операції заперечення та диз'юнкцію, і навпаки:
Вторинні операції
Три булеві операції описані вище називають базовими або первинними, що означає, що вони можуть бути базисом для всіх інших булевих операцій, оскільки всі інші операції можна виразити через них за допомогою композиції. Серед операцій, які можна побудувати з базових операцій є такі:
Ці визначення дають такі таблиці істинності, у яких показані значення цих операцій для всіх можливих вхідних значень.
0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1
Перша операція, x → y, називається імплікацією. Якщо x є істинним, тоді за значення виразу x → y приймається значення y. Але якщо x приймає хибне значення, то значення y можна було б ігнорувати; однак ця операція повинна повернути деяке логічне значення, і існує лише два варіанти вибору. То ж за визначенням, x → y є істиною коли x є хибним.
Друга операція, x ⊕ y, називається виключною диз'юнкцією (часто задається як абревіатура XOR), аби відрізнити її від диз'юнкції. Вона є істиною, лише коли x та y різні.
Третя операція, обернена до виключної диз'юнкції, називається еквівалентність або булева рівність: x ≡ y буде істиною, лише коли x та y мають однакове значення.
Для двох даних операндів, кожен з яких має 22 = 4 можливих комбінації входів. Оскільки кожен вихід може мати два можливих значення, існує загалом 24 = 16 можливих булевих операцій.
Закони
Законом у булевій алгебрі може виступати тотожність між двома булевими виразами такого вигляду як x∨(y∨z) = (x∨y)∨z, де булевий вираз (або логічне висловлювання) визначається як вираз, що побудований зі змінних та констант 0 та 1 та операцій між ними ∧, ∨, та ¬. Це поняття можна поширити й до виразів, що містять інші булеві операції, такі як ⊕, →, та ≡, але для формулювання законів таке розширення операцій не є необхідним. Для таких цілей додають визначення булевої алгебри як будь-якої моделі булевих законів, і як засіб для виведення нових законів з наявних, як наприклад доведення, що x∨(y∧z) = x∨(z∧y) з y∧z = z∧y.
Закони монотонності
Булева алгебра задовольняє багатьом відповідним законам звичайної алгебри, якщо зіставити операції ∨ з додаванням, а ∧ з множенням. Зокрема такі закони є спільними для обох типів алгебр:
Асоціативність операції : Асоціативність операції : Комутативність операції : Комутативність операції : Дистрибутивність операції over : Ідентичність для : Ідентичність для : Анігілятор для :
Такі закони є дійсними в булевій алгебрі, але не дійсні у звичайній алгебрі:
Анігілятор для : Ідемпотентність : Ідемпотентність : Абсорбція 1: Абсорбція 2: Дистрибутивність операції над :
Якщо прийняти x = 2 в третьому наведеному вище законі, ми бачимо, що це не закон зі звичайної алгебри, оскільки 2 × 2 = 4. Решта п'ять законів можна фальсифікувати у звичайній алгебрі, якщо прийняти, що значення всіх змінних буде 1, наприклад, у законі абсорбції 1 ліва сторона відношення була б 1(1 + 1) = 2, а права частина рівняння була 1, і так далі.
Усі ці закони, що розглядалися досі, були для кон'юнкції та диз'юнкції. Ці дві операції мають властивість, що за зміни будь-якого з аргументів вихід залишиться або незмінним, або змінить своє значення так само як вхід. Аналогічно, зміна значення будь-якої змінної з 0 на 1 ніколи не призведе до того, що вихід змінить своє значення з 1 на 0. Операції з такою властивістю називають монотонними. Таким робом, усі аксіоми досі були для монотонної булевої логіки. Немонотонність з'являється через операцію доповнення ¬, що наведено далі.
Закони немонотонності
Операція доповнення (заперечення) визначається такими двома законами.
Усі властивості заперечення, зокрема закони, що наведені нижче, випливають з двох вищенаведених законів.
Як у звичайній, так і в булевій алгебрі, операція заперечення працює як обмін пари елементів, тому в обох алгебрах вона задовольняє закону подвійного заперечення (також називається законом інволюції).
Але тоді як «звичайна алгебра» задовольняє таким двом законам:
булева алгебра задовольняє законам де Моргана:
Повнота
Закони, описані вище, визначають булеву алгебру в тому сенсі, що з них випливають усі інші наслідки. Для цього достатньо законів доповнення 1 та 2, разом із законами монотонності. Отже, їх можна вважати повною множиною законів або однією з можливих систем аксіоматизації булевої алгебри. Кожен закон булевої алгебри випливає логічним чином із цих аксіом. Крім того, булеві алгебри можна визначити як моделі з цих аксіом.
Принцип двоїстості
Принцип: Якщо {X, R} — частково впорядкована множина, тоді {X, R(обернена)} також частково впорядкована множина.
Ніякої магії у виборі символів для позначення логічних значень булевої алгебри не існує. Замість 0 і 1 можна було б використовувати, наприклад, α та β, доки ми робимо це послідовним чином повсюди, це досі залишатиметься булевою алгеброю, але з явними зовнішніми відмінностями.
Припустимо також, що ми переназвали 0 та 1 відповідно на 1 та 0. Тоді це також залишатиметься булевою алгеброю, що навіть оперує з тими самими значеннями. Однак вона не буде ідентичною до нашої початкової булевої алгебри, оскільки тепер операція ∨ поводитиметься так, як поводила себе операція ∧ і навпаки. Тож, вони також матимуть зовнішні відмінності, які показують, що ми змінили позначення, не дивлячись на те, що ми досі використовуємо 0-і та 1-і.
Але якщо в додаток до того, що ми замінили місцями імена змінних, ми замінимо місцями імена двох двійкових операцій, тепер немає ніякого сліду від того, що ми зробили. Кінцевий результат повністю не відрізняється від того, з чого ми почали. Ми помітимо, що колонки для операцій x∧y та x∨y у таблицях істинності змінили свої місця, але ця відмінність є незначною.
Коли існує така пара операцій, для яких усе залишається незмінним, якщо всі пари були одночасно взаємно змінені, ми називаємо такі елементи кожної пари двоїстими один з одним. У такий спосіб, 0 та 1 є двоїстими, і операції ∧ та ∨ також є двоїстими. Принцип двоїстості, також називають двоїстістю де Моргана, за якою стверджують, що булева алгебра залишається незмінною, якщо взаємно замінити всі двоїсті пари.
Аксіоми
Логічні операції
Простим і найширше вживаним прикладом такої алгебричної системи є множина B, що складається всього з двох елементів:
- B = { Хиба (0), Істина (1) }
Зазвичай у математичних виразах Хиба ототожнюється з логічним нулем, а Істина — з логічною одиницею, а операції заперечення (НІ), кон'юнкції (І) та диз'юнкції (АБО) визначаються у звичному нам розумінні. Легко показати, що на цій множині B можна задати чотири унарні та шістнадцять бінарних відношень і всі їх може бути отримано через суперпозицію трьох обраних операцій.
Спираючись на цей математичний інструментарій, логіка висловлювань вивчає висловлювання і предикати. Також запроваджуються додаткові операції, такі як еквівалентність («тоді й лише тоді, коли»), імплікація («отже»), складання по модулю два («виключна диз'юнкція»), штрих Шефера , стрілка Пірса та інші.
Логіка висловлювань послугувала основним математичним інструментом під час створення комп'ютерів. Вона легко перетворюється в бітову логіку: істинність висловлювання позначається одним бітом (0 — ХИБА, 1 — ІСТИНА); тоді операція набуває суті вирахування з одиниці; — немодульного додавання; & — множення; — рівності; — у буквальному розумінні сума за модулем 2 (виключне АБО — XOR); — сума не перевищує 1 (тобто A B = (A + B) <= 1).
Згодом булеву алгебру було узагальнено від логіки висловлювань через запровадження характерних для логіки висловлювань аксіом. Це дозволило розглядати, наприклад, логіку кубітів, тризначну логіку (коли є три варіанти істинності висловлювання: «істина», «хиба» і «невизначено») тощо.
Властивості логічних операцій
- Комутативність: xy = yx, {&, }.
- Ідемпотентність: xx = x, {&, }.
- Асоціативність: (xy)z = x(yz), {&, }.
- Дистрибутивність кон'юнкцій і диз'юнкції відносно диз'юнкції, кон'юнкції і суми за модулем два відповідно:
- ,
- ,
- .
- Закони де Мо́ргана:
- ,
- .
- Закони поглинання :
- ,
- .
- Інші (1):
- Інші(2) :
- .
- .
- .
- .
- Інші(3) (Доповнення законів де Мо́ргана) :
- .
- .
Існують методи спрощення логічної функції: наприклад, Карта Карно, метод Куайна — Мак-Класкі
Представлення у вигляді діаграм
Діаграма Венна
Діаграма Венна — це графічне представлення булевих операцій за допомогою зафарбованих областей, що перекриваються. По одній області для кожної змінної, всі області круглі, як показано на прикладах. Внутрішня й зовнішня частина області x відповідає значенням 1 (істина) та 0 (хиба) відповідно для змінної x. Зафарбована область показує значення операції для кожної комбінації цих областей, де зафарбована область означає 1, а не зафарбована — 0 (але в деяких книжках може зустрітися і навпаки).
Діаграми Венна на малюнку знизу показують операції кон'юнкції x∧y, диз'юнкції x∨y, та доповнення ¬x.
Для кон'юнкції, регіон у середині двох кругів зафарбований, що означає, що вираз x∧y дорівнює 1, коли обидві змінні мають значення 1. Інші області лишилися не зафарбованими, аби зазначити, що x∧y дорівнює 0 для всіх інших комбінацій.
На другій діаграмі, що показує диз'юнкцію x∨y зафарбована область, що знаходиться в середині двох кіл одночасно. Третя діаграма представляє доповнення ¬x, де зафарбована область не в середині кола.
Тут не показані діаграми для сталих 0 та 1, оскільки вони тривіальні та представляються незафарбованим або зафарбованим прямокутником, без кіл у середині. Однак ми б могли розмістити коло для змінної x у цих прямокутниках, у такому разі це б позначало функцію з одним аргументом, x, що позначає те саме значення, незалежно від x, що називається константною функцією. Що стосується результатів функцій, то константи й константні функції не відрізняються; їхня відмінність полягає в тому, що константа не приймає ніяких аргументів і називається нульовою операцією, тоді як константна функція приймає один аргумент, який ігнорується, і тому є унарною операцією.
Діаграми Венна є корисними для візуалізації законів. Закони комутативності для ∧ та ∨ можна побачити із симетричності діаграм: бінарна операція, що не є комутативною не мала б симетричної діаграми, оскільки заміна місцями x та y призвело до горизонтального віддзеркалення діаграми, і відсутність комутативності б відзначилася в не симетричності діаграми.
Ідемпотентність операцій ∧ та ∨ можна було б зобразити зсунувши два кола разом і зазначивши, що зафарбована область тоді стає цілим колом, як обох ∧ та ∨.
Цифрові логічні кола
Цифрова логіка застосовує булеву алгебру для 0 та 1 до електронної апаратури, що складається із з'єднаних між собою логічних елементів, і які утворюють електричну схему. Кожний елемент виконує булеву операцію, і в різних системах позначень позначається так, що його вигляд ідентифікує певну операцію. Форми позначень для елементів, що позначають кон'юнкцію (І-вентиль), диз'юнкцію (АБО-вентиль), і доповнення (інвертори) виглядають так.
Лінії по лівій стороні кожного елемента позначають вхідні з'єднання або порти. Значення на вході задається напругою. Для так званої логіки з «активним високим рівнем», 0 задається значенням напруги близьким до нуля або «землі», тоді як 1 задається значенням напруги близьким до джерела напруги; за активного низького рівня все буде навпаки. Лінія по правій стороні від кожного елемента задає вихідний порт, який переважно має ті самі узгодження щодо напруги, що й вхідні порти.
Доповнення виконується інвертуючим вентилем. Трикутник позначає операцію, яка просто копіює вхід на вихід; невелике коло на виході позначає фактичну дію доповнення до входу. У цій системі позначень розташування кола біля будь-якого порту означає, що сигнал, проходячи через цей порт, буде інвертований пройшовши крізь нього, незалежно від того, вхідний це порт, чи вихідний.
Принцип двоїстості, або правила де Моргана, можна розуміти як твердження: що доповнення всіх трьох портів вентиля І перетворює його на вентиль АБО і навпаки, як показано на рисунку нижче. Доповнення обох портів інвертора залишає операцію незмінною.
Застосування
Алгебра логіки як числення двох логічних значень є основою для комп'ютерних схем, програмування комп'ютерів і математичної логіки, а також вона використовується в інших галузях математики, таких як теорія множин та статистика.
Комп'ютери
На початку 20-го століття, декілька електротехніків інтуїтивним способом зрозуміли, що булева алгебра аналогічна поведінці певних електричних схем. Клод Шеннон формально довів, що така поведінка логічно еквівалентна булевій алгебрі в 1937 році.
Сьогодні всі сучасні комп'ютери загального призначення виконують свої функції за допомогою булевої логіки двох значень; таким чином, їхні електричні кола є фізичним втіленням булевої алгебри для двох значень. Вони досягають це багатьма способами: за допомогою напруги на з'єднаннях у високочастотних схемах і ємнісних пристроях зберігання даних, за допомогою орієнтації магнітного поля у феромагнітних пристроях зберігання інформації, за допомогою перфорації в перфокартах або паперових стрічках, і так далі. (деякі перші комп'ютери використовували десяткові кола або механізми замість двозначної логіки в електричних колах.)
Звісно, можна закодувати більше ніж два символи. Наприклад, можна використати відповідні значення в 0, 1, 2, і 3 вольта, аби закодувати алфавіт із чотирьох символів, або робити отвори різного розміру в перфокартах. На практиці, обмеження щодо швидкодії, малими розмірами, низьким енергоспоживанням об'єднуються так, що вирішальним фактором стають шуми. І стає важче відрізняти символи, коли в одному місці можуть виникнути декілька можливих символів. Замість того, щоб намагатися розрізнити чотири різні напруги на дроті, інженери цифрових схем зупинилися на двох значеннях напруги, високе і низьке.
Комп'ютери використовують булеві схеми для двох значень з описаних вище причин. Самі типові архітектури комп'ютерів використовують упорядковані послідовності булевих значень, наприклад, у 32 або 64 значень, які називають бітами. 01101000110101100101010101001011. Під час програмування на машинному коді, мові асемблера, і певних інших мовах програмування, програмісти працюють з низькорівневою цифровою структурою з регістрів даних. Ці регістри працюють з рівнями напруги, за яких близьке до нуля значення напруги представляє булеве значення 0, і опорна напруга (часто +5V, +3.3V, +1.8V) задає булеве значення 1. Такі мови підтримують числові операції та логічні операції. У контексті, «числові» означає, що комп'ютер розглядатиме послідовність бітів як двійкові числа (числа з основою два) і виконуватиме арифметичні операції такі як додавання, віднімання, множення або ділення. «Логічні» відноситься до логічних булевих операцій диз'юнкції, кон'юнкції і заперечення між двома послідовностями біт, за яких кожен біт однієї послідовності простим способом порівнюється з відповідним бітом в іншій послідовності. Таким способом, програмісти мають можливість обирати як працювати, застосовуючи правила числової алгебри чи булевої алгебри залежно від потреби. Основною відмінною функцією між родинами операцій є існування операції [en] в першій алгебрі, і відсутність в останній.
Історія
Засади алгебри логіки сформулював британський математик Джордж Буль у 1847 році. Алгебра Буля передувала сучасному розвитку абстрактної алгебри і математичної логіки; і вважають, що вона пов'язана з появою обох цих галузей. В абстрактному тлумаченні, булева алгебра була розвинена в кінці 19-го століття, чому значно приклали зусилля математики Вільям Джевонс, Ернст Шредер, [en] та інші, доки вона не досягла сучасного поняття (абстрактної) математичної структури. Наприклад, емпіричні спостереження про те, що можливо маніпулювати виразами в алгебрі множин, якщо перевести їх у вирази булевої алгебри пояснюються в сучасних термінах, що алгебра множин це Булева алгебра. Насправді, М. Г. Стоун у 1936 довів, що кожна булева алгебра є ізоморфною полю множин.
У 1930-х, під час вивчення [en], Клод Шеннон помітив, що в цій темі також можна використовувати закони булевої алгебри, і запропонував комутаційну алгебру, що дозволяє аналізувати та проєктувати схеми за допомогою алгебричних методів у термінах логічних елементів. Під час розробки схемотехніки сьогодні, немає великої потреби розглядати інші булеві алгебри, тому поняття «комутаційна алгебра» і «булева алгебра» часто використовуються як взаємозамінні. Під час розробки схем комбінаційної логіки фундаментальною задачею є [en] булевих функцій. Сучасні засоби автоматизації проєктування електронних систем для інтегральних схем надвеликого рівня інтеграції часто покладаються на ефективне представлення булевих функцій, що називають (скороченими впорядкованими) двійковими діаграмами рішень для синтезу логіки та формальної верифікації.
Логічні вирази, які можна представити в класичному численні висловлювань мають [en] в булевій алгебрі. Так, термін булева логіка іноді використовується для зазначення числення висловлювань, що здійснюється в такий спосіб. Булевої алгебри не достатньо для роботи з логічними формулами, у яких використовують квантори, таких як у логіці першого порядку. Хоча розвиток математичної логіки не відповідає булевій, зв'язок між його алгеброю і логікою пізніше був закладений в основу алгебричної логіки, що також вивчає алгебричні системи багатьох інших логік. Задача про ухвалення рішень про те, чи можуть змінні даної булевої формули (висловлювання) приймати такі значення, що формула буде розрахована як істина, називається задачею здійсненності булевих формул, і є дуже вадливою для теоретичної інформатики, що є першою задачею для якої було показано, що вона має складність NP-повної задачі. Тісно пов'язана з цим модель обчислення, що відома як [en] співвідносить часову складність (алгоритму) зі [en].
Див. також
Примітки
- Алгебра логіки // Большая советская энциклопедия : в 30 т. / главн. ред. А. М. Прохоров. — 3-е изд. — М. : «Советская энциклопедия», 1969—1978. (рос.)
- (2003) [1854]. An Investigation of the Laws of Thought. Prometheus Books. ISBN .
- «The name Boolean algebra (or Boolean 'algebras') for the calculus originated by Boole, extended by Schröder, and perfected by Whitehead seems to have been first suggested by Sheffer, in 1913.» E. V. Huntington, «New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia mathematica [ 8 вересня 2017 у Wayback Machine.]», in Trans. Amer. Math. Soc. 35 (1933), 274—304; footnote, page 278.
- (1931). . Т. 3. Harvard University Press. с. 13. ISBN . Архів оригіналу за 27 липня 2020. Процитовано 7 лютого 2019.
- Givant, Steven; Halmos, Paul (2009). Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, . ISBN .
- O'Regan, Gerard (2008). . Springer. с. 33. ISBN . Архів оригіналу за 27 липня 2020. Процитовано 7 лютого 2019.
- (July 1880). I. On the Diagrammatic and Mechanical Representation of Propositions and Reasonings (PDF). . 5. 10 (59): 1—18. doi:10.1080/14786448008626877. (PDF) оригіналу за 16 травня 2017. [1] [ 2 червня 2020 у Wayback Machine.] [2] [ 3 серпня 2021 у Wayback Machine.]
- (1949). The Synthesis of Two-Terminal Switching Circuits. Bell System Technical Journal. 28: 59—98. doi:10.1002/j.1538-7305.1949.tb03624.x.
- J. Michael Dunn; Gary M. Hardegree (2001). . Oxford University Press US. с. 2. ISBN . Архів оригіналу за 6 липня 2019. Процитовано 8 лютого 2019.
- Norman Balabanian; Bradley Carlson (2001). Digital logic design principles. John Wiley. с. 39–40. ISBN ., online sample [ 29 липня 2020 у Wayback Machine.]
- Rajaraman & Radhakrishnan (1 березня 2008). . PHI Learning Pvt. Ltd. с. 65. ISBN . Архів оригіналу за 27 липня 2020. Процитовано 8 лютого 2019.
- John A. Camara (2010). . www.ppi2pass.com. с. 41. ISBN . Архів оригіналу за 27 липня 2020. Процитовано 8 лютого 2019.
- Shin-ichi Minato, Saburo Muroga (2007). Binary Decision Diagrams. У Wai-Kai Chen (ред.). The VLSI handbook (вид. 2nd). CRC Press. ISBN . chapter 29.
- Alan Parkes (2002). . Springer. с. 276. ISBN . Архів оригіналу за 27 липня 2020. Процитовано 8 лютого 2019.
- ; ; Gerard Allwein; Dave Barker-Plummer; Albert Liu (1999). Language, proof, and logic. CSLI Publications. ISBN .
- Ben Goertzel (1994). . Springer. с. 48. ISBN . Архів оригіналу за 27 липня 2020. Процитовано 8 лютого 2019.
Література
- Винберг Э. Б. Курс алгебри. — 4-е изд. — Москва : МЦНМО, 2011. — 592 с. — .(рос.)
Посилання
- А́ЛГЕБРА ЛО́ГІКИ [ 21 квітня 2016 у Wayback Machine.] //ЕСУ
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ne plutati z Bulevoyu algebroyu strukturoyu yaka takozh vzhivayetsya dlya oznachennya zagalnishoyi algebrichnoyi strukturi Algebra logiki Buleva algebra Buleva logika dvijkova logika dvijkova algebra angl Boolean algebra rozdil matematichnoyi logiki sho vivchaye sistemu logichnih operacij nad vislovlyuvannyami V algebri logiki znachennyam zminnih ye znachennya istinnosti istina abo hiba yaki zazvichaj viznachayutsya yak 1 i 0 vidpovidno Na vidminu vid elementarnoyi algebri u yakij znachennyami zminnih ye chisla a osnovnimi operaciyami ye dodavannya i mnozhennya osnovnimi operaciyami bulevoyi algebri ye kon yunkciya operaciya I angl AND poznachayetsya yak diz yunkciya ABO angl OR poznachayetsya yak i zaperechennya NI angl NOT poznachayetsya yak Takim chinom formalizm dlya opisannya logichnih vidnoshen ye analogichnim tomu yak opisuyutsya chislovi vidnoshennya v elementarnij algebri Algebra logiki Nazvano na chestDzhordzh Bul Tema vivchennya doslidzhennyabuleva algebra i buleva funkciya Algebra logiki u Vikishovishi Bulevu algebru zaproponuvav Dzhordzh Bul u svoyij knizi Matematichnij analiz logiki 1847 i bilsh detalno v nastupnij knizi en 1854 Vidpovidno do en termin Buleva algebra vpershe zaproponuvav Sheffer u 1913 hocha Charlz Sanders Pirs u 1880 dav nazvu Buleva algebra z odniyeyu staloyu pershij glavi svoyeyi knigi Najprostisha matematika Buleva algebra ye fundamentalnoyu osnovoyu dlya rozvitku cifrovoyi elektroniki i vtilena v usih movah programuvannya Vona takozh vikoristovuyetsya v teoriyi mnozhin i statistici ViznachennyaBazovimi elementami yakimi operuye algebra logiki ye vislovlyuvannya Vislovlyuvannya buduyutsya nad mnozhinoyu B displaystyle lnot displaystyle land displaystyle lor 0 1 de B neporozhnya mnozhina nad elementami yakoyi viznacheni tri operaciyi displaystyle lnot zaperechennya unarna operaciya displaystyle land kon yunkciya binarna displaystyle lor diz yunkciya binarna a logichnij nul 0 i logichna odinicya 1 konstanti Tak samo vikoristovuyutsya nazvi diz yunkt propozicionalna formula sho ye diz yunkciyeyu odnogo abo bilshe literaliv napriklad x 1 x 2 x 4 displaystyle x 1 lor neg x 2 lor x 4 kon yunktiv propozicionalna formula sho ye kon yunkciyeyu odnogo abo bilshe literaliv napriklad x 1 x 2 x 4 displaystyle x 1 land neg x 2 land x 4 Unarna operaciya zaperechennya v teksti formul oformlyayetsya abo u viglyadi znachka pered operandom x displaystyle lnot x abo u viglyadi riski nad operandom x displaystyle bar x sho kompaktnishe ale zagalom mensh pomitno Znachennya Todi yak v elementarnij algebri virazi zazvichaj virazhayutsya v chislah v algebri logiki voni virazhayut znachennya istinnosti istina i hiba Ci znachennya zadayut za dopomogoyu bitiv abo dvijkovih chisel a same 0 ta 1 Voni ne povodyat sebe tak samo yak cili chisla 0 ta 1 dlya yakih 1 1 2 a mozhut viznachatisya yak elementi en sho ye cilochiselnoyu arifmetikoyu za modulem 2 dlya yakoyi 1 1 0 Algebra logiki takozh vivchaye funkciyi sho prijmayut znachennya v mnozhini 0 1 Predmet vivchennya Spochatku problematika algebri logiki peretinalasya z problematikoyu algebri mnozhin teoretiko mnozhinni operaciyi Prote iz zakinchennyam formuvannya teoriyi mnozhin 70 i roki 19 st do skladu yakoyi vhodila algebra mnozhin i podalshim rozvitkom matematichnoyi logiki predmet algebri logiki znachno zminivsya Suchasna algebra logiki rozglyadaye operaciyi nad vislovlyuvannyami div Chislennya vislovlen yak bulevu funkciyu i vivchaye vidnosno nih taki pitannya yak tablici istinnosti funkcionalna povnota zamkneni klasi predstavlennya u viglyadi DNF KNF polinoma Zhegalkina OperaciyiBazovi operaciyi Yak uzhe zaznachalosya bazovimi operaciyami bulevoyi algebri algebri logiki ye taki logichni operaciyi I kon yunkciya poznachayetsya x y inodi x I y zadovolnyaye x y 1 yaksho x y 1 ta x y 0 v inshih vipadkah ABO diz yunkciya poznachayetsya x y inodi x ABO y zadovolnyaye x y 0 yaksho x y 0 ta x y 1 v inshih vipadkah NI zaperechennya poznachayetsya x inodi NE x abo x zadovolnyaye x 0 yaksho x 1 ta x 1 yaksho x 0 Alternativnim sposobom znachennya x y x y ta x mozhna predstaviti v tablichnomu viglyadi dlya vsih mozhlivih znachen za dopomogoyu tablic istinnosti takim sposobom x displaystyle x y displaystyle y x y displaystyle x wedge y x y displaystyle x vee y 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 x displaystyle x x displaystyle neg x 0 1 1 0 Yaksho znachennya istinnosti 0 ta 1 interpretuvati yak cili chisla ci operaciyi mozhna bulo zadati yak zvichajni operaciyi arifmetiki de x y vikoristovuye dodavannya a xy vikoristovuye mnozhennya abo yak funkciyi minimumu maksimumu x y x y min x y x y x y x y max x y x 1 x displaystyle begin aligned x wedge y amp xy min x y x vee y amp x y xy max x y neg x amp 1 x end aligned Mozhna vvazhati sho lishe zaperechennya i odna z dvoh operacij sho zalishilisya ye bazovimi oskilki nastupni rivnyannya dozvolyayut viznachiti kon yunkciyu cherez operaciyi zaperechennya ta diz yunkciyu i navpaki x y x y x y x y displaystyle begin aligned x wedge y amp neg neg x vee neg y x vee y amp neg neg x wedge neg y end aligned Vtorinni operaciyi Tri bulevi operaciyi opisani vishe nazivayut bazovimi abo pervinnimi sho oznachaye sho voni mozhut buti bazisom dlya vsih inshih bulevih operacij oskilki vsi inshi operaciyi mozhna viraziti cherez nih za dopomogoyu kompoziciyi Sered operacij yaki mozhna pobuduvati z bazovih operacij ye taki x y x y displaystyle x rightarrow y neg x vee y x y x y x y x y x y displaystyle x oplus y x vee y wedge neg x wedge y x wedge neg y vee neg x wedge y x y x y x y x y displaystyle x equiv y neg x oplus y x wedge y vee neg x wedge neg y Ci viznachennya dayut taki tablici istinnosti u yakih pokazani znachennya cih operacij dlya vsih mozhlivih vhidnih znachen x displaystyle x y displaystyle y x y displaystyle x rightarrow y x y displaystyle x oplus y x y displaystyle x equiv y 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 Persha operaciya x y nazivayetsya implikaciyeyu Yaksho x ye istinnim todi za znachennya virazu x y prijmayetsya znachennya y Ale yaksho x prijmaye hibne znachennya to znachennya y mozhna bulo b ignoruvati odnak cya operaciya povinna povernuti deyake logichne znachennya i isnuye lishe dva varianti viboru To zh za viznachennyam x y ye istinoyu koli x ye hibnim Druga operaciya x y nazivayetsya viklyuchnoyu diz yunkciyeyu chasto zadayetsya yak abreviatura XOR abi vidrizniti yiyi vid diz yunkciyi Vona ye istinoyu lishe koli x ta y rizni Tretya operaciya obernena do viklyuchnoyi diz yunkciyi nazivayetsya ekvivalentnist abo buleva rivnist x y bude istinoyu lishe koli x ta y mayut odnakove znachennya Dlya dvoh danih operandiv kozhen z yakih maye 22 4 mozhlivih kombinaciyi vhodiv Oskilki kozhen vihid mozhe mati dva mozhlivih znachennya isnuye zagalom 24 16 mozhlivih bulevih operacij ZakoniZakonom u bulevij algebri mozhe vistupati totozhnist mizh dvoma bulevimi virazami takogo viglyadu yak x y z x y z de bulevij viraz abo logichne vislovlyuvannya viznachayetsya yak viraz sho pobudovanij zi zminnih ta konstant 0 ta 1 ta operacij mizh nimi ta Ce ponyattya mozhna poshiriti j do viraziv sho mistyat inshi bulevi operaciyi taki yak ta ale dlya formulyuvannya zakoniv take rozshirennya operacij ne ye neobhidnim Dlya takih cilej dodayut viznachennya bulevoyi algebri yak bud yakoyi modeli bulevih zakoniv i yak zasib dlya vivedennya novih zakoniv z nayavnih yak napriklad dovedennya sho x y z x z y z y z z y Zakoni monotonnosti Buleva algebra zadovolnyaye bagatom vidpovidnim zakonam zvichajnoyi algebri yaksho zistaviti operaciyi z dodavannyam a z mnozhennyam Zokrema taki zakoni ye spilnimi dlya oboh tipiv algebr Asociativnist operaciyi displaystyle vee x y z displaystyle x vee y vee z x y z displaystyle x vee y vee z Asociativnist operaciyi displaystyle wedge x y z displaystyle x wedge y wedge z x y z displaystyle x wedge y wedge z Komutativnist operaciyi displaystyle vee x y displaystyle x vee y y x displaystyle y vee x Komutativnist operaciyi displaystyle wedge x y displaystyle x wedge y y x displaystyle y wedge x Distributivnist operaciyi displaystyle wedge over displaystyle vee x y z displaystyle x wedge y vee z x y x z displaystyle x wedge y vee x wedge z Identichnist dlya displaystyle vee x 0 displaystyle x vee 0 x displaystyle x Identichnist dlya displaystyle wedge x 1 displaystyle x wedge 1 x displaystyle x Anigilyator dlya displaystyle wedge x 0 displaystyle x wedge 0 0 displaystyle 0 Taki zakoni ye dijsnimi v bulevij algebri ale ne dijsni u zvichajnij algebri Anigilyator dlya displaystyle vee x 1 displaystyle x vee 1 1 displaystyle 1 Idempotentnist displaystyle vee x x displaystyle x vee x x displaystyle x Idempotentnist displaystyle wedge x x displaystyle x wedge x x displaystyle x Absorbciya 1 x x y displaystyle x wedge x vee y x displaystyle x Absorbciya 2 x x y displaystyle x vee x wedge y x displaystyle x Distributivnist operaciyi displaystyle vee nad displaystyle wedge x y z displaystyle x vee y wedge z x y x z displaystyle x vee y wedge x vee z Yaksho prijnyati x 2 v tretomu navedenomu vishe zakoni mi bachimo sho ce ne zakon zi zvichajnoyi algebri oskilki 2 2 4 Reshta p yat zakoniv mozhna falsifikuvati u zvichajnij algebri yaksho prijnyati sho znachennya vsih zminnih bude 1 napriklad u zakoni absorbciyi 1 liva storona vidnoshennya bula b 1 1 1 2 a prava chastina rivnyannya bula 1 i tak dali Usi ci zakoni sho rozglyadalisya dosi buli dlya kon yunkciyi ta diz yunkciyi Ci dvi operaciyi mayut vlastivist sho za zmini bud yakogo z argumentiv vihid zalishitsya abo nezminnim abo zminit svoye znachennya tak samo yak vhid Analogichno zmina znachennya bud yakoyi zminnoyi z 0 na 1 nikoli ne prizvede do togo sho vihid zminit svoye znachennya z 1 na 0 Operaciyi z takoyu vlastivistyu nazivayut monotonnimi Takim robom usi aksiomi dosi buli dlya monotonnoyi bulevoyi logiki Nemonotonnist z yavlyayetsya cherez operaciyu dopovnennya sho navedeno dali Zakoni nemonotonnosti Operaciya dopovnennya zaperechennya viznachayetsya takimi dvoma zakonami Dopovnennya 1 x x 0 Dopovnennya 2 x x 1 displaystyle begin aligned amp text Dopovnennya 1 amp x wedge neg x amp 0 amp text Dopovnennya 2 amp x vee neg x amp 1 end aligned Usi vlastivosti zaperechennya zokrema zakoni sho navedeni nizhche viplivayut z dvoh vishenavedenih zakoniv Yak u zvichajnij tak i v bulevij algebri operaciya zaperechennya pracyuye yak obmin pari elementiv tomu v oboh algebrah vona zadovolnyaye zakonu podvijnogo zaperechennya takozh nazivayetsya zakonom involyuciyi Podvijne zaperechennya x x displaystyle begin aligned amp text Podvijne zaperechennya amp neg neg x amp x end aligned Ale todi yak zvichajna algebra zadovolnyaye takim dvom zakonam x y x y x y x y displaystyle begin aligned x y amp xy x y amp x y end aligned buleva algebra zadovolnyaye zakonam de Morgana de Morgana 1 x y x y de Morgana 2 x y x y displaystyle begin aligned amp text de Morgana 1 amp neg x wedge neg y amp neg x vee y amp text de Morgana 2 amp neg x vee neg y amp neg x wedge y end aligned Povnota Zakoni opisani vishe viznachayut bulevu algebru v tomu sensi sho z nih viplivayut usi inshi naslidki Dlya cogo dostatno zakoniv dopovnennya 1 ta 2 razom iz zakonami monotonnosti Otzhe yih mozhna vvazhati povnoyu mnozhinoyu zakoniv abo odniyeyu z mozhlivih sistem aksiomatizaciyi bulevoyi algebri Kozhen zakon bulevoyi algebri viplivaye logichnim chinom iz cih aksiom Krim togo bulevi algebri mozhna viznachiti yak modeli z cih aksiom Princip dvoyistosti Princip Yaksho X R chastkovo vporyadkovana mnozhina todi X R obernena takozh chastkovo vporyadkovana mnozhina Niyakoyi magiyi u vibori simvoliv dlya poznachennya logichnih znachen bulevoyi algebri ne isnuye Zamist 0 i 1 mozhna bulo b vikoristovuvati napriklad a ta b doki mi robimo ce poslidovnim chinom povsyudi ce dosi zalishatimetsya bulevoyu algebroyu ale z yavnimi zovnishnimi vidminnostyami Pripustimo takozh sho mi perenazvali 0 ta 1 vidpovidno na 1 ta 0 Todi ce takozh zalishatimetsya bulevoyu algebroyu sho navit operuye z timi samimi znachennyami Odnak vona ne bude identichnoyu do nashoyi pochatkovoyi bulevoyi algebri oskilki teper operaciya povoditimetsya tak yak povodila sebe operaciya i navpaki Tozh voni takozh matimut zovnishni vidminnosti yaki pokazuyut sho mi zminili poznachennya ne divlyachis na te sho mi dosi vikoristovuyemo 0 i ta 1 i Ale yaksho v dodatok do togo sho mi zaminili miscyami imena zminnih mi zaminimo miscyami imena dvoh dvijkovih operacij teper nemaye niyakogo slidu vid togo sho mi zrobili Kincevij rezultat povnistyu ne vidriznyayetsya vid togo z chogo mi pochali Mi pomitimo sho kolonki dlya operacij x y ta x y u tablicyah istinnosti zminili svoyi miscya ale cya vidminnist ye neznachnoyu Koli isnuye taka para operacij dlya yakih use zalishayetsya nezminnim yaksho vsi pari buli odnochasno vzayemno zmineni mi nazivayemo taki elementi kozhnoyi pari dvoyistimi odin z odnim U takij sposib 0 ta 1 ye dvoyistimi i operaciyi ta takozh ye dvoyistimi Princip dvoyistosti takozh nazivayut dvoyististyu de Morgana za yakoyu stverdzhuyut sho buleva algebra zalishayetsya nezminnoyu yaksho vzayemno zaminiti vsi dvoyisti pari Aksiomix x displaystyle bar bar x x involyutivnist zaperechennya zakon znyattya podvijnogo zaperechennya x x 1 displaystyle x lor bar x 1 x 1 1 displaystyle x lor 1 1 x x x displaystyle x lor x x x 0 x displaystyle x lor 0 x x x 0 displaystyle x land bar x 0 x x x displaystyle x land x x x 0 0 displaystyle x land 0 0 x 1 x displaystyle x land 1 x Logichni operaciyiProstim i najshirshe vzhivanim prikladom takoyi algebrichnoyi sistemi ye mnozhina B sho skladayetsya vsogo z dvoh elementiv B Hiba 0 Istina 1 Zazvichaj u matematichnih virazah Hiba ototozhnyuyetsya z logichnim nulem a Istina z logichnoyu odiniceyu a operaciyi zaperechennya NI kon yunkciyi I ta diz yunkciyi ABO viznachayutsya u zvichnomu nam rozuminni Legko pokazati sho na cij mnozhini B mozhna zadati chotiri unarni ta shistnadcyat binarnih vidnoshen i vsi yih mozhe buti otrimano cherez superpoziciyu troh obranih operacij Spirayuchis na cej matematichnij instrumentarij logika vislovlyuvan vivchaye vislovlyuvannya i predikati Takozh zaprovadzhuyutsya dodatkovi operaciyi taki yak ekvivalentnist displaystyle leftrightarrow todi j lishe todi koli implikaciya displaystyle rightarrow otzhe skladannya po modulyu dva displaystyle oplus viklyuchna diz yunkciya shtrih Shefera displaystyle mid strilka Pirsa displaystyle downarrow ta inshi Logika vislovlyuvan posluguvala osnovnim matematichnim instrumentom pid chas stvorennya komp yuteriv Vona legko peretvoryuyetsya v bitovu logiku istinnist vislovlyuvannya poznachayetsya odnim bitom 0 HIBA 1 ISTINA todi operaciya displaystyle neg nabuvaye suti virahuvannya z odinici displaystyle lor nemodulnogo dodavannya amp mnozhennya displaystyle leftrightarrow rivnosti displaystyle oplus u bukvalnomu rozuminni suma za modulem 2 viklyuchne ABO XOR displaystyle mid suma ne perevishuye 1 tobto A displaystyle mid B A B lt 1 Zgodom bulevu algebru bulo uzagalneno vid logiki vislovlyuvan cherez zaprovadzhennya harakternih dlya logiki vislovlyuvan aksiom Ce dozvolilo rozglyadati napriklad logiku kubitiv triznachnu logiku koli ye tri varianti istinnosti vislovlyuvannya istina hiba i neviznacheno tosho Vlastivosti logichnih operacijKomutativnist x displaystyle circ y y displaystyle circ x displaystyle circ in amp displaystyle lor oplus sim mid downarrow Idempotentnist x displaystyle circ x x displaystyle circ in amp displaystyle lor Asociativnist x displaystyle circ y displaystyle circ z x displaystyle circ y displaystyle circ z displaystyle circ in amp displaystyle lor oplus sim Distributivnist kon yunkcij i diz yunkciyi vidnosno diz yunkciyi kon yunkciyi i sumi za modulem dva vidpovidno x y z x y x z displaystyle x land y lor z x land y lor x land z x y z x y x z displaystyle x lor y land z x lor y land x lor z x y z x y x z displaystyle x land y oplus z x land y oplus x land z Zakoni de Mo rgana x y x y displaystyle overline x land y bar x lor bar y x y x y displaystyle overline x lor y bar x land bar y Zakoni poglinannya x x y x displaystyle x land x lor y x x x y x displaystyle x lor x land y x Inshi 1 x x x 0 x x 0 displaystyle x land bar x x land 0 x oplus x 0 x x x 1 x x x x 1 displaystyle x lor bar x x lor 1 x sim x x rightarrow x 1 x x x x x 1 x 0 x 0 x displaystyle x lor x x land x x land 1 x lor 0 x oplus 0 x x 1 x 0 x 0 x x x x x displaystyle x oplus 1 x rightarrow 0 x sim 0 x mid x x downarrow x bar x x x displaystyle bar bar x x involyutivnist zaperechennya zakon znyattya podvijnogo zaperechennya Inshi 2 x y x y x y x y x y displaystyle x oplus y x land bar y lor bar x land y x lor y land bar x lor bar y x y x y 1 x y x y x y x y x y displaystyle x sim y overline x oplus y 1 oplus x oplus y x land y lor bar x land bar y x lor bar y land bar x lor y x y x y x y x 1 displaystyle x rightarrow y bar x lor y x land y oplus x oplus 1 x y x y x y displaystyle x lor y x oplus y oplus x land y Inshi 3 Dopovnennya zakoniv de Mo rgana x y x y x y displaystyle x mid y overline x land y bar x lor bar y x y x y x y displaystyle x downarrow y overline x lor y bar x land bar y Isnuyut metodi sproshennya logichnoyi funkciyi napriklad Karta Karno metod Kuajna Mak KlaskiPredstavlennya u viglyadi diagramDiagrama Venna Diagrama Venna ce grafichne predstavlennya bulevih operacij za dopomogoyu zafarbovanih oblastej sho perekrivayutsya Po odnij oblasti dlya kozhnoyi zminnoyi vsi oblasti krugli yak pokazano na prikladah Vnutrishnya j zovnishnya chastina oblasti x vidpovidaye znachennyam 1 istina ta 0 hiba vidpovidno dlya zminnoyi x Zafarbovana oblast pokazuye znachennya operaciyi dlya kozhnoyi kombinaciyi cih oblastej de zafarbovana oblast oznachaye 1 a ne zafarbovana 0 ale v deyakih knizhkah mozhe zustritisya i navpaki Diagrami Venna na malyunku znizu pokazuyut operaciyi kon yunkciyi x y diz yunkciyi x y ta dopovnennya x Diagrami Venna dlya kon yunkciyi diz yunkciyi ta dopovnennya Dlya kon yunkciyi region u seredini dvoh krugiv zafarbovanij sho oznachaye sho viraz x y dorivnyuye 1 koli obidvi zminni mayut znachennya 1 Inshi oblasti lishilisya ne zafarbovanimi abi zaznachiti sho x y dorivnyuye 0 dlya vsih inshih kombinacij Na drugij diagrami sho pokazuye diz yunkciyu x y zafarbovana oblast sho znahoditsya v seredini dvoh kil odnochasno Tretya diagrama predstavlyaye dopovnennya x de zafarbovana oblast ne v seredini kola Tut ne pokazani diagrami dlya stalih 0 ta 1 oskilki voni trivialni ta predstavlyayutsya nezafarbovanim abo zafarbovanim pryamokutnikom bez kil u seredini Odnak mi b mogli rozmistiti kolo dlya zminnoyi x u cih pryamokutnikah u takomu razi ce b poznachalo funkciyu z odnim argumentom x sho poznachaye te same znachennya nezalezhno vid x sho nazivayetsya konstantnoyu funkciyeyu Sho stosuyetsya rezultativ funkcij to konstanti j konstantni funkciyi ne vidriznyayutsya yihnya vidminnist polyagaye v tomu sho konstanta ne prijmaye niyakih argumentiv i nazivayetsya nulovoyu operaciyeyu todi yak konstantna funkciya prijmaye odin argument yakij ignoruyetsya i tomu ye unarnoyu operaciyeyu Diagrami Venna ye korisnimi dlya vizualizaciyi zakoniv Zakoni komutativnosti dlya ta mozhna pobachiti iz simetrichnosti diagram binarna operaciya sho ne ye komutativnoyu ne mala b simetrichnoyi diagrami oskilki zamina miscyami x ta y prizvelo do gorizontalnogo viddzerkalennya diagrami i vidsutnist komutativnosti b vidznachilasya v ne simetrichnosti diagrami Idempotentnist operacij ta mozhna bulo b zobraziti zsunuvshi dva kola razom i zaznachivshi sho zafarbovana oblast todi staye cilim kolom yak oboh ta Cifrovi logichni kola Cifrova logika zastosovuye bulevu algebru dlya 0 ta 1 do elektronnoyi aparaturi sho skladayetsya iz z yednanih mizh soboyu logichnih elementiv i yaki utvoryuyut elektrichnu shemu Kozhnij element vikonuye bulevu operaciyu i v riznih sistemah poznachen poznachayetsya tak sho jogo viglyad identifikuye pevnu operaciyu Formi poznachen dlya elementiv sho poznachayut kon yunkciyu I ventil diz yunkciyu ABO ventil i dopovnennya invertori viglyadayut tak Liniyi po livij storoni kozhnogo elementa poznachayut vhidni z yednannya abo porti Znachennya na vhodi zadayetsya naprugoyu Dlya tak zvanoyi logiki z aktivnim visokim rivnem 0 zadayetsya znachennyam naprugi blizkim do nulya abo zemli todi yak 1 zadayetsya znachennyam naprugi blizkim do dzherela naprugi za aktivnogo nizkogo rivnya vse bude navpaki Liniya po pravij storoni vid kozhnogo elementa zadaye vihidnij port yakij perevazhno maye ti sami uzgodzhennya shodo naprugi sho j vhidni porti Dopovnennya vikonuyetsya invertuyuchim ventilem Trikutnik poznachaye operaciyu yaka prosto kopiyuye vhid na vihid nevelike kolo na vihodi poznachaye faktichnu diyu dopovnennya do vhodu U cij sistemi poznachen roztashuvannya kola bilya bud yakogo portu oznachaye sho signal prohodyachi cherez cej port bude invertovanij projshovshi kriz nogo nezalezhno vid togo vhidnij ce port chi vihidnij Princip dvoyistosti abo pravila de Morgana mozhna rozumiti yak tverdzhennya sho dopovnennya vsih troh portiv ventilya I peretvoryuye jogo na ventil ABO i navpaki yak pokazano na risunku nizhche Dopovnennya oboh portiv invertora zalishaye operaciyu nezminnoyu ZastosuvannyaAlgebra logiki yak chislennya dvoh logichnih znachen ye osnovoyu dlya komp yuternih shem programuvannya komp yuteriv i matematichnoyi logiki a takozh vona vikoristovuyetsya v inshih galuzyah matematiki takih yak teoriya mnozhin ta statistika Komp yuteri Na pochatku 20 go stolittya dekilka elektrotehnikiv intuyitivnim sposobom zrozumili sho buleva algebra analogichna povedinci pevnih elektrichnih shem Klod Shennon formalno doviv sho taka povedinka logichno ekvivalentna bulevij algebri v 1937 roci Sogodni vsi suchasni komp yuteri zagalnogo priznachennya vikonuyut svoyi funkciyi za dopomogoyu bulevoyi logiki dvoh znachen takim chinom yihni elektrichni kola ye fizichnim vtilennyam bulevoyi algebri dlya dvoh znachen Voni dosyagayut ce bagatma sposobami za dopomogoyu naprugi na z yednannyah u visokochastotnih shemah i yemnisnih pristroyah zberigannya danih za dopomogoyu oriyentaciyi magnitnogo polya u feromagnitnih pristroyah zberigannya informaciyi za dopomogoyu perforaciyi v perfokartah abo paperovih strichkah i tak dali deyaki pershi komp yuteri vikoristovuvali desyatkovi kola abo mehanizmi zamist dvoznachnoyi logiki v elektrichnih kolah Zvisno mozhna zakoduvati bilshe nizh dva simvoli Napriklad mozhna vikoristati vidpovidni znachennya v 0 1 2 i 3 volta abi zakoduvati alfavit iz chotiroh simvoliv abo robiti otvori riznogo rozmiru v perfokartah Na praktici obmezhennya shodo shvidkodiyi malimi rozmirami nizkim energospozhivannyam ob yednuyutsya tak sho virishalnim faktorom stayut shumi I staye vazhche vidriznyati simvoli koli v odnomu misci mozhut viniknuti dekilka mozhlivih simvoliv Zamist togo shob namagatisya rozrizniti chotiri rizni naprugi na droti inzheneri cifrovih shem zupinilisya na dvoh znachennyah naprugi visoke i nizke Komp yuteri vikoristovuyut bulevi shemi dlya dvoh znachen z opisanih vishe prichin Sami tipovi arhitekturi komp yuteriv vikoristovuyut uporyadkovani poslidovnosti bulevih znachen napriklad u 32 abo 64 znachen yaki nazivayut bitami 01101000110101100101010101001011 Pid chas programuvannya na mashinnomu kodi movi asemblera i pevnih inshih movah programuvannya programisti pracyuyut z nizkorivnevoyu cifrovoyu strukturoyu z registriv danih Ci registri pracyuyut z rivnyami naprugi za yakih blizke do nulya znachennya naprugi predstavlyaye buleve znachennya 0 i oporna napruga chasto 5V 3 3V 1 8V zadaye buleve znachennya 1 Taki movi pidtrimuyut chislovi operaciyi ta logichni operaciyi U konteksti chislovi oznachaye sho komp yuter rozglyadatime poslidovnist bitiv yak dvijkovi chisla chisla z osnovoyu dva i vikonuvatime arifmetichni operaciyi taki yak dodavannya vidnimannya mnozhennya abo dilennya Logichni vidnositsya do logichnih bulevih operacij diz yunkciyi kon yunkciyi i zaperechennya mizh dvoma poslidovnostyami bit za yakih kozhen bit odniyeyi poslidovnosti prostim sposobom porivnyuyetsya z vidpovidnim bitom v inshij poslidovnosti Takim sposobom programisti mayut mozhlivist obirati yak pracyuvati zastosovuyuchi pravila chislovoyi algebri chi bulevoyi algebri zalezhno vid potrebi Osnovnoyu vidminnoyu funkciyeyu mizh rodinami operacij ye isnuvannya operaciyi en v pershij algebri i vidsutnist v ostannij IstoriyaZasadi algebri logiki sformulyuvav britanskij matematik Dzhordzh Bul u 1847 roci Algebra Bulya pereduvala suchasnomu rozvitku abstraktnoyi algebri i matematichnoyi logiki i vvazhayut sho vona pov yazana z poyavoyu oboh cih galuzej V abstraktnomu tlumachenni buleva algebra bula rozvinena v kinci 19 go stolittya chomu znachno priklali zusillya matematiki Vilyam Dzhevons Ernst Shreder en ta inshi doki vona ne dosyagla suchasnogo ponyattya abstraktnoyi matematichnoyi strukturi Napriklad empirichni sposterezhennya pro te sho mozhlivo manipulyuvati virazami v algebri mnozhin yaksho perevesti yih u virazi bulevoyi algebri poyasnyuyutsya v suchasnih terminah sho algebra mnozhin ce Buleva algebra Naspravdi M G Stoun u 1936 doviv sho kozhna buleva algebra ye izomorfnoyu polyu mnozhin U 1930 h pid chas vivchennya en Klod Shennon pomitiv sho v cij temi takozh mozhna vikoristovuvati zakoni bulevoyi algebri i zaproponuvav komutacijnu algebru sho dozvolyaye analizuvati ta proyektuvati shemi za dopomogoyu algebrichnih metodiv u terminah logichnih elementiv Pid chas rozrobki shemotehniki sogodni nemaye velikoyi potrebi rozglyadati inshi bulevi algebri tomu ponyattya komutacijna algebra i buleva algebra chasto vikoristovuyutsya yak vzayemozaminni Pid chas rozrobki shem kombinacijnoyi logiki fundamentalnoyu zadacheyu ye en bulevih funkcij Suchasni zasobi avtomatizaciyi proyektuvannya elektronnih sistem dlya integralnih shem nadvelikogo rivnya integraciyi chasto pokladayutsya na efektivne predstavlennya bulevih funkcij sho nazivayut skorochenimi vporyadkovanimi dvijkovimi diagramami rishen dlya sintezu logiki ta formalnoyi verifikaciyi Logichni virazi yaki mozhna predstaviti v klasichnomu chislenni vislovlyuvan mayut en v bulevij algebri Tak termin buleva logika inodi vikoristovuyetsya dlya zaznachennya chislennya vislovlyuvan sho zdijsnyuyetsya v takij sposib Bulevoyi algebri ne dostatno dlya roboti z logichnimi formulami u yakih vikoristovuyut kvantori takih yak u logici pershogo poryadku Hocha rozvitok matematichnoyi logiki ne vidpovidaye bulevij zv yazok mizh jogo algebroyu i logikoyu piznishe buv zakladenij v osnovu algebrichnoyi logiki sho takozh vivchaye algebrichni sistemi bagatoh inshih logik Zadacha pro uhvalennya rishen pro te chi mozhut zminni danoyi bulevoyi formuli vislovlyuvannya prijmati taki znachennya sho formula bude rozrahovana yak istina nazivayetsya zadacheyu zdijsnennosti bulevih formul i ye duzhe vadlivoyu dlya teoretichnoyi informatiki sho ye pershoyu zadacheyu dlya yakoyi bulo pokazano sho vona maye skladnist NP povnoyi zadachi Tisno pov yazana z cim model obchislennya sho vidoma yak en spivvidnosit chasovu skladnist algoritmu zi en Div takozhBuleva mnozhina Buleva funkciya Tablici istinnosti Pravila de Morgana Karta Karno Metod Kuajna Mak Klaski Relyacijna algebra Bulevi operaciyi nad mnogokutnikamiPrimitkiAlgebra logiki Bolshaya sovetskaya enciklopediya v 30 t glavn red A M Prohorov 3 e izd M Sovetskaya enciklopediya 1969 1978 ros 2003 1854 An Investigation of the Laws of Thought Prometheus Books ISBN 978 1 59102 089 9 The name Boolean algebra or Boolean algebras for the calculus originated by Boole extended by Schroder and perfected by Whitehead seems to have been first suggested by Sheffer in 1913 E V Huntington New sets of independent postulates for the algebra of logic with special reference to Whitehead and Russell s Principia mathematica 8 veresnya 2017 u Wayback Machine in Trans Amer Math Soc 35 1933 274 304 footnote page 278 1931 T 3 Harvard University Press s 13 ISBN 978 0 674 13801 8 Arhiv originalu za 27 lipnya 2020 Procitovano 7 lyutogo 2019 Givant Steven Halmos Paul 2009 Introduction to Boolean Algebras Undergraduate Texts in Mathematics Springer ISBN 978 0 387 40293 2 O Regan Gerard 2008 Springer s 33 ISBN 978 1 84800 083 4 Arhiv originalu za 27 lipnya 2020 Procitovano 7 lyutogo 2019 July 1880 I On the Diagrammatic and Mechanical Representation of Propositions and Reasonings PDF 5 10 59 1 18 doi 10 1080 14786448008626877 PDF originalu za 16 travnya 2017 1 2 chervnya 2020 u Wayback Machine 2 3 serpnya 2021 u Wayback Machine 1949 The Synthesis of Two Terminal Switching Circuits Bell System Technical Journal 28 59 98 doi 10 1002 j 1538 7305 1949 tb03624 x J Michael Dunn Gary M Hardegree 2001 Oxford University Press US s 2 ISBN 978 0 19 853192 0 Arhiv originalu za 6 lipnya 2019 Procitovano 8 lyutogo 2019 Norman Balabanian Bradley Carlson 2001 Digital logic design principles John Wiley s 39 40 ISBN 978 0 471 29351 4 online sample 29 lipnya 2020 u Wayback Machine Rajaraman amp Radhakrishnan 1 bereznya 2008 PHI Learning Pvt Ltd s 65 ISBN 978 81 203 3409 0 Arhiv originalu za 27 lipnya 2020 Procitovano 8 lyutogo 2019 John A Camara 2010 www ppi2pass com s 41 ISBN 978 1 59126 166 7 Arhiv originalu za 27 lipnya 2020 Procitovano 8 lyutogo 2019 Shin ichi Minato Saburo Muroga 2007 Binary Decision Diagrams U Wai Kai Chen red The VLSI handbook vid 2nd CRC Press ISBN 978 0 8493 4199 1 chapter 29 Alan Parkes 2002 Springer s 276 ISBN 978 1 85233 464 2 Arhiv originalu za 27 lipnya 2020 Procitovano 8 lyutogo 2019 Gerard Allwein Dave Barker Plummer Albert Liu 1999 Language proof and logic CSLI Publications ISBN 978 1 889119 08 3 Ben Goertzel 1994 Springer s 48 ISBN 978 0 306 44690 0 Arhiv originalu za 27 lipnya 2020 Procitovano 8 lyutogo 2019 LiteraturaVinberg E B Kurs algebri 4 e izd Moskva MCNMO 2011 592 s ISBN 978 5 94057 685 3 ros PosilannyaA LGEBRA LO GIKI 21 kvitnya 2016 u Wayback Machine ESU