Booleovský vzorec

Booleovská formule (pojmenovaná po George Boole ) je výroková logická formule . Může obsahovat logické proměnné a výrokové spojky — spojku (" "), disjunkci (" "), negaci (" "") a další. $\klín$ $\vee$ $\neg$

Vzorec se nazývá shodně true ( false ), pokud je pravdivý (false) pro jakékoli hodnoty proměnných. O dvou booleovských vzorcích se říká , že jsou ekvivalentní tehdy a pouze tehdy, pokud jsou pravdivé ve stejné podmnožině množiny hodnot argumentů.

Booleovský vzorec v n proměnných definuje booleovskou funkci , kde $E^{n}\to E$

E=\{0;1\}

je množina hodnot pro každou proměnnou ,

x_{i}

hodnota 0 odpovídá false a hodnota 1 odpovídá true.

x_{i}

x_{i}

Existuje celkem booleovských funkcí, takže existuje tolik tříd ekvivalentních booleovských vzorců. $2^{{2^{n}}}$