Laboratorní práce Booleovské funkce logické algebry. Rozklad booleovské funkce v proměnných Shannonův rozklad z hlediska proměnné online

3.1 Rozklad booleovských funkcí v proměnných

3.2 Zhegalkinova algebra

Výše jsme ukázali, že jakoukoli booleovskou funkci lze zadat pomocí tabulky pravdivosti. Tato část popisuje přechod z tabulkového přechodu nastavení funkce na analytický.

3.1 Rozklad booleovských funkcí v proměnných.

Nechť G je parametr rovný 0 nebo 1. Zavedeme zápis:

Je snadné to ověřit ověřením, že X G = 1 právě tehdy, když X = G. Z toho tedy vyplývá, že spojka
se rovná 1 (zde G se rovná 0 nebo 1) právě tehdy
... Například spojka
(kde G 2 = G 1 = 0, G 3 = G 4 = 1) se rovná 1 pouze v případě, kdy X 1 =X 2 = 0,X 3 =X 4 = 1.

Věta 1Libovolná booleovská funkceF(X 1 , X 2 ,…, X n ) lze předložit v následující podobě:

kde 1 ≤k ≤ n, v disjunkci je převzat všechny sady hodnot proměnných.

Tato reprezentace se nazývá rozšíření funkce z hlediska proměnných.
... Například pro n = 4, k = 2 má rozšíření (3.1) tvar:

.

Dokažme platnost rozšíření (3.1). Chcete -li to provést, vezměte libovolnou sadu hodnot proměnných
... Ukažme, že levá a pravá strana vztahu (3.1) pro ni mají stejnou hodnotu. Opravdu, protože X G = 1 právě tehdy, když X = G, pak mezi spojkou 2 K
na pravé straně (3.1), pouze jeden ve kterém
... Všechna ostatní spojení
jsou rovny nule.

Proto . V důsledku rozkladu (3.1) získáme následující dva speciální rozklady.

Variabilní expanzeX n :

Pokud booleovská funkce není konstanta 0, pak expanze

Rozšíření ve všech proměnných:

,
(3.3)

kde disjunkce převezme všechny sady
pro které hodnota funkce
se rovná 1.

Rozšíření (3.3) se nazývá dokonalá disjunktivní normální forma (zkratka pro SDNF) funkce.

Rozšíření (3.3) poskytuje způsob, jak vytvořit SDNF. Chcete -li to provést, označte všechny řádky v tabulce pravdy
, ve kterém
... Pro každý takový řádek tvoříme spojku
a poté spojíme všechny výsledné spojky znaménkem disjunkce.

Mezi tabulkou pravdivosti funkce tedy existuje vzájemná korespondence
a jeho SDNF. To znamená, že SDNF pro logickou funkci je jedinečný.

Jedna booleovská funkce, která nemá SDNF, je konstanta 0.

Příklad 1 Najděte perfektní disjunktivní formu pro funkci
.

Pojďme sestavit pravdivostní tabulku pro tuto funkci:

Odtud získáváme:
==.

Následující rozšíření booleovských funkcí hraje důležitou roli v algebře logiky.

Věta 2Libovolná booleovská funkce
lze předložit v následující podobě:

kde 1≤k≤n, a je použita spojka celé 2 k sady hodnot proměnných.

Skutečně nechť
- libovolná sada hodnot proměnných. Ukažme, že levá a pravá strana vztahu (3.4) pro ni mají stejnou hodnotu. Protože
pouze když
, pak mezi 2 k disjunkce
na pravé straně (3.4) zmizí pouze jeden, ve kterém
... Všechny ostatní klauzule se rovnají 1.

Proto
==
.

Rozšíření booleovských funkcí vyplývají přímo z rozšíření (3.4):

Poslední rozklad se nazývá dokonalá konjunktivní normální forma (SKNF). Rozšíření (3.6) poskytuje způsob, jak vytvořit SKNF. Chcete -li to provést, označte všechny řádky v tabulce pravdy
, ve kterém. Pro každý takový řádek tvoříme disjunkci
a pak jsou všechny výsledné spojky spojeny znaménkem spojky. Mezi tabulkou pravdivosti funkce tedy existuje vzájemná korespondence
a jeho SKNF. To znamená, že SKNF pro logickou funkci je jedinečný.

Jedinou booleovskou funkcí, která nemá SCNF, je konstanta 1.

Příklad 2 Najděte pro tuto funkci perfektní konjunktivní normální formu
.

Pojďme sestavit pravdivostní tabulku pro tuto funkci.

Z toho získáváme SKNF

Vzorec (krátký zápis
), kde
- spojky
volala disjunktivní normální forma (DNF).

Na základě výše uvedené definice DNF budou výrazy například:
,
.

Jak je uvedeno v odstavci 2.2, všechny logické operace lze redukovat na tři: spojka, disjunkce a negace. Navíc s ohledem na de Morganův zákon lze předpokládat, že znak negace je připisován pouze proměnným.

Nyní pomocí distribučního zákona rozbalíme závorky a dostaneme disjunktivní normální formu. Následující věta je tedy pravdivá.

Teorém3 Pro jakýkoli vzorec algebry logiky existuje disjunktivní normální forma, která je jí ekvivalentní.

Důkaz této věty poskytuje způsob, jak sestrojit disjunktivní normální formu pro jakýkoli vzorec v algebře logiky.

Příklad 3 Najděte disjunktivní normální formu pro následující vzorec:
.

Vyjímající znak
podle zákona
a použitím zákonů de Morgana a dvojité negace získáme:

Poté pomocí zákona o distribučnosti rozbalíme závorky

Poslední výraz je disjunktivní normální forma.

Zobrazit formulář
(krátký záznam ), kde
- disjunkce
volala konjunktivní normální forma (CNF).

Jedná se například o výrazy:

,
.

Jak je uvedeno výše, pro jakýkoli vzorec algebry logiky existuje její ekvivalentní disjunktivní forma. Pomocí distribučního zákona je snadné získat CNF z daného DNF.

Následující věta je tedy pravdivá.

Věta 4Pro jakýkoli vzorec algebry logiky existuje ekvivalentní normální forma spojivky.

Důkaz této věty poskytuje způsob, jak sestrojit spojkovou normální formu pro jakýkoli vzorec v algebře logiky.

Příklad4 Najděte disjunktivní a spojovací normální formy pro následující vzorec:
.

Používání zákona
, vyloučit znaménko
... Získáme vzorec
.

Pomocí de Morganova zákona získáme vzorec
... Rozbalením závorek získáme disjunktivní normální formu

.

Abychom dostali spojivkovou normální formu, použijeme vzorec
distribučního práva, získáme:

Poslední výraz je spojovací normální forma. Protože
a
, pak získaný CNF odpovídá následujícímu CNF:

Ze všech normálních vzorců tohoto vzorce rozlišujeme dokonalou normální formu, disjunktivní i konjunktivní. S ohledem na expanzi (3) je snadné vidět, že dokonalá disjunktivní normální forma vzorce logické algebry obsahující přesně n různých proměnných je její disjunktivní normální forma, ve které:

1) všechny spojky jsou párově odlišné;

2) každá spojka obsahuje přesně n proměnných;

3) každá spojka obsahuje všech n proměnných.

Pomocí příkladu 1 jsme zkoumali jeden ze způsobů konstrukce SDNF na základě kompilace tabulky pravd. Další způsob konstrukce SDNF je založen na aplikaci zákonů algebry logiky.

Příklad 5 Najděte dokonalou disjunktivní formu vzorce
.

Pomocí toho
, dostaneme
... S ohledem na de Morganovy zákony a dvojí negaci jsme získali disjunktivní normální formu
... Tento DNF je ekvivalentem vzorce.

Rozbalením závorek získáme :.

Pomocí zákona idempotency získáme požadovaný SDNF:

S přihlédnutím k expanzi (3.6) je snadné vidět, že perfektní konjunktivní normální forma vzorce booleovské algebry obsahující přesně n různé proměnné, existuje jeho spojivá normální forma, ve které:

1) všechny disjunkce jsou párově odlišné;

2) každá disjunkce obsahuje přesně n výrazů;

3) v každé disjunkci je všech n proměnných.

Pomocí příkladu 2 jsme zkoumali jeden ze způsobů konstrukce SCNF na základě kompilace tabulky pravd. Další způsob konstrukce SKNF je založen na aplikaci zákonů algebry logiky.

Příklad 6 Najděte perfektní konjunktivní normální formu vzorce
.

Použitím,
, dostaneme
.

Tento vzorec je konjunktivní normální forma. To se rovná vzorce.

Pomocí zákona o distribuci získáme:

Aplikujeme -li zákon idempotence, získáme požadovanou perfektní konjunktivní normální formu

stejně pravdivé pokud pro všechny hodnoty v ní obsažených proměnných nabývá hodnoty opravdu.

Příklady identicky pravdivých vzorců jsou:

Nazývá se vzorec algebry logiky stejně nepravdivé pokud pro všechny hodnoty v ní obsažených proměnných nabývá hodnoty Ležící.

Příklady identicky falešných vzorců jsou vzorce:

,

Nazývá se vzorec algebry logiky realizovatelný, pokud pro některé hodnoty proměnných, které jsou v něm obsaženy, bere hodnotu skutečný.

Příklady spustitelných vzorců jsou následující vzorce:

,
.

V algebře logiky lze položit následující problém: určit metodu (algoritmus), která umožňuje každému vzorci algebry logiky zjistit, zda je identicky pravdivý nebo ne. Úkol se nazývá problémy s rozlišením.

Zvažte následující dva způsoby, jak tento problém vyřešit.

Metoda 1 (tabulková) Abychom zjistili, zda je daný vzorec shodný nebo ne, stačí sestavit jeho tabulku pravd.

Tato metoda, přestože poskytuje zásadní řešení problému řešitelnosti, je poměrně těžkopádná.

Metoda 2 založené na redukci vzorců na normální formu.

Věta 4Vzorec logické algebry je stejně pravdivý tehdy a jen tehdy, pokud každá disjunkce ve své spojivové normální formě obsahuje nějakou proměnnou společně s její negací.

Skutečně, pokud každá disjunkce v konjunktivní normální formě obsahuje proměnnou spolu s její negací, pak jsou všechny disjunkce rovny 1, protože
,
... Z toho vyplývá, že CNF je identicky pravdivý.

Nyní nechť je tento vzorec stejně pravdivý a nechť
v CNF tohoto vzorce existuje určitá disjunkce. Předpokládejme, že daná disjunkce neobsahuje proměnnou spolu s její negací. V tomto případě můžeme každé proměnné, která není pod záporným znaménkem, dát hodnotu 0, a každé proměnné pod záporným znaménkem - hodnotu 1. Po této substituci se všechny disjunkce stanou rovnými 0, proto vzorec není identicky pravdivý. Dostali jsme rozpor.

Příklad 7 Zjistěte, zda vzorec

.

Pomocí toho
, dostaneme
.

Aplikací zákona o distribuci získáme CNF:

Protože každá disjunkce obsahuje nějakou proměnnou společně s její negací, je vzorec identicky pravdivý.

Podobně jako u předchozí věty je prokázána následující věta:

Věta 5 Vzorec logické algebry je identicky nepravdivý právě tehdy, pokud každá spojka ve své disjunktivní formě obsahuje nějakou proměnnou společně s její negací.

Zvažte problém prezentace n-místní booleovská funkce F(X 1 ,X 2 ,…,X n) podle nějakého výrokového algebraického vzorce.

Představme notaci, kde je parametr roven 0 nebo 1.

To je evidentní

Věta 1.1. Každá funkce booleovské algebryF(X 1 , X 2 ,…, X n ) pro jakékolim (1£ m £ n) mohou být zastoupeny v následující formě:

kde disjunkce přebírá všechny možné sady hodnot proměnných.

Důkaz... Zvažte libovolnou sadu hodnot pro všechny proměnné dané funkce. Ukažme, že v této sadě mají levá a pravá strana vzorce (1) stejnou hodnotu. Levá strana se rovná , že jo

od té doby pokud jen, pokud, pak lze odpovídající logický termín zahodit.

Komentář... Reprezentace funkce uvedené ve větě se nazývá rozšíření funkce v m proměnné.

Důsledek 1(rozšíření v jedné proměnné).

V tomto případě funkce a se nazývají rozkladné složky.

Důsledek 2(rozšíření ve všech proměnných).

Očividně kdyby , pak

Pokud tedy funkce F(X 1 ,X 2 ,…,X n) není identicky falešná funkce, pak ji lze vyjádřit ekvivalentním vzorcem, který je logickým součtem různých produktů formuláře, a taková reprezentace je jedinečná.

Vzorec (2) lze výrazně zjednodušit. Je známo, že jakýkoli vzorec algebry logiky může být redukován ekvivalentními transformacemi na vzorec obsahující pouze spojku a negaci nebo disjunkci a negaci. V důsledku provádění ekvivalentních transformací lze získat několik vzorců, ale pouze jeden z nich bude mít následující vlastnosti:

1. Každý logický výraz obsahuje všechny proměnné zahrnuté ve vzorci F(X 1 ,X 2 ,…,X n).

2. Žádný logický výraz neobsahuje proměnnou ani její negaci.

3. Všechny logické výrazy ve vzorci jsou různé.

4. Žádný logický výraz neobsahuje stejnou proměnnou dvakrát.

Tyto čtyři vlastnosti se nazývají vlastnosti dokonalosti(nebo vlastnosti C).

Li F(X 1 ,X 2 ,…,X n) je dáno tabulkou pravdy, pak je odpovídající vzorec algebry logiky rekonstruován zcela jednoduše. Pro všechny hodnoty argumentů X 1 ,X 2 ,…,X n na které F nabývá hodnoty 1, musíte napsat spojku elementárních proměnných, přičemž jako spojovací člen x i, pokud x i= 1, a pokud x i= 0. Rozpojení všech zaznamenaných spojek bude nezbytným vzorcem. O významech F 0 nemusíte mít obavy, protože odpovídající termín ve vzorci bude roven 0 a může být vyřazen z důvodu ekvivalence FÚ 0 ≡ F.

Nechte například funkci F(X, y, z) má následující pravdivostní tabulku:

X	y	z	F(X, y, z)

Označme podle. Pak

x s=

Zejména pokud a pouze pokud.

S pomocí „výkonové funkce“ jakékoli booleovské funkce může být reprezentován jako:

volala rozšíření booleovské funkce podle proměnné.

Skutečně, pokud, pak, a

Pokud, pak a

Příklad 4.

Rozbalte funkci podle proměnné. K tomu nejprve vytvoříme funkční tabulku:

Tabulka ukazuje, že a.

Pomocí expanzního vzorce z hlediska proměnné zjistíme

Příklad 5.

Rozbalte funkci z příkladu 4 pro všechny proměnné. Protože funkce nabývá hodnoty 1 na třech sadách :, pak podle důsledků na větu o rozkladu máme

Definice 3.

Rozklad booleovské funkce nad všemi proměnnými ve formuláři

volala perfektní disjunktivní normální forma(SDNF).

Příklad 6.

- SDNF pro funkci (viz příklad 5).

Věta 2.

Každá booleovská funkce (kromě 0) má jedinečný SDNF.

Důkaz. Podle důsledků na rozkladovou větu

Komentář. Pokud disjunkcí jednoho výrazu rozumíme samotný tento termín, pak disjunkce nuly termínů neexistuje, proto pro funkci 0 neexistuje SDNF.

Při konstrukci SDNF platí následující.

Pravidlo jednoho. nabývá hodnoty 1; pro každou takovou sadu v SDNF se pro daný termín vytvoří mezera ... Pokud je v dané sadě argumentů zavěšen zápor na proměnnou v připravovaném výrazu: .

Věta 3.

Libovolnou booleovskou funkci lze vyjádřit pojmem disjunkce, konjunkce a negace:

Důkaz.

Li , pak ... Li , pak

Věta 4.

Libovolnou booleovskou funkci (kromě 1) lze jednoznačně vyjádřit ve formě dokonalé konjunktivní normální formy (SCNF):

Důkaz.

Li , pak a

Uplatnění zásady duality na poslední identitu, zjistíme

Při konstrukci SCNF platí následující.

Pravidlo nuly. Jsou zohledněny pouze ty sady argumentů, pro které funkce nabývá hodnoty 0; pro každou takovou sadu se ve SKNF vytvoří mezera faktoru. Pokud je v dané sadě argumentů zavěšen zápor na proměnnou v připraveném faktoru: .

Příklad 7.

Pojďme sestrojit funkci pro implikaci: ... Důsledek nabývá hodnoty 0 v jedné sadě:

Protože v této kolekci a potom nulovým pravidlem získáváme

.

Tak, je požadovaná funkce pro implikaci.

Úplnost systému

Definice 4. Funkční systém ( F 1 , F 2 , ..., F s, ...) Ì P 2 se nazývá kompletní v R. 2 pokud nějaká funkce F(X 1 , ..., x n) Î P 2 lze zapsat jako vzorec prostřednictvím funkcí tohoto 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, protože jakoukoli funkci algebry logiky lze zapsat jako vzorec prostřednictvím těchto funkcí.

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

Lemma(dostatečná podmínka pro úplnost)

Nechte systém U = {F 1 , F 2 , ..., f s, ...) je kompletní v R. 2. Nech být B = {G 1 , G 2 , ..., g k, ...) je nějaký systém od R. 2 a jakoukoli funkci f i Î U lze vyjádřit vzorcem nad B, pak systém B plný R. 2 .

7. Systém ( X 1 &X 2 , X 1 Å X 2, 0, 1) je kompletní v R. 2 , U = {X 1 &X 2 , }, = X 1 Å1.

Zhegalkinův polynom

F(X 1 , ..., x n) Î P 2, reprezentujeme to ve formě vzorce pomocí spojení a součtu modulo dva pomocí čísel 0 a 1. To lze provést, protože ( X 1 &X 2 , X 1 Å X 2, 0, 1) je kompletní v R. 2. Na základě majetku X & (yÅ z) = xy Å xz můžete rozšířit všechny závorky, zadat podobné výrazy a získáte polynom o n proměnné skládající se z členů formuláře NS NS ...NS spojeno znakem Å. Takový polynom se nazývá Zhegalkinův polynom.

Obecná forma Zhegalkinův polynom:

kde , s = 0, 1, ..., n, a na s= 0 získáme volný termín A 0 .

Reprezentace funkce ve formě Zhegalkinova polynomu

1. Zastupujeme jakoukoli funkci pomocí vzorce nad ( X 1 &X 2,) a nahradit = XÅ1. Tato metoda je výhodná, pokud je funkce určena vzorcem.

Pří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 třeba mít na paměti, že v součtu je sudý počet stejných výrazů mod 2 dává 0.

2. Metoda nedefinovaných koeficientů. Je výhodné, když je funkce definována tabulkou.

Příklad 10.

Píšeme s neurčitými koeficienty Zhegalkinův polynom pro funkci tří proměnný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. Poté najdeme koeficienty pomocí hodnot funkce na všech množinách. Na setu (0, 0, 0) F(0, 0, 0) = 0, na druhou stranu, nahrazením této sady do polynomu získáme F(0, 0, 0) = A 0, tedy A 0 = 0. F(0, 0, 1) = 1, nahrazením množiny (0, 0, 1) v polynomu dostaneme: F(0, 0, 1) = A 0 Å A 3, protože A 0 = 0, tedy A 3 = 1. Podobně 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; pak Zhegalkinův polynom pro tuto funkci bude mít tvar: F(X 1 , X 2 , X 3) = X 1 Å X 2 Å X 3 .

Polynom Zhegalkin lze také získat pomocí Pascalova trojúhelníku v jednotkách jeho levé strany podle následující tabulky. Pro funkci vytvořme Zhegalkinův polynom F= (10011110). Horní strana trojúhelníku je funkce F... Jakýkoli jiný prvek trojúhelníku je součet modulo dvou sousedních prvků předchozí řady. Levá strana trojúhelníku pro funkci F obsahuje šest jednotek. Zhegalkinův polynom bude obsahovat šest výrazů. První jednotka trojúhelníku odpovídá množině (000). První člen polynomu je 1. Třetí jednotka zespodu na levé straně trojúhelníku odpovídá množině (101). Jako výraz v polynomu vezmeme X 1 X 3. Stejně tak pro ostatní jednotky trojúhelníků. Vlevo od množin jsou zobrazeny podmínky Zhegalkinova polynomu.

Zhegalkinova věta

Každá funkce od může být reprezentována ve formě Zhegalkinova polynomu jedinečným způsobem.

Zde je chápána jedinečnost až po pořadí pojmů v součtu a pořadí faktorů ve spojkách:

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

Důkaz.

Jakákoli funkce od R. 2 může být reprezentováno vzorcem nad ( X 1 & X 2 , X 1 Å X 2, 0, 1) a tento vzorec po otevření všech závorek a redukci podobných výrazů dává Zhegalkinův polynom. Ukažme jedinečnost reprezentace. Zvažte funkce F(X 1 , ..., x n) z n proměnné. Víme, že všechny tyto funkce, tj. jejich pravdivostní tabulky, 2 n... Počítejme počet různých Zhegalkinových polynomů z n proměnné, tj. počet variant zobrazení: ... Počet sad se rovná počtu všech podmnožin sady ( X 1 , ..., x n), to také zahrnuje prázdnou sadu (pokud s= 0). Počet podmnožin sady n prvků je 2 n, a protože každá sada je zahrnuta s koeficientem, který nabývá dvou hodnot: 0 nebo 1, bude počet všech možných polynomů. Protože každý polynom odpovídá jedné funkci, počet funkcí od n proměnných se rovná počtu polynomů, pak každá funkce bude odpovídat jednomu polynomu.

Definice.

Funkce F(X 1 , ..., x n), Zhegalkinův polynom, pro který má následující formu, lineární s ohledem na proměnné: F = A 0 Å A 1 NS 1 Å A 2 NS 2 Е ... Е a n x n, se nazývá lineární.

Lemma o nelineární funkci .

Superpozicí nelineární funkce, negace a konstanty 1 můžete získat spojku.

Důkaz.

Nech být F(X 1 , ..., x n) Je nelineární funkce. Pak Zhegalkinův polynom pro něj obsahuje součet, ve kterém je součin x i x j... Pro jednoduchost to budeme předpokládat X 1 X 2 v Zhegalkinově polynomu je tento produkt. Po seskupení výrazů funkce F reprezentovat ve formě

Funkce h 0 není identická nula, jinak Zhegalkinův polynom postrádá s produktem výraz X 1 X 2. Pak je tu sada ( A 3 , …, a n) od 0 a 1, pro které h 0 (A 3 , …, a n) = 1. Nechť h 1 (A 3 , …, a n) = A, h 2 (A 3 , …, a n) = b, h 3 (A 3 , …, a n) = C... Pak

Pojďme vytvořit funkci:

Kde d = ab Å C... Li d= 0, pak h(X 1 , X 2) = X 1 X 2. Li d= 1, tedy h(X 1 , X 2) = X 1 X 2 Å 1 a potom Lemma je dokázáno.

Funkce F(X 1 , ..., X n) zachovává konstantu AÎ (0, 1) pokud F(A, …, A) = A.

Příklad 11.

Funkce xy zachovává 0, zachovává 1. Funkce X® y zachová 1 a nezachová 0.

Minimalizace booleovských funkcí

Minimalizace běžných formulářů

Minimální DNF (MDNF) funkce F(X 1 , ... ,x n) se nazývá DNF, který tuto funkci implementuje F a obsahující minimální počet symbolů proměnných ve srovnání se všemi ostatními typy DNF, které tuto funkci implementují F.

Pokud pro jakoukoli sadu = ( A 1 , ..., a n) hodnoty proměnných podmínka G() = 1 znamená, pak funkce G nazývaná část funkce F(nebo funkce F krycí funkce G). Pokud navíc pro nějakou sadu = ( C 1 , ..., c n) funkce G() = 1, pak říkají, že funkce G pokrývá jednotku funkce F na setu (nebo co G pokrývá složku jednotky funkce F). Všimněte si, že jednotková složka funkce F je tam část funkce F pokrývající jedinou jednotku funkce F.

Elementární konjunkce K se nazývá funkce implicant F pokud pro libovolnou sadu = ( A 1 , ..., a n) od 0 a 1 podmínka K() = 1 znamená F()=1.

Implicant K funkce F se nazývá jednoduchý, pokud výraz z něj získaný vyhozením jakýchkoli faktorů již není implikací funkce F.

Je zřejmé, že jakýkoli implikace funkce F je tam část funkce F.

Věta 5.

Jakákoli funkce je realizována disjunkcí všech jejích hlavních imlicantů (PI).

Proto, F = A... Věta je prokázána.

Zkráceně DNF funkce F je disjunkce všech implikátorů jednoduchých funkcí F... Libovolná funkce F implementován jeho zkráceně DNF. Pro jakoukoli funkci, která není identicky nulová, existuje jedinečná zkrácená DNF.

Nech být A a B- libovolné vzorce. Následující reverzibilní pravidla pro transformaci DNF vyplývají z vlastností booleovských operací:

1) - plné propojení (nasazení);

2) - neúplné lepení;

3) - generalizované lepení;

4) - absorpce;

5) - idempotency (odstranění duplicitních členů).

Quineova věta. Pokud funkce SDNF funguje F provést všechny operace neúplného lepení a poté všechny operace absorpce a odstranění duplicitních výrazů, výsledkem bude snížení funkce DNF F.

Důkaz.

Nechme zkrácenou DNF funkce F... Proveďme všechny operace expanze na každý jednoduchý implicant, abychom získali chybějící proměnné v každém disjunktivním členu redukovaného DNF. Ve výsledném výrazu z několika identických disjunktivních výrazů ponecháme pouze jednu kopii. V důsledku toho získáme funkci SDNF F... Nyní na základě získaného SDNF v opačném pořadí provedeme operace přidání stejných disjunktivních výrazů (pomocí pravidel idempotence), neúplného lepení a absorpce. V důsledku toho získáme původní zkráceně DNF.

Množina B, na které jsou definovány dvě binární operace (spojka a disjunkce) a jedna unární operace (negace) a jsou vybrány dva prvky 0 a 1, se nazývá booleovská algebra.

Navíc pro tyto operace musí být splněny následující vlastnosti:

Asociativita

Komutativita

Distribučnost spojky s ohledem na disjunkci

Distribučnost disjunkce vzhledem ke konjunkci

Idempotency

Dvakrát ne

Konstantní vlastnosti

De Morganova pravidla

Zákon rozporu

Vyloučený třetí zákon

V algebře logiky se tyto zákony nazývají ekvivalence.

Dokonalé normální formy

Perfektní disjunktivní normální forma

Představíme notaci:

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

Vzorec X A 1 …… X A n, kde A = je libovolná binární množina a mezi proměnnými Xi mohou existovat shodné, se nazývá elementární spojka.

Jakákoli disjunkce elementárních spojek se nazývá disjunktivní normální forma (DNF).

Elementární spojka se nazývá správná, pokud ji každá proměnná zadá maximálně jednou (včetně jejího výskytu pod znaménkem negace).

Například: 1) (ikona spojky je v tomto případě vynechána).

1), 4) - pravidelné elementární spojky;

2) - proměnná x zadá jednou sama a podruhé pod znaménkem negace;

Proměnná y se objeví třikrát: jednou sama a dvakrát pod znaménkem negace.

Pravidelná elementární spojka se nazývá úplná vzhledem k proměnným x 1… ..x n, pokud obsahuje každou z těchto proměnných pouze jednou (může to být záporné znaménko).

Například: ze spojek uvedených v předchozím příkladu jsou úplné pouze 4) relativně proměnné x, y, z, t; ale s ohledem na proměnné x, y, z kompletní je pouze 1).

Dokonalá disjunktivní normální forma (SDNF) s ohledem na proměnné x 1 ... ..xn je disjunktivní normální forma, ve které neexistují žádné identické elementární spojky a všechny elementární spojky jsou správné a úplné s ohledem na proměnné x 1 ... ..xn

Rozšíření v proměnných

Věta 1. V SDNF může být zastoupena jakákoli logická funkce:

kde m, a disjunkce je převzata všemi 2 m sadami hodnot proměnných x 1, ... x m. Funkce f je rozšířena v prvních n-proměnných. Tato rovnost se nazývá variabilní expanze. x 1, ... x m. Například pro n = 4, m = 2 je rozšíření:

věta je prokázána nahrazením libovolné kolekce (b 1, ..., b m, b m + 1, ..., b n) všech n-proměnných do obou stran rovnosti (1).

Pro m = 1 získáme z (1) rozšíření funkce v jedné proměnné:

Podobné rozšíření je evidentní pro jakoukoli z n-proměnných.

Další důležitý případ když n = m. V tomto případě všechny proměnné na pravé straně (1) dostanou pevné hodnoty a funkce ve spojení na pravé straně se stanou rovnými 0 nebo 1, což dává:

kde disjunkce převezme všechny množiny (b 1… b n), na kterých f = 1. Pro f = 0 je množina spojek na pravé straně prázdná. Tento rozklad se nazývá dokonalá disjunktivní normální forma. SDNF funkce f obsahuje přesně tolik spojek, kolik jich je v tabulce pravdivosti f. Každá množina jednotek (b 1,…, b n) odpovídá konjunkci všech proměnných, ve které je x i bráno s negací, pokud b i = 0 b, a bez negace, pokud b i = 1. Mezi tabulkou pravdivosti funkce f a jejím SDNF tedy existuje individuální korespondence, a proto je SDNF jedinečný pro jakoukoli logickou funkci. Jedinou funkcí, která nemá SDNF, je konstanta 0.

Věta 2... Libovolnou logickou funkci lze reprezentovat jako booleovský vzorec.

Skutečně, pro jakoukoli funkci, kromě konstanty 0, může její SDNF sloužit jako taková reprezentace. Konstanta 0 může být reprezentována booleovským vzorcem.

Nastavení booleovských funkcí proměnných pomocí pravdivostní tabulky, definování vzorce, typy nejdůležitějších ekvivalencí (zákonitostí) algebry logiky. Ekvivalentní vzorce, zákony ekvivalence, logické rovnice. Rozklad booleovských funkcí v proměnných.

Kliknutím na tlačítko „Stáhnout archiv“ stáhnete požadovaný soubor zdarma.
Před stažením tohoto souboru pamatujte si ty dobré eseje, testy, úkoly v kurzu, práce, články a další dokumenty, které jsou ve vašem počítači nevyzvednuty. Toto je vaše práce, musí se podílet na rozvoji společnosti a prospívat lidem. Najděte tato díla a odešlete je do znalostní báze.
My a všichni studenti, postgraduální studenti, mladí vědci, kteří využíváte znalostní základnu při studiu a práci, vám budeme velmi vděční.

Chcete-li stáhnout archiv s dokumentem, zadejte do níže uvedeného pole pětimístné číslo a klikněte na tlačítko „Stáhnout archiv“

Podobné dokumenty

Základní axiomy a identity algebry logiky. Analytická forma reprezentace booleovských funkcí. Elementární funkce algebry logiky. Funkce algebry logiky jednoho argumentu a formy jeho implementace. Vlastnosti, vlastnosti a typy logických operací.

abstrakt, přidáno 12.6.2010


Pojem algebry logiky, její podstata a rysy, základní pojmy a definice, předmět a metoda studia. Zákony algebry logiky a jejich důsledky, metody pro konstrukci vzorců podle dané pravdivostní tabulky. Formy reprezentace booleovských funkcí.

návod, přidáno 29.04.2009


Booleovské algebry jsou speciálním typem mřížky používané při studiu logiky (logiky lidského myšlení i logiky digitálního počítače) a také spínacích obvodů. Minimální formy booleovských polynomů. Abstraktní booleovské věty o algebře.

semestrální práce, přidáno 05/12/2009


Operace s logickými příkazy: Booleovské funkce a vyjádření některých z těchto závislostí prostřednictvím jiných. Výrokové formule a některé zákony logiky výroků. Překlad výrazů přirozeného jazyka do symbolické řeči algebry logiky.

test, přidáno 26. 4. 2011


Logika je věda o zákonech a formách myšlení a základním pojmem algebry logiky je tvrzení. Základní pojmy a identity booleovské algebry. Studium metod pro minimalizaci booleovských funkcí. Quinova metoda založená na aplikaci dvou základních vztahů.

test, přidáno 01/20/2011


Základní pojmy algebry logiky. Disjunktivní a spojovací normální formy. Podstata Shannonovy věty. Booleovské funkce dvou proměnných. Konzistentní a paralelní připojení dva spínače. Vlastnosti elementárních funkcí algebry logiky.

test, přidáno 29/11/2010


Booleovská proměnná v booleovské algebře. Logické operace: negace, konjunkce, disjunkce, implikace, ekvivalence. Základní zákony algebry logiky. Minimalizační pravidla pro logickou funkci (zbavení se implikačních a ekvivalenčních operací).

semestrální práce, přidáno 16. 1. 2012