Булева алгебра и теория множеств

Примеры булевых алгебр:

(; &,Ú,Ø) – булева алгебра логических функций;

( (m); &,Ú,Ø) – булева алгебра логических функций m переменных, (m)Ì ;

(b(U); Ç,È,Ø) – булева алгебра множеств над U;

(b(U ¢); Ç,È,Ø) – булева алгебра множеств над U ¢, U ¢Ì U;

(; &,Ú,Ø) – булева алгебра двоичных векторов длины n с покомпонентными (поразрядными) логическими операциями над двоичными векторами, определенными следующим образом.

Для любых векторов и :

а) , где , если и в любом другом случае;

б) , где , если и в любом другом случае;

в) , где , если и в противном случае.

Теорема 1.6.1. Если | U |= n, то булева алгебра множеств (b(U); Ç,È,Ø) изоморфна булевой алгебре двоичных векторов (; &,Ú,Ø).

Теорема 1.6.2. Если | U |=2 ^m, то булева алгебра множеств (b(U); Ç,È,Ø) изоморфна булевой алгебре функций ( (m); &,Ú,Ø).

Взаимный изоморфизм данных булевых алгебр выполняется, если

| U |= n =2 ^m.

В этом случае |b(U)|=| |=| (m)| и между множествами b(U), и (m) устанавливается взаимно однозначное соответствие.

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

Пример 1. Показать на примере конкретных множеств A, B Í U изоморфизм между булевыми алгебрами множеств (b(U); Ç,È,Ø), где | U |=4, и булевой алгеброй двоичных векторов длины 4 (; &,Ú,Ø).

Пусть U ={ a, b, c, d }. Тогда

b(U)={Æ, { a }, { b }, { c }, { d }, { a, b },...,{ a, b, c },...,{ a, b, c, d }};

={(0000), (0001), (0010),..., (1111)};

|b(U)|=| |=2⁴=32

Если булевы алгебры (b(U); Ç,È,Ø) и (; &,Ú,Ø) изоморфны, то:

1) существует взаимно однозначное соответствие – отображение Г:b(U)® , т.е. ) = A ].

2) для отображение Г:b(U)® выполняется условие гомоморфизма: если Г(A)= , а Г(B)=b, то:

а) Г(A Ç B)= , б) Г(A È B)= , в) Г()= .

Проиллюстрируем выполнение всех условий изоморфизма заданных алгебр на примере двух конкретных множеств, например, A ={ b, c } и B ={ a, c, d }:

1) взаимно однозначное соответствие:

Г(A)=(0110)= , Г(B)=(1011)=b и наоборот, Г^-1()=Г^-1((0110))= { b, c }; Г^-1(b)=Г^-1((1011))={ a, c, d };

2) условие гомоморфизма:

а) Г(A Ç B)=Г({ b, c }Ç{ a, c, d })=Г({ c })=(0010)=(0110)&(1011)= ;

б) Г(A È B)=Г({ b, c }È{ a, c, d })=Г({ a, b, c, d })=(1111)=(0110)Ú(1011)

= ;

в) Г()=Г(U \ A)=Г({ a, b, c, d }\{ b, c })=Г({ a, b })=(1001)= .

Таким образом, алгебры (b(U); Ç,È,Ø) и (; &,Ú,Ø) гомоморфны и отображение множеств Г:b(U)® взаимнооднозначно, следовательно, данные алгебры также изоморфны при данном отображении.

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

1) над множествами A ={ a, d, e }, B ={ b, c, d };

2) над двоичными векторами t=(100110) и s=(010011).

Булевы алгебры множеств (b(U); Ç,È,Ø) и двоичных векторов (; &,Ú,Ø) изоморфны при выполнении условия: | U |= n.

1) Пусть | |= n =5 и ={ a, b, c, d, e }, так что A, B Í U. Булева алгебра множеств (b(); Ç,È,Ø), где ={ a, b, c, d, e }, изоморфна булевой алгебре двоичных векторов длины 5 (; &,Ú,Ø). Выполним операции над множествами {Ç,È,Ø}, используя изоморфизм этих алгебр Г:b()® :

Г(A)=Г({ a, d, e })=(10011)= ,

Г(B)=Г({ b, c, d })=(01110)= b.

Тогда:

а) Г(A Ç B)= =(10011)&(01110)=(00010).

Но вектору (00010) соответствует множество { d }: Г^-1((00010))={ d }. Таким образом, A Ç B ={ d }.

б) Г(A È B)= =(10011)Ú(01110)=(11111), но Г^-1((11111))= { a, b, c, d, e }. Таким образом, A È B ={ a, b, c, d, e }.

в) Г()= = =(01100), но Г^-1((01100))={ b, c }, откуда ={ b, c }.

Изоморфизм булевых алгебр множеств и двоичных векторов позволяет заменить теоретико-множественные операции над множествами поразрядными логическими операциями над двоичными векторами.

2) Длина n заданных двоичных векторов t=(100110) и s=(010011) равна 6. Поэтому пусть | |= n =6 и ={ f, g, h, k, m, q }.

Выполним операции (&,Ú,Ø) над векторами, используя изоморфизм алгебр Г: ®b():

Г(t)=Г((100110))={ f, k, m }= C;

Г(s)=Г((010011))={ g, m, q }= D.

Тогда:

а) Г(t&s)= C Ç D ={ f, k, m }Ç{ g, m, q }={ m }.

Но множеству { m } соответствует вектор (000010): Г^-1({ m })= (000010). Таким образом, t&s=(100110)&(010011)=(000010).

б)Г(tÚs)= C È D ={ f, k, m }È{ g, m, q }={ f, g, k, m, q }, но Г^-1({ f, g, k, m, q })= (110111). Таким образом, tÚs=(100110)Ú(010011)=(110111).

в) Г(t)= = \ C ={ f, g, h, k, m, q }\{ f, k, m }={ g, h, q }, но Г^-1({ g, h, q })= (011001). Следовательно, t=(011001).

Пример 3. Проиллюстрировать изоморфизм между булевыми алгебрами множеств (b(U); Ç,È,Ø) и логических функций ( (m); &,Ú,Ø) для | U |=2 ^m.

Пусть | U |=2 ^m при m =2; U ={ a, b, c, d }. Изоморфизм данных алгебр означает:

1. Между логическими функциями двух переменных из (2) и множествами из b(U) существует взаимно однозначное соответствие Г: (2)®b(U), т.е. любой функции f Î (2) соответствует одно и только одно множество Îb(U), так что Г(f)= и Г^-1()= f. При этом функция f называется характеристической функцией множества .

2. Для отображения Г: (2)®b(U) выполняется условие гомоморфизма, которое для данных алгебр (b(U); Ç,È,Ø) и ( (m); &,Ú,Ø) сводится к трем равенствам: если Г(f)= и Г(g)= , то:

а) Г(f & g)= Ç ; б) Г(f Ú g)= È ; в) Г()= .

В силу изоморфизма этих алгебр справедливо и обратное:

а) Г^-1( Ç )= f & g; б) Г^-1( È )= f Ú g; в) Г^-1()=

Однако из-за взаимной однозначности Г достаточно показать справедливость лишь первых трех равенств.

Пусть ={ a, c } и ={ b, c }; , Îb(U).

Таблица 1.6.1
Элемент множества U	x ₁	x ₂	f	g	f & g	f Ú g
a	0	0	1	0	0	1	0
b	0	1	0	1	0	1	1
c	1	0	1	1	1	1	0
d	1	1	0	0	0	0	1

Функции f и g, соответствующие множествам и при взаимно однозначном отображении Г (характеристические функции для и ), определены таблицами истинности 1.6.1. В крайнем левом столбце таблицы 1.6.1 перечислены элементы множества U ={ a, b, c, d }, являющиеся, по существу, обозначениями всех возможных наборов двух переменных {(00),(01),(11)}. Множества и представляют собой единичные множества функций f и g соответственно, т.е. множества наборов, на которых эти функции равны единице. Тогда (см. табл. 1.6.1):

1) Г(f)= ={ a, c }, Г(g)= ={ b, c } и, наоборот, Г^-1()= f и Г^-1()= g;

2) Г(f & g)= ={ c }={ a, c }Ç{ b, c }= Ç ,

Г(f Ú g)= ={ a, b, c }={ a, c }È{ b, c }= È ,

Г()= ={ b, d }= U \{ a, c }= U \ = .

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

1) и определены таблицами истинности в табл. 1.6.2

2) и определены своими СДНФ:

Изоморфизм булевых алгебр логических функций ( (m); &,Ú,Ø) и двоичных векторов (; &,Ú,Ø) позволяет переходить от операций над функциями к операциям над двоичными векторами и обратно при выполнении условия: 2 ^m = n. Поэтому функциям трех переменных (m =3) соответствуют вектора длины n =8. Установим взаимно однозначное соответствие Г: (3)® и выполним необходимые операции, используя изоморфизм булевых алгебр.

1)Зафиксировав последовательность рассмотрения всех возможных наборов значений переменных, например, как это указано в табл. 1.6.2, установим взаимно однозначное соответствие Г: (3)® следующим образом:

для функции f, представленной таблицей истинности, в соответствующем ей векторе i -я компонента , если для f i -й набор значений переменных является единичным, т.е. функция на этом наборе принимает значение f =1, и – в противном случае.

Таблица 1.6.2
x ₁	x ₂	x ₃	f ₁	f ₂	f ₁& f ₂	f ₁Ú f ₂	f ₁
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	1	0	1	1
0	1	1	1	1	1	1	0
1	0	0	1	0	0	1	0
1	0	1	0	1	0	1	1
1	1	0	1	1	1	1	0
1	1	1	1	1	1	1	0

Тогда:

Г()=(00011011)= , Г()=(00110111)=b.

Выполним операции (&,Ú,Ø) над функциями и , используя изоморфизм булевых алгебр Г: (3)® :

а) Г()= =(00011011)&(00110111)=(00010011).

Но вектору (00010011) соответствует функция :

Г^-1((00010011))= ,

таблица истинности которой представлена в табл. 1.6.2.

б) Г()= =(00011011)Ú(00110111)=(00111111).

Но Г^-1((00111111))= (см. табл. 1.6.2).

в) Г()= = =(11100100).

Г^-1((11100100))= (см. табл. 1.6.2).

2) Определим последовательность всех возможных элементарных конъюнкций всех переменных () и установим взаимно однозначное соответствие Г: (3)® следующим образом:

для функции f, представленной СДНФ, в соответствующей ей векторе i -я компонента , если в СДНФ f имеется i -я конъюнкция, и – в противном случае.

Тогда:

Г()=Г()=(00011011)= ,

Г()=()=(00110111)= b.

Выполним операции (&,Ú,Ø) над функциями и , используя изоморфизм булевых алгебр Г: (3)® :

а) Г()= =(00011011)&(00110111)=(00010011).

Но вектору (00010011) соответствует функция, СДНФ которой

Г^-1((00010011)) .

Таким образом, .

б) Г()= =(00011011)Ú(00110111)=(00111111).

Но Г^-1((00111111)) .

Таким образом, .

в) Г()= = =(11100100).

Но Г^-1((11100100)) .

Таким образом, .

Пример 5. Выполнить операции объединения и пересечения над множествами A, B Í U из примера 2, используя изоморфизм булевых алгебр множеств и логических функций.

Изоморфизм булевых алгебр позволяет переходить от операций над множествами к операциями над функциями и обратно. Изоморфизм булевых алгебр требует выполнения условия: | U |=2 ^m. Поэтому для выполнения операции над A ={ a, d, e }, B ={ b, c, d } рассмотрим изоморфные алгебры: (b(U); Ç,È,Ø) и ( (3); &,Ú,Ø).

Пусть U ={ a, b, c, d, e, h, k, l }; взаимно однозначное соответствие Г:b(U)® (3) установим так, как показано в табл. 1.6.3, где в крайнем правом столбце перечислены элементы множества U. Функции f и g, соответствующие множествам A, B, а также их конъюнкция, дизъюнкция, отрицание даны таблицами истинности (табл. 1.6.3).

Тогда:

Г(A & B)= f & g, но Г^-1(f & g)= ={ d }, т.е. A & B ={ d };

Г(A Ú B)= f Ú g, но Г^-1(f Ú g)= ={ a, b, c, d, e }, т.е. A Ú B ={ a, b, c, d, e }.

Таблица 1.6.3
x	y	z	f	g	f & g	f Ú g	Элемент множества U
0	0	0	1	0	0	1	a
0	0	1	0	1	0	1	b
0	1	0	0	1	0	1	c
0	1	1	1	1	1	1	d
1	0	0	1	0	0	1	e
1	0	1	0	0	0	0	h
1	1	0	0	0	0	0	k
1	1	1	0	0	0	0	l

Вопросы для самопроверки и упражнения.

1. Показать изоморфизм булевых алгебр (b(U); Ç,È,Ø) и (; &,Ú,Ø) на примере A, B Í U, если:

а) A ={2,4,6}, B ={1,2,3,6}, U ={1,2,3,4,5,6};

б) A ={ a, c, d, f }, B ={ b, c, e, f }, U ={ a, b, c, d, e, f };

в) A ={1,3,4,6}, B ={2,3,5,6}, U ={1,2,3,4,5,6};

г) A ={ c, d, e }, B ={ a, b, c, f }, U ={ a, b, c, d, e, f };

2. Показать изоморфизм булевых алгебр (b(U); Ç,È,Ø) и ( (m); &,Ú,Ø) на примере A, B Í U, если:

а) A ={2,4,6}, B ={1,2,3,6}, U ={1,2,3,4,5,6,7,8};

б) A ={1,3,4,6,8}, B ={2,3,5,6,7}, U ={1,2,3,4,5,6,7,8};

в) A ={ a, c, d, h }, B ={ b, c, d, e, h }, U ={ a, b, c, d, e, f, g, h };

г) A ={ c, d, e, g }, B ={ a, c, d, g, h }, U ={ a, b, c, d, e, f, g, h };

3. Задать множества A, B Í U. Выполнить операции {Ç,È,Ø} над множествами A, B, используя изоморфизм булевых алгебр множеств (b(U); Ç,È,Ø) и:

а) двоичных векторов (; &,Ú,Ø);

б) логических функций ( (m); &,Ú,Ø).

ЛОГИКА ПРЕДИКАТОВ.

Основные понятия.

Предикат P (, ,..., ) является функцией типа P: ® B, где множества называются предметными областями предиката; , ,..., – предметными переменными, Î , Î ,..., Î ; B ={И,Л} или {1,0}. Если предикатные переменные принимают значения на одном множестве, то P: ® B.

Соответствия между предикатами, отношениями и функциями:

1. Для любых M и n существует взаимно однозначное соответствие между n -местными отношениями R Í и n -местными предикатами P (, ,..., ), P: ® B:

- каждому n -местному отношению R соответствует предикат P (, ,..., ) такой, что P (, ,..., )=1, если и только если (, ,..., )Î R;

- всякий предикат P (, ,..., ) определяет отношение R такое, что (, ,..., )Î R, если и только если P (, ,..., )=1.

При этом R задает область истинности предиката P.

2. Всякой функции f (, ,..., ), f: ® M, соответствует предикат P (, ,..., , ), P: ® B, такой, что P (, ,..., , )=1, если и только если f (, ,..., )= .

Выражение P (, ,..., ) будем понимать как высказывание “ P (, ,..., )=1” или “ P (, ,..., ) истинно”, а выражение P (, ,..., ) – как переменное высказывание, истинность которого определяется подстановкой элементов множества M вместо переменных , ,..., . При этом будем также называть P (, ,..., ) логической (двоичной) переменной, в отличие от , ,..., – предметных (нелогичных) переменных.

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

Для обозначения двухместных предикатов помимо префиксной записи P (, ) используется нередко инфиксная запись P .

Пример 1. Каким отношениям и функциям соответствуют следующие предикаты, определенные на множестве натуральных чисел:

1. Предикат тождества E: ® B: E (, )=1Û = .

2. Предикат порядка Q: ® B: Q (, )=1Û £ .

3. Предикат делимости D: ® B: D (, )=1Û делится на .

4. Предикат суммы S: ® B: S (, , )=1Û + = .

5. Предикат произведения П: ® B: П (, , )=1Û × = .

1. Двухместному предикату тождества E – “ = ” взаимно однозначно соответствуют:

а) двухместное отношение – “быть равным”, Í : (, )Î Û E (, )=1;

б) одноместная функция (операция) тождества ()= , а именно: (x)= x, f: N ® N.

2. Двухместному предикату порядка Q – “ £ ” взаимно однозначно соответствует двухместное отношение – “быть не больше”, Í : (, )Î Û Q (, )=1;

3. Двухместному предикату делимости D – “ делится на ” взаимно однозначно соответствует двухместное отношение – “делиться”, Í : (, )Î Û D (, )=1;

4. Трехместному предикату суммы S – “ + = ” взаимно однозначно соответствуют:

а) трехместное отношение Í : (, , )Î Û S (, , )=1;

б) двухместная функция (операция арифметики) – сложение (, )= , а именно: + = .

5. Трехместному предикату произведения П – “ × = ” взаимно однозначно соответствуют:

а) трехместное отношение Í : (, , )Î Û П (, , )=1;

б) двухместная функция (операция арифметики) – умножение (, )= , а именно: × = .

Взаимная однозначность соответствия между S и (П и ) обусловлена выполнением для предиката S (П) условия: для каждой системы элементов , Î N существует единственный элемент Î N такой, что S (, , )=1 (соответственно, для П (, , )=1).

Кванторы.

Пусть P (x) – предикат, определенный на M, т.е. x Î M.

Высказывание “для всех x из M P (x) истинно” обозначается " x P (x); знак " x называется квантором общности. Высказывание “существует такой x из M, что P (x) истинно” обозначается $ x; знак $ x называется квантором существования.

Переход от P (x) к " x P (x) или $ x P (x) называется связыванием переменной x, или навешиванием квантора на переменную x (или на предикат P), или квантификацией переменной P.

Переменная, на которую навешен квантор, называется связанной, несвязанная квантором переменная называется свободной.

Выражение, на которое навешивается квантор " x или $ x, называется областью действия квантора; все вхождения переменной x в это выражение являются связанными.

Пример 1. Пусть N (x) – предикат “ x – натуральное число”. Рассмотреть варианты навешивания кванторов. Проинтерпретировать полученные высказывания и определить их истинность.

" x N (x) – высказывание “все числа – натуральные” истинно на любом множестве натуральных чисел и ложно, если M содержит хотя бы одно ненатуральное число, например, целое отрицательное;

$ x N (x) – высказывание “существует натуральное x ” истинно на любом множестве M, содержащим хотя бы одно натуральное число, и ложно – в противном случае.

Пример 2. Какой смысл имеют предикатные формулы:

а) " y " z $ x П (x, y, z);

б) " x " y " z " u (П (x, y, z)& П (x, y, u)® E (z, u)),

где П, Е – предикаты произведения и равенства, определенные на N. Истинны ли эти формулы? Привести примеры наборов переменных, иллюстрирующие заключение относительно истинности или ложности формул.

а) Формула " y " z $ x П (x, y, z) – высказывание “для всех натуральных чисел y и z существует натуральное число x такое, что x × y = z ” является ложным. Например, П (x,5,2) не выполняется ни при каком натуральном x, т.е. не для любых y, z существует x такое, что x × y = z, следовательно, высказывание, заданное формулой " y " z $ x П (x, y, z), – ложно.

б) " x " y " z " u (П (x, y, z) & П (x, y, u) ® E (z, u)) – высказывание, отражающее однозначность операции умножения “для любых натуральных чисел x, y, z, u из того, что x × y = z и x × y = u, следует, что z = u ” истинно. Для подтверждения этого заключения рассмотрим варианты наборов чисел, значения предикатов и формулы в целом на этих наборах:

1) (2,3,6,6): П (2,3,6)& П (2,3,6)® Е (6,6)=1&1®1=1®1=1;

2) (2,3,5,5): П (2,3,5)& П (2,3,5)® Е (5,5)=0&0®1=0®1=1;

3) (2,3,3,6): П (2,3,3)& П (2,3,6)® Е (3,6)=0&1®0=0®0=1;

4) (2,3,3,5): П (2,3,3)& П (2,3,5)® Е (3,5)=0&0®0=0®0=1;

5) (2,3,6,5): П (2,3,6)& П (2,3,5)® Е (6,5)=1&0®0=0®0=1;

Очевидно, нет таких натуральных чисел x, y, произведение которых было бы не единственно, т.е. не существует набора чисел (a, b, c, d), на котором были бы истинны предикаты П (a, b, c) и П (a, b, d) и одновременно ложен предикат E (c, d), следовательно, высказывание " x " y " z " u (П (x, y, z)& П (x, y, u)® E (z, u)) истинно.

Вопросы для самопроверки и упражнения.

1. Рассмотреть варианты навешивания кванторов на предикат P (x), определенный на множестве натуральных чисел с нулем . Дать словесную формулировку исходных и полученных высказываний и определить их истинность, если: