Boole'i avaldiste lahendaja

tõeväärtustabel samm-sammuliste osaavaldisteveergudega

Algväärtused — Boole'i avaldiste lahendaja

Boole'i avaldis	A & B

Muuda ülal mõnda juhtelementi ja tulemused arvutatakse uuesti.

Interaktiivse simulatsiooni laadimine...

Vali muutuja, mis seletab kõige rohkem 🖖

Kasulik riistvaratrikk: vali sisend, mis eraldab TÕENE/VÄÄR käitumist kõige paremini, seejärel implementeeri iga haru ja multipleks selle sisendi järgi.

üks rida iga võimaluse kohta 🖖

Tõeväärtustabel on lihtsalt ammendav loend: see kirjutab välja iga võimaliku TÕENE/VÄÄR sisendite kombinatsiooni ja näitab, mida avaldis igal juhul teeb. n muutuja korral on 2ⁿ rida, nii et iga uus sisend kahekordistab tabeli — 3 muutujat annavad 8 rida, 5 annavad 32. Ka vaheveerud on olulised: need ehitavad iga alamavaldise sammhaaval üles, nii et saad loogikat jälgida operaatorhaaval, mitte lõpptulemust pimesi usaldada.

32 rida, neli miljardit funktsiooni 🖖

Ja siin tuleb üllatus: 5 muutuja tabelis on ainult 32 rida, kuid erinevate avaldiste arv, mille saab nende üle defineerida, on 2³² = 4,294,967,296. Iga erinev viis täita väljundveerg nullide ja ühtedega on omaette Boole'i funktsioon, ja neid on kokku 2^(2ⁿ). Nõnda liigub see tagasihoidlik tööriist vaikselt läbi enam kui nelja miljardi võimaliku loogikalülituse ruumi — üks iga mustri kohta, mille viimane veerg võib võtta.

LOOGIKAAVALDISED — MILLINE SEADUS SEDA LIHTSUSTAB?

Millise lihtsustamisjuhtumiga on tegemist?

Kaks avaldist on üks ja seesama avaldis täpselt siis, kui nende tõeväärtustabelid langevad kokku — ja ainult see kontroll otsustab. Boole’i algebra seadused ongi lihtsalt need kokkulangevused, mida tasub nägemise järgi teada: eituse sissetoomine, sulgude avamine, midagi mittemuutva liikme kustutamine ja selle liikme äratundmine, mille teised juba katsid. Pange tabel kokku ja vastus ei ole enam kahtluse all.

Eitus sulgude peal — De Morgan vahetab sideme ¬(A ∧ B) = ¬A ∨ ¬B

Sulud, mis tuleb avada — distributiivsus A ∧ (B ∨ C) = (A∧B) ∨ (A∧C)

Liige, mis ei lisa midagi — absorptsioon A ∨ (A ∧ B) = A

Liige, mille teised juba katavad — konsensusteoreem (A∧B) ∨ (¬A∧C) ∨ (B∧C) = (A∧B) ∨ (¬A∧C)

Avaldis ei sõltu enam üldse oma sisenditest A ∨ ¬A = 1

Eitus sulgude peal — De Morgan vahetab sideme

Mida te teate: Eitus terve avaldise kohal. Kui see sisse tuua, muutub AND OR-iks või OR AND-iks ja iga osa saab teel eituse.

Seadus: ¬(A ∧ B) = ¬A ∨ ¬B

Näidisarvutus: !(A & B) on seesama avaldis mis !A | !B — mõlemad väljundveerud langevad kõigil neljal real kokku

Ava see juhtum: De Morgani !(A & B)

Eitus sulgude peal — De Morgan vahetab sideme. Tooge eitus sisse ja AND-ist saab OR; mõlemad väljundveerud on ühesugused. Eitus terve avaldise kohal. Kui see sisse tuua, muutub AND OR-iks või OR AND-iks ja iga osa saab teel eituse. — Tooge eitus sisse ja AND-ist saab OR; mõlemad väljundveerud on ühesugused.

Sulud, mis tuleb avada — distributiivsus

Mida te teate: AND jaotub üle OR-i täpselt nii, nagu korrutamine jaotub üle liitmise. Avamine annab korrutiste summa, standardkuju, millest skeem kokku pannakse.

Seadus: A ∧ (B ∨ C) = (A∧B) ∨ (A∧C)

Näidisarvutus: A & (B | C) on sama mis (A & B) | (A & C), kõigil kolme muutuja kaheksal real

Ava see juhtum: A & (B | C)

Sulud, mis tuleb avada — distributiivsus. Sulgude avamine annab kaks korrutisliiget, mille OR vastab algsele avaldisele. AND jaotub üle OR-i täpselt nii, nagu korrutamine jaotub üle liitmise. Avamine annab korrutiste summa, standardkuju, millest skeem kokku pannakse. — Sulgude avamine annab kaks korrutisliiget, mille OR vastab algsele avaldisele.

Liige, mis ei lisa midagi — absorptsioon

Mida te teate: Kui üks liige juba järeldab teist, saab nõrgema ära jätta. A | (A & B) ongi lihtsalt A, ükskõik mis on B.

Seadus: A ∨ (A ∧ B) = A

Näidisarvutus: A | (A & B) = A: seal, kus A on 1, on väljund niikuinii 1, ja seal, kus A on 0, on ka teine liige 0

Ava see juhtum: absorptsiooniseadus

Liige, mis ei lisa midagi — absorptsioon. Teine liige rakendub ainult seal, kus esimene juba rakendus, seega ei mõjuta ta kunagi väljundit. Kui üks liige juba järeldab teist, saab nõrgema ära jätta. A | (A & B) ongi lihtsalt A, ükskõik mis on B. — Teine liige rakendub ainult seal, kus esimene juba rakendus, seega ei mõjuta ta kunagi väljundit.

Liige, mille teised juba katavad — konsensusteoreem

Mida te teate: Kolm liiget, kus kolmas on kahe esimese konsensus: ta katab ainult neid juhte, mida need kaks juba koos katavad. Tema eemaldamine ei muuda tabelis ühtegi rida.

Seadus: (A∧B) ∨ (¬A∧C) ∨ (B∧C) = (A∧B) ∨ (¬A∧C)

Näidisarvutus: (A & B) | (!A & C) | (B & C) võrdub avaldisega (A & B) | (!A & C) — kolmas liige on üleliigne kõigil kaheksal real

Ava see juhtum: konsensuse teoreem

Liige, mille teised juba katavad — konsensusteoreem. Kolmanda liikme ärajätmine jätab väljundveeru igal real puutumata. Kolm liiget, kus kolmas on kahe esimese konsensus: ta katab ainult neid juhte, mida need kaks juba koos katavad. Tema eemaldamine ei muuda tabelis ühtegi rida. — Kolmanda liikme ärajätmine jätab väljundveeru igal real puutumata.

Avaldis ei sõltu enam üldse oma sisenditest

Mida te teate: Üleni ühtedest koosnev veerg on tautoloogia, üleni nullidest koosnev on vastuolu. Kummalgi juhul on muutujad kaotanud tähtsuse.

Seadus: A ∨ ¬A = 1

Näidisarvutus: A | !A on mõlemal real 1 ja tema peegelpilt A & !A on mõlemal real 0

Ava see juhtum: tautoloogia A | !A

Avaldis ei sõltu enam üldse oma sisenditest. Mõlemad read annavad sama väljundi, seega ei mõjuta sisend üldse midagi. Üleni ühtedest koosnev veerg on tautoloogia, üleni nullidest koosnev on vastuolu. Kummalgi juhul on muutujad kaotanud tähtsuse. — Mõlemad read annavad sama väljundi, seega ei mõjuta sisend üldse midagi.

Allikad (2)

Ülesanded täielikult lahendatud

Mintermite summa avaldisele !(A & B) 5 sammu
Avaldis kahe muutuja A ja B korral on !(A & B). Loenda read, kus selle tulemus on 1, kirjuta funktsioon mintermide summana ning selgita välja, mida saab ehitada vaid sellest ühest loogikaelemendist.
1. Kaks muutujat, millest kumbki võib olla 0 või 1, seega saab tabel iga paari kohta ühe rea. Parser teatab selle arvu enne mis tahes väärtuse arvutamist, sest ülesande suurus on määratud muutujate, mitte nende kohale kirjutatud avaldisega.
  
  $2^{2} = 4$
2. Täida kõigepealt sisemine veerg. A & B on 1 ainult siis, kui mõlemad sisendid on 1, seega kolmel real on 0 ja viimasel 1. Tabel kuvab selle alamavaldise tulemuse kõrvale eraldi veeruna, mis võimaldab kontrollida parsimist, mitte ainult vastust.
  
  $A \land B : 0, 0, 0, 1$
3. NOT pöörab iga sisestuse ümber ega tee midagi muud. Kolm nulli muutuvad ühtedeks ja see ainus üks muutub nulliks, seega on tulemuse veerg selle kohal oleva veeru täpne eitus.
  
  $\neg (A \land B) : 1, 1, 1, 0$
4. Nii jääb 4 reast 3 väärtuseks 1. Murruna on see 0,75, mida paneel esitab sisendkombinatsioonide protsendina.
  
  $\frac{3}{4} = 0.75 = 75.0%$
5. Nimeta iga tõene rida konjunktsiooni järgi, mis on 1 vaid sellel real ja mitte ühelgi teisel — selle mintermiks — ning ühenda need kolm OR-tehtega. See on kanooniline disjunktiivne normaalvorm ja just selle loendi kuvab tööriist tabeli all.
  
  $(\neg A \land \neg B) \lor (\neg A \land B) \lor (A \land \neg B)$
Vastus

NAND on 1 tulemusega 4 reast 3 real, ehk 75,0%, ja selle normaalvormiks on need 3 mintermi. Nüüd peamine tulemus. Suuna A mõlemasse sisendisse ja A NAND A on !(A & A), mis on !A — oledki saanud NOT-tehte. Suuna ühe NAND-i väljund teise NAND-i mõlemasse sisendisse ning kaks eitust taanduvad välja, seega (A NAND B) NAND (A NAND B) on AND. OR-tehte jaoks eita kõigepealt mõlemat sisendit: (A NAND A) NAND (B NAND B) on !(!A & !B) ning !A & !B on 1 vaid ühel real 0,0, seega selle eitus on 1 ülejäänud 3 real — mis ongi A OR B. NOT, AND ja OR on täpselt need tehted, mida samm 5 kasutas funktsiooni kirjutamiseks normaalvormis, seega suudab see üks 4-realine veerg väljendada mistahes arvuga muutujate mis tahes Boole'i funktsiooni.

$A ↑ A = \neg A, (A ↑ A) ↑ (B ↑ B) = A \lor B$
Veeru nullist koostamine avaldisele !A | !B 6 sammu
Nüüd võta !A | !B, millel pole tehet !(A & B)-ga ühist — ei mingit eitatud sulgu ega AND-tehet kuskil. Ehita selle veerg nullist ja vaata, kuhu see välja jõuab.
1. Kaks NOT-veergu, mõlemad kuvatud tulemuse kõrval. !A on 1 neil 2 real, kus A on 0; !B on 1 neil 2 real, kus B on 0. Need ühtivad ühel real ja mõlema tulemus on 0 ühel real.
  
  $\neg A : 1, 1, 0, 0 \neg B : 1, 0, 1, 0$
2. OR on 0 ainult seal, kus mõlemad selle sisendid on 0, ja see juhtub täpselt ühel real: A=1, B=1, real, kus kumbki eitus ei jää kehtima. Igal teisel real on vähemalt üks 1, mis annab oma panuse.
  
  $\neg A \lor \neg B : 1, 1, 1, 0$
3. Seega 3 reast 4-st on 1 — sama 0,75, esitatuna sama protsendina.
  
  $\frac{3}{4} = 75.0%$
4. Ka mintermid kattuvad, liige liikme haaval ja samas järjekorras nagu esimeses ülesandes.
  
  $(\neg A \land \neg B) \lor (\neg A \land B) \lor (A \land \neg B)$
5. Nüüd võrdle neid kahte avaldist üldse ilma tabelita. A & B on 1 täpselt ühel real, seega !(A & B) on 0 täpselt sellel real, ning see on seesama rida, mis andis avaldise !A | !B tulemuseks 0. Kaks veergu, mis on samas kohas 0 ja igal pool mujal 1, on üks ja seesama veerg.
  
  $\neg (A \land B) \equiv \neg A \lor \neg B$
6. Kui avaldatud muljet see peaks tegema? 4-realises tabelis on 4 tulemuslahtrit, igaüks 0 või 1, seega võimaldavad kaks muutujat kokku vaid 16 erinevat funktsiooni. Kattuvus on nii väikeses hulgas kerge tulema — mispärast samm 5 ongi see osa, mis loeb: see fikseeris ühe rea ega lugenud kunagi ülejäänuid.
  
  $2^{2^{2}} = 2^{4} = 16$
Vastus

Mõlema avaldise tulemus on 75,0% samade 3 mintermiga, sest need on üks ja seesama funktsioon kahe erineva nimega. Kanooniline vorm on nagu sõrmejälg: kaks avaldist on samaväärsed täpselt siis, kui nende mintermide hulgad kattuvad, seega taandub küsimus sellest, kas kaks lülitust käituvad ühtmoodi, sellele, kas kaks loendit kattuvad. Mis aga ei taandu, on loendite koostamise hind. 2 muutujat vajavad 4 rida ja need arvutasid peast; 20 muutujat vajavad 1 048 576 rida; 100 muutujat vajavad umbes 1,27×10³⁰ rida — sõrmejälg on endiselt õige mõte, kuid tabel ei ole enam toimiv meetod. Reahaaval tuletatud argument sammus 5 on see, mis jääb kehtima ka pärast seda hüpet, sest selles ei mainitud kordagi, mitu rida tabelis oli.

$2^{20} = 1048576, 2^{100} \approx 1.27 \times 1 0^{30}$

42Mathi meeskond · Uuendatud 2026-07-27

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

lihtne AND - AND: väljund on 1 ainult siis, kui nii A kui ka B on 1
(A OR B) AND NOT C - 3 muutujat, 8 rida — näitab, kuidas NOT pöörab terve haru ümber
3-sisendi enamus - Enamushääletus: 1, kui vähemalt 2 muutujat A, B, C on 1
2:1 multiplekser - Multiplekser: S=0 korral väljund A, S=1 korral väljund B
tautoloogia A | !A - A | !A on tõene igas reas, seega koosneb tulemuste veerg ainult ühtedest ja sisend ei oma mingit tähtsust. Koos oma vastandiga A & !A moodustavad need kaks funktsiooni, mida tõeväärtustabel suudab kuvada nii, et muutujat pole üldse tarvis lugedagi.
vastuolu A & !A - A & !A on igas reas väär. Iga teine avaldis sellel lehel paigutub antud funktsiooni ja selle vastandi vahele. Need kaks ei ole lihtsalt kurioosumid, vaid tähistavad skaala äärmusi.
De Morgani !(A & B) - Laadige see avaldis ja seejärel tema paariline !A | !B. Need kaks tulemuste veergu on identsed, mida De Morgani seadus täpselt väidabki: konjunktsiooni eitus annab tulemuseks eituste disjunktsiooni. Kaks avaldist, üks funktsioon.
De Morgani !A | !B - De Morgani paari teine pool. Kõrvutage see avaldisega !(A & B) ning märkate, et tulemuste veerud kattuvad reast ritta. Need kaks avaldist ei ole lihtsalt mõnel juhul samaväärsed, vaid on üks ja seesama funktsioon kahel kujul kirja panduna.
A & (B | C) - A & (B | C) ehk distributiivsusseaduse vasak pool. Selle paariline avab avaldise kujule (A & B) | (A & C). Tõeväärtustabelid kattuvad täielikult ja just see teebki taolise laiendamise matemaatiliselt kehtivaks, mitte pelgalt usutavaks.
(A & B) | (A & C) - Avatud kuju. See nõuab kaht NING- ja ühte VÕI-väravat, samas kui kompaktne versioon piirdub mõlemast vaid ühega. Seaduspära, mis jätab tõeväärtustabeli samaks, ei ole seega riistvaras sugugi tasuta. Samal põhjusel ongi algebra rakendamine enne vooluringi ehitamist alati vaeva väärt.
XOR laiendatud kuju - XOR on siin lahti kirjutatud nende kahe juhu põhjal, kus sisendid omavahel erinevad. XOR-operaator on siit meelega välja jäetud. Selle funktsiooni käsitlemine mintermide summana näitab ilmekalt, kuidas iga võimaliku loogikafunktsiooni saab üles ehitada vaid nende kolme tehte abil, mida te juba tunnete.
A AND A AND A AND A - Muutujale neli korda järjest iseendaga NING-tehte rakendamine tagastab sellesama muutuja. Pange tähele, milline on selle hind. Vaja läheb kolme loogikaväravat, mis ei muuda midagi. Just selliste liigsuste eemaldamiseks ongi optimeerija loodud.
absorptsiooniseadus - A | (A & B) lihtsustub A-ks ja B-veerg paistab silma just sellega, et seda eiratakse. Kui A on tõene, on ka kogu avaldis nagunii tõene, ning kus A on väär, on väär ka teine liige.
konsensuse teoreem - Keskmine liige on liiast ja tabel tõestab seda. Kustutage B & C ning tulemuste veerg ei muutu. Palja silmaga on seda keeruline märgata, mistõttu ongi teoreemile antud oma nimi.
implikatsioon A -> B - A-st järeldub B ei ole algtehe, vaid esitub kujul !A | B. Tõeväärtustabel on selle elavaks tõestuseks. Enim üllatab inimesi rida, kus A on väär ja B on tõene, ent implikatsioon siiski kehtib.
3-sisendi paarsus - Tõene siis, kui paaritu arv sisendeid on 1, mis on kolme muutuja vahel aheldatud XOR-tehe. See on mälusõna kontrollbitt. See tuvastab kõik ühebitised vead täpselt seetõttu, et ühe sisendi ümberpööramine pöörab alati ümber ka väljundi.