Implicants de o funcție booleană

Soluția de rezolvare a problemei de minimizare a funcției booleene prin Quine și îmbunătățită metoda Quine Mc-KLASCO se bazează pe conceptele de implicants și a sistemelor lor.

Definiția. Funcția Boolean g (X), numit implicant funcția booleană f (X), în cazul în care pentru orice set dat de argumente asupra cărora g (X) = 1, f (X) este de asemenea egal cu unu.

1) Între implicant și funcția în sine există relație de incluziune g (X)Ì f (X).

2) Se poate argumenta că, pentru orice set de argumente pe care funcția este zero, ea implicant este de asemenea zero.

3) Când g (X) și j (X) sunt implicants funcția f (X), atunci disjuncție lor este implicant această funcție.

Cele mai simple Exemplele implicants termeni conjunctive pot fi incluse într-o funcție arbitrară a DNP.

disjuncție Arbitrare a acestor termeni este, de asemenea, funcția implicant.

Opredelenie.Prostoy (primar) funcția boolean implicant este numit pe termen conjunctivă, care este el însuși implicant această funcție, dar nici o parte a propriei sale nu mai este implicant această funcție.

Definiția. Sub partea corespunzătoare a termenului se referă la un nou termen derivat din pornire, prin eliminarea unui număr arbitrar de caractere.

Pentru acest exemplu, funcția (#) implicants prime sunt:

Set de prim implicants poate fi asociată cu setul de cuburi maximale.

Definiția. Disjuncția tuturor implicants prime ale unei funcții boolean este un DNF această funcție, care se numește scurtat - PDNF.

Pentru funcția (#) din exemplul PDNF:

Conceptul de „reducere“ a fost acordat un DNF, în sensul că acesta conține, de obicei, mai puține litere și termeni în comparație cu KDNF. De exemplu nostru KDNF conține 15 litere și 5 termeni, și PDNF - 8 litere și 4 pe termen.