Булевы функции и теория множеств

Решение задач

Пусть множества В1,В2>...>Вm составлены из множеств A1,A2,...,An с помощью формул, содержащих теоретикомножественные операции ∪, ∩, \, Δ , -.

Тогда любому из множеств Bi i = l,...,m можно поставить в соответствие булеву функцию fi(a1,a2,...an), i = 1,...,m, полученную из формулы, задающей Bi заменой имён множеств Ai на символы переменных ai-, символ ∪ заменяется на V, ∩ на ∧, \ на ↛, А на +, знак дополнения — понимается, как отрицание.

Тогда B1=B2 ⇔ f1=f2, B1⊆B2 ⇔ f1 → f2 ≡ 1

B1∩B2 ≡ Ø ⇔ f1 ∧ f2 ≡ 0

Если между множествами B1,B2,...,Bm записано соотношение, содержащее, кроме символов теоретико-множественных операций, символы: × (декартово произведение), ⊆ (включение), = (равенство), Ø (пустое множество), U (универсальное множество), то в соответствующей формуле для булевой функции делается замена × на ∧, с на →, = на ↔, Ø на 0, U на 1.

Тогда исходное соотношение будет истинным для любых множеств В1В2,...,Вm тогда и только тогда, когда соответствующая этому соотношению булева функция будет тождественно равна 1.



Задание 2.2.1

Выяснить взаимное расположение множеств D,E,F, если А,В,С — произвольные подмножества универсального множества U.

Таблица 2.2.1

D B∪C
E (B∩C)∪(C\(A∩B))
F (B∩C)∪(B∩(C\A))
D (A∩B)∪(A\B)∪B∪C
E A∪B∪C
F (B∩C)∪(B∩A)
D (AΔC)∪(B∩A)
E A∪C
F (A\C)∪(B∩C)∪(C\A)
D (B∩C)∪ A∪C
E ((B∪C)\A)∪(C∩B)
F A∪C
D (C∩B)∪B(A\B)∪A∪C
E A∪B∪C
F (AΔB)∪(C∩A)∪C∪B
D A∪B∪(C∩B)
E (B∩A)∪(C∩(B\A))
F A∪C
D (AΔC)∪(C\B)
E (A∩C\A)∪(C∩A)
F A∪C∪B
D (A\C)∪ A∪B
E (B∪A)∪((A\B)\C)
F (A\C)∪B
D AΔC∪(A∩B)
E (A∩C)∪((A\B)\C)
F A∪C
D (B∩C \A)∪(C\B)
E B∪C ∪(C∩B)
F A∪C
D (AΔB)∪(C\A)
E ((A∪C)\B)∪((C∪)\A)
F A∪(A\B)
D AΔC ∪(C∩(B\A)
E (A∩Bl)∪((C\B)\A)
F A∪B
D AΔC∪(X\B)
E A∪C
F (A∩C)∪(C∩(A\B))
D (AΔB)∪(C∩B)
E A∪B
F (B\A)∪(A∩C)∪(A\B)
D A∪B ∪(C∩A)
E A∪B
F ((C∪A)\B)∪(C∩A))
D (C∩A)∪(B\A)∪ A∪C
E (A∩C)∪(C∩B)
F A∪C∪B
D (A∩C)∪(B\C)∪ A∪B
E (CΔB)∪(B∩A)∪ C∪B
F C∪A∪B
D (A∩C)∪ B∪C
E A∪B
F (B∩C)∪(A∩(C\B))
D AΔB ∪(A\C)
E B∪C∪A
F (A∩C\B)∪(A∩B)
D C∪B ∪(B\A)
E (B\A)∪C
F (B∩C)∩((B\C)\A)
D A∪B
E (A∩B)∪((B\C)\A)
F AΔB ∪(C∩B)
D A∪B ∪(C∪A)
E A∪(A\B)
F (A∩C\B)∪(A\C)
D (B\C)∪B
E (BΔC)∪(A\B)
F ((B∪A)\C)∪((C∪A)\B)
D BΔC ∪(A∩(C\B)
E B∪C
F (B∩C)∪((A\C)\B)
D B∪C
E ((CΔB)∩B)∪(C∩(A∪B))
F (B∩A)∪(B∩C)
D ((A\B)∩C)∪ A∪C
E (A∩C)∪(A\(C∩B)
F A∪C
D (C∩B)∪(B\A)∪A∪C
E A∪B∪C
F (C∩B)∪ C∪A
D A∪B ∪(C∩A)
E ((C∩A)\B)∪(C∩A)
F B∩A
D (AΔB)∪(C∩B)
E B∪A
F (A\B)∪(A∪C)∪(B\A)
D (A∩C)∪ C∪B
E (B∩C)∪(A∩(C\B))
F B∪A


Примеры решения задания 2.2.1

Пример 1.

Выяснить взаимное расположение множеств D=(B\C)∪(A\B), E=A\(B\C), F = A∪B, если А,В,С —произвольные подмножества универсального множества U.

Найдём соответствующие булевы функции:

fD(a,b,c) = (b⇸c)∨(a⇸b), fE(a,b.c) = a⇸(b ⇸ с),

fF(a,b,c) = a∨b и, построив таблицы, найдем векторы значений этих функций:

fD=(0010 1110), fЕ=(0000 1101), fF=(0011 1111).

Так как множество единичных наборов функций fD и fE строго включены в множество единичных наборов функции fF,to fD → fF≡1 и fE → fF≡1, но fD≠fE и fE≠fF, значит, D⊆F и E⊆F.

Пример 2.

Решить задание 2.2.2 для множеств E=BΔC ∪(B\A), D=A∪C∪(B∩C)∪(B∩C), F=B∪C

Найдём соответствующие булевы функции и векторы их значений:

fE=b + c∨(b↛a) = (1011 1001)
fD=a∨c∨(b∧c)∨(b∨c) = (1011 1001)
fF=b∨c = (1011 1011).

Так как fЕ ≡fD, то E = D. Заметим, что fE ≠ fF, и, построив таблицу, можем убедиться, что fE → fF ≡ 1. Значит, справедливы соотношения: Е = D ⊆ F.

 



Задание 2.2.2

Проверить, что для любых множеств A,В,С выполнение включения α влечёт выполнение включения β.

Таблица 2.2.2

№ α β
1 A∩B⊆ C A∪B⊆(AΔB)∪(A∩C)
2 A∩B⊆ C A\C⊆(A\B)∪C
3 AΔC⊆ AΔC⊆(A\B)∪C
4 AΔC⊆ (B\C)∪(A\C)⊆AΔB
5 A∩B⊆ C B⊆(B\A)∪C
6 A⊆B∩C AΔC⊆(A∩B)∪C
7 A⊆B∩C A\B⊆A∩C
8 A⊆B∩C A∪B⊆B∪C
9 A⊆B∩C (A\B)∪(A∩C)⊆C
10 A⊆B∩C (A\C)∪(A∩C)⊆C
11 A⊆B∩C (A\B)\C⊆C\A
12 A∩B⊆C AΔB⊆(A∩B)∪C
13 A∩B⊆C A∩C⊆A∪(B\A)
14 A∩B⊆C A∩B⊆(B∩C)∪(A∩C)
15 A∩B⊆C B\A⊆B∩C
16 A⊆B\C A∩B⊆A\C
17 A⊆B\C C∩B⊆A\C
18 A∪B⊆C AΔC⊆C\A
19 A∪B⊆C (B\C)∪(A\B)⊆A∩C
20 A∪B⊆C B⊆A∪(C\A)
21 B\C⊆A A∪B⊆(B∩C)∪A
22 B\C⊆A BΔC⊆C∪(A∩B)
23 B\C⊆A B\A⊆(C\A)∪(A∩B)
24 B\C⊆A B⊆C∪(B∩A)
25 B\C⊆A BΔC⊆C∪A
26 B\C⊆A B⊆C∪(A\C)
27 B⊆C\A A∪(B\C)⊆A\B
28 B⊆C\A (A\B)∪((B\C)\A)⊆A
29 B⊆C\A (B\C)∪(B\A)⊆B∩C
30 B⊆C\A C∪B⊆(C\A)∪(C\B)


Пример решения задание 2.2.2

Проверить, что для любых множеств А,В,С выполнение включения A\B⊆C влечёт выполнение включения СΔA⊆(A∩B)∪С.

Составим булеву функцию, соответствующую высказыванию, которое надо доказать:

f( a,b,c) = ((a ↛ Ь) → с) —> (с + а → а л Ь v с).

Построим таблицу, убедимся, что заключительный столбец, являющийся вектором значений функции f(a,b,c), состоит из одних единиц, что доказывает справедливость требуемого утверждения.

 

Задание 2.2.3

Для произвольных множеств Ф, В, Н проверить, является ли выполнение включения α необходимым и достаточным условием выполнения равенства β.

Таблица 2.2.3

№ α β
1 A⊆B\H H\A = H∪(A\B)
2 A⊆B\H H=(H\A)∪((A\B)\H)
3 A⊆B\H A∩B = (A\H)∪(A\B)
4 A⊆B\H B = (AΔB)∪(A\H)
5 A⊆B\H A∪B = (B\H)∪(B\A)
6 A⊆B\H B\A = (AΔB)∪(B∩H)
7 A⊆B\H AΔH = H∪(A∩B)
8 A⊆B\H АΔВ = (В\А)∪(Н∩В)
9 A⊆B\H A∪H=(H\A)∪((A∩B)\H)
10 A⊆B\H A∩B = (A\B)\H
11 A⊆B\H A\H = A∩(B∪H)
12 A⊆B\H A\B = A∩B∩H
13 A⊆B∩H H =(АΔН)∪(В∩А)
14 A⊆B∩H A∪B = (BпH)∪(B\A)
15 A⊆B∩H АΔB = (B\H)∪(B\А)
16 A⊆B∩H B\H=(A\B)∪((B\A)\H)
17 A⊆B∩H (B\A)\H=(B\H)∪(A\B)
18 A⊆B∩H A∩B = (A\B)∪(A∩H)
19 A⊆B∩H А\Н=(А∩Н)\В
20 A⊆B∩H H\A =(AΔH)∪(A\B)
21 A⊆B∩H B\A =(A\H)∪((B∩H)\A)
22 A⊆B∩H A∪H =H∪(B\A)
23 A⊆B∩H A∩H =A∪(B\H)
24 A⊆B∩H H\A = (AΔH)∪(B\A)
25 A⊆B∩H BΔH =(A\B)∪(H\B)
26 A⊆B∩H А∩В = ((АΔВ)\Н)∪(А∩В∩Н)
27 A⊆B∩H AΔB = (H∩(AΔB))∪((A∪B)\H)
28 A⊆B∩H H\A = (AΔH)\(A\B)
29 A⊆B∩H B\H =(B\A)\H
30 A⊆B∩H A∪B = (AΔB)∪(B∩H)


Пример решения задания 2.2.3

Для произвольных множеств A, B, H проверить, является ли выполнение включения A∪B⊆H необходимым и достаточным условием выполнения равенства АΔH = (В\А)∪(Н\А).

Составим булеву функцию, соответствующую высказыванию, которое надо доказать:

f(a,b,h) = ((a v b) → h) ↔ (а + h ↔ ((b⇸a) v (h⇸a))).

Построим таблицу, убедимся, что заключительный столбец, являющийся вектором значений функции f(a,b,h) состоит из одних единиц, что доказывает справедливость требуемого ждения.



Задание 2.2.4

Выяснить, верно ли равенство α для произвольных А, В, С.

Таблица 2.2.4

№ α
1 A×C = (A×(C\B))∪(A×(C∩B))
2 A×C = (A×(C∩B))∪(A×(A×C))
3 A×(BΔC) = (A×(B∪C)\(A×(C∩B))
4 A×C = (A×(C\B))∪(A×C)
5 A×(B∪C) = (A×B)∪(A×(C\B)
6 A×(C\B) = (A×C)Δ(A×(C∩B))
7 A×C = (A × (C ∪ B)) ∩ (A × C)
8 A×(C∩(BΔC)) = (A×C)Δ(A×(C∩B))
9 A×(C\B) = (A×C)\(A×(C∩B))
10 A×(B∪C) = A×(BΔC))(A×(B∩C)
11 A×C = (A×(C∪B))\(A×(B\C))
12 A×(B∩C) = (A×C)\(A×(C\B))
13 A×(B∩C) = (A×(B∪C))\(A×(BΔC))
14 A×(CB) = (A×(B∪C))\(A×B)
15 B×A = (B×(A\C))∪(B×(A∩C)
16 B×A = (B×(A∩C))∪(B×A)
17 B×A = (B×A)(B×(A\C))
18 B×(A∪C) = (B×(A\C))
19 B×A = (B×A)∩(B×(A∪C)
20 B×(A\C) = (B×A)\(B×(A∩C))
21 B×A = (B×(A∪C))\(B×(C\A))
22 B×(A∩C) = (B×A)\(B×(A\C))
23 B×(A\C) = (B×A)Δ(B×(A∩C)
24 B×(AC\) = (B×(A∪C))\(B×C)
25 C×B = (C×(B\A))∪(C×(B∩A)
26 C×B = (C×(B∩A))∪(C×B)
27 C×(AB) = (C×(AΔB)\(C×(A∩B))
28 C×B = (С×(B\A))∪(С×B)
29 C×(A∪B) = (C×A)(C×(B\A))
30 C×(B\A) = (C×B)\(C×(A∩B))


Пример решения задания 2.2.4

Выяснить, верно ли равенство

Сх(В\А) = (СхВ)Δ(Сх(А∩В)) для произвольных А, В, С.

Составим булеву функцию, соответствующую высказыванию, которое надо доказать:

f(a,b,с) = (с ∧ (b ↛ а)) ↔ (с ∧ b) + (с ∧ (а ∧ b)).

Построим таблицу, убедимся, что заключительный столбец, являющийся вектором значений функции f(a,b,c), состоит из одних единиц, что доказывает справедливость требуемого утверждения.