Тема даної статті – особлива гілка алгебри, у якій значення змінних є істинними і помилковими, зазвичай обозначаемыми 1 і 0 відповідно. Замість класичної математики, де значення змінних є числами, а простими операціями вважаються додавання і множення, основними завданнями алгебри логіки є кон’юнкція і позначається, як ∧; диз’юнкція позиціонується, як ∨, а заперечення не записується як .

Походження

Алгебра логіки була введена Джорджем Булем і більш повно викладена в його праці «Дослідження законів мислення» (1854). Згідно Хантингтону, сам термін був вперше запропонований Шеффером в 1913 році. В наших широтах він не закріпився. Алгебра логіки була фундаментальній в розвитку цифрової електроніки.

Історія досліджень

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

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

Особливості

У той час як в елементарній алгебрі вираження позначають в основному числа, в мові алгебри логіки вони позначають істинні значення false та true. Ці значення представлені бітами (або двійковими цифрами). Вони можуть бути ідентифіковані з елементами двухэлементного поля GF (2), тобто цілочисельна арифметика по модулю 2. Потім додавання і множення грають булеву роль XOR (виключає або) і AND (кон’юнкція) відповідно, з диз’юнкцією x∨y (включно) або визначається як x + y – xy.

Алгебра логіки висловлювання також має справу з функціями, значення яких знаходяться в множині {0, 1}. Послідовність бітів є зазвичай використовуваної такою функцією. Іншим поширеним прикладом є підмножина множини E: наприклад, з F E пов’язана функція індикатора, яка приймає значення 1 на F і 0 за межами його. Найбільш загальний приклад – це елементи булевої алгебри з усіма наведеними вище прикладами.

Як і у випадку елементарної алгебри, чисто эквациональная частина теорії може бути розроблена без врахування явних значень змінних.

Закони та принципи

Закон булевої алгебри – це тотожність. Булев термін визначається як вираження, побудоване з змінних і констант 0 і 1 з використанням операції ∧, ∨ і . Концепція може бути розширена до термінів, що включають інші булеві операції, такі як ⊕, →≡, але такі розширення не потрібні для цілей, до яких застосовуються закони. Такі цілі включають визначення булевої алгебри, як будь-якої моделі з цих законів і як засіб для виведення нових показників з старих, як описано в розділі про аксиоматизации.

Прийняття x = 2 у третьому законі показує, що це не звичайний канон алгебри, оскільки 2 × 2 = 4. Решта п’ять законів можуть бути фальсифіковані у звичайній точної науки, якщо взяти всі змінні рівними 1.

Новаторська роль

Всі закони, які розглядалися досі, стосувалися з’єднання і диз’юнкції. Ці операції мають властивість, що полягає в тому, що зміна або аргументу, або вихідних показників залишає останні без змін, або вихідні дані змінюються так само, як і вхідні. Еквівалентно, зміна будь-якої змінної від 0 до 1 ніколи не призводить до зміни виводу з 1 на 0. Операції з цією властивістю називаються монотонними. Таким чином, аксіоми досі існували для монотонної булевої логіки. Немонотонність набирає чинності через додаток наступним чином:

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

Пояснення

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

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

Принцип: якщо {X, R} є набором, то {X, R (зворотний)} також є набором.

Зміни

Одним із змін, яке нам не потрібно було вносити в рамках цього обміну, було доповнення. Ми говоримо, що додаток є самодвойственной операцією, наприклад, «тотожність» або «нічого не робити» x (копіювання введення на вихід) також є такою.

Принцип двоїстості можна пояснити з точки зору теорії груп тим, що існує рівно чотири функції, які є взаємно однозначними відображеннями (автоморфизмами) безлічі булевих многочленів назад в себе:

• одинична;
• доповнення;
• подвійна функція;
• протилежна (доповнена двоїстої).

Ці 4 функції утворюють групу під загальною композицією, изоморфную чотиризначному аналогу Клейна, що діє на множині булевих многочленів. Уолтер Готшалк зазначив, що, отже, більш відповідна назва для цього явища буде принципом (або квадратом) кватернальности. Спори про цих квадратах не вщухають між математиками до сьогоднішнього дня.

Діаграма Венна

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

• Внутрішня і зовнішня частини області x відповідають значенням 1 (правда) і 0 (брехня) для змінної x.
• Затінення вказує на значення операції для кожної комбінації регіонів, де темний позначає 1, а світлий 0.

Три діаграми Венна на малюнку нижче представляють відповідно кон’юнкцію x∧y, диз’юнкцію x∨y і доповнення x.

Для з’єднання область всередині обох кіл заштрихована, щоб вказати, що x∧y дорівнює 1, коли обидві змінні дорівнюють 1. Інші відділи залишаються не заштрихованными, щоб вказати, що x∧y дорівнює 0 для трьох інших комбінацій. Ця математична модель дуже корисна для того, щоб вивчати складні і абстрактні закони логіки з допомогою рахунки і множення численних цифр, а також інших обчислювальних операцій. Таким чином, це низведення філософської логіки на більш конкретний математичний рівень.

Хоча ми не показали діаграм Венна для констант 0 і 1, вони тривіальні і являють собою відповідно білий і темний прямокутники, причому жоден з них не містить коло. Однак ми можемо поставити гурток для x у цих полях, і в цьому випадку кожен з них буде позначати функцію з одним аргументом x, яка повертає одне і те ж значення незалежно від x, звану постійною функцією. Що стосується їх вихідних даних, різниця в тому, що константа не має аргументів, званих нульовий (або нульовий операцією), а константа є унарной операцією.

Діаграми Венна корисні для візуалізації законів. Норми комутативності для ∧ і ∨ можна побачити із симетрії діаграм: бінарна операція, яка не була комутативність, не мала відповідної діаграми, тому що взаємозамінність x і y мала б ефектом відображення графіка по горизонталі, а будь-який збій комутативності потім з’являються, як порушення симетрії.

Идемпотентность

Идемпотентность ∧ і ∨ можна візуалізувати, з’єднавши два кола разом і зазначивши, що затемнена область стає цілим колом як для ∧, так і для ∨.

Щоб побачити перший закон поглинання, x∧ (x∨y) = x, почніть з діаграми в середині x∨y і зверніть увагу, що частина затіненій області, загальна з колом x, є цілим колом x.

Для другого закону поглинання, x∨ (x∧y) = x, почніть з лівої діаграми для x∧y і зверніть увагу, що затемнення всього кола x приводить до затінення тільки області x, так як попередня заливка була всередині х.

Щоб візуалізувати її, (x) ∧ (y) = (x∨y), почніть з середньої діаграми для x∨y і доповніть її штрихуванням так, щоб затемнилась тільки область поза обох кіл, яка це те, що описує права частина закону. Результат знаходиться як поза кола х, так і поза кола, тобто в поєднанні їх зовнішніх елементів.

Другий приклад, (x) ∨ (y) = (x∧y), однаково працює з двома взаємозамінними діаграмами.

Перший закон доповнення, x∧x = 0, каже, що внутрішня і зовнішня частини кола x не перекриваються. Другий закон доповнення, x∨x = 1, говорить, що все знаходиться або всередині, або зовні кола x.

Цифрова логіка

Цей термін означає застосування законів алгебри логіки 0 та 1 до електронного обладнання, що складається з логічних елементів, з’єднаних для формування принципової схеми. Кожен вентиль реалізує логічну операцію і схематично зображується формою, що позначає операцію. Головна область застосування такої алгебри логіки – інформатика.

Далі слід пояснити інші важливі моменти, безпосередньо відносяться до теми. Значення введення представлено напругою на виводі. Для так званої логіки «активний-високий», 0 представлений напругою, близьким до нуля, або «землею», а 1 представлений аналогом, близькою до напруги живлення; активний-низький змінює це. Лінія праворуч від кожного вентиля представляє вихідний порт, який зазвичай відповідає угодам по напрузі, що і вхідні порти.