Logička funkcija naziva se konjunktivni normalni oblik. Konjunktivni oblici predstavljanja logičkih funkcija

Normalni oblici logičkih funkcija Reprezentacija Bulove funkcije u obliku disjunkcije konjunktivnih članova konstituenata jedinice Ki 2.7 naziva se disjunktivnim normalnim oblikom DNF ove funkcije. sadrže tačno jednu od svih logičkih varijabli uzetih sa ili bez negacija, onda se ovaj oblik reprezentacije funkcije naziva savršena disjunktivna normalna forma SDNF ove funkcije. Kao što možete vidjeti, kada sastavljate SDNF funkciju, morate kreirati disjunkciju svih minterma za koje funkcija uzima vrijednost 1.

Ako vam ovaj rad ne odgovara, na dnu stranice nalazi se lista sličnih radova. Možete koristiti i dugme za pretragu

Predavanje 1.xx

Normalni oblici logičkih funkcija

Reprezentacija Booleove funkcije u obliku disjunkcije konjunktivnih pojmova (jedinični konstituent) K i

, (2.7)

pozvao disjunktivni normalni oblik(DNF) ove funkcije.

Ako su svi konjunktivni pojmovi u DNF-u minterms , tj. sadrže tačno jednu od svih logičkih varijabli, uzetih sa ili bez negacija, onda se ovaj oblik predstavljanja funkcije nazivasavršena disjunktivna normalna forma(SDNF ) ovu funkciju. Zove se SDNF savršeno , jer svaki pojam u disjunkciji uključuje sve varijable; disjunktivni , jer je glavna operacija u formuli disjunkcija. Koncept “normalan oblik” znači nedvosmislen način za pisanje formule koja implementira datu funkciju.

Uzimajući u obzir gore navedeno, iz teoreme 2.1 slijedi sljedeća teorema.

Teorema 2. Bilo koja Booleova funkcija(nije identično 0) može biti predstavljen u SDNF-u, .

Primjer 3. Neka nam je data funkcija u tablici f (x 1 , x 2 , x 3 ) (Tabela 10).

Tabela 10

Na osnovu formule (2.6) dobijamo:

Kao što možete vidjeti, kada sastavljate SDNF funkciju, morate kreirati disjunkciju svih minterm-a na kojoj funkcija poprima vrijednost 1.

Reprezentacija Booleove funkcije u obliku konjunkcije disjunktivnih pojmova (nulti konstituent) D i

, (2.8)

pozvao konjunktivni normalni oblik(CNF) ove funkcije.

Ako su svi disjunktivni CNF termini maxterms , tj. sadrže tačno jednu od svih logičkih varijabli funkcije, uzetih sa ili bez negacija, onda se takav CNF nazivasavršena konjunktivna normalna forma(SKNF) ove funkcije.

Teorema 3. Bilo koja Booleova funkcija(nije identično 1) može se dostaviti SKNF-u, a takva reprezentacija je jedina.

Dokaz teoreme se može izvesti slično kao i dokaz teoreme 2.1 na osnovu sljedeće Šenonove leme o konjunktivnoj dekompoziciji.

Šenonova lema . Bilo koja Booleova funkcija f (x 1, x 2, …, x m) iz m varijable se mogu predstaviti ovako:

. (2.9)

Treba napomenuti da su oba oblika predstavljanja logičke funkcije (DNF i CNF) teoretski jednaka u svojim mogućnostima: bilo koja logička formula može biti predstavljena i u DNF (osim identične nule) i u CNF (osim identične ). Ovisno o situaciji, prikaz funkcije u jednom ili drugom obliku može biti kraći.

U praksi se najčešće koristi DNF, jer je ovaj oblik poznatiji osobi: od djetinjstva je više naviknut na zbrajanje proizvoda nego na množenje suma (u potonjem slučaju intuitivno ima želju da otvori zagrade i tako prijeđe na DNF).

Primjer 4. Za funkciju f (x 1 , x 2 , x 3 ), dato u tabeli. 10, napišite to u SKNF.

Za razliku od SDNF-a, prilikom kompajliranja SCNF-a u tablici istinitosti logičke funkcije, morate pogledati kombinacije varijabli kod kojih funkcija uzima vrijednost 0 i kreirati konjunkciju odgovarajućih maxtermsa,ali varijable se moraju uzeti sa obrnutom inverzijom:

Treba napomenuti da je nemoguće direktno preći sa SDNF funkcije na njen SCNF ili obrnuto. Prilikom pokušaja takvih transformacija, rezultati su funkcije koje su suprotne od željenih. Izrazi za SDNF i SCNF funkcije mogu se direktno dobiti samo iz njegove tablice istinitosti.

Primjer 5. Za funkciju f (x 1 , x 2 , x 3 ), dato u tabeli. 10, pokušajte se prebaciti sa SDNF na SKNF.

Koristeći rezultat primjera 2.3 dobijamo:

Kao što možete vidjeti, pod općom inverzijom dobili smo SCNF logičke funkcije, koja je inverzna funkciji dobivenoj u primjeru 2.4:

jer sadrži sve maxterme koji nisu u izrazu za SCNF funkcije koja se razmatra.

1. Koristeći svojstva operacija (vidi tabelu 9) identitet (), suma po modulu 2 (), implikacija (), prelazimo na operacije I, ILI, NOT (u Booleovoj osnovi).

2. Koristeći svojstva negacije i De Morganove zakone (vidi tabelu 9), osiguravamo da se operacije negacije primjenjuju samo na pojedinačne varijable, a ne na cijele izraze.

3. Koristeći svojstva logičkih operacija AND i OR (vidi tabelu 9), dobijamo normalni oblik (DNF ili CNF).

4. Ako je potrebno, prijeđite na savršene forme (SDNF ili SKNF). Na primjer, da biste dobili SCNF, često morate koristiti svojstvo: .

Primjer 6. Pretvorite logičku funkciju u SKNF

Provodeći redom korake gornjeg algoritma, dobijamo:

Koristeći svojstvo apsorpcije, dobijamo:

Tako smo dobili CNF funkciju f (x 1, x 2, x 3 ). Da biste dobili njegov SCNF, trebate ponoviti svaku disjunkciju u kojoj nedostaje bilo koja varijabla, dva puta sa ovom varijablom i sa njenom negacijom:

2.2.6. Minimiziranje logičkih funkcija

Pošto se ista logička funkcija može predstaviti kao h lične formule, zatim pronalaženje najjednostavnijeg oblika R mazga koja definira Booleovu funkciju, pojednostavljuje logičko kolo koje implementira Booleovu funkciju to tion. Minimalni oblik l O logička funkcijau nekoj osnovi možemo uzeti u obzir onu koja sadrži minimalni broj superpozicija zabave To cije osnove, dozvoljavajući zagrade. Međutim, teško je izgraditi efikasan l algoritam za takvu minimizaciju da bi se dobila minimalna zagrada r we.

Razmotrimo jednostavniji problem minimizacije u sintezi kombinacijskih kola, u kojem ne tražimo minimalni zagrade funkcije, već njen minimalni DNF. Postoje jednostavni, efikasni algoritmi za ovaj zadatak.

Quineova metoda

Funkcija koju treba minimizirati je predstavljena u SDNF-u i na nju se primjenjuju sve moguće nepotpune operacije lijepljenja

, (2.10)

a zatim i apsorpciju

, (2.11)

i ovaj par koraka se primjenjuje više puta. Tako je moguće smanjiti rang pojmova. Ovaj postupak se ponavlja sve dok ne preostane niti jedan termin koji se može vezati za bilo koji drugi termin.

Imajte na umu da se lijeva strana jednačine (2.10) može odmah minimizirati na jednostavniji i očigledniji način:

Ova metoda je loša jer kod takvog direktnog minimiziranja konjunktivni pojmovi ili nestaju, iako su još uvijek mogući slučajevi njihove upotrebe za lijepljenje i apsorpciju sa preostalim pojmovima.

Treba napomenuti da je Quineova metoda prilično radno intenzivna, pa je vjerovatnoća da ćete pogriješiti tijekom transformacije prilično velika. Ali njegova prednost je u tome što se teoretski može koristiti za bilo koji broj argumenata i kako se broj varijabli povećava, transformacije postaju manje komplicirane.

Metoda Carnaughove karte

Metoda Carnot mapa (tabela) je vizualniji, manje radno intenzivan i pouzdan način za minimiziranje logičkih funkcija, ali je njegova upotreba praktično ograničena na funkcije od 3-4 varijable, maksimalno 5-6 varijabli.

Karnotova karta ovo je dvodimenzionalni tabelarni oblik predstavljanja tablice istinitosti Bulove funkcije, koji vam omogućava da lako pronađete minimalne DNF-ove logičkih funkcija u grafičkom vizualnom obliku. Svaka ćelija tabele je povezana sa SDNF mintermom funkcije koja se minimizira, i to na takav način da sve ose simetrije tabele odgovaraju zonama koje su međusobno inverzne u odnosu na neku varijablu. Ovakav raspored ćelija u tabeli olakšava određivanje lepljivih termina SDNF-a (koji se razlikuju po predznaku inverzije samo jedne varijable): oni se nalaze simetrično u tabeli.

Tablice istine i Carnaughove karte za AND i OR funkcije dvije trake e Varijable su predstavljene na Sl. 8. Vrijednost je upisana u svaku ćeliju kartice A Vrijednost funkcije na skupu vrijednosti argumenata koji odgovaraju ovoj ćeliji N druže

A) I b) ILI

Rice. 8. Primjer Karnaughovih mapa za funkcije dvije varijable

U Karnaugh mapi postoji samo jedna 1 za funkciju I, tako da se ne može zalijepiti ni za šta. Izraz za minimalnu funkciju će sadržavati samo termin koji odgovara ovoj 1:

f = x y .

U Carnot karti za funkciju ILI već postoje tri 1 i možete napraviti dva lijepa para, pri čemu 1 odgovara pojmu xy , koristi se dva puta. U izrazu za minimalnu funkciju potrebno je da zapišete termine za parove koji se lijepe zajedno, ostavljajući u njima sve varijable koje se ne mijenjaju za ovaj par, i uklonite varijable koje mijenjaju svoju vrijednost. Za horizontalno lijepljenje dobijemo x , a za vertikalnu y , kao rezultat dobijamo izraz

f = x + y.

Na sl. 9 prikazuje tablice istinitosti dvije funkcije tri varijable ( A ) i njihove Carnot karte ( b i c). Funkcija f 2 razlikuje se od prvog po tome što nije definisan na tri skupa varijabli (u tabeli je to označeno crticom).

Prilikom određivanja minimalne DNF funkcije koriste se sljedeća pravila. Sve ćelije koje sadrže 1 se kombinuju u zatvorene pravougaone oblasti tzv k-kocke, gdje je k = log 2 K, K količina 1 u pravougaonoj površini. U ovom slučaju, svaka oblast treba da bude pravougaonik sa brojem ćelija 2 k, gdje je k = 0, 1, 2, 3, …. Za k = 1 pravougaonik se zove jedan je kocka i sadrži 2 1 = 2 jedinice; za k = 2 pravougaonik sadrži 2 2 = 4 jedinice i zove se dvije kocke; za k = 3 oblast od 2 3 = 8 jedinica se zove tri kocke ; itd. Jedinice koje se ne mogu kombinovati u pravougaonike mogu se pozvati nula kocke , koji sadrže samo jednu jedinicu (2 0 = 1). Kao što se može vidjeti, za čak k površine mogu imati kvadratni oblik (ali ne nužno) i ako su neparne k samo pravougaonici.

Rice. 9. Primjer Karnaughovih mapa za funkcije tri varijable

Ove regije se mogu preklapati, odnosno iste ćelije mogu ući u različite regije. Tada se minimalna DNF funkcija zapisuje kao disjunkcija svih konjunktivnih članova koji odgovaraju k - kocke.

Svako od naznačenih područja na Karnaugh karti je u minimalnom DNF-u predstavljeno konjunkcijom, broj argumenata u kojoj je k manji od ukupnog broja argumenata funkcije m , tj. ovaj broj je jednak mk . Svaka konjunkcija minimalnog DNF-a sastoji se samo od onih argumenata koji za odgovarajuće područje karte imaju vrijednosti ili bez inverzija ili samo sa inverzijama, tj. ne mijenjaju svoje značenje.

Stoga, kada pokrivamo ćelije karte zatvorenim područjima, treba nastojati da broj područja bude minimalan, a da svako područje sadrži što je moguće više ćelija, jer će u tom slučaju broj pojmova u minimalnom DNF biti minimalan i broj argumenata u odgovarajućoj konjunkciji će biti minimalan.

Za funkciju prema Karnaugh karti na sl. 9, b nalazimo

budući da za gornji zatvoreni region varijable x 1 i x 2 imaju vrijednosti bez inverzija, za niže x 1 stvari sa inverzijom, i x 3 bez inverzije.

Nedefinirane vrijednosti na karti na sl. 9, V može se dalje definirati zamjenom sa nulom ili jedinicom. Za ovu funkciju je jasno da je isplativije zamijeniti obje nedefinirane vrijednosti sa 1. U ovom slučaju se formiraju dvije oblasti koje su različite vrste 2-kocke. Tada će izraz za minimalnu DNF funkciju biti sljedeći:

Prilikom konstruisanja zatvorenih područja, dozvoljeno je savijanje Carnotove karte u cilindar i horizontalno i vertikalno. R tikalne osi sa spojem suprotnih strana R vi, tj. jedinice koje se nalaze duž rubova Carnotove karte simetrije h ali se mogu i kombinovati.

Carnaughove karte mogu se crtati na različite načine (slika 10).

a b

Rice. 10. Različiti načini prikazivanja Carnaughovih karata
za funkciju od 3 varijable

Ali najpogodnije opcije za Karnaughove karte za funkcije od 2-4 varijable su one prikazane na Sl. 11 tabela, jer se prikazuju za svaku ćeliju A Imamo sve varijable u direktnom ili inverznom obliku.

a b

Rice. jedanaest. Najprikladnija slika Carnaughovih karata
za funkcije 3 ( a) i 4 (b) varijable

Za funkcije od 5 i 6 varijabli, metoda prikazana na Sl. 10, V.

Rice. 12. Slika Karnaughove karte za funkciju od 5 varijabli

Rice. 13. Slika Karnaughove karte za funkciju od 6 varijabli

Standardna osnova. Elementarne formule su literali. Elementarna konjunkcija (disjunkcija). Disjunktivni (konjunktivni) normalni oblik i savršeni oblik. Teorema: svaka Booleova funkcija različita od 0 (od 1) može biti predstavljena u obliku SDNF (SCNF). Kompletnost standardne osnove. Primeri kompletnih baza: Žegalkinova osnova, Šeferov potez, Pirsova strelica.

Standardna osnova je skup od tri osnovne operacije Booleove algebre: zbrajanje (unija), množenje (presjek) i negacija.

Evo mi ćemo zvati doslovno varijabla x ili njena negacija x i označavamo xˆ. Boolean presek nekoliko literala definisanih različitim varijablama, tj. izraz oblika X = xˆ 1 xˆ 2 . . . xˆ l, tzv elementarna konjunkcija . Zahtjev da sve varijable budu različite određen je sljedećim. Ako konjunkcija uključuje nekoliko identičnih literala, onda je zbog komutativnosti, asocijativnosti i idempotencije konjunkcije moguće, prelazeći na ekvivalentnu formulu, ostaviti samo jedan literal (na primjer, x 1 x 1 = x 1). Ako konjunkcija uključuje varijablu i njenu negaciju, tada je formula ekvivalentna konstanti 0, budući da je x x = 0 i za bilo koju formulu Y imamo Y x x = 0.

Disjunkcija nekoliko elementarnih konjunkcija naziva se disjunktivni normalni oblik , ili DNF . Na primjer,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

Ako je sastav varijabli u svakoj elementarnoj konjunkciji datog DNF-a isti, tada se DNF naziva savršeno . Navedeni primjer je DNF koji nije savršen. Naprotiv, formula

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

postoji savršena forma.

Budući da su u Booleovoj algebri zbrajanje i množenje simetrične operacije i uvijek možete protumačiti sabiranje kao množenje, a množenje kao sabiranje, postoji dvostruki koncept - konjunktivni normalni oblik (KNF ), što je konjunkcija elementarnih disjunkcija, i savršeni konjunktivni oblik (SKNF ). Iz principa dualnosti za simetrične poluprstenove slijedi da se na bilo koju tvrdnju u vezi DNF-a odgovara dualnom tvrdnjom u vezi sa CNF-om, koja se dobija zamjenom sabiranja (disjunkcije) sa množenjem, množenja (konjunkcije) sa sabiranjem, konstanta 0 sa konstantom 1, konstanta 1 sa konstantom 0, odnos poretka sa dualnim (inverznim) redom. Stoga ćemo se dalje fokusirati na proučavanje samo DNF-a.

Teorema 1.4. Bilo koja Booleova funkcija osim konstante 0 može se predstaviti kao SDNF.

◀Složimo se da pod x σ podrazumijevamo formulu x ako je σ = 1, a formulu x ako je σ = 0. Neka funkcija f(y 1 , . . . , y n) uzme vrijednost 1 na vektoru (t 1 , , t n sastavna jedinica ). Tada elementarna konjunkcija također uzima vrijednost 1 na ovom skupu, ali nestaje na svim ostalim n-dimenzionalnim Bulovim vektorima. Razmotrite formulu

u kojoj se zbir (unija) proteže na sve one skupove (t 1, . . . , t n) vrijednosti argumenata na kojima data funkcija uzima vrijednost 1. Imajte na umu da skup takvih skupova nije prazan, pa zbir sadrži najmanje jedan pojam.

Lako je vidjeti da formula Φ postaje 1 za one i samo za one vrijednosti varijabli za koje dotična funkcija postaje 1. To znači da formula Ψ predstavlja funkciju f.

Posljedica 1.1. Standardna osnova je kompletna.

◀ Zaista, ako funkcija nije konstanta 0, onda se može predstaviti ili u obliku SDNF-a, što je formula na standardnoj bazi. Konstanta 0 se može predstaviti, na primjer, formulom f(x 1, x 2, . . . , x n) = x 1 x 1.

Primjer 1.2. Razmotrimo funkciju tri varijable m(x 1, x 2, x 3) (tabela 1.4), tzv. većinska funkcija ̆. Ova funkcija daje vrijednost 1 ako više od polovine njenih argumenata ima vrijednost 1. Stoga se često naziva funkcija glasanja. Hajde da napravimo SDNF za to.

Potpunost standardne osnove omogućava odabir drugih kompletnih sistema funkcija. Kompletnost skupa F može se utvrditi iz sljedećih razmatranja. Pretpostavimo da je svaka od tri standardne busis funkcije predstavljena formulom preko F. Tada će, prema teoremi 1.3, identitet F biti potpun.

Primjer 1.3. Skup operacija po modulu 2 zbrajanje, množenje i konstanta 1 se zove Zhegalkinova osnova . Sabiranje po modulu 2 i množenje su osnovne operacije Z2 prstena sastavljeni izrazi su polinomi nad Z2 prstenom. Konstanta 1 u ovom slučaju je neophodna za pisanje slobodnog člana. Pošto je xx = x, onda svi faktori u polinomu imaju stepen 1. Stoga, kada pišete polinom, možete bez koncepta stepena. Primjeri formula preko Zhegalkinove baze:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Svaka takva formula naziva se Zhegalkin polinom. U stvari, Žegalkinov polinom je polinom nad prstenom Z2.

Nije teško konstruirati formule preko baze Žegalkina, koje predstavljaju operacije sabiranja i negacije standardne baze (uobičajeno je množenje dvije baze):

x+y=x⊕y⊕xy, x =x⊕1.

Stoga je Zhegalkinova osnova kompletan set.
Može se pokazati da je za bilo koju Bulovu funkciju Zhegalkin polinom jedinstveno definiran

(tačnije, do reda termina). Koeficijenti Zhegalkinovog polinoma sa malim brojem varijabli mogu se pronaći metodom neodređenih koeficijenata.

Primjer 1.4. Razmotrimo skup jedne funkcije - Schaefferov potez*. Ovaj skup je kompletan, kao što slijedi iz sljedećih lako provjerljivih identiteta:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

Primjer 1.5. Osnova koja se sastoji od jedne funkcije, Peirceove strelice, također je potpuna. Test za ovo je sličan slučaju Schaefferovog moždanog udara. Međutim, ovaj zaključak se može donijeti i na osnovu principa dualnosti za simetrične poluprstenove.

*Schaefferov moždani udar je binarna, ali ne asocijativna operacija. Stoga, kada koristite infiks formu, trebate biti oprezni: rezultat ovisi o redoslijedu operacija. U ovom slučaju, preporučuje se eksplicitno naznačiti redoslijed operacija pomoću zagrada, na primjer, napisati (x | y) | z, ne x | y | z, iako su oba oblika ekvivalentna.

Definicija 1.Konjunktivni monom (elementarna konjunkcija) varijabli je konjunkcija ovih varijabli ili njihove negacije.

Na primjer, je elementarna konjunkcija.

Definicija 2.Disjunktivni monom (elementarna disjunkcija) od varijabli naziva se disjunkcija ovih varijabli ili njihove negacije.

Na primjer, je elementarna disjunkcija.

Definicija 3. Formula koja je ekvivalentna datoj formuli propozicionalne algebre i koja je disjunkcija elementarnih konjunktivnih monoma naziva se disjunktivni normalni oblik(DNF) ove formule.

Na primjer,– DNF.

Definicija 4. Formula koja je ekvivalentna datoj formuli propozicionalne algebre i koja je konjunkcija elementarnih disjunktivnih monoma naziva se konjunktivni normalni oblik(CNF) ove formule.

Na primjer, – KNF.

Za svaku formulu propozicione algebre može se pronaći skup disjunktivnih i konjunktivnih normalnih oblika.

Algoritam za konstruisanje normalnih oblika

Koristeći ekvivalentnosti logičke algebre, zamijenite sve osnovne operacije u formuli: konjunkcija, disjunkcija, negacija:

Riješite se dvostrukih negativa.

Primijenite, ako je potrebno, svojstva distributivnosti i formule apsorpcije na operacije konjunkcije i disjunkcije.

2.6. Savršeni disjunktivni i savršeni konjunktivni normalni oblici

Bilo koja Booleova funkcija može imati mnogo reprezentacija u obliku DNF i CNF. Posebno mjesto među ovim prikazima zauzimaju savršeni DNF (SDNF) i savršeni CNF (SCNF).

Definicija 1. Savršena disjunktivna normalna forma(SDNF) je DNF u kojem svaki konjunktivni monom sadrži svaku varijablu iz skupa tačno jednom, bilo samu sebe ili njenu negaciju.

Strukturno, SDNF za svaku formulu propozicionalne algebre svedenu na DNF može se definirati na sljedeći način:

Definicija 2. Savršena disjunktivna normalna forma(SDNF) formule propozicionalne algebre naziva se njen DNF, koja ima sljedeća svojstva:

Definicija 3. Savršena konjunktivna normalna forma(SCNF) je CNF u kojem svaki disjunktivni monom sadrži svaku varijablu iz skupa tačno jednom, a pojavljuje se ili sam ili njegova negacija.

Strukturno, SCNF za svaku formulu propozicionalne algebre redukovane na CNF može se definirati na sljedeći način.

Definicija 4. Savršena konjunktivna normalna forma(SCNF) date formule propozicione algebre naziva se takva njena CNF koja zadovoljava sljedeća svojstva.

Teorema 1. Svaka Booleova funkcija varijabli koja nije identično lažna može biti predstavljena u SDNF, i to na jedinstven način.

Metode za pronalaženje SDNF

1. metoda

2. metoda

odaberite linije u kojima formula uzima vrijednost 1;

sastavljamo disjunkciju konjunkcija pod uslovom da ako je varijabla uključena u konjunkciju sa vrednošću 1, onda zapisujemo ovu promenljivu sa vrednošću 0, onda njenu negaciju. Dobijamo SDNF.

Teorema 2. Svaka Booleova funkcija varijabli koja nije identično istinita može biti predstavljena u SCNF-u, i to na jedinstven način.

Metode za pronalaženje SCNF-a

1. metoda– korištenjem ekvivalentnih transformacija:

2. metoda– korištenjem tablica istinitosti:

odaberite linije u kojima formula uzima vrijednost 0;

sastavljamo konjunkciju disjunkcija pod uslovom da ako je promenljiva uključena u disjunkciju sa vrednošću 0, onda zapisujemo ovu promenljivu sa vrednošću 1, onda njenu negaciju. Dobijamo SKNF.

Primjer 1. Konstruirajte CNF funkcije.

Rješenje

Uklonimo vezni "" koristeći zakone transformacije varijable:

= /de Morganovi zakoni i dvostruka negacija/ =

/distributivni zakoni/ =

Primjer 2. Dajte formulu DNF-u.

Rješenje

Izrazimo logičke operacije koristeći i:

= /klasificirajmo negaciju kao varijable i smanjimo dvostruke negativne vrijednosti/ =

= /zakon distributivnosti/ .

Primjer 3. Napišite formulu u DNF i SDNF.

Rješenje

Koristeći zakone logike, ovu formulu svodimo na oblik koji sadrži samo disjunkcije elementarnih konjunkcija. Rezultirajuća formula će biti željeni DNF:

Da bismo konstruirali SDNF, napravimo tablicu istinitosti za ovu formulu:

Označavamo one redove tabele u kojima formula (zadnja kolona) uzima vrednost 1. Za svaki takav red ispisujemo formulu koja je tačna na skupu varijabli ovog reda:

red 1: ;

red 3: ;

red 5: .

Disjunkcija ove tri formule će poprimiti vrijednost 1 samo na skupovima varijabli u redovima 1, 3, 5, i stoga će biti željeni savršeni disjunktivni normalni oblik (PDNF):

Primjer 4. Donesite formulu u SKNF na dva načina:

a) korištenjem ekvivalentnih transformacija;

b) korištenjem tablice istinitosti.

Rješenje:

Transformirajmo drugu elementarnu disjunkciju:

Formula izgleda ovako:

b) sastaviti tabelu istinitosti za ovu formulu:

Označavamo one redove tabele u kojima formula (zadnja kolona) uzima vrednost 0. Za svaki takav red ispisujemo formulu koja je tačna na skupu varijabli ovog reda:

red 2: ;

red 6: .

Konjunkcija ove dvije formule će poprimiti vrijednost 0 samo na skupovima varijabli u redovima 2 i 6, i stoga će biti željeni savršeni konjunktivni normalni oblik (PCNF):

Pitanja i zadaci za samostalno rješavanje

1. Koristeći ekvivalentne transformacije, svesti formule na DNF:

2. Koristeći ekvivalentne transformacije, donesite formule u CNF:

3. Koristeći drugi distributivni zakon, pretvorite DNF u CNF:

A) ;

4. Pretvorite date DNF-ove u SDNF-ove:

5. Pretvorite dati CNF u SCNF:

6. Za date logičke formule, konstruirajte SDNF i SCNF na dva načina: korištenjem ekvivalentnih transformacija i korištenjem tablice istinitosti.

b) ;

Disjunktivni i konjunktivni normalni oblici propozicionalne algebre. Za svaku propozicionu logičku funkciju može se konstruisati tabela istinitosti. Inverzni problem je također uvijek rješiv. Hajde da uvedemo nekoliko definicija.

Elementarni veznici (konjunkti) nazivaju se konjunkcije varijabli ili njihove negacije u kojima se svaka varijabla javlja najviše

jednom.

Disjunktivni normalni oblik(DNF) je formula koja ima oblik disjunkcije elementarnih konjunkcija.

Elementarne disjunkcije (disjunkti) nazivaju se disjunkcija varijabli sa ili bez negacija.

Konjunktivna normalna forma(CNF) je formula koja ima oblik konjunkcije elementarnih disjunkcija.

Za svaku funkciju propozicione algebre može se pronaći skup disjunktivnih i konjunktivnih normalnih oblika.

Algoritam za konstruisanje DNF-a:

1. Idite na Booleove operacije koristeći ekvivalentne formule transformacije.

2. Idite na formule sa bliskim negacijama, odnosno na formulu u kojoj se negacije nalaze ne više nego iznad varijabli - primijenite De Morganove zakone.

3. Otvorite zagrade - primijenite zakone distributivnosti.

4. Uzmite ponavljanje termina jedan po jedan - zakon idempotencije.

5. Primijenite zakone apsorpcije i poluapsorpcije.

Primjer 6. Pronađite DNF formule: .

U Booleovoj algebri je istina princip dualnosti. To je kako slijedi.

Funkcija se poziva dual na funkciju ako . One. Da bismo pronašli funkciju dualnu datoj, potrebno je konstruisati negaciju funkcije iz negacija argumenata.

Primjer 7. Pronađite funkciju dualnu .

Među elementarnim funkcijama algebre logike, 1 je dualno prema 0 i obrnuto, x je dualno prema xu, dualno prema , dualno i obrnuto.

Ako u formuli F 1 koja predstavlja funkciju zamijenimo sve konjunkcije

na disjunkciju, disjunkciju na konjunkciju, 1 na 0, 0 na 1, tada dobijamo formulu F * koja predstavlja funkciju * ​​dualnu na .

Konjunktivni normalni oblik (CNF) je dvostruki koncept za DNF, tako da se može lako konstruirati prema sljedećoj shemi:

Primjer 8. Pronađite CNF formulu: .

Koristeći rezultat primjera 6, imamo

Savršeni disjunktivni i savršeni konjunktivni normalni oblici. U svakom od tipova normalnih oblika (disjunktivni i konjunktivni) može se razlikovati klasa savršenih oblika SDNF i SCNF.

Savršena elementarna konjunkcija je logički proizvod svih varijabli sa ili bez negacije, a svaka varijabla se pojavljuje u proizvodu samo jednom.

Bilo koji DNF se može svesti na SDNF cijepanjem konjukcija koje ne sadrže sve varijable, tj. dodavanjem za promenljivu koja nedostaje x i se množi korišćenjem distributivnog zakona

Primjer 9. Pronađite SDNF za DNF primjera 6

Savršena elementarna disjunkcija je logički zbir svih varijabli sa ili bez negacija, a svaka varijabla je uključena u zbir samo jednom.

Bilo koji CNF se može svesti na SCNF dodavanjem vezničkog termina koji ne sadrži nijednu varijablu X i pomoću konjukcije i primjenom distributivnog zakona

Primjer 10. Donesite KNF u SKNF:

Da biste konstruirali SCNF, možete koristiti dijagram

Primjer 11. Pronađite SCNF za formulu primjera 6.

Svaka funkcija ima SDNF i, osim toga, jedinstven. Svaka funkcija ima SCNF i, osim toga, jedinstvenu.

Jer SDNF i SKNF su jedinstveno definisani formulama, mogu se konstruisati koristeći tabelu istinitosti formule.

Za konstruiranje SDNF-a potrebno je odabrati redove u kojima F uzima vrijednost 1 i za njih zapisati savršene elementarne konjunkcije. Ako je vrijednost varijable u željenom redu tablice istinitosti jednaka jedan, tada se u savršenoj konjunkciji uzima bez negacije, ako je nula, onda sa negacijom. Tada se savršene konjunkcije (njihov broj je jednak broju jedinica u tabeli) povezuju znakovima disjunkcije.

Za konstruiranje SCNF-a koristeći tablicu istinitosti, potrebno je odabrati redove u njoj gdje je F = 0, i zapisati savršene elementarne disjunkcije, a zatim ih povezati znakovima konjunkcije. Ako u traženom redu tablice istinitosti (F=0) vrijednost varijable odgovara nuli, onda se u perfektnoj klauzuli uzima bez negacije, ako je jedan, onda sa negacijom.

Primjer 12. Pronađite SDNF i SCNF koristeći tablicu istinitosti za formulu primjera 6.

Tabela 14 prikazuje samo konačnu vrijednost F=10101101. Trebali biste sami provjeriti valjanost ove izjave tako što ćete napraviti detaljnu tabelu istinitosti.

Tabela 14

Za bilo koju logičku formulu, koristeći transformacije identiteta, može se konstruisati beskonačno mnogo formula koje su njoj ekvivalentne. U algebri logike, jedan od glavnih zadataka je traženje kanonskih formi (tj. formula konstruisanih prema jednom pravilu, kanonu).

Ako je logička funkcija izražena kroz disjunkciju, konjunkciju i negaciju varijabli, onda se ovaj oblik reprezentacije naziva normalnim.

Među normalnim oblicima razlikuju se savršeni normalni oblici (oni oblici u kojima su funkcije napisane na jedinstven način).

Savršena disjunktivna normalna forma (PDNF)

Definicija. Formula se naziva elementarnom konjunkcijom ako je formirana konjunkcijom određenog broja varijabli ili njihovih negacija.

Primjeri: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definicija. Formula se naziva disjunktivnim normalnim oblikom (DNF) ako je disjunkcija neponavljajućih elementarnih veznika.

DNF se piše u sljedećem obliku: F 1 ∨ F 2 ∨ ... ∨ F n , gdje je F i elementarna konjunkcija

Primjeri: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3 , ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definicija. Logička formula u k varijabli naziva se savršena disjunktivna normalna forma (PDNF) ako:
1) formula je DNF, u kojoj je svaka elementarna konjunkcija konjunkcija k varijabli x 1, x 2, ..., x k, a na i-tom mjestu ove konjunkcije nalazi se ili varijabla x i ili njena negacija ;
2) sve elementarne konjunkcije u takvom DNF su parno različite.

Primjer: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Savršena konjunktivna normalna forma (PCNF)

Definicija. Formula se naziva elementarna disjunkcija ako je formirana disjunkcijama određenog broja varijabli ili njihovim negacijama.

Primjeri: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definicija. Formula se naziva konjunktivni normalni oblik (CNF) ako je konjunkcija neponovljivih elementarnih disjunkcija.

CNF se piše u sljedećem obliku: F 1 ∧ F 2 ∧ ... ∧ F n , gdje je F i elementarna disjunkcija

Primjeri: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definicija. Logička formula u k varijabli naziva se savršena konjunktivna normalna forma (CPNF) ako:
1) formula je CNF, u kojoj je svaka elementarna disjunkcija disjunkcija k varijabli x 1, x 2, ..., x k, a na i-tom mjestu ove disjunkcije nalazi se ili varijabla x i ili njena negacija;
2) sve elementarne disjunkcije u takvoj CNF su parno različite.

Primjer: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

primeti, to bilo koja logička funkcija koja nije identično jednaka 0 ili 1 može se predstaviti kao SDNF ili SKNF.

Algoritam za konstruisanje SDNF-a koristeći tabelu istinitosti

1. Odaberite sve redove tablice u kojima je vrijednost funkcije jednaka jedan.
2. Za svaki takav red napišite konjunkciju svih varijabli na sljedeći način: ako je vrijednost neke varijable u ovom skupu jednaka 1, tada u konjukciju uključujemo i samu varijablu, u suprotnom njenu negaciju.
3. Sve nastale konjunkcije povezujemo s operacijama disjunkcije.

Algoritam za konstruisanje SCNF-a koristeći tabelu istinitosti

1. Odaberite sve redove tablice u kojima je vrijednost funkcije nula.
2. Za svaki takav red, napišite disjunkciju svih varijabli na sljedeći način: ako je vrijednost neke varijable u ovom skupu jednaka 0, tada uključujemo i samu varijablu u konjukciju, inače, njenu negaciju.
3. Sve nastale disjunkcije povezujemo sa konjunkcijskim operacijama.

Analiza algoritama pokazuje da ako je na većini redova tablice istinitosti vrijednost funkcije 0, onda je za dobivanje njene logičke formule bolje konstruirati SDNF, inače - SCNF.

Primjer: Data je tabela istinitosti logičke funkcije od tri varijable. Konstruirajte logičku formulu koja implementira ovu funkciju.

Jer u većini redova tabele istinitosti vrednost funkcije je 1, tada ćemo konstruisati SCNF. Kao rezultat, dobijamo sledeću logičku formulu:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Provjerimo rezultirajuću formulu. Da bismo to uradili, konstruisaćemo tabelu istinitosti funkcije.

Uspoređujući izvornu tablicu istinitosti i onu konstruiranu za logičku formulu, primjećujemo da se stupci vrijednosti funkcije podudaraju. To znači da je logička funkcija ispravno konstruirana.