30. Булева алгебра. Аксиомы и теоремы булевой алгебры.

Булева алгебра – алгебра, образованная множеством В={0, 1} вместе со всеми возможными логическими операциями на нём.

31. Теорема о разложении функции алгебры логики по переменным (с доказательством).

Каждую функцию алгебры логики f(x₁, x₂, …, x_n) для ∀m ∈ {1, 2, …, n} можно представить в виде , где дизъюнкция берется по всевозможным наборам значений переменных x₁,…, x_m. Такое представление функции f называется разложением этой функции по m переменным.

Доказательство: Рассмотрим произвольный набор значений переменных (α1,…,αn), и вычислим f(α1, …, αn) сначала стандартным образом, а затем как в формулировке доказываемой теоремы: = [по ранее доказанному, если , то ]=, = [так что = 1] = f(α1, …, αn), что и требовалось доказать.

Следствия:

1) Если m=1, то f(x₁,…,x_n) =

2) m = n. Тогда f(x₁, …, x_n)= , так как остались лишь те наборы, при которых 

Получаем из следствия 2 равенство:

f(x₁,…,x_n)=

32. Сднф функций алгебры логики.

Совершенная дизъюнктивная нормальная форма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных конъюнкций

в каждой конъюнкции нет одинаковых пропозициональных букв

каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.

Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причем единственным образом, то есть для любой выполнимой функции алгебры логики существует своя СДНФ, причём единственная.

В ячейках результата отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так:

Переменные второго члена:

в этом случае будет представлен без инверсии:

Таким образом анализируются все ячейки . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).

Совершенная ДНФ этой функции:

33. СКНФ функций алгебры логики.

Совершенная конъюнктивная нормальная форма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных дизъюнкций

в каждой дизъюнкции нет одинаковых пропозициональных переменных

каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

Любая булева формула, не являющаяся тождественно истинной, может быть приведена к СКНФ.

В ячейках строки отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.

Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так:

Остальные члены СКНФ составляются по аналогии.