Implikant

I boolesk logik har termen implikant antingen en generisk eller en speciell betydelse. I den generiska användningen hänvisar det till hypotesen om en implikation ( implikant ). I den specifika användningen är en produktterm (dvs. en konjunktion av bokstaver) P en implikant av en boolesk funktion F , betecknad $P\leq F$ , om P antyder F (dvs. när P tar värde 1 så gör F ). Till exempel implikationer av funktionen

f(x,y,z,w)=xy+yz+w

inkludera termerna $xy$ , $xyz$ , $xyzw$ , $w$ , samt några andra.

Prime implicant

En primär implikant av en funktion är en implikant (i ovanstående speciella mening) som inte kan täckas av en mer generell, (mer reducerad, betydelse med färre bokstavliga ) implikant. W. V. Quine definierade en primär implikant som en implikant som är minimal – det vill säga att avlägsnandet av någon bokstavlig från P resulterar i en icke-implikant för F . Essential prime implicants (även kända som prime prime implicants ) är prime implicants som täcker en utdata av funktionen som ingen kombination av andra prime implicants kan täcka.

Genom att använda exemplet ovan kan man lätt se att medan $xy$ (och andra) är en primär implikant, är $xyz$ och $xyzw$ det inte. Från den senare kan flera bokstaver tas bort för att göra den prime:

$x$ , $y$ och $z$ kan tas bort, vilket ger $w$ .
Alternativt kan $z$ och $w$ tas bort, vilket ger $xy$ .
Slutligen kan $x$ och $w$ tas bort, vilket ger $yz$ .

Processen att ta bort bokstavliga ord från en boolesk term kallas att utöka termen. Att expandera med en bokstavlig fördubbling av antalet indatakombinationer för vilka termen är sann (i binär boolesk algebra). Med hjälp av exempelfunktionen ovan kan vi expandera $xyz$ till $xy$ eller till $yz$ utan att ändra omslaget till $f$ .

Summan av alla primtal implikanter av en boolesk funktion kallas dess fullständiga summa , minimal täckande summa eller Blake kanoniska form .

Se även

externa länkar