1 Множества. Логика Буля - лекции
.pdfЭто определение можно записать с помощью логических формул
так:
(x1 \ x2 ) (x1 |
x2 ) 1, (x1 \ x2 ) (x1 x2 ) 0 . |
|||
Таблица истинности импликации имеет вид (табл. 7): |
||||
|
|
|
Табл. 7 |
|
|
|
|
|
|
|
x1 |
x2 |
y x1 x2 |
|
|
0 |
0 |
1 |
|
|
|
|
|
|
|
0 |
1 |
1 |
|
|
|
|
|
|
|
1 |
0 |
0 |
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
Из неѐ видно, что
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y x1 |
x2 |
x1 \ x2 |
|
x1 |
|
|
x2 |
(x1 |
|
x2 ) (x1 |
x2 ) (x1 |
x2 ) , |
|||||||||
|
Диаграмма Эйлера–Венна импликации приведена на рис. 8. |
||||||||||||||||||||||
|
Суще- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ствуют |
|
ещѐ две вза- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
имно до- |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
V |
|
|
|
||||
полняющие |
|
|
|
5 |
|
|
|
|
|
|
1 |
|
2 |
|
|
|
|
|
операции |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
над |
множе- |
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
ствами. |
||||
|
|
|
|
|
|
|
6 |
А |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
Сим- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
метри- |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
ческой |
раз- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ностью |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В |
9 |
|
|
|
|||||
множеств |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A и B |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
11 |
|
|
|
3 |
|
|
|
|
|
|||||||||
называется |
|
|
|
|
|
|
|
|
|
|
|
|
|
объеди- |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
||||||||
нение |
разно- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
стей |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
A \ B |
и |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B \ A: |
|
|
|
|
|
|
Рис. 8. Импликация А в В |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||
A |
B |
{x | x |
(( A \ B) |
(B \ A))} . |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
При A |
{1, 2, 4, 6} и B |
{2, 3, 4, 8, 9} имеем: |
|
|
|
|
|
|||||||||||||||
|
|
|
A |
B |
{1, 6} |
{3, 8, 9} |
|
C1 C2 |
{1, 3, 6, 8, 9} . |
|
|
Эквивалентность определяется теми элементами множеств A и B , которые для них являются общими. Элементы, не входящие ни в A , ни в B , также считаются эквивалентными:
|
|
|
|
|
|
|
A |
B |
{x | x (( A B) ( A B))}. |
||||
То есть A B C0 |
C3 |
{2, 4, 5, 7, 10, 11}. |
|
|
|
|
Из условия дополнительности операций вытекают следующие соотношения:
15
|
(x1 |
x2 ) (x1 |
x2 ) 1, |
(x1 x2 ) (x1 |
x2 ) 0, |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y x1 |
x2 x1 |
x2 (x1 |
x2 ) (x1 |
|
x2 ) (x1 x2 ) (x1 x2 ) (x1 x2 ) . |
На рисунках 9, 10 выделены штриховкой симметрическая разность и эквивалентность соответственно.
|
|
|
V |
|
|
|
V |
5 |
1 |
|
|
5 |
1 |
|
|
|
2 |
|
|
2 |
|
||
|
|
8 |
|
|
8 |
||
6 |
А |
|
6 |
А |
|
||
4 |
|
4 |
|
||||
|
|
|
|
|
|
||
10 |
|
|
|
10 |
|
|
|
|
|
3 В |
9 |
|
|
3 В |
9 |
11 |
|
|
11 |
|
|
||
|
|
7 |
|
|
7 |
||
|
|
|
|
|
|
Рис. 9. Симметрическая разность А и В |
Рис. 10. Эквивалентность А и В |
Таблицы 8, 9 являются таблицами истинности этих операций.
|
|
Табл. 8 |
|
|
|
x1 |
x2 |
y x1 x2 |
|
|
|
0 |
0 |
0 |
|
|
|
0 |
1 |
1 |
|
|
|
1 |
0 |
1 |
|
|
|
1 |
1 |
0 |
|
|
|
Табл. 9
x1 |
x2 |
y x1 |
x2 |
|
|
|
|
0 |
0 |
1 |
|
|
|
|
|
0 |
1 |
0 |
|
|
|
|
|
1 |
0 |
0 |
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
Замечание. Симметрическая разность имеет несколько названий:
строгая дизъюнкция, исключающая альтернатива, сумма по модулю два,
антиэквивалентность. Эту операцию можно передать словами «либо A , либо B », то есть это логическая связка «или», но без включѐнной в неѐ связки «и».
16
ЛЕКЦИЯ 3. ЭЛЕМЕНТАРНЫЕ БУЛЕВЫ ФУНКЦИИ И ИХ СВОЙСТВА. МЕТОДЫ ДОКАЗАТЕЛЬСТВА В ЛОГИКЕ БУЛЯ
Элементарные булевы функции. Логическая переменная x , прини-
мающая одно из двух возможных значений 0 или 1, называется булевой.
Функция f (x1 , x2 , ..., xn ) n булевых переменных называется булевой. Еѐ об-
ластями определения и значений является множество {0, 1}.
Любую булеву функцию можно задать таблицей (истинности), в которой перечисляются все наборы возможных значений переменных, и для каждого такого набора указывается соответствующее значение функции.
Две булевы функции, принимающие одинаковые значения при одних и тех же наборах значений переменных, называются равными.
Набор значений переменных, на котором булева функция принимает значение 1, называется единичным.
Построим таблицу истинности булевой функции одной переменной
(табл. 1):
|
|
|
|
|
|
|
|
Табл. 1 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
f1 (x) |
|
f2 (x) |
|
f3 (x) |
f4 (x) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
0 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
1 |
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
Как видно из таблицы 1, булевых функций одной переменной – че- |
|||||||||||
тыре. |
|
|
|
|
|
|
|
|
|
|
|
Функции |
f1 (x) и |
f4 (x) называются константами – соответственно |
|||||||||
|
|
|
|
|
0 и 1. |
|
|
|
|
|
|
Функция |
f2 (x) |
совпадает с переменной |
x и называется тожде- |
||||||||
ственной: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f2 (x) |
x . |
|
|
|
||
Функция |
f3 (x) |
принимает значения, противоположные значениям |
|||||||||
|
|
|
|
||||||||
аргумента x , и называется отрицанием x , обозначается x : |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f3 (x) x . |
|
|
|
|||
Построим таблицу истинности булевых функций двух переменных |
|||||||||||
fi (x1; x2 ) fi , i |
1, …, 16 (табл. 2): |
|
|
|
|
|
|
|
17
Табл. 2
x1 |
x2 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
f16 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Всего булевых функций двух переменных – шестнадцать, трѐх переменных – тридцать две и так далее. Понятно, что число булевых функций
n переменных равно 22n .
Как видно из таблицы 2, к функциям двух переменных относятся и
такие, которые зависят от одной переменной. |
|
|
|
|
|
||||||||
Функции f1 |
|
0 и f16 |
1 есть константы 0 и 1. |
|
|
|
|
|
|||||
Функции |
f 4 , |
f6 , f11 , |
f13 |
существенно зависят только от одной пере- |
|||||||||
|
|
|
|
|
|
|
|
|
|||||
менной: |
f4 x1 , |
f6 |
x2 |
– тождественные функции, f11 |
|
x2 , f13 x1 – |
|||||||
отрицания. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Остальные функции имеют следующие обозначения: |
|
|
|
|
|
||||||||
f2 |
x1 |
x2 |
– конъюнкция, |
|
|
|
|
|
|
||||
f8 |
x1 |
x2 – дизъюнкция, |
|
|
|
|
|
|
|||||
f10 |
x1 |
x2 – эквивалентность, |
|
|
|
|
|
|
|||||
f7 |
x1 |
x2 |
– сумма по модулю два или сумма Жегалкина, |
||||||||||
f12 |
x2 |
x1 – конверсия, |
|
|
|
|
|
|
|||||
f14 |
x1 |
x2 –импликация, |
|
|
|
|
|
|
|||||
f15 |
x1 | x2 – штрих Шеффера, |
|
|
|
|
|
|
||||||
f9 |
x1 |
x2 |
– стрелка Пирса, |
|
|
|
|
|
|
||||
функции |
f3 |
и |
f5 логически несовместимы с импликацией и конвер- |
||||||||||
сией, называются функциями запрета. |
|
|
|
|
|
|
|||||||
Булевы функции одной и двух переменных называются элементар- |
|||||||||||||
ными. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Свойства операций над множествами, свойства элементарных бу- |
|||||||||||||
левых функций |
|
|
|
|
|
|
|
|
|
|
|
|
|
1. Идемпотентность объединения, пересечения: |
|
|
|
|
|
||||||||
|
|
|
|
A |
|
A |
A , |
A A A , |
|
|
|
|
|
в частности |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
Ø |
A , |
A |
Ø=Ø, A U U , A U |
A . |
|||||||
Идемпотентность дизъюнкции, конъюнкции: |
|
|
|
|
|
||||||||
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
x |
x, |
x |
x |
x, |
в частности |
|
|
|
|
|
x 0 x , |
x 0 0, |
x 1 1, |
x 1 x . |
||
2. Коммутативность объединения, пересечения: |
|||||
A B B A, |
A B B A. |
||||
Коммутативность дизъюнкции, конъюнкции: |
|||||
x |
y |
y x , |
x y |
y |
x. |
Коммутативность показывает, что порядок записи переменных в дизъюнкции, конъюнкции, может быть любым (аналог в алгебре чисел – сумма, произведение не зависит от порядка записи сомножителей, слагаемых). Коммутативными операциями также являются сумма по модулю два,
стрелка |
Пирса, штрих Шеффера. |
|
|
3. |
Ассоциативность объединения, пересечения: |
|
|
|
A (B C) ( A B) C , |
A (B C) ( A B) |
C . |
Ассоциативность дизъюнкции, конъюнкции: |
|
||
|
x ( y z) (x y) |
z , x ( y z) (x y) |
z . |
Ассоциативность показывает, что порядок выполнения конъюнкции и дизъюнкции может быть произвольным. Ассоциативной также является операция сумма по модулю два.
4. Дистрибутивность объединения относительно пересечения и наоборот:
A (B C) ( A B) ( A C) , |
A (B C) ( A B) ( A C) . |
Дистрибутивность дизъюнкции относительно конъюнкции и наобо- |
|
рот: |
|
x ( y z) (x y) (x z) , |
x ( y z) (x y) (x z) . |
Дистрибутивность определяет правила раскрытия скобок. В алгебре чисел умножение дистрибутивно относительно сложения. Сумма по модулю два дистрибутивна.
5. Поглощение пересечения, объединения:
( A B) A A, |
( A B) A A. |
Поглощение конъюнкции, дизъюнкции: |
|
(x y) y y , |
(x y) y y . |
Законы поглощения позволяют упрощать булевы функции. 6. Инволютивность (закон двойного дополнения):
A A .
Закон двойного отрицания:
x x .
19
7. Законы де Моргана9 (двойственности): |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A B |
|
|
A |
|
B, |
|
|
|
|
A |
B |
A B. |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
x y x y , |
|
|
|
|
x y x y . |
|||||||||||||||||||||
Законы де Моргана устанавливают связь между дизъюнкцией и |
||||||||||||||||||||||||||||
конъюнкцией. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
8. Закон дополнения: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
U , |
|
|
|
|
|
|
|
|
|
Ø. |
|
|
|
|||||||||
|
|
A |
|
A |
|
|
|
|
A |
|
|
A |
|
|
|
|||||||||||||
Тавтология или закон исключения третьего (закон склеивания): |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|||
Непротиворечивость: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 . |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
x |
x |
|
|
|
|
|
|
|
|
|
|
|
|
Операции над булевыми функциями имеют следующий приоритет: наиболее сильная операция – отрицание, затем следует конъюнкция, потом
– дизъюнкция, затем – импликация, затем – эквивалентность. Порядок выполнения других операций указывают скобки. Для упрощения записи знак конъюнкции можно не записывать по аналогии со знаком умножения в алгебре чисел. Например, законы де Моргана записываются так: xy x y ,
x y x y .
Чтобы доказать законы 1–8 и другие теоретико-множественные равенства, можно:
–нарисовать диаграммы Эйлера–Венна левой и правой частей равенства и убедиться в том, что они совпадают;
–воспользоваться таблицей истинности;
–провести формальное рассуждение по следующей схеме.
Пусть требуется доказать теоретико-множественное равенство M N , где M и N – некоторые множества.
Первая часть доказательства состоит в том, чтобы показать, что если некоторый элемент принадлежит множеству M , то он также принадлежит множеству N . Этим будет доказана справедливость отношения M N .
Во второй части доказательства нужно показать, что если некоторый элемент принадлежит множеству N , то он также принадлежит множеству
9 Огастес де Морган (1806, Мадура, Индия — 1871, Лондон) – шотландский математик и логик; профессор математики университетского колледжа в Лондоне; первый президент Лондонского математического общества. Основные труды: по математической логике и теории рядов; к своим идеям в алгебре ло-
гики пришёл независимо от Дж. Буля; изложил элементы логики высказываний и логики классов,
дал первую развитую систему алгебры отношений; с его именем связаны известные теоретико-
множественные соотношения (законы де Моргана).
20
M . Этим будет доказана справедливость соотношения N |
M . Тогда из |
||||||||
того, что M N и N M , следует, что M |
N . |
|
|
||||||
►Пример. Доказать включение ( A |
B) \ C A (B \ C) . |
||||||||
Решение. Изобразим диаграммы Эйлера-Венна для левой и правой |
|||||||||
частей: |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
U |
|
|
|
U |
||
|
|
А |
С |
|
|
А |
С |
||
|
|
|
|
|
|
|
|
|
В |
В |
|
Рис. 3. Множество ( A B) \ C |
Рис. 4. Множество A (B \ C) |
выделено штриховкой |
выделено штриховкой |
|
◄ |
►Пример. Докажем справедливость тождества
(a b) (c d ) ((a b) (c d )) ((a b) | (c d ))
с помощью таблицы истинности.
Аналогично докажите коммутативность суммы по модулю два, стрелки Пирса, штриха Шеффера; ассоциативность суммы по модулю два.
Решение. Пусть
f1 |
a |
b , |
f2 |
c |
d , |
f L |
f1 |
f2 , |
f3 |
a |
b , |
f4 |
f3 |
f2 , |
f5 |
f1 | |
f2 , |
f R |
f4 |
f5 . |
Таблица истинности (табл. 4) имеет вид:
21
Табл. 4
a |
b |
c |
d |
f1 |
f 2 |
f L |
f3 |
f 4 |
f5 |
f R |
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
Наборы значений из нулей и единиц для левой части f L совпали с наборами правой части f R , значит, исходное тождество верное.
В правильности тождества можно убедиться с помощью диаграмм Эйлера-Венна.
На рис. 5, 6 изображены две операции – a b и c d , – из левой части данного тождества. В роли исходных областей выберем эллипсы, тогда диаграмма будет содержать 16 областей (если выбрать круги, то диаграмма будет содержать 14 областей и будет неполной).
|
U |
|
|
U |
b |
c |
|
b |
c |
|
|
|||
a |
a |
|
||
|
|
|||
|
|
d |
||
|
d |
|
|
|
|
|
|
|
Рис. 5. a b |
Рис. 6. c d |
22
На рис. 7, 8, 9, 10 изображены диаграммы (последняя – результирующая), соответствующие операциям правой части тождества. Такая же результирующая диаграмма получится при сложении по модулю 2 двух первых диаграмм: (a b) (c d ) . Результирующие диаграммы левой и правой частей одинаковые, поэтому тождество – верное.
U
|
b |
c |
a |
|
|
|
|
d
Рис. 7. a b
U
b
c
a
d
U
b
c
a
d
Рис. 8. (a b) | (c d )
U
b
a c d
Рис. 9. |
(a b) (c d ) |
Рис. 10. |
|
(a b) (c d ) ((a b) | (c d )) |
|||
|
|
Можно ставить обратную задачу, то есть по известной диаграмме находить отвечающее ей компактное аналитическое выражение.
►Пример. Дана диаграмма, изоб- |
|
|
||||||
|
U |
|||||||
ражѐнная на рис. 11. Найдѐм соответ- |
|
|||||||
|
|
|||||||
ствующее ей аналитическое выражение. |
C2 |
а |
||||||
Запишем аналитические выраже- |
||||||||
|
|
|||||||
ния, соответствующие |
заштрихованным |
c |
C1 |
|||||
областям: |
|
|
|
|
||||
|
|
|
b |
|
||||
|
|
|
|
|
|
|
||
C1 a b c , C2 |
a b c . |
|
||||||
|
|
|||||||
|
|
|
|
|
|
|
|
Рис. 11
23
Искомое выражение получается при объединении C1 и C2 :
|
|
|
|
|
|
|
|
|
|
по закону |
|
|
|
|
|
|
|
|
|
|
дистрибутивности |
x C1 C2 |
(a b c) (a b c) |
|||||||||
|
|
|
|
|
|
|
|
по определению |
||
|
|
|
|
|
|
|
|
|
операции |
|
|
|
|
|
|
|
|
антиэквивалентность |
|||
b ((a c) (a c)) |
|
|
b (a c) . |
|||||||
►Пример. Докажем первое равенство в законе 1 формальными рас- |
||||||||||
суждениями: |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
A |
|
A |
|
A . |
|
Решение. Возьмем элемент x такой, что x A A. По определению |
||||||||||
операции объединения имеем |
x A |
x |
A. В любом случае x A. Взяв |
произвольный элемент из множества в левой части равенства, обнаружили, что он принадлежит множеству в правой части. Отсюда по определению
включения множеств получаем, что A A |
A . |
|
|
|
|
|
|
|
|
|
||||||
|
Пусть теперь x |
|
A. Тогда очевидно, |
x |
A |
x |
A. Отсюда по опре- |
|||||||||
делению операции |
объединения |
имеем |
x |
A |
A. Таким образом, |
|||||||||||
A |
A A . Следовательно, |
по |
определению |
равенства |
множеств: |
|||||||||||
A |
A A .◄ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Аналогичные рассуждения нетрудно провести и для остальных |
|||||||||||||||
свойств операций над множествами. |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|||||||
|
►Пример. Докажем один из законов де Моргана A B |
A |
B . |
|||||||||||||
|
|
|
|
|
|
|
|
|
||||||||
|
Пусть x A |
B . По |
определению |
операции |
дополнения |
имеем |
x |
|
A |
|
B , но x |
U . Следовательно, x A и вместе с тем x B . Таким об- |
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
разом, x |
A и x |
|
B . Из определения операции пересечения получаем, что |
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
x |
|
A |
|
B . Учитывая произвольность элемента x |
|
A B , имеем |
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A B |
A B . |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
Пусть теперь x A |
|
B . Тогда очевидно, |
x |
A |
x B . Таким обра- |
||||||||||||||||||||||||||
зом, |
|
x |
A |
и |
|
|
x |
B . Поэтому |
|
x |
A |
|
B . |
|
|
Следовательно, |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
x |
U \ ( A |
|
B) |
A |
|
B . Поскольку x – произвольный элемент из A B , то |
окончательно получаем
A B A B .
Приходим к выводу, что A B A B .
|
|
|
|
|
|
|
|
|
|
|
|
|
Закон де Моргана x y |
|
x y можно доказать иначе. «Умножим» |
||||||||||
обе части равенства справа (или слева) на скобку x y : |
||||||||||||
|
|
|
|
|
|
|
|
|||||
(x y) |
(x y) (x y) (x y) . |
Так как x x 0 , левая часть равенства равна нулю. Раскрывая скобки в правой части, также получаем нуль.
24