Правила (законы) де Моргана

Ассоциативность

х₁(х₂ х₃) = (х₁х₂)х₃;

х₁Ú (х₂ Ú х₃) = (х₁Ú х₂) Ú х₃.

Коммутативность

х₁ х₂ = х₂ х₁

х₁Ú х₂ = х₂Ú х₁

Дистрибутивность конъюнкции относительно дизъюнкции

х₁ (х₂ Ú х₃) = х₁х₂Ú х₁х₃.

Дистрибутивность дизъюнкции относительно конъюнкции

х₁ Ú(х₂ × х₃) = (х₁Úх₂) × (х₁Úх₃).^*

Идемпотентность (тавтология)

x & x = x

x Ú x = x

Двойное отрицание

Свойства констант

x & 1 = x; (законы универсального множества)

x Ú 1 = 1;

x & 0 = 0; (законы нулевого множества)

x Ú 0 = x;

`0 = 1;

`1 = 0;

Правила (законы) де Моргана

Закон противоречия (дополнительности)

`x x = 0;

Закон исключения третьего (дополнительности)

`x Ú x = 1;

Доказательства всех этих формул тривиальны. Один из вариантов –построение таблиц истинности левой и правой частей и их сравнение.

Правила склеивания

Правило склеивания для элементарных конъюнкций следует из распределительного закона, закона дополнительности и закона универсального множества: дизъюнкцию двух соседних конъюнкций можно заменитьодной элементарной конъюнкцией, являющейся общей частьюисходных конъюнкций.

Правило склеивания для элементарных сумм следует из распределительного закона второго рода, закона дополнительности и закона нулевого множества: конъюнкцию двух соседних дизъюнкций можно заменить одной элементарной дизъюнкцией, являющейся общей частьюисходных дизъюнкций.

Правило поглощения

Правило поглощения для суммы двух элементарных произведений следует из распределительного закона первого рода и законов универсального множества: дизъюнкцию двух элементарных конъюнкций, из которых одна является составной частью другой, можно заменить конъюнкцией, имеющейменьшее количество операндов.

Правило поглощения для произведения элементарных сумм следует из распределительного закона второго рода и законов нулевого множества: конъюнкцию двух элементарных дизъюнкций, из которых одна является составной частью другой, можно заменить элементарной дизъюнкцией, имеющей меньшее количество операндов.

Правило развертывания

Это правило определяет действие обратное склеиванию.

Правило развертывания элементарного произведения в логическую сумму элементарных произведений большего ранга (в пределе до r = n, т.е. до конституент единицы, как и будет рассмотрено ниже) следует из законов универсального множества, распределительного закона первого рода и производится в три этапа:

- в развертываемое элементарное произведение ранга r вводится в качестве сомножителей n-r единиц, где n- ранг конституенты единицы;

- каждая единица заменяется логической суммой некоторой, не имеющейся в исходном элементарном произведении переменной и ее отрицания: x_i v `x_i = 1;

- производится раскрытие всех скобок на основе распределительного закона первого рода, что приводит к развертыванию исходного элементарного произведения ранга r в логическую сумму 2^n-r конституент единицы.

Правило развертывания элементарного произведения используется для минимизации функций алгебры логики (ФАЛ).

Правило развертывания элементарной суммы ранга r до произведения элементарных сумм ранга n (конституент нуля) следует их законов нулевого множества (6) и распределительного закона второго рода (14) и производится в три этапа:

- в развертываемую сумму ранга r в качестве слагаемых вводится n-r нулей;

- каждый нуль представляется в виде логического произведения некоторой, не имеющейся в исходной сумме переменной и ее отрицания: x_i·`x_i = 0;

-получившееся выражение преобразуется на основе распределительного закона второго рода (14) таким образом, чтобы исходная сумма ранга r развернулась в логическое произведение 2^n-r конституент нуля.

16.Понятие полной системы. Примеры полных систем (с доказательством)

Определение. Множество функций алгебры логики A называется полной системой (в P2), если любую функцию алгебры логики можно выразить формулой над A.

Система функций A={ f₁, f₁,…, f_m }, являющаяся полной, называется базисом.

Минимальным базисом называется такой базис, для которого удаление хотя бы одной функции f₁ , образующей этот базис, превращает систему функций (f₁, f₁,…, f_m) в неполную.

Теорема. Система A = {∨, &, } является полной.

Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то f выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь дизъюнкция, конъюнкция и отрицание. Если же f ≡ 0, то f = x & x . Теорема доказана.

Лемма. Если система A — полная, и любая функция системы A может быть выражена формулой над некоторой другой системой B, то B — также полная система.

Доказательство. Рассмотрим произвольную функцию алгебры логики f (x₁, …, x_n) и две системы функций: A = {g₁, g₂, …} и B = {h₁, h₂, …}. В силу того, что система A полна, функция f может быть выражена в виде формулы над ней:

f (x₁, …, x_n) = ℑ[g1, g2,…]

где g_i= ℜ_i[h1,h2,…]

то есть функция f представляется в виде

f (x₁, …, x_n)=ℑ[ℜ1,ℜ2,...]

иначе говоря, может быть представлена формулой над B. Перебирая таким образом все функции алгебры логики, получим, что система B также полна. Лемма доказана.

Теорема. Следующие системы являются полными в P₂:

1) {V, } ;

2) {&, } ;

3) { | };

4) {&, ⊕ , 1}базис Жегалкина.

Доказательство.

1) Известно (теорема 3), что система A = {&, V, } полна. Покажем, что полна система B = { V, . Действительно, из закона де Моргана (x& y) = (x ∨ y) получаем, что x & y = (x ∨ y) , то есть конъюнкция выражается через дизъюнкцию и отрицание, и все функции системы A выражаются формулами над системой B. Согласно лемме система B полна.

2) Аналогично пункту 1: ( x ∨ y) = x & y ⇔ x ∨ y =( x & y) и из леммы 2 следует истинность утверждения пункта 2.

3) x | y=(x&y), x | x = x ; x & y = (x | y) = (x | y) | (x | y) и согласно лемме 2 система полна.

4) x = x ⊕1 и согласно лемме 2 система полна.

Теорема доказана.

17.Алгебра Жегалкина. Свойства операций и полнота

Множество булевых функций, заданных в базисе Жегалкина S4={⊕,&,1} называется алгеброй Жегалкина.

Основные свойства.

1. коммутативность

h1⊕h2=h2⊕h1 h1&h2=h2&h1

2. ассоциативность

h1⊕(h2⊕h3)=(h1⊕h2)⊕h3 h1&(h2&h3)=(h1&h2)&h3

3. дистрибутивность

h1&(h2⊕h3)=(h1&h2)⊕(h1&h3)

4. свойства констант

h&1=h h&0=0

h⊕0=h

5. h⊕h=0 h&h=h
Утверждение. Через операции алгебры Жегалкина можно выразить все другие булевы функции:

x=1⊕x

xvy=x⊕y⊕xy

x∼y=1⊕x⊕y

x→y=1⊕x⊕xy

x↓y=1⊕x⊕y⊕xy

x|y=1⊕xy

18.Полином Жегалкина. Способы построения. Пример.

. Полиномом Жегалкина (полиномом по модулю 2) от n переменных x₁,x₂ ... x_n называется выражение вида:

c₀⊕c₁x₁⊕c₂x₂⊕ ... ⊕c_nx_n⊕c₁₂x₁x₂⊕ ... ⊕c_{12 ... n}x₁x₂ ... x_n,

где постоянные C_k могут принимать значения 0 ли 1.

Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным (линейная функция).

Например, f=x⊕yz⊕xyz и f₁=1⊕x⊕y⊕z - полиномы, причем вторая является линейной функцией.

Теорема. Каждая булева функция представляется в виде полинома Жегалкина единственным образом.

Приведем основные методы построения полиномов Жегалкина от заданной функции.

1. Метод неопределенных коэффициентов. Пусть P(x₁,x₂ ... x_n) - искомый полином Жегалкина, реализующий заданную функцию f(x₁,x₂ ... x_n). Запишем его в виде

P=c₀⊕c₁x₁⊕c₂x₂⊕ ... ⊕c_nx_n⊕c₁₂x₁x₂⊕ ... ⊕c_{12 ... n}x₁x₂ ... x_n

Найдем коэффициенты C_k. Для этого последовательно придадим переменным x₁,x₂ ... x_n значения из каждой строки таблицы истинности. В итоге получим систему из 2ⁿ уравнений с 2ⁿ неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(X₁,X₂ ... X_n).

2. Метод, основанный на преобразовании формул над множеством связок {,&}. Строят некоторую формулу F над множеством связок {,&}, реализующую данную функцию f(X₁,X₂ ... X_n). Затем заменяют всюду подформулы вида A на A⊕1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

Пример. Построить полином Жегалкина функции f(X,Y)=X→Y

Решение.
1. (метод неопределенных коэффициентов). Запишем искомый полином в виде:

P=c₀⊕c₁x⊕c₂y⊕c₁₂xy

Пользуясь таблицей истинности импликации получаем, что

f(0,0)=P(0,0)=C₀=1

f(0,1)=P(0,1)=C₀⊕C₂=1

f(1,0)=P(1,0)=C₀⊕C₁=0

f(1,1)=P(1,1)=C₀⊕C₁⊕C₂⊕C₁₂=1

Откуда последовательно находим, C₀=1, C₁=1, C₂=0, C₁₂=1

Следовательно: x→y=1⊕X⊕XY.

2. (Метод преобразования формул.). Имеем: x→y=xvy=(xy)=(x(y⊕1)) ⊕1=1⊕x⊕xy
Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул.