implikujący

W logice boolowskiej termin implikant ma znaczenie ogólne lub szczególne. W użyciu ogólnym odnosi się do hipotezy implikacji ( implicant ). W konkretnym użyciu termin iloczynu (tj. koniunkcja literałów) P jest implikantem funkcji boolowskiej $F$ , oznaczonej jeśli P implikuje ( tj. ilekroć P wartość 1 tak samo F. ). Na przykład implikanty funkcji

{\ Displaystyle f (x, y, z, w) = xy + yz + w}

obejmują terminy ${\ displaystyle xy}$ , ${\ displaystyle xyz}$ , ${\ displaystyle xyzw}$ , ${\ displaystyle w}$ , a także kilka innych.

Główny implikant

Główny implikant funkcji jest implikantem (w powyższym szczególnym znaczeniu), którego nie można objąć bardziej ogólnym (bardziej zredukowanym, czyli z mniejszą liczbą literałów ) implikantem. WV Quine zdefiniował główny implikant jako implikant, który jest minimalny - to znaczy usunięcie dowolnego literału z P skutkuje brakiem implikanta dla F . Niezbędne implikanty pierwsze (znane również jako podstawowe implikanty pierwsze ) są implikantami głównymi, które obejmują wynik funkcji, którego nie jest w stanie pokryć żadna kombinacja innych implikantów głównych.

$}$ można łatwo zauważyć, że chociaż $)$ jest głównym implikantem, to i $xyzw$ nie są. Z tego ostatniego można usunąć wiele literałów, aby uczynić go pierwszym:

${\ displaystyle x}$ , ${\ displaystyle y}$ i ${\ displaystyle z}$ można usunąć, uzyskując ${\ displaystyle w}$ .
Alternatywnie $_$ $,$ można $_$ . _
$}$ , i można usunąć, otrzymując $y$ $yz$ .

Proces usuwania literałów z terminu boolowskiego nazywa się rozszerzaniem terminu. Rozszerzenie o jeden literał podwaja liczbę kombinacji wejściowych, dla których termin jest prawdziwy (w binarnej algebrze Boole'a). Korzystając z powyższej przykładowej funkcji, możemy rozwinąć $}$ lub do $\ displaystyle yz$ $}$ bez zmiany okładki $f$ .

Suma wszystkich głównych implikantów funkcji boolowskiej nazywana jest jej sumą całkowitą , minimalną sumą pokrywającą lub postacią kanoniczną Blake'a .

Zobacz też

Linki zewnętrzne