- история
- структура
- Приложения
- постулати
- Сума (+)
- Продукт (.)
- Противоположно (НЕ)
- теореми
- Правило на нула и единство
- Равни правомощия или безразсъдство
- Допълването
- Инволюция или двойно отрицание
- комутативен
- асоциативен
- разпределителен
- Закони за усвояване
- Теорема на Морган
- Двойствеността
- Карта на Карнау
- Примери
- Опростете логическата функция
- Опростете логическата функция до най-простата й форма
- Препратки
В Булева алгебра или булева алгебра е алгебрични нотация се използва за лечение на бинарни променливи. Той обхваща изследванията на всяка променлива, която има само 2 възможни резултата, допълващи се и взаимно изключващи се. Например променливи, чиято единствена възможност е вярна или невярна, правилна или неправилна, включена или изключена, са в основата на изследването на булева алгебра.
Булева алгебра представлява основата на цифровата електроника, което я прави доста присъстваща днес. Тя се управлява от концепцията на логическите порти, където известните операции в традиционната алгебра са значително засегнати.
Източник: pexels.com
история
Булева алгебра е въведена през 1854 г. от английския математик Джордж Бул (1815 - 1864), който е учен на самоуки по онова време. Тревогата му възникна от съществуващ спор между Август Де Морган и Уилям Хамилтън относно параметрите, които определят тази логическа система.
Джордж Бул твърди, че определението на числовите стойности 0 и 1 съответства в областта на логиката на интерпретацията съответно Нищо и Вселена.
Намерението на Джордж Бул беше да определи чрез свойствата на алгебра изразите на логиката на предложенията, необходими за справяне с променливи от двоичен тип.
През 1854 г. в книгата „Изследване на законите на мисълта, на която се основават математическите теории на логиката и вероятността“, са публикувани най-значимите раздели на булева алгебра “.
Това любопитно заглавие ще бъде обобщено по-късно като „Законите на мисълта“ („Законите на мисълта“). Заглавието се издигна до славата поради непосредственото внимание, което получи от математическата общност на онова време.
През 1948 г. Клод Шенън го прилага при проектирането на бистабилни електрически комутационни вериги. Това послужи като въведение към приложението на булева алгебра в рамките на цялата електронно-цифрова схема.
структура
Елементарните стойности в този тип алгебра са 0 и 1, които съответстват съответно на FALSE и TRUE. Основните операции в булева алгебра са 3:
- И операция или връзка. Представен от период (.). Синоним на продукта.
- ИЛИ операция или прекъсване. Представен от кръст (+). Синоним на сумата.
- НЕ експлоатация или отрицание. Представена от префикса НЕ (НЕ А). Известен е и като допълнение.
Ако в набор A 2 законите с вътрешен състав са дефинирани като продукт и сбор (. +), Се казва, че тройката (A. +) е булева алгебра, ако и само ако споменатата тройка отговаря на условието да бъде решетка разпределителни.
За да дефинирате разпределителна решетка, условията за разпространение трябва да бъдат изпълнени между дадените операции:
, е разпределителен по отношение на сумата + a. (b + c) = (a. b) + (a. c)
+ е дистрибуторен по отношение на продукта. a + (b. c) = (a + b). (a + c)
Елементите, които съставят набор A, трябва да са двоични, като по този начин имат стойности на Вселена или празнота.
Приложения
Основният му сценарий за приложение е цифровият клон, където той служи за структуриране на веригите, които съставляват включените логически операции. Изкуството на простотата на веригата в полза на оптимизирането на процесите е резултат от правилното приложение и практика на булева алгебра.
От разработването на електрически панели, преминавайки през предаването на данни, до достигането на програмирането на различни езици, често можем да намерим булева алгебра във всички видове цифрови приложения.
Булевите променливи са много често срещани в структурата на програмирането. В зависимост от използвания език за програмиране в кода ще има структурни операции, които използват тези променливи. Условията и аргументите на всеки език допускат булеви променливи за дефиниране на процесите.
постулати
Съществуват теореми, които управляват структурните логически закони на булева алгебра. По същия начин има постулати за познаване на възможните резултати в различни комбинации от двоични променливи, в зависимост от извършената операция.
Сума (+)
Операторът OR, чийто логичен елемент е обединението (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
един. A = A
Равни правомощия или безразсъдство
Операциите между равни променливи се определят като:
A + A = A
ДА СЕ. A = A
Допълването
Всяка операция между променлива и нейното допълнение се дефинира като:
A + НЕ A = 1
ДА СЕ. НЕ A = 0
Инволюция или двойно отрицание
Всяко двойно отрицание ще се счита за естествената променлива.
НЕ (НЕ А) = А
комутативен
A + B = B + A; Комутативност на сумата.
ДА СЕ. B = B. ДА СЕ; Комутативност на продукта.
асоциативен
A + (B + C) = (A + B) + C = A + B + C; Асоциативност на сумата.
ДА СЕ. (Б. С) = (А. Б). С = А. Б. ° С; Асоциативност на продуктите.
разпределителен
A + (B. C) = (A + B). (A + C); Разпределение на сумата по отношение на продукта.
ДА СЕ. (B + C) = (A. B) + (A + C); Разпространение на продукта по отношение на сумата.
Закони за усвояване
Има много закони за усвояване сред многобройните справки, някои от най-известните са:
ДА СЕ. (A + B) = A
ДА СЕ. (НЕ A + B) = A. B
НЕ A (A + B) = НЕ A. B
(A + B). (A + НЕ B) = A
A + A B = A
A + НЕ A. B = A + B
НЕ А + А. B = НЕ A + B
ДА СЕ. B + A НЕ B = A
Теорема на Морган
Те са закони на трансформация, които обработват двойки променливи, които взаимодействат между дефинираните операции на булева алгебра (+.).
НЕ (A. B) = НЕ A + НЕ B
НЕ (A + B) = НЕ A. НЕ Б
A + B = НЕ (НЕ A + НЕ B)
ДА СЕ. B = НЕ (НЕ А. НЕ Б)
Двойствеността
Всички постулати и теореми притежават способността за дуалност. Това означава, че чрез обмен на променливи и операции полученото предложение се проверява. Тоест при обмен на 0 за 1 и AND за ИЛИ или обратно; се създава израз, който също ще бъде напълно валиден.
Например, ако се вземе постулата
един. 0 = 0
И се прилага двойствеността
0 + 1 = 1
Получава се още един напълно валиден постулат.
Карта на Карнау
Картата на Karnaugh е диаграма, използвана в булева алгебра за опростяване на логическите функции. Състои се от двуизмерна подредба, подобна на таблиците за истинност на логиката на предложенията. Данните от таблиците за истинност могат да бъдат директно заснети на картата на Karnaugh.
Картата на Karnaugh може да побере процеси до 6 променливи. За функции с по-голям брой променливи се препоръчва използването на софтуер за опростяване на процеса.
Предложена през 1953 г. от Морис Карно, тя е създадена като неподвижен инструмент в областта на булева алгебра, тъй като нейното изпълнение синхронизира човешкия потенциал с необходимостта от опростяване на булевите изрази, ключов аспект в плавността на цифровите процеси.
Примери
Булева алгебра се използва за намаляване на логическите порти в дадена верига, където приоритет е да се доведе сложността или нивото на веригата до най-ниското й възможно изражение. Това се дължи на изчислителното закъснение, което всяка порта предполага.
В следващия пример ще наблюдаваме опростяването на логическия израз до неговия минимален израз, използвайки теоремите и постулатите на Булева алгебра.
НЕ (AB + A + B). НЕ (A + НЕ B)
НЕ. НЕ (A + НЕ B); Факторинг А с общ фактор.
НЕ. НЕ (A + НЕ B); По теорема A + 1 = 1.
НЕ (A + B). НЕ (A + НЕ B); по теорема А. 1 = A
(НЕ А. НЕ Б).;
По теорема на Морган НЕ (A + B) = НЕ A. НЕ Б
(НЕ А. НЕ Б). (НЕ А. Б); Чрез теорема за двойно отрицание НЕ (НЕ А) = А
НЕ А. НЕ Б. НЕ А. Б; Алгебраично групиране.
НЕ А. НЕ А. НЕ Б. Б; Комутативност на продукт А. B = B. ДА СЕ
НЕ А. НЕ Б. Б; По теорема А. A = A
НЕ А. 0; По теорема А. НЕ A = 0
0; По теорема А. 0 = 0
ДА СЕ. Б. C + НЕ A + A. НЕ Б. ° С
ДА СЕ. ° С. (B + НЕ B) + НЕ A; Факторинг (A. C) с общ фактор.
ДА СЕ. ° С. (1) + НЕ А; По теорема A + НЕ A = 1
ДА СЕ. C + НЕ A; По правило на нулевата теорема и единство 1. A = A
НЕ A + C; По закон на Morgan A + NOT A. B = A + B
За това решение законът на Морган трябва да бъде разширен, за да определи:
НЕ (НЕ А). C + НЕ A = НЕ A + C
Защото НЕ (НЕ А) = А чрез инволюция.
Опростете логическата функция
НЕ А. НЕ Б. НЕ С + НЕ А. НЕ Б. C + НЕ A. НЕ С до минималния си израз
НЕ А. НЕ Б. (НЕ С + С) + НЕ А. НЕ С; Факторинг (НЕ А. НЕ Б) с общ фактор
НЕ А. НЕ Б. (1) + НЕ А. НЕ С; По теорема A + НЕ A = 1
(НЕ А. НЕ Б) + (НЕ А. НЕ В); По правило на нулевата теорема и единство 1. A = A
НЕ А (НЕ Б + НЕ С); Факторинг НЕ А с общ фактор
НЕ А. НЕ (Б. С); По законите на Морган НЕ (А. Б) = НЕ А + НЕ Б
НЕ по законите на Морган НЕ (A. B) = НЕ A + НЕ B
Всяка от 4-те опции с удебелен шрифт представлява възможно решение за намаляване на нивото на веригата
Опростете логическата функция до най-простата й форма
(А. НЕ Б. В + А. НЕ Б. Б. Д + НЕ А. НЕ Б). ° С
(А. НЕ Б. С + А. 0. D + НЕ А. НЕ Б). ° С; По теорема А. НЕ A = 0
(А. НЕ Б. С + 0 + НЕ А. НЕ Б). ° С; По теорема А. 0 = 0
(А. НЕ Б. В + НЕ А. НЕ Б). ° С; По теорема A + 0 = A
ДА СЕ. НЕ Б. ° С. C + НЕ A. НЕ Б. ° С; По разпределение на продукта по отношение на сумата
ДА СЕ. НЕ Б. C + НЕ A. НЕ Б. ° С; По теорема А. A = A
НЕ Б. С (А + НЕ А) ; Факторинг (НЕ Б. С) с общ фактор
НЕ Б. С (1); По теорема A + НЕ A = 1
НЕ Б. ° С; По правило на нулевата теорема и единство 1. A = A
Препратки
- Булева алгебра и нейните приложения J. Eldon Whitesitt. Издателска компания Continental, 1980.
- Математика и инженерство в компютърните науки. Кристофър Дж. Ван Уик. Институт за компютърни науки и технологии. Национално бюро за стандарти. Вашингтон, окръг Колумбия 20234
- Математика за компютърни науки. Ерик Леман. Google Inc.
F Thomson Leighton Катедра по математика и компютърна наука и AI Laboratory, Масачузетски технологичен институт; Akamai Technologies.
- Елементи на абстрактния анализ. Доктор на науките Мичел О'Съркойд. Катедра по математика. Университетски колеж Дъблин, Beldfield, Дъблинд.
- Въведение в логиката и методологията на дедуктивните науки. Алфред Тарски, Ню Йорк Оксфорд. Университетска преса в Оксфорд.