Dekompozícia booleovskej funkcie z hľadiska premennej online. Princíp duality. rozšírenie booleovských funkcií v premenných. dokonalé disjunktívne a konjunktívne normálne formy. Dekompozícia booleovských funkcií v premenných

Označme podľa. Potom

x s=

Najmä vtedy a len vtedy.

Pomocou „funkcie napájania“ ľubovoľnej booleovskej funkcie môže byť reprezentovaný ako:

volal rozšírenie booleovskej funkcie podľa premennej.

Skutočne, ak, potom a

Ak, tak a

Príklad 4

Rozbaľte funkciu podľa premennej. Aby sme to dosiahli, najprv vytvoríme tabuľku funkcií:

Tabuľka ukazuje, že a.

Pomocou expanzného vzorca z hľadiska premennej nájdeme

Príklad 5.

Rozbaľte funkciu z príkladu 4 pre všetky premenné. Keďže funkcia nadobúda hodnotu 1 na troch množinách:, potom podľa následku k rozkladovej vete máme

Definícia 3.

Dekompozícia booleovskej funkcie nad všetkými premennými vo formulári

volal dokonalá disjunktívna normálna forma(SDNF).

Príklad 6.

- SDNF pre funkciu (pozri príklad 5).

Veta 2.

Každá booleovská funkcia (okrem 0) má jedinečný SDNF.

Dôkaz. Podľa následku k rozkladovej vete

Komentujte. Ak pod disjunkciou jedného člena rozumieme tento samotný člen, potom disjunkcia nuly členov neexistuje, preto pre funkciu 0 neexistuje SDNF.

Pri konštrukcii SDNF platí nasledovné.

Pravidlo jedného. má hodnotu 1; pre každý takýto súbor v SDNF sa pre daný výraz urobí medzera ... Ak je v danej množine argumentov, potom je nad premennou v pripravenom výraze zavesený zápor: .

Veta 3.

Akákoľvek booleovská funkcia môže byť vyjadrená pomocou disjunkcie, konjunkcie a negácie:

Dôkaz.

Ak , potom ... Ak , potom

Veta 4.

Akákoľvek booleovská funkcia (okrem 1) môže byť jednoznačne vyjadrená vo forme dokonalej konjunktívnej normálnej formy (SCNF):

Dôkaz.

Ak , potom a

Aplikovaním princípu duality na poslednú identitu nájdeme

Pri konštrukcii SCNF platí nasledovné.

Pravidlo nuly. Do úvahy sa berú len tie množiny argumentov, pre ktoré je funkcia nadobúda hodnotu 0; pre každý takýto súbor sa v SKNF vyhotoví polotovar faktora. Ak je v danej množine argumentov, potom sa nad premennou v pripravenom faktore zavesí zápor: .

Príklad 7.

Zostavme funkciu pre implikáciu: ... Implikácia má hodnotu 0 na jednej množine:

Keďže v tejto kolekcii a potom podľa nulového pravidla dostaneme

.

takze je požadovaná funkcia pre implikáciu.

Úplnosť systému

Definícia 4. Funkčný systém ( f 1 , f 2 , ..., f s, ...) Ì P 2 sa nazýva kompletný v R 2 ak nejakú funkciu f(X 1 , ..., x n) Î P 2 možno zapísať ako vzorec prostredníctvom funkcií tohto systému.

Kompletné systémy

1. P 2 - kompletný systém.

2. Systém M={X 1 &X 2 , X 1 Ú X 2,) je kompletný systém, od r pomocou týchto funkcií možno ľubovoľnú funkciu algebry logiky zapísať ako vzorec.

Príklad 8. Neúplné systémy: ( }, {0,1}.

Lemma(dostatočná podmienka pre úplnosť)

Nechajte systém U = {f 1 , f 2 , ..., f s, ...) je dokončená v R 2. Nechať byť B = {g 1 , g 2 , ..., g k, ...) je nejaký systém z R 2 a akúkoľvek funkciu f i Î U možno vyjadriť vzorcom cez B, potom systém B plný R 2 .

7. Systém ( X 1 &X 2 , X 1 Á X 2, 0, 1) je dokončená v R 2 , U = {X 1 &X 2 , }, = X 1 Å1.

Zhegalkinov polynóm

f(X 1 , ..., x n) Î P 2, znázorníme ho vo forme vzorca cez spojku a súčet modulo dva pomocou čísel 0 a 1. Dá sa to urobiť, keďže ( X 1 &X 2 , X 1 Á X 2, 0, 1) je dokončená v R 2. Na základe vlastnosti X & (rÅ z) = xy Å xz môžete rozšíriť všetky zátvorky, priniesť podobné výrazy a dostanete polynóm z n premenné pozostávajúce z členov formulára NS NS ...NS spojené znakom Å. Takýto polynóm sa nazýva Zhegalkinov polynóm.

Celkový pohľad na Zhegalkinov polynóm:

kde , s = 0, 1, ..., n, a o s= 0 dostaneme voľný termín a 0 .

Znázornenie funkcie vo forme Zhegalkinovho polynómu

1. Ľubovoľnú funkciu reprezentujeme vzorcom nad ( X 1 &X 2) a nahradiť = XÅ1. Táto metóda je vhodná, ak je funkcia špecifikovaná vzorcom.

Príklad 9. (X 1 (X 2 X 3))(X 1 Ú X 2) X 3 = (X 1 Ú X 2 Ú X 3)(X 1 Ú X 2) X 3 = (`X 1 X 2 Ú X 1 X 3 Ú X 1 X 2 Ú X 2 Ú X 2 X 3)X 3 = (`X 1 X 3 Ú X 2)X 3 = X 1 X 3 X 2 X 3 = ((X 1 X 3 Å1) X 2 Å1) X 3 = X 1 X 2 X 3 Å X 2 X 3 Å X 3 .

Je potrebné mať na pamäti, že párny počet rovnakých výrazov v súčte nad mod 2 dáva 0.

2. Metóda nedefinovaných koeficientov. Je vhodné, ak je funkcia definovaná tabuľkou.

Príklad 10.

Neurčitými koeficientmi píšeme Zhegalkinov polynóm pre funkciu troch premenných f(X 1 , X 2 , X 3) = (01101001) = a 0 Å a 1 NS 1 Á a 2 NS 2 Á a 3 NS 3 Å b 1 X 1 X 2 Á b 2 X 2 X 3 Å b 3 X 1 X 3 Å cx 1 X 2 X 3. Potom nájdeme koeficienty pomocou hodnôt funkcie na všetkých množinách. Na scéne (0, 0, 0) f(0, 0, 0) = 0, na druhej strane dosadením tejto množiny do polynómu dostaneme f(0, 0, 0) = a 0, teda a 0 = 0. f(0, 0, 1) = 1, dosadením množiny (0, 0, 1) v polynóme dostaneme: f(0, 0, 1) = a 0 Å a 3, pretože a 0 = 0, teda a 3 = 1. Podobne f(0, 1, 0) = 1 = a 2, f (0, 1, 1) = 0 = a 2 Á a 3 Å b 2 b 2 = 0; a 1 = 1; 0 = a 1 Á a 3 Å b 3 , b 3 = 0; 0 = a 1 Á a 2 Á b 1 , b 1 = 0; 1 = 1 Å 1 Å 1 Å c; c= 0; potom Zhegalkinov polynóm pre túto funkciu bude mať tvar: f(X 1 , X 2 , X 3) = X 1 Á X 2 Á X 3 .

Zhegalkinov polynóm možno získať aj pomocou Pascalovho trojuholníka v jednotkách jeho ľavej strany podľa nasledujúcej tabuľky. Zostrojme pre funkciu Zhegalkinov polynóm f= (10011110). Horná strana trojuholníka je funkcia f... Akýkoľvek iný prvok trojuholníka je súčtom modulo dvoch susedných prvkov predchádzajúceho riadku. Ľavá strana trojuholníka pre funkciu f obsahuje šesť jednotiek. Zhegalkinov polynóm bude obsahovať šesť členov. Prvá jednotka trojuholníka zodpovedá množine (000). Prvý člen polynómu je 1. Tretia jednotka zdola na ľavej strane trojuholníka zodpovedá množine (101). Ako výraz v polynóme berieme X 1 X 3. Rovnako pre ostatné trojuholníkové jednotky. Naľavo od množín sú zobrazené členy Zhegalkinovho polynómu.

Zhegalkinova veta

Každá funkcia z môže byť reprezentovaná vo forme Zhegalkinovho polynómu jedinečným spôsobom.

Jedinečnosť sa tu chápe až do poradia pojmov v súčte a poradia faktorov v spojkách:

, s = 0, 1, ..., n.

Dôkaz.

Akákoľvek funkcia z R 2 môže byť vyjadrené vzorcom cez ( X 1 & X 2 , X 1 Á X 2, 0, 1) a tento vzorec po otvorení všetkých zátvoriek a zmenšení podobných výrazov dáva Zhegalkinov polynóm. Dokážme jedinečnosť reprezentácie. Zvážte funkcie f(X 1 , ..., x n) od n premenné. Vieme, že všetky takéto funkcie, t.j. ich pravdivostné tabuľky, 2 n... Spočítajme počet rôznych Zhegalkinových polynómov z n premenné, t.j. počet variácií zobrazenia: ... Počet množín sa rovná počtu všetkých podmnožín množiny ( X 1 , ..., x n), patrí sem aj prázdna množina (ak s= 0). Počet podmnožín množiny n prvkov je 2 n a keďže každá množina obsahuje koeficient, ktorý má dve hodnoty: 0 alebo 1, potom bude počet všetkých možných polynómov rovnaký. Keďže každý polynóm zodpovedá jednej funkcii, počet funkcií z n premenných sa rovná počtu polynómov, potom bude každá funkcia zodpovedať jednému polynómu.

Definícia.

Funkcia f(X 1 , ..., x n), Zhegalkinov polynóm, pre ktorý má nasledujúci tvar, lineárny vzhľadom na premenné: f = a 0 Å a 1 NS 1 Á a 2 NS 2 Е ... Е a n x n, sa nazýva lineárny.

Lemma o nelineárnej funkcii .

Superpozíciou nelineárnej funkcie, negácie a konštanty 1 môžete získať konjunkciu.

Dôkaz.

Nechať byť f(X 1 , ..., x n) Je nelineárna funkcia. Potom Zhegalkinov polynóm obsahuje výraz, ktorý obsahuje súčin x i x j... Pre jednoduchosť to budeme predpokladať X 1 X 2 v Zhegalkinovom polynóme je tento produkt. Po zoskupení pojmov funkcia f reprezentovať vo forme

Funkcia h 0 nie je identická nula, inak v Zhegalkinovom polynóme chýba člen so súčinom X 1 X 2. Potom je tu sada ( a 3 , …, a n) od 0 a 1, pre ktoré h 0 (a 3 , …, a n) = 1. Let h 1 (a 3 , …, a n) = a, h 2 (a 3 , …, a n) = b, h 3 (a 3 , …, a n) = c... Potom

Zostavme funkciu:

Kde d = ab Å c... Ak d= 0 teda h(X 1 , X 2) = X 1 X 2. Ak d= 1 teda h(X 1 , X 2) = X 1 X 2 Å 1 a potom Lema je dokázaná.

Funkcia f(X 1 , ..., X n) zostáva konštantná aÎ (0, 1) ak f(a, …, a) = a.

Príklad 11.

Funkcia xy zachováva 0, zachováva 1. Funkcia X® r zachováva 1 a nezachováva 0.

Minimalizácia boolovských funkcií

Minimalizácia normálnych foriem

Minimálna DNF (MDNF) funkcie f(X 1 , ... ,x n) sa nazýva DNF, ktorý implementuje funkciu f a obsahujúci minimálny počet symbolov premenných v porovnaní so všetkými ostatnými typmi DNF, ktoré implementujú funkciu f.

Ak pre akúkoľvek množinu = ( a 1 , ..., a n) hodnoty podmienok premenných g() = 1 znamená, potom funkcia g nazývaná časť funkcie f(alebo funkciu f pokrýva funkciu g). Ak navyše pre nejakú množinu = ( c 1 , ..., c n) funkciu g() = 1, potom hovoria, že funkcia g pokrýva jednotku funkcie f na scéne (alebo čo g pokrýva zložku jednotky funkcie f). Všimnite si, že jednotka je súčasťou funkcie f je tam časť funkcie f pokrývajúci jedinú jednotku funkcie f.

Elementárna konjunkcia K sa nazýva implikant funkcie f ak pre akúkoľvek množinu = ( a 1 , ..., a n) z podmienky 0 a 1 K() = 1 znamená f()=1.

Implicitné K funkcie f sa nazýva jednoduchý, ak výraz získaný z neho vyhodením akýchkoľvek faktorov už nie je implikantom funkcie f.

Je jasné, že akýkoľvek implikant funkcie f je tam časť funkcie f.

Veta 5.

Akákoľvek funkcia je realizovaná disjunkciou všetkých jej primárnych imlikantov (PI).

teda f = A... Veta je dokázaná.

Skrátene DNF funkcie f existuje disjunkcia všetkých implikantov jednoduchých funkcií f... Akákoľvek funkcia f realizuje jeho skrátene DNF. Pre každú funkciu, ktorá nie je identicky nulová, existuje jedinečná skratka DNF.

Nechať byť A a B- ľubovoľné vzorce. Nasledujúce reverzibilné pravidlá pre transformáciu DNF vyplývajú z vlastností booleovských operácií:

1) - úplné spojenie (nasadenie);

2) - neúplné lepenie;

3) - generalizované lepenie;

4) - absorpcia;

5) - idempotencia (odstránenie duplicitných členov).

Quineova veta. Ak SDNF funguje f vykonať všetky operácie neúplného lepenia a potom všetky operácie absorpcie a odstraňovania duplicitných termínov, výsledkom bude zníženie funkcie DNF f.

Dôkaz.

Nech máme skrátené DNF funkcie f... Urobme všetky operácie expanzie pre každý jednoduchý implikant, aby sme získali chýbajúce premenné v každom disjunktívnom člene redukovaného DNF. Vo výslednom výraze z viacerých rovnakých disjunktívnych výrazov ponecháme len jednu kópiu. V dôsledku toho získame funkciu SDNF f... Teraz, vychádzajúc zo získaného SDNF, v opačnom poradí vykonáme operácie pridávania rovnakých disjunktívnych členov (pomocou pravidiel idempotencie), neúplného lepenia a absorpcie. V dôsledku toho dostaneme originál skrátený DNF.

3.1 Dekompozícia booleovských funkcií v premenných

3.2 Zhegalkinova algebra

Vyššie sme ukázali, že pomocou pravdivostnej tabuľky je možné špecifikovať akúkoľvek boolovskú funkciu. Táto časť popisuje prechod od tabuľkového prechodu nastavenia funkcie k analytickému.

3.1 Dekompozícia booleovských funkcií v premenných.

Nech G je parameter rovný 0 alebo 1. Zaveďme zápis:

Je ľahké overiť to overením X G = 1 vtedy a len vtedy X = G. Z toho vyplýva, že spojka
sa rovná 1 (tu sa G rovná 0 alebo 1) vtedy a len vtedy
... Napríklad spojka
(v ktorom G 2 = G 1 = 0, G 3 = G 4 = 1) sa rovná 1 iba v prípade, keď X 1 =X 2 = 0,X 3 =X 4 = 1.

Veta 1Akákoľvek booleovská funkciaf(X 1 , X 2 ,…, X n ) môžu byť prezentované v tejto forme:

kde 1 ≤k ≤ n, v disjunkcii sa preberajú všetky množiny premenných hodnôt.

Táto reprezentácia sa nazýva expanzia funkcie z hľadiska premenných.
... Napríklad pre n = 4, k = 2 má rozšírenie (3.1) tvar:

.

Dokážme platnosť expanzie (3.1). Na tento účel vezmite ľubovoľnú množinu hodnôt premenných
... Ukážme, že ľavá a pravá strana vzťahu (3.1) majú rovnakú hodnotu. Skutočne, odvtedy X G = 1 vtedy a len vtedy X = G, potom medzi 2 К spojkou
na pravej strane (3.1), iba jeden v ktorom
... Všetky ostatné spojky
sa rovnajú nule.

Preto . V dôsledku rozkladu (3.1) získame nasledujúce dva špeciálne rozklady.

Variabilná expanziaX n :

Ak booleovská funkcia nie je konštantná 0, potom expanzia

Rozšírenie vo všetkých premenných:

,
(3.3)

kde sa disjunkcia preberá všetky množiny
pre ktoré je hodnota funkcie
sa rovná 1.

Rozšírenie (3.3) sa nazýva dokonalá disjunktívna normálna forma (skratka pre SDNF) funkcie.

Rozšírenie (3.3) poskytuje spôsob konštrukcie SDNF. Za týmto účelom označte všetky riadky v tabuľke pravdy
, v ktorom
... Pre každý takýto riadok tvoríme spojku
a potom všetky výsledné spojky spojíme so znakom disjunkcie.

Existuje teda zhoda jedna ku jednej medzi pravdivostnou tabuľkou funkcie
a jeho SDNF. To znamená, že SDNF pre booleovskú funkciu je jedinečný.

Jediná booleovská funkcia, ktorá nemá SDNF, je konštanta 0.

Príklad 1 Nájdite dokonalý disjunktívny tvar pre funkciu
.

Zostavme pravdivostnú tabuľku pre túto funkciu:

Odtiaľto dostaneme:
==.

Nasledujúce rozšírenie booleovských funkcií hrá dôležitú úlohu v algebre logiky.

Veta 2Akákoľvek booleovská funkcia
môžu byť prezentované v nasledujúcej forme:

kde 1≤k≤n a je prevzatá konjunkcia všetko cez 2 k množiny premenných hodnôt.

Skutočne, nech
- ľubovoľný súbor premenných hodnôt. Ukážme, že ľavá a pravá strana vzťahu (3.4) majú rovnakú hodnotu. Pretože
iba ak
, potom medzi 2 k disjunkcie
na pravej strane (3.4) zmizne iba jeden, v ktorom
... Všetky ostatné vety sa rovnajú 1.

Preto
==
.

Rozšírenia booleovských funkcií vyplývajú priamo z rozšírenia (3.4):

Posledný rozklad sa nazýva dokonalá konjunktívna normálna forma (SKNF). Rozšírenie (3.6) poskytuje spôsob konštrukcie SKNF. Za týmto účelom označte všetky riadky v tabuľke pravdy
, v ktorom. Pre každý takýto riadok vytvoríme disjunkciu
a potom všetky vzniknuté spojky spojíme spojkovým znamienkom. Existuje teda zhoda jedna ku jednej medzi pravdivostnou tabuľkou funkcie
a jeho SKNF. To znamená, že SKNF pre booleovskú funkciu je jedinečný.

Jediná booleovská funkcia, ktorá nemá SCNF, je konštanta 1.

Príklad 2 Nájdite dokonalú konjunktívnu normálnu formu funkcie
.

Zostavme si pravdivostnú tabuľku pre túto funkciu.

Z toho získame SKNF

Vzorec formulára (krátky zápis
), kde
- spojky
volal disjunktívna normálna forma (DNF).

Na základe vyššie uvedenej definície DNF budú existovať napríklad výrazy:
,
.

Ako je uvedené v článku 2.2, všetky logické operácie možno zredukovať na tri: konjunkciu, disjunkciu a negáciu. Navyše vzhľadom na de Morganov zákon možno predpokladať, že znamienko negácie možno pripísať iba premenným.

Teraz pomocou distributívneho zákona rozšírime zátvorky a získame disjunktívnu normálnu formu. Takže nasledujúca veta je pravdivá.

Veta3 Pre každý vzorec algebry logiky existuje jeho ekvivalentná disjunktívna normálna forma.

Dôkaz tejto vety poskytuje spôsob, ako zostrojiť disjunktívnu normálnu formu pre akýkoľvek vzorec v algebre logiky.

Príklad 3 Nájdite disjunktívnu normálnu formu pre nasledujúci vzorec:
.

Bez znamienka
podľa zákona
a použitím de Morganových zákonov a dvojitej negácie dostaneme:

Potom pomocou zákona distributivity rozšírime zátvorky

Posledným výrazom je disjunktívna normálna forma.

Zobraziť formulár
(krátky vstup ), kde
- disjunkcie
volal konjunktívna normálna forma (CNF).

Sú to napríklad výrazy:

,
.

Ako je uvedené vyššie, pre každý vzorec algebry logiky existuje ekvivalentný disjunktívny tvar. Pomocou distribučného zákona je ľahké získať CNF z daného DNF.

Takže nasledujúca veta je pravdivá.

Veta 4Pre každý vzorec algebry logiky existuje ekvivalentná konjunktívna normálna forma.

Dôkaz tejto vety poskytuje spôsob, ako zostrojiť konjunktívnu normálnu formu pre akýkoľvek vzorec v algebre logiky.

Príklad4 Nájdite disjunktívne a konjunktívne normálne formy pre nasledujúci vzorec:
.

Používanie zákona
, vylúčte znamenie
... Dostaneme vzorec
.

Pomocou de Morganovho zákona získame vzorec
... Rozšírením zátvoriek dostaneme disjunktívnu normálnu formu

.

Ak chcete získať konjunktívnu normálnu formu, použijeme vzorec
distributívny zákon, dostaneme:

Posledný výraz je konjunktívna normálna forma. Pretože
a
, potom získaný CNF je ekvivalentný nasledujúcemu CNF:

Spomedzi všetkých normálnych vzorcov tohto vzorca vyberáme perfektnú normálnu formu, disjunktívnu aj konjunktívnu. Ak vezmeme do úvahy rozklad (3), je ľahké vidieť, že dokonalá disjunktívna normálna forma vzorca logickej algebry obsahujúcej presne n rôznych premenných je jej disjunktívna normálna forma, v ktorej:

1) všetky spojky sú párovo odlišné;

2) každá spojka obsahuje presne n premenných;

3) každá spojka obsahuje všetkých n premenných.

Pomocou príkladu 1 sme skúmali jeden zo spôsobov konštrukcie SDNF na základe zostavenia pravdivostnej tabuľky. Ďalší spôsob konštrukcie SDNF je založený na aplikácii zákonov algebry logiky.

Príklad 5 Nájdite perfektnú disjunktívnu formu vzorca
.

Pomocou toho
, dostaneme
... Vzhľadom na de Morganove zákony a dvojitú negáciu sme dostali disjunktívnu normálnu formu
... Tento DNF je ekvivalentný vzorcu.

Rozbalením zátvoriek dostaneme:.

Pomocou zákona idempotencie získame požadovaný SDNF:

Ak vezmeme do úvahy rozklad (3.6), je ľahké vidieť, že dokonalá konjunktívna normálna forma vzorca Booleovej algebry obsahujúca presne n rôznych premenných, existuje jeho konjunktívna normálna forma, v ktorej:

1) všetky disjunkcie sú párovo odlišné;

2) každá disjunkcia obsahuje presne n členov;

3) v každej disjunkcii je všetkých n premenných.

Pomocou príkladu 2 sme skúmali jeden zo spôsobov konštrukcie SCNF na základe zostavenia pravdivostnej tabuľky. Ďalší spôsob konštrukcie SKNF je založený na aplikácii zákonov algebry logiky.

Príklad 6 Nájdite dokonalú konjunktívnu normálnu formu vzorca
.

Použitím,
, dostaneme
.

Tento vzorec je konjunktívnou normálnou formou. To sa rovná vzorcu.

Pomocou distribučného zákona dostaneme:

Aplikovaním zákona idempotencie získame požadovanú dokonalú konjunktívnu normálnu formu

rovnako pravdivé ak pre všetky hodnoty premenných v ňom zahrnutých nadobúda hodnotu veru.

Príklady identicky pravdivých vzorcov sú:

Algebra logického vzorca je tzv rovnako falošné, ak pre všetky hodnoty premenných v ňom zahrnutých nadobúda hodnotu Klamstvo.

Príklady identicky falošných vzorcov sú:

,

Algebra logického vzorca je tzv uskutočniteľné, ak pre niektoré hodnoty premenných v ňom zahrnutých nadobúda hodnotu pravda.

Príklady spustiteľných vzorcov sú nasledujúce vzorce:

,
.

V algebre logiky môže nastať nasledujúci problém: naznačiť metódu (algoritmus), ktorý umožní každému vzorcu algebry logiky zistiť, či je identicky pravdivý alebo nie. Úloha sa volá problémy s riešením.

Zvážte nasledujúce dva spôsoby riešenia tohto problému.

Metóda 1 (tabuľková) Na určenie, či je daný vzorec identicky pravdivý alebo nie, stačí zostaviť jeho pravdivostnú tabuľku.

Táto metóda, hoci poskytuje zásadné riešenie problému riešiteľnosti, je však dosť ťažkopádna.

Metóda 2 založené na redukcii vzorcov na normálnu formu.

Veta 4Vzorec logickej algebry je identicky pravdivý vtedy a len vtedy, ak každá disjunkcia vo svojej konjunktívnej normálnej forme obsahuje nejakú premennú spolu s jej negáciou.

V skutočnosti, ak každá disjunkcia v konjunktívnej normálnej forme obsahuje premennú spolu s jej negáciou, potom sa všetky disjunkcie rovnajú 1, pretože
,
... Z toho vyplýva, že CNF je rovnako pravdivý.

Teraz nech je tento vzorec rovnako pravdivý a nech
existuje určitá disjunkcia v CNF tohto vzorca. Predpokladajme, že daná disjunkcia neobsahuje premennú spolu s jej negáciou. V tomto prípade môžeme každej premennej, ktorá nie je pod záporným znamienkom, priradiť hodnotu 0 a každej premennej so záporným znamienkom hodnotu 1. Po tejto substitúcii sa všetky disjunkcie stanú rovnými 0, preto vzorec neplatí rovnako. Máme rozpor.

Príklad 7 Zistite, či vzorec

.

Pomocou toho
, dostaneme
.

Aplikovaním zákona distributivity dostaneme CNF:

Keďže každá disjunkcia obsahuje nejakú premennú spolu s jej negáciou, vzorec je identicky pravdivý.

Podobne ako v predchádzajúcej vete je dokázaná nasledujúca veta:

Veta 5 Vzorec algebry logiky vtedy a len vtedy, ak je rovnako nepravdivý, keď každá spojka vo svojej disjunktívnej forme obsahuje nejakú premennú spolu s jej negáciou.

Nechať byť s nadobúda hodnoty 0 alebo 1, t.j. s {0, 1}.

Predstavme si notáciu:

x s = Ø X, ak s = 0, x s = X, ak s = 1.

Tie. X 0 = Ø X, X 1 = X.

To je zrejmé x s= 1 ak X = s a x s= 0 ak X s.

Veta 4.5(o expanzii booleovskej funkcie v premenných).

Každá booleovská funkcia f(X 1 , X 2 , ... , x n) môže byť reprezentovaný ako:

f(X 1 , X 2 , ... , x n) = f(X 1 , X 2 , ... , x m, x m +1 , ... , x n) =

V X 1 s 1 &X 2 s 2 &...&x m sm& f(s 1 , s 2 , ... s m, x m +1 , ... , x n), (4.1)

m n, kde sa disjunkcia preberá všetky množiny ( s 1 , s 2 , ... , s m) (sú 2 m).

Napríklad pre m = 2, n= 4, rozšírenie (4.1) zahŕňa štyri (2 m= 2 2 = 4) spojka a má tvar:

f(X 1 , X 2 , X 3 , X 4) = X &X &f(0, 0, X 3 , X 4) V X &X &f(0, 1, X 3 , X 4) V X & X &f(1, 0, X 3 , X 4) V X & X &f(1, 1, X 3 , X 4) = Ø X 1 a Ø X 2 &f(0, 0, X 3 , X 4) V Ø X 1 &X 2 &f(0, 1, X 3 , X 4) V X 1 a Ø X 2 &f(1, 0, X 3 , X 4) V X 1 &X 2 &f(1, 1, X 3 , X 4).

Dôkaz vety 4.5.

Veta bude dokázaná, ak ukážeme, že rovnosť (4.1) platí pre ľubovoľnú množinu premenných ( r 1, r 2 , ... , y m, y m +1 , ... , y n) .

Túto ľubovoľnú množinu premenných dosadíme na ľavú a pravú stranu rovnosti (4.1).

Na ľavej strane sa dostaneme f (r 1, r 2 , ... , y n) .

T. do. y s= 1 iba vtedy r = s, potom medzi 2 m spojky r 1 s 1 &r 2 s 2 &...&y m sm na pravej strane (4.1) sa iba jedna zmení na 1 - tá, v ktorej r 1 = s 1 ,…, y m = s m... Všetky ostatné spojky sa rovnajú 0. Preto na pravej strane (4.1) dostaneme:

r 1 r 1 &r 2 r 2 &...&y m ym&f(r 1, r 2 , ... , y m, y m +1 , ... , y n) = f(r 1, r 2 , ... , y n) .

Veta 4.5 je dokázaná.

Veta 4.6(o reprezentácii booleovskej funkcie vzorcom v SDNF),

Akákoľvek booleovská funkcia f(X 1 , X 2 , ... , x n), ktorý nie je identicky rovný 0, môže byť reprezentovaný vzorcom v SDNF, ktorý je jednoznačne určený až po preskupenie disjunktívnych členov.

Dôkaz.

o m = n dostávame dôležitý dôsledok vety 4.5:

f(X 1 , X 2 , ... , x n) = V X 1 s 1 &X 2 s 2 &...&x n sn, (4.2)

f(s 1 , s 2 , ... , s n) = 1

kde sa disjunkcia preberá všetky množiny ( s 1 , s 2 , ... , s n), kde f = 1.

Je zrejmé, že expanzia (4.2) nie je nič iné ako SDNF vzorca f ktorý obsahuje toľko spojok, koľko ich je v tabuľke hodnôt f... V dôsledku toho je SDNF pre akúkoľvek booleovskú funkciu jedinečný až do preskupenia jej disjunktívnych členov.

Je tiež zrejmé, že pre booleovskú funkciu f(X 1 , X 2 , ... , x n), zhodne rovný 0, rozklad (2) neexistuje.

Vzhľadom na vyššie uvedené, získať vzorec pre booleovskú funkciu f(X 1 , X 2 , ... , x n) v SDNF, môžete použiť nasledujúci algoritmus.

Algoritmus 4.3. (Algoritmus na reprezentáciu booleovskej funkcie danej tabuľkou pomocou vzorca v SDNF).

Krok 1. s 1 , s 2 , ... , s n pre ktoré je hodnota f rovná sa 1, t.j. f (s 1 , s 2 , ... , s n) = 1.

Krok 2. Pre každú takúto množinu (riadok tabuľky) zostavíme spojku X 1 s 1 &X 2 s 2 &...&x n sn, kde x i si = x i, ak s i= 1 a x i si =Ø x i, ak s i = 0, i = 1, 2, ... ,n.

Krok 3 Všetky výsledné spojky robíme disjunkciu. Výsledkom bude vzorec pre túto funkciu v SDNF.

Príklad 4.15.

Nájdite vzorec v SDNF pre funkciu f(X 1 , X 2 , X 3) uvedené v tabuľke 4.4.

f(X 1 , X 2 , X 3) = 1. Toto je 4., 5. 6. a 8. riadok.

2. Pre každý vybraný riadok zostavte spojky podľa pravidla špecifikovaného v kroku 2. Pre štyri vybrané riadky získame:

X 1 0 &X 2 1 &X 3 1 = Ø X 1 &X 2 &X 3 .

X 1 1 &X 2 0 &X 3 0 = X 1 a Ø X 2 a Ø X 3 .

X 1 1 &X 2 0 &X 3 1 = X 1 a Ø X 2 &X 3 .

X 1 1 &X 2 1 &X 3 1 = X 1 &X 2 &X 3 .

3. Zo všetkých získaných konjunkcií zostavíme disjunkciu a nájdeme SDNF:

f(X 1 , X 2 , X 3) = Ø X 1 &X 2 &X 3 V X 1 a Ø X 2 a Ø X 3 V X 1 a Ø X 2 &X 3 V X 1 &X 2 &X 3 .

Uisťujeme sa, že tento výraz sa zhoduje s reprezentáciou SDNF nášho vzorca získaného skôr v príklade 4.13.

Komentujte. Ak je booleovská funkcia daná vzorcom v SDNF, potom použitím Algoritmu 4.3 v opačnom poradí môžeme ľahko získať tabuľku hodnôt tejto funkcie.

Veta 4.7(o reprezentácii booleovskej funkcie vzorcom v SKNF),

Akákoľvek booleovská funkcia f(X 1 , X 2 , ... , x n), ktorý nie je identicky rovný 1, môže byť v SKNF reprezentovaný vzorcom, ktorý je jednoznačne určený až po preskupenie disjunktívnych členov.

Dôkaz.

Zvážte funkciu Ø f(X 1 , X 2 , ... , x n). Ak sa podľa vety 4.6 nerovná 0, existuje na to vzorec v SDNF. Označujeme tento vzorec F 1. Je zrejmé, že podmienka, že funkcia Ø f(X 1 , X 2 , ... , x n) nie je identicky rovné 0, čo je ekvivalentné podmienke, že funkcia f(X 1 , X 2 , ... , x n) nie je zhodne rovný 1. Okrem toho podľa de Morganovho zákona vzorec F 2º Ø F 1 je v SKNF (negácia spojky je disjunkcia negácií). Podľa zákona dvojitej negácie

F 2º Ø F 1º ØØ f(X 1 , X 2 , ... , x n) º f(X 1 , X 2 , ... , x n),

čo dokazuje vetu.

Získanie vzorca booleovskej funkcie f(X 1 , X 2 , ... , x n) v SKNF by sa mal použiť nasledujúci algoritmus.

Algoritmus 4.4. (Algoritmus na reprezentáciu booleovskej funkcie danej tabuľkou vzorcom v SKNF)

Krok 1. Vyberte všetky množiny premenných v tabuľke s 1 , s 2 , ... , s n pre ktoré je hodnota f (s 1 , s 2 , ... , s n) = 0.

Krok 2. Pre každú takúto množinu (riadok tabuľky) zostavíme disjunkciu

X 1 Ø s 1 V X 2 Ø s 2 V ... V x n Ø sn, kde x i Ø si = x i, ak s i= 0 a x i Ø si = Ø x i, ak s i = 1, i = 1, 2, ... , n.

Krok 3 Zo všetkých získaných disjunkcií skladáme konjunkciu. Výsledkom je SKNF.

Príklad 4.16.

Nájdite vzorec v SKNF pre funkciu f(X 1 , X 2 , X 3) uvedené v tabuľke 4.4.

1. Vyberte riadky v tabuľke, kde f(X 1 , X 2 , X 3) = 0. Toto sú 1., 2. a 3. a 7. riadok.

2. Pre každý vybraný riadok zostavte disjunkcie podľa pravidla špecifikovaného v kroku 2. Získame pre tri vybrané riadky:

X 11 V X 2 1 V X 3 1 = X 1 V X 2 V X 3 .

X 11 V X 2 1 V X 3 0 = X 1 V X 2 VØ X 3 .

X 11 V X 20 V X 3 1 = X 1 VØ X 2 V X 3 .

X 10 V X 20 V X 3 1 = Ø X 1 VØ X 2 V X 3 .

3. Zo všetkých získaných disjunkcií zostavíme konjunkciu a nájdeme SKNF:

f(X 1 , X 2 , X 3) = (X 1 V X 2 V X 3)&(X 1 V X 2 VØ X 3)&(X 1 VØ X 2 V X 3) & (Ø X 1 VØ X 2 V X 3).

Tento výraz sa zhoduje s reprezentáciou SKNF nášho vzorca získaného skôr v príklade 4.14.

Komentujte. Keďže celkový počet riadkov v tabuľke funkcií je 2 n, potom ak je počet disjunktívnych členov v SDNF rovný p, a počet konjunktívnych pojmov v SKNF je q, potom p+q=2n.

Takže pre funkciu uvažovanú v príkladoch 4.15 a 4.16, n = 3, p = 4, q = 4, p + q = 8 = 2 3 .

Zvážte otázku prezentácie n-lokálna boolovská funkcia f(X 1 ,X 2 ,…,X n) nejakým vzorcom výrokovej algebry.

Uveďme si zápis, kde sa parameter rovná 0 alebo 1.

To je zrejmé

Veta 1.1. Každá funkcia booleovskej algebryf(X 1 , X 2 ,…, X n ) pre akékoľvekm (1£ m £ n) môžu byť zastúpené v tejto forme:

kde sa disjunkcia preberá všetky možné množiny premenných hodnôt.

Dôkaz... Zvážte ľubovoľnú množinu hodnôt pre všetky premenné danej funkcie. Ukážme, že na tejto množine má ľavá a pravá strana vzorca (1) rovnakú hodnotu. Ľavá strana sa rovná , správny

odkedy , ak len, ak, potom príslušný logický člen možno zahodiť.

Komentujte... Reprezentácia funkcie naznačená vo vete sa nazýva expanzia funkcie v zmysle m premenné.

Dôsledok 1(expanzia v jednej premennej).

V tomto prípade funkcie a sa volajú rozkladné zložky.

Dôsledok 2(rozšírenie vo všetkých premenných).

Je zrejmé, že ak , potom

Ak teda funkcia f(X 1 ,X 2 ,…,X n) nie je identicky nepravdivá funkcia, potom môže byť vyjadrená ekvivalentným vzorcom, ktorý je logickým súčtom rôznych súčinov tvaru a takéto zobrazenie je jedinečné.

Vzorec (2) sa dá značne zjednodušiť. Je známe, že každý vzorec algebry logiky môže byť redukovaný ekvivalentnými transformáciami na vzorec obsahujúci iba konjunkciu a negáciu alebo disjunkciu a negáciu. V dôsledku vykonania ekvivalentných transformácií je možné získať niekoľko vzorcov, avšak iba jeden z nich bude mať nasledujúce vlastnosti:

1. Každý logický výraz obsahuje všetky premenné zahrnuté vo vzorci f(X 1 ,X 2 ,…,X n).

2. Ani jeden logický člen neobsahuje premennú aj jej negáciu.

3. Všetky logické pojmy vo vzorci sú rôzne.

4. Žiadny logický člen neobsahuje tú istú premennú dvakrát.

Tieto štyri vlastnosti sa nazývajú vlastnosti dokonalosti(alebo vlastnosti C).

Ak f(X 1 ,X 2 ,…,X n) je daný pravdivostnou tabuľkou, potom sa dá zodpovedajúci vzorec algebry logiky celkom jednoducho rekonštruovať. Pre všetky hodnoty argumentov X 1 ,X 2 ,…,X n na ktorom f má hodnotu 1, musíte napísať spojenie príkazov elementárnych premenných, pričom ako spojovací výraz x i, ak x i= 1, a ak x i= 0. Nevyhnutným vzorcom bude disjunkcia všetkých zaznamenaných spojok. O významoch f 0 sa nemusíte báť, pretože zodpovedajúci člen vo vzorci sa bude rovnať 0 a môže byť vyradený z dôvodu ekvivalencie fÚ 0 ≡ f.

Napríklad, nechajte funkciu f(X, r, z) má nasledujúcu pravdivostnú tabuľku:

X	r	z	f(X, r, z)

Množina B, na ktorej sú definované dve binárne operácie (konjunkcia a disjunkcia) a jedna unárna operácia (negácia) a vybrané dva prvky 0 a 1, sa nazýva Booleova algebra.

Okrem toho pri týchto operáciách musia byť splnené tieto vlastnosti:

Asociativita

Komutatívnosť

Distributivita konjunkcie vzhľadom na disjunkciu

Distributivita disjunkcie vzhľadom na konjunkciu

Idempotencia

Dvakrát nie

Konštantné vlastnosti

De Morganove pravidlá

Zákon protirečenia

Vylúčený tretí zákon

V algebre logiky sa tieto zákony nazývajú ekvivalencie.

Dokonalé normálne formy

Dokonalá disjunktívna normálna forma

Predstavme si notáciu:

; A A = 1; X A = 1, ak X = A, X A = 0, ak XA.

Vzorec X A 1 …… X A n, kde A = je ľubovoľná binárna množina a medzi premennými Xi môžu byť aj zhodné, sa nazýva elementárna konjunkcia.

Akákoľvek disjunkcia elementárnych konjunkcií sa nazýva disjunktívna normálna forma (DNF).

Elementárna spojka sa nazýva správna, ak do nej každá premenná vstupuje najviac raz (vrátane jej výskytu pod znamienkom negácie).

Napríklad: 1) (ikona spojky je v tomto prípade vynechaná).

1), 4) - pravidelné elementárne spojky;

2) - premenná x vstupuje raz sama a druhýkrát pod znamienko negácie;

Premenná y sa objavuje trikrát: raz sama o sebe a dvakrát pod znamienkom negácie.

Regulárna elementárna konjunkcia sa nazýva úplná vzhľadom na premenné x 1 ... ..x n, ak do nej každá z týchto premenných vstupuje iba raz (môže byť aj záporné znamienko).

Napríklad: zo spojok uvedených v predchádzajúcom príklade je úplný len 4) vzhľadom na premenné x, y, z, t; a vzhľadom na premenné x, y, z je kompletný len 1).

Dokonalá disjunktívna normálna forma (CDNF) vzhľadom na premenné x 1 ... ..xn je disjunktívna normálna forma, v ktorej neexistujú identické elementárne spojky a všetky elementárne spojky sú správne a úplné vzhľadom na premenné x 1 ... ..xn

Expanzia v premenných

Veta 1. Každá logická funkcia môže byť reprezentovaná v SDNF:

kde m, a disjunkcia preberá všetky 2 m množiny hodnôt premenných x 1, ... x m. Funkcia f je rozšírená v prvých n-premenných. Táto rovnosť sa nazýva variabilná expanzia. x 1, ... x m. Napríklad pre n = 4, m = 2, je rozšírenie:

veta sa dokazuje dosadením do oboch strán rovnosti (1) ľubovoľného súboru (b 1,…, b m, b m + 1,…, b n) všetkých n-premenných.

Pre m = 1 z (1) dostaneme rozšírenie funkcie v jednej premennej:

Je zrejmé, že podobné rozšírenie platí pre ktorúkoľvek z n-premenných.

Ďalší dôležitý prípad je, keď n = m. V tomto prípade všetky premenné na pravej strane (1) dostanú pevné hodnoty a funkcie v spojení pravej strany sa stanú rovnými 0 alebo 1, čo dáva:

kde disjunkcia preberá všetky n-tice (b 1… b n), na ktorých f = 1. Pre f = 0 je množina spojok na pravej strane prázdna. Tento rozklad sa nazýva dokonalá disjunktívna normálna forma. SDNF funkcie f obsahuje presne toľko konjunkcií, koľko ich je v pravdivostnej tabuľke funkcie f. Každá množina jednotiek (b 1,…, b n) zodpovedá konjunkcii všetkých premenných, v ktorej x i sa berie s negáciou, ak b i = 0 b, a bez negácie, ak b i = 1. Existuje teda zhoda jedna ku jednej medzi pravdivostnou tabuľkou funkcie f a jej SDNF, a preto je SDNF jedinečná pre akúkoľvek logickú funkciu. Jediná funkcia, ktorá nemá SDNF, je konštanta 0.

Veta 2... Akákoľvek logická funkcia môže byť reprezentovaná ako booleovský vzorec.

V skutočnosti pre akúkoľvek funkciu, okrem konštanty 0, môže jej SDNF slúžiť ako taká reprezentácia. Konštanta 0 môže byť vyjadrená boolovským vzorcom.