Podręcznik

Innym typowym zastosowaniem algebry Boole’a jest przekształcanie wyrażeń boolowskich z postaci typu „iloczyn sum” (CNF – Conjunctive Normal Form) na postać typu „suma iloczynów” (DNF – Disjunctive Normal Form).

Korzysta się przy tym z zasad uproszczonego mnożenia, z których pierwsza jest omawianą już zasadą rozdzielności dodawania względem mnożenia, a drugą wykazujemy poniżej.

            Wykazać, że:  \(\left(x+y\right)\left(\bar{x}+z\right)=\ xz+\bar{x}y\)

\(\begin{array}{{>{\displaystyle}l}} ( x+y)\left(\overline{x} +z\right) =x\overline{x} +xz+\overline{x} y+yz=xz+\overline{x} y+yz=\\ =xz+\overline{x} y+1yz=xz+\overline{x} y+\left( x+\overline{x}\right) yz=xz+\overline{x} y+xyz+\overline{x} yz=\\ =xz+xyz+\overline{x} y+\overline{x} yz=xz( 1+y) +\overline{x} yy( 1+1) =\ xz+\overline{x} y \end{array}\)

Ogromne znaczenie w syntezie logicznej mają przekształcenia wyrażeń boolowskich jednorodnych, tzn. takich w których zmienne występują wyłącznie w postaci prostej albo zanegowanej.

Nietrudno przypuszczać, że w praktycznych zastosowaniach będziemy mieli do czynienia z bardziej rozbudowanymi przekształceniami CNF na DNF. W celu ułatwienia skomplikowanych obliczeń i zapisów zmienne boolowskie x_i, x_j, x_k będziemy reprezentowali ich indeksami i, j, k.

Transformacja CNF na DNF jest również wygodnym i często stosowanym narzędziem przy obliczaniu pokrycia kolumnowego binarnej macierzy M.

Pokryciem kolumnowym binarnej macierzy reprezentowanej tablicą M: 

\(M=\left[m_{ij}\right],\ i\in\left\{1,\ldots,w\right\},\ j\in\left\{1,\ldots,n\right\}\)

jest zbiór   \(L\ \in\left\{1,\ldots,n\right\}\)  taki, że dla każdego \(i\in{1,\ldots,w}\)  istnieje \(\ j\in\ L,\)  dla którego \(m_{ij}=1\) . Jeżeli usunięcie którejkolwiek z kolumn skutkuje brakiem pokrycia, jest to minimalne pokrycie kolumnowe. Inaczej mówiąc elementami pokrywanymi są wiersze M, a pokrywającymi – kolumny tej macierzy. Jednak brak formalnych elementów pokrywanych i pokrywających skłania do wprowadzenia nazwy „pokrycie kolumnowe”.    

W wyrażeniu CNF czynniki koniunkcji są dysjunkcjami zmiennych boolowskich etykietujących te kolumny M dla których w danym wierszu \(m_{ij}=1\) . Liczba czynników jest równa liczbie wierszy macierzy M. Istotnym problemem jest transformacja CNF na DNF, gdyż składniki wyrażenia DNF są koniunkcjami zmiennych reprezentujących kolumny macierzy M.