Quine módszer, logika, példák a problémák megoldására
- Definíció. Elementary összefüggésben K implicants az f függvény, ha bármely készlet A = (a1, a2, ..., an) a 0 és 1, a feltétel az R (a) = 1 azt jelenti, f (a) = 1.
- Definíció: Egy f függvény applikátorát egyszerűnek nevezik. ha az abból nyert kifejezés bármilyen tényezőt kivetve többé már nem az "f" függvény befogadója.
- Az f függvény bármely lényeges eleme az f függvény része.
- Tétel. Minden funkciót az összes egyszerű implikáns diszjunkciója valósít meg.
- Definíció: Egy f függvény redukált DNF-je az f függvény összes egyszerű implikátorának diszjunciója.
- Jóváhagyása. Minden f funkciót a rövidített DNF valósítja meg.
- Minden olyan funkció esetében, amely nem azonos a nulla értékkel, létezik egy egyedülálló rövidített DNF.
- A tétel (Quine). Ha az f függvény PDNF végezzen az összes művelet hiányos kötés, majd az összes abszorpció működését és az eltávolítását a redundáns tagjai, az eredmény egy csökkentett DNF f függvény.
Quine algoritmusa egy redukált DNF létrehozására
1. Vegye le a CDNF funkciót.
2. Végezzen minden hiányos ragasztási műveletet.
3. Végezzen minden abszorpciós műveletet.
Egy példa. Minimáld a funkciót f = 1111010010101111.
A megoldás.
1. Egy adott funkciót tartalmazó táblázatot építünk (táblázat). Építjük az SDNF funkciókat. Az összegek száma és oszlopban (táblázat) írva.
2. Teljesítjük a tökéletlen ragasztási műveleteket.
A ragasztás első szakasza (táblázat):
A ragasztás első szakaszában a CDNF valamennyi feltétele részt vett, ami azt jelenti, hogy az eredeti kifejezések egyike sem szerepel a rövidített DNF-ben. A ragasztás első szakasza (és a lehetséges felszívódás) után ezt megkapjuk
A kapott DNF-ben a diszjunktív kifejezéseket egymás után sorrendben számoljuk 1-től 15-ig (táblázat).
A ragasztás második fázisa:
A második szakaszban történő ragasztási eljárás során az 5. és 8. komponensek nem vettek részt az előző lépésben, ezért a beillesztés és a későbbi felszívódás második szakaszát követően azt találtuk, hogy
Mivel a további ragasztás lehetetlen, ez lesz az eredeti funkció rövidített DNF-je.