Būlio algebra: istorija, teoremos ir postulatai, pavyzdžiai
Būlio algebra arba Būlio algebra yra algebrinė notacija, naudojama binarinių kintamųjų gydymui. Jis apima bet kurio kintamojo, turinčio tik du galimus rezultatus, tyrimus, papildančius ir tarpusavyje nesuderinamus. Pavyzdžiui, kintamieji, kurių vienintelė galimybė yra teisinga arba klaidinga, teisinga ar neteisinga, įjungta arba išjungta, yra Būlio algebros tyrimo pagrindas.
Būlio algebra sudaro skaitmeninės elektronikos pagrindą, kuris tampa gana dabartiniu metu. Ją reglamentuoja loginių vartų koncepcija, kur reikšmingai paveikiamos tradicinėje algebroje žinomos operacijos.
Istorija
Būlio algebrą 1854 m. Pristatė anglų matematikas George'as Boole (1815–1864), kuris buvo savarankiškas laiko mokytojas. Jo susirūpinimas kilo dėl Augustus De Morgan ir William Hamilton ginčo apie parametrus, apibrėžiančius šią loginę sistemą.
George'as Boole teigė, kad skaitinių reikšmių 0 ir 1 apibrėžimas logikos srityje atitinka atitinkamai „ Nieko ir visatos“ interpretaciją.
George'o Boole tikslas buvo per algebros savybes apibrėžti pasiūlymo logikos, reikalingos dvejetainių tipų kintamiesiems, išraiškas.
1854 m. Svarbiausios Būlio algebros dalys yra paskelbtos knygoje „ Mąstymo įstatymų, kuriais grindžiamos logikos ir tikimybės matematinės teorijos, tyrimas“.
Šis smalsus pavadinimas bus apibendrintas toliau kaip „ Mąstymo įstatymai“ („Mąstymo įstatymai“). Pavadinimas šoktelėjo į šlovę dėl neatidėliotino dėmesio, kurį turėjo matematinė bendruomenė.
1948 m. Claude Shannon jį taikė projektuodamas bistable elektros grandines. Tai buvo įvadas į Būlio algebros taikymą visoje elektroninėje skaitmeninėje sistemoje.
Struktūra
Šio tipo algebros elementinės reikšmės yra 0 ir 1, atitinkančios atitinkamai FALSE ir TRUE. Pagrindinės Būlio algebros operacijos yra 3:
- Veikimas IR arba kartu. Atstovaujamas laikotarpis (.). Produkto sinonimas
- ARBA operacija ar sujungimas. Atstovaujamas kryžiumi (+).
- operacija NE arba neigimas. Atstovaujama prefiksu NOT (NOT A). Jis taip pat žinomas kaip priedas.
Jei rinkinys A apibrėžia 2 vidaus kompozicijos įstatymus, pažymėtus kaip produktą ir sumą (. +), Sakoma, kad trigubas (A. +) yra Būlio algebra, jei ir tik tada, kai minėtas trigubas atitinka sąlygą būti tinkleliu paskirstymo
Norint nustatyti paskirstymo tinklą, turi būti įvykdytos paskirstymo sąlygos tarp nurodytų operacijų:
, yra paskirstomas pagal sumą + a. (b + c) = (a. b) + (a. c)
+ skirstomas pagal produktą. a + (b. c) = (a + b). (a + c)
Elementai, sudarantys A rinkinį, turi būti dvejetainiai, todėl turi visatos ar tuščias vertes .
Programos
Jo pagrindinis taikymo scenarijus yra skaitmeninis filialas, kuriame naudojamasi struktūros grandinėms, sudarančioms atitinkamas logines operacijas. Procesų optimizavimo grandinių paprastumo menas yra teisingo Būlio algebros taikymo ir praktikos rezultatas.
Nuo elektrinių plokščių kūrimo, per duomenų perdavimą, programavimą skirtingomis kalbomis, dažnai galime rasti Būlio algebrą visų tipų skaitmeninėse programose.
Būlio kintamieji yra labai paplitę programavimo struktūroje. Atsižvelgiant į naudojamą programavimo kalbą, bus naudojami struktūriniai kodo veiksmai, kurie naudoja šiuos kintamuosius. Kiekvienos kalbos sąlyginiai ir argumentai padeda Būlio kintamiesiems apibrėžti procesus.
Postuliuoja
Yra teorijų, reguliuojančių loginio algebros struktūrinius loginius įstatymus. Panašiai yra ir postulatai, kad žinotų galimus skirtingų binarinių kintamųjų derinių rezultatus, priklausomai nuo atliktos operacijos.
Suma (+)
OR operatorius, kurio loginis elementas yra sąjunga (U), yra apibrėžiamas dvejetainiams kintamiesiems:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Produktas (.)
IR operatorius, kurio loginis elementas yra sankirtos (∩), yra apibrėžiamas dvejetainiams kintamiesiems:
0 0 = 0
0 1 = 0
1 0 = 0
1 1 = 1
Prieštaraujama (NE)
„ NOT“ operatorius, kurio loginis elementas yra komplementas (X), yra apibrėžiamas dvejetainiams kintamiesiems:
NOT 0 = 1
NE 1 = 0
Daugelis postulatų skiriasi nuo įprastinių algebrų ekvivalentų. Taip yra dėl kintamųjų domeno. Pavyzdžiui, visuotinių elementų pridėjimas Būlio algebroje (1 + 1) negali suteikti įprastinio 2 rezultato, nes jis nepriklauso dvejetainio rinkinio elementams.
Teorijos
Nulio taisyklė ir vienybė
Apibrėžta bet kokia paprasta operacija, kurioje yra elementas su binariniais kintamaisiais:
0 + A = A
1 + A = 1
0 A = 0
1 A = A
Lygios galios arba idempotencia
Operacijos tarp lygių kintamųjų apibrėžiamos taip:
A + A = A
A. A = A
Papildymas
Kiekviena kintamojo ir jo papildymo operacija apibrėžiama taip:
A + NOT A = 1
A. NOT A = 0
Involiucija arba dvigubas neigimas
Bet koks dvigubas neigimas bus laikomas natūraliu kintamuoju.
NĖRA (NE A) = A
Komutacinis
A + B = B + A; Sumos komutatyvumas.
A. B = B A; Produkto komutatyvumas.
Asociacija
A + (B + C) = (A + B) + C = A + B + C; Sumos asociatyvumas.
A. (B.C) = (A. B). C = A B. C; Produkto asociatyvumas.
Paskirstymas
A + (B. C) = (A + B). (A + C); Sumos paskirstymas produktui.
A. (B + C) = (A. B) + (A + C); Produkto pasiskirstymas pagal sumą.
Absorbcijos įstatymai
Yra daug įstatymų dėl absorbcijos tarp daugelio
A. (A + B) = A
A. (NOT A + B) = A. B
NĖRA A (A + B) = NE A. B
(A + B). (A + NE B) = A
A + A. B = A
A + NE A. B = A + B
NOT A + A. B = NE A + B
A. B + A. NĖRA B = A
Morgano teorema
Tai yra transformacijos įstatymai, kurie tvarko kintamųjų poras, kurios sąveikauja tarp nustatytų Būlio algebros (+) operacijų.
NE (A. B) = NE A + NE B
NE (A + B) = NE A. NE B
A + B = NE (NE A + NE B)
A. B = NE (NE A. NE B)
Dvilypumas
Visi postulatai ir teoremos turi dvilypumo fakultetą. Tai reiškia, kad keičiant kintamuosius ir operacijas, gautas pasiūlymas yra patikrintas. Tai reiškia, kad keičiantis 0 už 1 ir IR OR arba atvirkščiai; sukuriama išraiška, kuri taip pat bus visiškai tinkama.
Pavyzdžiui, jei vartojate postulatą
1 0 = 0
Ir taikomas dvilypumas
0 + 1 = 1
Gautas dar vienas galiojantis postulatas.
Karnaugho žemėlapis
Karnaugh žemėlapis yra schema, naudojama Būlio algebroje, kad būtų supaprastintos loginės funkcijos. Jis susideda iš dvimatės struktūros, panašios į tiesinės logikos tiesos lenteles. Tiesos lentelių duomenys gali būti tiesiogiai užfiksuoti Karnaugh žemėlapyje.
„Karnaugh“ žemėlapis gali apimti iki 6 kintamųjų procesus. Funkcijoms su didesniu kintamųjų skaičiumi, siekiant supaprastinti procesą, rekomenduojama naudoti programinę įrangą.
1953 m. Maurice Karnaugh pasiūlė, kad ji buvo sukurta kaip fiksuota priemonė Būlio algebros srityje, nes jos įgyvendinimas sinchronizuoja žmogaus potencialą su būtinybe supaprastinti Būlio išraiškas, svarbiausią skaitmeninių procesų sklandumą.
Pavyzdžiai
Būlio algebra naudojama loginių vartų sumažinimui grandinėje, kur pirmenybė teikiama grandinės sudėtingumui ar lygiui pasiekti kuo mažesnę išraišką. Taip yra dėl skaičiavimo vėlavimo, kurį prisiima kiekviena durys.
Toliau pateiktame pavyzdyje mes stebime loginės išraiškos supaprastinimą iki minimalios išraiškos, naudojant Būlio algebros teorijas ir postulatus.
NE (AB + A + B). NE (A + NE B)
NE [A (B + 1) + B]. NOT (A + NOT B); A faktoriaus faktoringas.
NE [A (1) + B]. NOT (A + NOT B); Pagal teoriją A + 1 = 1.
NE (A + B). NOT (A + NOT B); pagal A teoriją. 1 = A
(NE A. NE B). [NOT A. NOT (NOT B)];
Morgano teorema NE (A + B) = NE A. NE B
(NE A. NE B). (NE A. B); Pagal dvigubą neigiamą teoriją NOT (NOT A) = A
NE A. NĖRA B. NE A. B; Algebrinė grupė
NE A. NE A. NĖRA B. B; Produkto komutatyvumas A. B = B A
NE A. NĖRA B. B; Pagal teoriją A. A = A
NE A. 0; Pagal teoriją A. NOT A = 0
0; Pagal teoriją A. 0 = 0
A. B. C + NOT A + A. NĖRA B. C
A. C. (B + NOT B) + NE A; Faktoringas (A. C) su bendru veiksniu.
A. C. (1) + NE A; Pagal A + NOT A = 1
A. C + NOT A; Pagal taisyklę nulio ir vieneto 1 taisyklė. A = A
NOT A + C ; Pagal Morgano įstatymą A + NOT A. B = A + B
Dėl šio sprendimo Morgano teisė turėtų būti išplėsta, kad būtų apibrėžta:
NE (NE A). C + NOT A = NE A + C
Kadangi NE (NĖRA A) = A pagal involiuciją.
Supaprastinkite loginę funkciją
NE A. NĖRA B. NOT C + NOT A. NĖRA B. C + NOT A. NE C į jo minimalią išraišką
NE A. NĖRA B. (NE C + C) + NE A. NE C; Faktoringas (NOT A. NOT B) su bendru veiksniu
NE A. NĖRA B. (1) + NE A. NE C; Pagal A + NOT A = 1
(NE A. NE B) + (NE A. NE C); Pagal taisyklę nulio ir vieneto 1 taisyklė. A = A
NOT A (NOT B + NOT C); Faktoringas NE A su bendru veiksniu
NE A. NOT (B. C); Pagal Morgano įstatymus NE (A. B) = NE A + NE B
NĖRA [A + (B. C)] Morgano įstatymais NE (A. B) = NE A + NE B
Bet kuris iš trijų paryškintų variantų - tai galimas sprendimas sumažinti grandinės lygį
Supaprastinkite loginę funkciją iki minimumo
(A) NOT B, C + A, NOT B, B, D + NOT A, NOT B). C
(A, NOT B, C + A, 0, D + NOT, NOT B). C; Pagal teoriją A. NOT A = 0
(A, NOT B, C + 0 + NE A, NE B). C; Pagal teoriją A. 0 = 0
(A, NOT B, C + NOT A, NOT B). C; Pagal A + 0 = A
A. NĖRA B. C. C + NOT A. NĖRA B. C; Pagal produkto pasiskirstymą pagal sumą
A. NĖRA B. C + NOT A. NĖRA B. C; Pagal teoriją A. A = A
NĖRA B. C (A + NOT A) ; Faktoringas (NE B. C) su bendru veiksniu
NĖRA B. C (1); Pagal A + NOT A = 1
NĖRA B. C; Pagal taisyklę nulio ir vieneto 1 taisyklė. A = A
