Глава 4 Алгебра логики (стр. 2 )

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

Одна и та же функция может иметь множество реализаций формулами над данным базисом (т. е. множеством логических операций). Формулы, реализующие одну и ту же функцию, называются равносильными (т. е. на всех наборах переменных их значение истинности совпадает). Отношение равносильности формул является отношением эквивалентности.

Пусть даны формулы F(y1, y2, …, ym ), f1(x1, x2, …, xn ), …, fm(x1, x2, …, xn ). Тогда подстановкой формул fi в формулу F называется следующая конструкция: (F| yi fi )(x1, x2, …, xn) º F(f1(x1, x2, …, xn ), …, fm(x1, x2, …, xn )).

Теорема 4.2  (О подстановке формул)

Если F(y1, y2, …, ym ) и fi (x1, x2, …, xn ) – формулы алгебры логики, то
(F| yi fi )(x1, x2, …, xn ) также является формулой.

Иначе: Вместо некоторой подформулы в формулу может быть подставлена другая формула, и в результате получится правильно построенная формула.

Правило подстановки

Если в равносильных формулах: F(y1, y2, …, ym ) ºG(y1, …, ym ) – вместо всех вхождений некоторой переменной yi подставить одну и ту же формулу, то получатся равносильные формулы.

Правило замены

Если в формуле F заменить некоторую подформулу yi на равносильную gi, то получатся равносильные формулы.

ФАЛ, при образовании которых используются только операции отрицания, конъюнкции и дизъюнкции, называются булевыми формулами.

Теорема 4.3  Для любой формулы алгебры логики существует равносильная ей булева формула.

4.1.4  Булевы функции и булева алгебра

Множество булевых функций с определенными на нем операциями отрицания, конъюнкции и дизъюнкции называется булевой алгеброй. Множество булевых функций от n аргументов будем обозначать Pn.

Для булевой алгебры выполняется ряд равносильностей, которые являются ее аксиомами.

Аксиомы булевой алгебры:

1.  Операции с константами:
1) A Ú 1 º 1; A & 1 º A; 2) A Ú 0 º A; A & 0 º 0.

2.  Противоречие: A & ØA º 0.

3.  Исключение третьего: A Ú ØA º 1.

4.  Идемпотентность: A & A º A; A Ú A º A.

5.  Двойное отрицание: Ø ØA º A.

6.  Коммутативность: A & B º B & A; A Ú B º B Ú A.

7.  Ассоциативность:
(AÚB)ÚC º AÚ(BÚC); (A&B)&C º A&(B&C).

8.  Дистрибутивность:
A & (B Ú C) º (A & B) Ú (A & C); A Ú (B & C) º (A Ú B) & (A Ú C).

9.  Законы де Моргана: Ø(A&B) º ØA Ú ØB; Ø(AÚB) º ØA & ØB.

Используя приведенные аксиомы, возможно выполнять равносильные преобразования, выводить и доказывать новые законы. В частности, при выполнении преобразований часто используются законы поглощения:
1) A & (A Ú B) º A; A Ú A & B º A;
2) ØA & (A Ú B) º ØA & B; A Ú ØA & B º A Ú B.

Эти законы несложно доказать с помощью аксиом.

4.1.5  Принцип двойственности

Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция f*(x1, x2, …, xn ) º f (`x1,`x2, …,`xn ). Из определения видно, что двойственность инволютивна: f**=f.

Если двойственная функция f* совпадает с исходной функцией f, то такая функция f называется самодвойственной.

  Пример 4.3  (0)* º`0º1; (x)*= (`x) º x Þ Функция, тождественно равная своему аргументу, является самодвойственной.

Теорема 4.4  (Общий принцип двойственности)

Если G(x1, …, xn ) получена подстановкой fi из F(y1, …, ym ):
G(x1, …, xn )º (F| yi fi )(x1, …, xn ), то G*(x1, …, xn )º (F*| yi f*i )(x1, …, xn ).

Теорема 4.5  (Принцип двойственности для булевых функций)

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

x	y	f=xÚy	x	y	f*
0	0	0	1	1	1
0	1	1	1	0	0
1	0	1	0	1	0
1	1	1	0	0	0

  Пример 4.4  (x`y Ú z)* º (xÚ`y) & z., (xÚy)* º x&y Þ в таблице истинности значения функции и переменных меняются на противоположные

4.1.6  Алгебра Жегалкина

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

Аксиомы алгебры Жегалкина:

1.  Операции с константами: A×1 º A; A×0 º 0; A Å 0 º A.

2.  Идемпотентность: A×A º A; A Å A º 0.

3.  Коммутативность: A×B º B×A; A Å B º B Å A.

4.  Ассоциативность: (A Å B) Å C º AÅ (B Å C); (A×B)×C º A×(B×C).

5.  Дистрибутивность: A×(B Å C) º A×B Å A×C.

Можно перейти от алгебры Буля к алгебре Жегалкина, используя следующие соотношения: A Å 1 º`A; AÚB=A Å B Å A×B.

И наоборот, от алгебры Жегалкина к алгебре Буля: A Å B =`A×BÚ A×`B

  Пример 4.5  Перейти к выражению булевой алгебры: (x Å 1)×yÅ (x Å 1) = `x×y Å`x = `xy×`x Ú x×`xy = (x Ú`y)×`x Ú 0 =`x`y.

4.1.7  Контрольные вопросы

1.  Какие высказывания являются равносильными? Приведите пример.

2.  Какие существуют логические операции?

3.  Какие логические операции дают в результате их применения к двум аргументам только одно истинное (ложное) значение? На каких наборах переменных достигается это значение?

4.  Какие операции на всех наборах значений переменных имеют взаимно противоположные значения?

5.  Какие существуют формулы, позволяющие выразить одну операцию через другую?

6.  Каков порядок логических операции в соответствии с их приоритетом?

7.  Что такое переключательная функция?

8.  Сколько существует различных наборов аргументов для функции 5 переменных?

9.  Какая функция является полностью определенной?

10.  Что такое булева алгебра? Что представляют собой аксиомы?

11.  Какая функция является самодвойственной?

12.  В чем состоит принцип двойственности для булевых функций?

13.  Какие операции определяют алгебру Жегалкина?

14.  Как связаны алгебры Буля и Жегалкина?

4.2  Способы представления булевых функций

4.2.1  Нормальные формы

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

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

Элементарной дизъюнкцией (произведением) называется дизъюнкция (произведение) переменных или их отрицаний, в котором каждая переменная встречается только один раз.

ДНФ – это дизъюнкция элементарных произведений. КНФ – это произведение элементарных дизъюнкций. Как ДНФ, так и КНФ функции не единственна. Обычно предполагают, что входящие в ДНФ (КНФ) элементарные конъюнкции (дизъюнкции) попарно различны.

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

Ñ  СДНФ (СКНФ) функции единственна.

  Пример 4.6  Элементарные дизъюнкции: xÚ`y, z. Элемент. конъюнкции: x×`y×z, x. f(x, y,z) = xyz Ú`xy – ДНФ ; f(x, y,z) = (x Ú`y)×z – КНФ.