Fontos kifejezések
Előadás 6. A kanonikus logikai formulák, amelyek használják a számítógépet
6.1 A legfontosabb feltételek. A koncepció PDNF és SKNF.
6.2 Algoritmusok és összeállításának PDNF SKNF az igazság táblázat.
Minden logikai képlet határozza némi logikai funkciókat. Ugyanakkor egyértelmű, hogy meg tudjuk írni végtelen számú a formula minden Boole-függvény (lásd. 3. feladat § 3.6). Valóban, ha van legalább egy általános képletű expresszáló Boole-függvény, akkor használja a személyazonosságát átalakulás, ez lehet változtatni ezt a képletet megszerkesztésével tetszőlegesen bonyolult egyenértékű képletnek, például,
egy xor b ≡ (a és (nem b)), vagy ((nem a) és b).
Az egyik fő célkitűzése a logikai - a megállapítás kanonikus formát (azaz a képletek által épített egy bizonyos szabály, kánon ..), valamint a legegyszerűbb képlet képviselő logikai funkciókat.
Definíció 1. Ha a logikai függvény által kifejezett szétválás, összefüggésben és tagadása változók, például a prezentációs normálisnak nevezik.
Között szokásos formák kiválasztják azokat, amelyek a funkciókat írva egyedülálló módon. Ezek az úgynevezett tökéletes.
Egy különleges szerepet a matematikai logika osztályok játszani tökéletes diszjunktív és konjunktív normálforma (PDNF és SKNF). Ezek alapján a koncepció egy elemi diszjunkció és az elemi összefüggésben.
2. Definíció A képlet az úgynevezett elemi együtt, ha ez egy kötőszó egy vagy több változó, étellel vagy anélkül tagadás tagadása. A változó vagy annak tagadása tartják az egyik távú elemi összefüggésben.
1. példa Formula kötőszók elemi; Az első kettő - az egyik távon.
3. meghatározása képletű nevezzük diszjunktív normál forma (DNF), ha azt nem ismétlődő elemi diszjunkciót kötőszavak. DNP felírható, ahol minden Ai - elemi összefüggésben.
2. példa Az alábbiakban két diszjunktív normál forma:
Definíció 4. A képlet k változó nevezzük tökéletes diszjunktív normál forma (PDNF), ha:
1) A jelentése DNF, amelyben minden egyes elemi együtt egy konjunkciója k változó, és az i-edik pozícióban ennek összefüggésben érdemes egy változó, vagy a negáltját;
2) az összes elemi összefüggésben az ilyen DNP különbözőek.
Feladat 1. képletek:
;
;
Határozza meg, hogy azok PDNF két változó között.
Határozat. A képlet az PDNF két változó között. Képletek B és C nem PDNF. Formula B függ három változó, de a változók száma kevesebb, mint három elemi kötőszavak. A képlet változók X2 kétszer szerepel ugyanazon elemi összefüggésben.
Tökéletes Diszjunktív normál forma egy általános képletű épül jól meghatározott szabályok belül sorrendben elemi kötőszavak (diszjunktív értelemben) az ott. Ez egy példa egy egyértelmű ábrázolásának a Boole-függvény, mint egy Képlettároló (algebrai) felvételt.
Definíció 5. A képlet az úgynevezett elemi diszjunkciót, ha ez egy diszjunkció (talán az egyik távú) változók és negáltjai változók.
1. példa ad három elemi diszjunkciót:
.
6. meghatározása képletű nevezzük konjunktív normál forma (CNF), ha azt nem ismétlődő együtt elemi diszjunkcióban.
CNF írott formában, ahol minden Ai - elemi diszjunkció.
Ezek konjunktív normál forma.
Definíció 7. Egy általános képletű K-ben változók nevezik tökéletes konjunktív normál forma (SKNF), ha:
1) Mi a CNF, amelyben minden egyes elemi diszjunkció egy diszjunkcióját k változó, és az i-edik pozíciója diszjunkcióját érdemes egy x változó vagy a negáltja;
2) az összes elemi diszjunkció CNF ilyen egymástól eltérő.
2. Cél képletek és. Határozza meg, hogy azok SKNF.
Határozat. Formula A jelentése SKNF és a B képlet nem SKNF változtatható duplán belép az első konjunktív kifejezés, amellett, a változók száma az egyes elemi diszjunkciót kevesebb, mint három, míg a képlet függ három változó.
Kérdésre. Van-e logikai függvény leírható az egyik helység kanonikus tökéletes alakot?
Válasz. Igen, bármely Boole-függvény, nem azonosan egyenlő 0 vagy 1, úgy reprezentálható, mint PDNF vagy SKNF.
Alátámasztani az állítást egy tétel.
1. Tétel Legyen - logikai n-változós függvény, nem azonosan nulla. Aztán ott van a tökéletes diszjunktív normál forma, amely kifejezi az f függvény.
Egy algoritmust építésére PDNF igazság táblázat:
1. Az igazság táblázat figyelmét a változókat, amelyek a függvény értéke f egyenlő egységét.
2. Írja minden jelölt együttállása egy sor minden változót a következő módon: ha a változó értékét a készletben 1, összefüggésben többek között a változó magát, különben - a tagadása.
3. Minden beérkezett kötőszavak csatlakozni eltérésre.
Következménye tétel 1. Bármelyik formula megtalálható ez egyenértékű DNF.
3. példa felépítéséhez szükséges a képlet az f (x1, x2 x3 ..) által definiált igazság táblázat:
A fenti algoritmusnak megépíteni PDNF ez:
2. Tétel Let - Boole-függvény n változók, nem azonosan egyenlő eggyel. Aztán ott van a tökéletes konjunktív normál forma, amely kifejezi az f függvény.
Ennek alapján a 2. Tétel tudjuk javasolni a következő algoritmus építésére SKNF igazság táblázat funkciót.
Egy algoritmust építésének SKNF igazság táblázat ^
1. Az igazság táblázat figyelmét a változókat, amelyek a függvény értéke f egyenlő nullával.
2. Írja minden halad sor diszjunkcióját összes változót az alábbi módon: ha a változó értékét a készletben egyenlő 0, összefüggésben többek között a változó magát, különben - a tagadása.
3. Minden beérkezett diszjunkcióját munkatársa műveletek összefüggésben.
Következménye Tétel 2. Bármely képletű megtalálható ez az egyenértékű CNF.
4. példa Express vonatkozások funkciót negáció műveletek diszjunkciót és összefüggésben. Ehhez írunk igazság táblázat kihatással funkciók: