Примеры булевых алгебр:
(; &,Ú,Ø) – булева алгебра логических функций;
( (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)|=| |=24=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 1 | x 2 | 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 1 | x 2 | x 3 | f 1 | f 2 | f 1& f 2 | f 1Ú f 2 | f 1 |
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), определенный на множестве натуральных чисел с нулем . Дать словесную формулировку исходных и полученных высказываний и определить их истинность, если:
а) P (x)=$ y S (y, y, x); в) P (x)=$ y П (x, y, y);
б) P (x)=$ y П (y, y, x); г) P (x)=$ y S (x, y, y).
Примечание: S и П – предикаты суммы и произведения соответственно.
2. Пусть Q (x, y) – предикат порядка “ x &po