Matematika - matematikai logika

Táblázat Ai, j - konstans 0 vagy 1, meghatározzuk argumentum értékek; Fj - konstans 0 vagy 1, meghatározása az értékek a érvek egy adott kombinációja; M = 2 N - a száma az összes lehetséges kombinációt.

Mi határozza meg függvényében 1 érv:

Ezután az eredeti funkciója is képviselteti magát:

Mint látható, ez kifejeződik csupán a feladatok,

és . Minden sor ebben a rendeletben (*) egy sornak felel meg a táblázatban.

Továbbra is azt bizonyítják, hogy a bal oldalon a (*) valóban megegyezik az eredeti funkciót. Veszünk egy tetszőleges n-edik sorának az asztalra. Biztosítani kell, hogy a funkció Fn valóban egyenlő az érték a bal oldali (*), ahol az érvek feltüntetett értékeket ebben a sorban: xi = Ai, n i = 1, 2, 3. N.

Azaz, a kiválasztott N, és minden i igaz:

Vegyünk egy (*) n-edik sorban, mi helyettesítheti benne (1), és alkalmazza az abszorpciós törvény x 1 = x.

Most veszünk (*) bármely más sorban, kivéve az N -edik. Legyen ez az a szám m. Mivel minden táblázat sorait tartalmazza különböző készletek Ai, j. legalább ugyanabban az oszlopban lesz a különbség. Legyen a különbség tartalmazza k-edik oszlop:

Azaz, a kiválasztott k és m igaz:

Vegyünk egy (*) m-edik sorban, mi helyettesítheti benne (2), és alkalmazza az abszorpciós törvényi x 0 = 0, és 0 x = 0.

Így a értéke PDNF minden vonal kivételével n -edik jelentése 0 miatt nulla, amely legalább egy különbség a érveket készletek. Csak N-edik sorban egyenlő Fn.

Az eredmény:

És törvényei felszívódását x 0 = x 0 és x = x kapjuk:

Mi úgy tetszőleges n -edik sora az asztalra, és látható, hogy egy sor érvek írva ebben a sorban egybeesik a értéke a függvény értéke a bal oldalon (*). Pontosan ugyanaz az érvelés lehet ismételni az összes többi sort, nem számít, hogy mennyit lehet. Így a függvény értéke egybeesik a bal oldalon (*) az összes lehetséges készletek érveket. QED.

A képletben (*) sorokban, ahol Fj = 0 lehet hagyni, mivel a felszívódás törvény: X 0 = 0, x 0 = x 0 és x = x. És a sort, ahol Fj = 1 elhagyható Fj. miatt az abszorpciós törvény: x 1 = x.

A felvétel után ezek a csökkentések kapunk, amely az úgynevezett teljes diszjunktív normál forma (PDNF).

Példa a PDNF.

Írása PDNF egy funkció, amely a korábban idézett példaként.

PDNF össze az alábbiak szerint: minden egyes sorban egy egység a jobb szélső oszlopban alkotják a zárójelben és összekapcsolják azok működését. Minden tartó inszertált szekvencia egyszerű elemek kombinált működését : A táblázat cella, ahol elhelyezett 1, írja a változó érv, és minden cellában, ahol elhelyezni 0 write változó érv a jel

PDNF lehet egyszerűsíteni, és a további, amelyekre vannak különböző módszerek, például a módszer az úgynevezett „Karnaugh térkép”, amely azon az intuitív vizuális képeket. Mindezek a módszerek szabályai alapján egyszerűsítés:

b c) = a c
(a b) (a

Azaz, ha PDNF talált két konzolok, amelyek csak a jel

előtt az egyik eleme, akkor helyettesíthető egy konzol, ahol ez az elem nincs jelen. Például a kapott fenti képlet egyszerűsíteni lehet ez a szabály kombinálásával az utolsó két zárójelben egy: