4.Функции алгебры высказываний (булевы функции)

Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B={1, 0}, где 1 соответствует значению “И”, а 0 – значению “Л”.

Булева функция (или логическая функция, или функция алгебры логики) от n переменных отображение Bn -> B, где B = {0,1} — булево множество. Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно».

Логическую функцию n переменных f(x1,x2,...,xn) можно задать таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части - значения функции на этих наборах. Такие таблицы носят название таблиц истинности.

Множество всех булевых функций от любого числа переменных часто обозначается P2, а от n переменных — P2(n).

Конъюнктивная нормальная форма1 (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.Кнф- произведение элементарных сумм. ДНФ- сумма элементарных произведений.