A dnf minimalizálása a Quine módszerrel

Mindegyik képletnek véges számú változója van. Egy változó előfordulása alatt azt a helyet értjük, amelyet a változó foglal magában a képletben. A probléma az, hogy egy adott logikai függvényhez f találjon egy DNP-t, amely ezt a függvényt képviseli, és a legkisebb számú változó előfordulása.






Ha x egy logikai változó, és σ∈, akkor kifejezés

¬x ha σ = 0

úgynevezett litera. A kötőszó betűk összekötése. Például a XYZZ és XYX¬X képletek kötődnek. Az elemi termék egy kötőszó, amelybe bármely változó egyszerre lép be (önmagában vagy annak negációjával).






Az f1 képletet az f képlet fogalmának nevezzük, ha f1 egy elemi termék és f1f = f1, vagyis az adott f1≤f függvény képlet érvényes. Az (f) képlet implicit f1 jelentése egyszerű, ha bármelyik f1 betű eldobása után nem kapjuk meg az (f) képlettel rendelkező képletet.
Egy példa. Az összes fentebb említett imant és egyszerű imantant megtaláljuk az f = X → Y képletre. Összesen 8 elemi termék van, X és Y változókkal. Az egyértelműség érdekében az igazságtábláit megadják.

A holtpont DNP kiválasztott minimális számú prime implicants, diszjunkció, amely megtartja az összes alkotórészt egység, m. E., mindegyik oszlopa a mátrix tartalmaz egy lánckereket Quine állt a keresztezi megfelelő vonal egy kiválasztott implicants. A minimum DNF választott patthelyzet, amely a legkisebb számú előfordulása változó.
Az előző példában a Quine mátrix használatával megállapítjuk, hogy egy adott függvény minimális DNF-je ¬X¬YvXZ.
Megjegyzés. Egy f függvény minimális CNF-jének megépítéséhez elegendő egy minimális DNF-t létrehozni egy f függvényre, majd f = β (β) és de Morgan-törvényeket használva.