Булева алгебра.

Книга: Калужнин. Что такое математическая логика?

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

Формулой «булева алгебра» - всякое выражение, составленное из конечного числа букв U, V, W знаков операций булевой алгебры - V ^ и констант 0, 1 включая ( ) для выполнения различных операций. Будем говорить что формула А(U,VOmega) построена правильна если подстановки в нее (аргументов) произвольных булевых функций формула приводится к вполне определенной булевой функции.

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

Все буквы U,V Omega с индексами и без них, а так же константы 0 и 1 являются правильно построенными функциями

2. Если А и B правильно построенные формулы, то тогда выражение вида (!A),(A^B),(AvB) являются правильно построенными формулами. Для упрощения написания правильно построенной формулы вводится правило: При прочих равных условиях в первую очередь выполняется отрицание, затем конъюнкция и после дизъюнкция. При сохранении этого порядка скобки не ставятся.

3. Когда используется операция отрицания скобки не ставятся, а знак ставится над нужными членами.

Замечание: В дальнейшем будут рассматриваться лишь правильно построенные формулы.

Одной из основных задач булевой алгебры является установление тождественных соотношений вида А(U,V, Omega…) = B(U,V,Omega) (1)

A,B – формулы, а U, V, Omega – произвольные булевы функции

Формулы А и B определяют некоторые булевые функции. Их необходимо проверить на соответствие всем наборам аргументов. При совпадении на всех наборах тождество выполняется, в противном случае нет.

Соотношение:

22. Закон коммутативности для конъюнкции X^Y = Y^X

23. (X ^ Y)^Z = X^(Y^Z)

24. X^X = X Идемпотентности закон

25. X v Y = Y v X

26. (X v Y) v Z = X v (Y v Z)

27. X v X = X

28. X ^ (Y v Z) = (X ^ Y v X ^ Z) – Закон дистрибутивности

29. X ^ Y v Z = (X v Y) ^ (X v Z) – Закон дистрибутивности

7 и 8 аналогичны законам действующие в алгебре множеств

30. правило поглощения X v X ^ Y = X

31. X ^ (X v Y) = X

9, 10 выполняется для любых наборов аргументов

32. Закон двойного отрицания !!X = X (соответствует операции инволюции в алгебре множеств)

33. Законы Де Моргана !(X ^ Y) = !X v !Y

34. !(X v Y) = !X ^ !Y

35. X v !X = 1

36. Закон противоречия: X ^ !X = 0

37. X v 0 = X

38. X v 1 = X

39. X ^ 0 = 0

40. !1 = 0

41. X ^ 1 = X

42. !0 = 1

Следствия из этих соотношений Формулы:

Следует, что порядок действий не имеет значения и поэтому эти формулы записываются без скобок.

Если в формуле 2 хотя бы один член равен нулю, то вся конъюнкция будет равна 0. Если в дизъюнкции формулы 3 хотя бы один из членов равен 1, то вся дизъюнкция будет равна 1

Из соотношений 16 и 20 следует, что в любой дизъюнкции могут быть опущены члены равные нулю, а в любой конъюнкции могут быть опущены любые члены равные 1.

Обозначения:

X с волной – либо X, либо !X

Определение :

1. Всякую конъюнкцию вида X1(с волной), X1(с волной) , Xk(с волной) в которой каждая буква встречается не более 1 раза, будем называть элементарной конъюнкцией.

!X1 ^ X1 не элементарно.

2. К элементарным конъюнкциям причисляются так же сами переменные xi, xi(wave), 1

3. Число переменных входящих в элементарную конъюнкцию называется ее длинной.

4. Пусть формула А(U, V, W) содержит n переменных (аргументов), множество переменных входящих в формулу вида А есть M

из элементов М можно составить различные элементарные конъюнкции длиной от нуля до n. Элементарная конъюнкция максимальной длины из выбранных конъюнкций называется конституантой единицы (n-членов). Каждый элемент множества M входит в конституанту ровно 1 раз согласно определению конституанты. Например M={u,v,x,y} где u ^ v ^ !x ^y поэтому для множества из n элементов можно построить 2^n возможных конституант 1

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

5. Число дизъюнктивных нормальных членов входящих в состав ДНФ называется ее длиной. При этом ДНФ может состоять всего из одного члена. И даже предполагают, что ДНФ может иметь нулевую длину и не содержать ни одного члена. ДНФ = 0;

Пусть для

Xi ДНФ единичной длины.

1 – ДНФ

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

Теорема 1: С помощью основных соотношений (1-21) любая формула булевой алгебры может быть приведена к СДНФ.

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

Три этапа:

3. Покажем что эту форму с помощью правил Де Моргана и правила отризация отрицания можно перевести формулу А в формулу B. A(x1,x2,xn) -> B(x1,x2…xn,!x1, !x2…!xn) это значит, что в формуле B могут быть члены !Xi, но не !(Xi ^ xj) то есть к самим переменным. Пример: !((X v Y ^ !Z) v !Y ^ Z) = !(X v Y ^ !Z) ^ !(!y ^ z) = !X ^ !(Y ^ !Z) ^ !(Y ^ !Z) = !x ^ (!Y v !!!Z) ^(!!Y V !Z) = !X ^ (!Y v Z)V(Y v !Z)

4. На втором этапе формулу вида B всегда можно представить в виде ДНФ. Формула вида B строится из членов при помощи операций конъюнкции и дизъюнкции (так как эти операции коммутативные и ассоциативные, а так же обладают двумя свойствами дистрибутивности) (X v Y )^Z = X^Z v Y^Z ; (x v Y) v Z = (X v Z) ^ (Y v Z) можно произвести раскрытие скобок по аналогии с обычной алгеброй. Таким образом, можно утверждать, что в формуле вида B можно раскрыть скобки по правилам обычной элементарной алгебры. После преобразований некоторые конъюнкции могут быть равными 1, а дизъюнкции равными нулю, которые могут быть опущены. После раскрытия скобок получим дизъюнкцию некоторых конъюнкций. Это еще не ДНФ. Что бы получить ДНФ нужно все конъюнкции входящие в нее сделать элементарными. ~X ^ X2 ^ … ^ ~Xk еще не элементарно. От повторяющихся членов вида xi можно избавиться при помощи закона идемпотентности для конъюнкции. Если конъюнкция не элементарна, то есть в нее входят члены xi и ~xi, то от них надо избавляться, так как xi и ~xi = 0 и тогда вся форма ДНФ = 0. Таким образом используя закон идемпотентности и противоречия можно все неэлементарные конъюнкции сделать элементарными. При этом полученная дизъюнкция может быть не ДНФ, так как в ней могут быть одинаковые дизъюнкции, которые можно вывести при помощи закона идемпотентности. Оставшиеся при этом члены составят ДНФ. Закончим этот пример. // окончание примера.

!X ^ (Y v Z) ^ (Y v !Z) = (!X ^ !Y v !X ^ Z) ^ (Y v !Z)= !X^ !Y ^ Y V !X ^ Z ^ Y ^

Любую ДНФ можно привести к равной ей совершенной ДНФ. Воспользуемся первым соотношением и законом исключенного третьего.

Xi ^ 1= xi & x v !x = 1

Пусть имеется в нашей ДНФ дизъюнктивный член не являющийся конституантой единицы.

Xi ^ Xj ^ 1 = Xi ^ Xj ^ (Xk v !Xk) = Xi^ Xj ^ Xk v Xi ^ Xj ^ Xk

Xi ^ !Xi = 0;

Таким образом, любую ДНФ можно преобразовать в совершенную и равную ей ДНФ. Например:

Xv!Y ^ Z = X^(Yv!Y)^(Zv!Z)v!YvZ^(Xv!X)= X^ Y ^ Zv X^Y^!ZvX^!Y^ZvX^!Y^!Z СДНФ

Дана ДНФ но не СДНФ.

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

Все выполненные шаги обратимы, то есть от полученной СДНФ можно получить обратный переход к исходной формуле.

Достаточно неравенства А(x1,x2…xn) = B(x1,x2..)?

Теорема 2:

Для любой конечноместной булевой функции f(x1,x2..xn) может быть построена одна и с точностью до перестановки дизъюнктивных и конъюнктивных членов только одна равная ей совершенная ДНФ с тем же самым множеством переменных.

Пусть Alpha1 Alpha2 Alphan – некоторый набор значений этих переменных. Общей вид конституанты единицы будет x1(wave)^x2(wave) … ^ xn(wave)

Каждому набору переменных можно поставить в соответствие одну и только одну конституанту единицы вида x1(wave)^x2(wave) … ^ xn(wave), которая обращается на этом наборе в единицу

Из 2^n конституант единиц существует одна и только одна конституэнта единицы равная единице, а остальные равны нулю.

Если Alpha1 = 1, то в x1 она должна входить непосредственно.

Если Alpha2 = 0 то x1 ^ !X2

Правило: Такая конституанта единицы однозначно определяет условие xi(wave)=xi если Alphai = 1

И xi (wave) = 1xi, если Alphai = 0

Только при таком условии (правиле) мы получим нужную нам конституанту единицы. Пример:

{11 x2, x3 x4 x5} построить 2^5 конституэнт. Зададим этому набору какие-то значения.

{0 1 1 0 1 } тогда получим согласно предыдущему уравнению !x1 ^ x2 ^ x3 ^ !x4 ^ x5 получили требуемую конституэнту, которая обращается в единицу.

Конституэнту единиц равную единице на наборе значений аргументов {Alpha1…Alphan} будем называть соответствующей данному набору.

Существует 2^n наборов, из которых выберем все те наборы, где функция равна 1 и составим дизъюнкцию из всех коституэнт единицы соответствующих этим наборам. В результате получим совершенную ДНФ которую обозначим g(x1, x2… xn).

Полученная СДНФ обладает требуемыми свойствами, для чего возьмем на любом наборе ДНФ равную единице. На всех наборах значений аргументов , на которых функция f обращается в единицу СДНФ g(x1,x2…xn) так же обращается в единицу. С другой стороны на всех наборах значений аргументов, на которых функция равна нулю СДНФ g так же будет равна нулю в силу своего способа построения, то есть g(x1,x2…xn) = f(x1,x2,xn)

Здесь каждой функции f соответствует единственное значение совершенной ДНФ в g. (с точностью до перестановки дизъюнктивных и конъюнктивных членов)

Из теоремы 1 и 2 следует теорема 3:

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

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

Пусть имеем 2 формы: а и б! Эквивалентные меж собой. То есть А=Б => g

Переходим по теореме 2.

Доказанные теоремы позволяют проверять тождественные соотношения для чего обе части нужно привести к СДНФ. Затем нужно проверить совпадают ли они.

Наряду с СДНФ для проверки тождественности соотношений булевой алгебры используются конъюнктивные нормальные формы

Определение: Всякую дизъюнкцию вида x1(wave) ^ x2(wave) ^ Xk(wave),в которой каждая переменная встречается не более 1 раза, будем называть элементарной дизъюнкцией. В частности к элементарным дизъюнкциям относят константу 0. Длина элементарной дизъюнкции есть число переменных входящих в эту дизъюнкцию. Пусть задано некоторое множество элементов M = {x1,x2,xn}. Элементарную дизюнкцию, включающую в себя элементы этого множества, будем называть конституэнтой нуля.

Для каждого такого множества переменных существует 2 ^ n конституэнт нуля. Для любого набора значений аргументов Alpha1 Alpha2 Alphan существует единственная конституэнта нуля.

Правило.

Если Alphai = 0, то x1 = xi

Если Alphai = 1, то ^Xi = !Xi

При соблюдении этого правила не выполнится основное условие.

Конъюнкция любого числа элементарных дизъюнкций не содержащая 2х одинаковых дизъюнкций называется КНФ. КНФ состоящая из конституэнт нуля называется совершенной КНФ или СКНФ. Если КНФ равно нулю, то длина ее равна 1.