БУЛЕВА АЛГЕБРА: ІСТОРІЯ, ТЕОРЕМИ ТА ПОСТУЛАТИ, ПРИКЛАДИ - МАТЕМАТИКА - 2024

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

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

Джерело: pexels.com

Історія

Булева алгебра була введена в 1854 році англійським математиком Джорджем Булом (1815 - 1864), який був вченим-самоуком того часу. Його стурбованість виникла з існуючої суперечки між Августом Де Морганом та Вільямом Гамільтоном щодо параметрів, які визначають цю логічну систему.

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

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

У 1854 р. В книзі "Дослідження законів думки, на якій базуються математичні теорії логіки та ймовірності", були опубліковані найбільш значні розділи булевої алгебри.

Цей цікавий заголовок згодом було б узагальнено як «Закони думки» («Закони думки»). Титул піднявся на славу завдяки безпосередній увазі, яку він отримав від тогочасного математичного співтовариства.

У 1948 році Клод Шеннон застосував його для проектування бістабільних електричних схем комутації. Це послужило вступом до застосування булевої алгебри у всій електронно-цифровій схемі.

Будова

Елементарні значення в цьому типі алгебри дорівнюють 0 та 1, що відповідають ЛІЖНІЙ та ІСТИЧНОЇ відповідно. Основними операціями булевої алгебри є 3:

- І операція, або з'єднання. Представлений періодом (.). Синонім твору.

- АБО операція чи диз'юнкція. Представлений хрестом (+). Синонім суми.

- НЕ операція чи заперечення. Представлений префіксом NOT (NOT A). Він також відомий як доповнення.

Якщо в наборі A 2 закони внутрішнього складу визначені як добуток і сума (. +), То потрійний (A. +) вважається булевою алгеброю, якщо і лише тоді, коли зазначена трійка відповідає умові решітки. розподільний.

Для визначення розподільної решітки повинні бути дотримані умови розподілу між даними операціями:

. є розподільним щодо суми + а. (b + c) = (a. b) + (a. c)

+ є розподільним щодо продукту. a + (b. c) = (a + b). (a + c)

Елементи, що складають множину A, повинні бути бінарними, таким чином, мати значення всесвіту чи порожнечі.

Програми

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

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

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

Постулати

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

Сума (+)

Оператор АБО, чий логічний елемент є об'єднанням (U), визначається для бінарних змінних наступним чином:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Товар (.)

Оператор AND , логічним елементом якого є перетин (∩), визначається для бінарних змінних наступним чином:

0. 0 = 0

0. 1 = 0

один. 0 = 0

один. 1 = 1

Навпроти (НЕ)

Оператор NOT , логічним елементом якого є доповнення (X) ', визначається для бінарних змінних наступним чином:

НЕ 0 = 1

НЕ 1 = 0

Багато постулатів відрізняються від своїх аналогів звичайною алгеброю. Це пов’язано з доменом змінних. Наприклад, додавання елементів Всесвіту в булеву алгебру (1 + 1) не може дати умовний результат 2, оскільки він не належить до елементів бінарного набору.

Теореми

Правило нуля і єдності

Будь-яка проста операція, що включає елемент з бінарними змінними, визначається:

0 + A = A

1 + А = 1

0. A = 0

один. А = А

Рівні повноваження або ідентифікація

Операції між рівними змінними визначаються як:

А + А = А

ДО. А = А

Доповнення

Будь-яка операція між змінною та її доповненням визначається як:

А + НЕ А = 1

ДО. НЕ A = 0

Інволюція або подвійне заперечення

Будь-яке подвійне заперечення вважатиметься природною змінною.

НЕ (НЕ А) = А

Комутативний

А + В = В + А; Комутативність суми.

ДО. B = B. ДО; Комутативність виробу.

Асоціативний

A + (B + C) = (A + B) + C = A + B + C; Асоціативність суми.

ДО. (Б. С) = (А. Б). С = А. Б. C; Асоціативність продукту.

Розподільний

A + (B. C) = (A + B). (A + C); Розподіл суми щодо продукту.

ДО. (B + C) = (A. B) + (A + C); Розподіл товару за сумою.

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

Серед декількох посилань є багато законів поглинання, деякі з найбільш відомих:

ДО. (A + B) = A

ДО. (НЕ A + B) = A. Б

НЕ A (A + B) = НЕ A. Б

(A + B). (A + NOT B) = A

А + А. В = А

А + НЕ. B = A + B

НЕ А + А. B = НЕ A + B

ДО. В + А. НЕ В = А

Теорема Моргана

Вони є законами перетворення, які обробляють пари змінних, які взаємодіють між визначеними операціями булевої алгебри (+.).

НЕ (А. В) = НЕ А + НЕ В

НЕ (A + B) = НЕ A. НЕ Б

A + B = NOT (NOT A + NOT B)

ДО. B = НЕ (НЕ A. НЕ B)

Подвійність

Усі постулати та теореми мають факультет подвійності. Це означає, що шляхом обміну змінними та операціями отримане пропозиція перевіряється. Тобто при обміні 0 на 1 і AND на АБО або навпаки; створюється вираз, який також буде повністю дійсним.

Наприклад, якщо взятий постулат

один. 0 = 0

І застосовується подвійність

0 + 1 = 1

Отриманий ще один абсолютно дійсний постулат.

Карта Карно

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

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

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

Приклади

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

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

НЕ (AB + A + B). НЕ (A + NOT B)

НЕ. НЕ (А + НЕ Б); Факторинг A із загальним фактором.

НЕ. НЕ (А + НЕ В); За теоремою A + 1 = 1.

НЕ (A + B). НЕ (А + НЕ Б); за теоремою А. 1 = А

(НЕ А. НЕ Б). ;

За теоремою Моргана НЕ (А + В) = НЕ А. НЕ Б

(НЕ А. НЕ Б). (НЕ А. Б); За теоремою подвійного заперечення НЕ (НЕ А) = А

НЕ А. НЕ Б. НЕ А. Б; Алгебраїчне групування.

НЕ А. НЕ А. НЕ Б. Б; Комутативність виробу А. B = B. ДО

НЕ А. НЕ Б. Б; За теоремою А. А = А

НЕ А. 0; За теоремою А. НЕ A = 0

0; За теоремою А. 0 = 0

ДО. Б. C + НЕ A + A. НЕ Б. С

ДО. C. (B + NOT B) + NOT A; Факторинг (А. С) із загальним фактором.

ДО. C. (1) + НЕ; За теоремою А + НЕ А = 1

ДО. С + НЕ; За правилом нульової теореми та єдності 1. А = А

НЕ A + C ; За законом Моргана А + НЕ. B = A + B

Для цього рішення закон Моргана повинен бути розширений, щоб визначити:

НЕ (НЕ). C + NOT A = NOT A + C

Тому що НЕ (НЕ А) = А шляхом інволюції.

Спростіть логічну функцію

НЕ А. НЕ Б. НЕ С + НЕ. НЕ Б. С + НЕ. НЕ C до мінімального вираження

НЕ А. НЕ Б. (НЕ С + С) + НЕ А. НЕ С; Факторинг (НЕ А. НЕ Б) із загальним фактором

НЕ А. НЕ Б. (1) + НЕ НЕ С; За теоремою А + НЕ А = 1

(НЕ А. НЕ В) + (НЕ А. НЕ С); За правилом нульової теореми та єдності 1. А = А

NOT A (NOT B + NOT C); Факторинг НЕ A із загальним фактором

НЕ А. НЕ (Б. С); За законами Моргана NOT (A. B) = NOT A + NOT B

НЕ за законами Моргана НЕ (A. B) = NOT A + NOT B

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

Спростіть логічну функцію до її найпростішої форми

(A. NOT B. C + A. NOT B. B. D + NOT A. NOT B). С

(A. NOT B. C + A. 0. D + NOT A. NOT B). C; За теоремою А. НЕ A = 0

(A. NOT B. C + 0 + NOT A. NOT B). C; За теоремою А. 0 = 0

(A. NOT B. C + NOT A. NOT B). C; За теоремою A + 0 = A

ДО. НЕ Б. C. С + НЕ. НЕ Б. C; За розподілом продукту відносно суми

ДО. НЕ Б. С + НЕ. НЕ Б. C; За теоремою А. А = А

НЕ Б. C (A + NOT A) ; Факторинг (НЕ B. С) із загальним фактором

НЕ Б. C (1); За теоремою А + НЕ А = 1

НЕ Б. C; За правилом нульової теореми та єдності 1. А = А

Список літератури

1. Булева алгебра та її застосування Дж. Елдона Уайтсітта. Видавнича компанія Continental, 1980.
2. Математика та інженерія в галузі інформатики. Крістофер Дж. Ван Вік. Інститут комп'ютерних наук та технологій. Національне бюро стандартів. Вашингтон, округ Колумбія, 20234
3. Математика для інформатики. Ерік Леман. Google Inc.
   F Томсон Лейтон, кафедра математики та лабораторії обчислювальної техніки та AI, Массачусетський технологічний інститут; Akamai Technologies.
4. Елементи абстрактного аналізу. Мічел О'Серкоїд, кандидат наук. Кафедра математики. Університетський коледж Дубліна, Beldfield, Dublind.
5. Вступ до логіки та методології дедуктивних наук. Альфред Тарскі, Нью-Йорк Оксфорд. Оксфордська університетська преса.