Спекторський І.Я. Дискретна математика
Подождите немного. Документ загружается.
hS, ∪, ∩,
c
, ∅, Ui S
∅ U
¿
À
A, ∨, ∧, , 0, 1
®
¿
∨
À ¿
∧
À ¿ À
0 1
¿
∨
À ¿
∧
À ¿
∧
À ¿
∨
À
0 1 1 0
a ∨ 1 = 1,
a ∧ 0 = 0.
a ∨ (a ∧ b) = a,
a ∧ (a ∨ b) = a.
a ∨ a = a,
a ∧ a = a.
a ∨ (b ∨ c) = (a ∨ b) ∨ c,
a ∧ (b ∧ c) = (a ∧ b) ∧ c.
(
a ∨ x = 1,
a ∧ x = 0
x
x = a a ∨ x = 1 a ∧ x = 0 x = a
a = a
a ∨ b = a ∧ b,
a ∧ b = a ∨ b.
(a ∨ b) ∧ (a ∨ b) = a,
(a ∧ b) ∨ (a ∧ b) = a.
a ∧ (a ∨ b) = a ∧ b,
a ∨ (a ∧ b) = a ∨ b.
A ∨ 1 = (A ∨ 1) ∧ 1 = (A ∨ 1) ∧ (A ∨ ¬A) = A ∨ (1 ∧ ¬A) = A ∨ ¬A = 1.
A, ∨, ∧, , 0, 1
®
hA, ∨, ∧i
hA, ∨, ∧i
hA, ∨, ∧i
(0 4 a) ⇔ (0 ∨ a = a); (1 < a) ⇔ (1 ∧ a = a) (a ∈ A),
0 = inf A 1 = sup A
a ∈ A hA, ∨, ∧i a
hA, ∨, ∧i
a ∈ A a
A a 7→ a
hA, ∨, ∧i
0 1
A, ∨, ∧, , 0, 1
®
a a ∈ A
hA, ∨, ∧i
a
a ∈ A
hL
n
, ·
·
·
i n ∈ N
n = p
1
p
2
· · · p
m
p
1
p
2
p
m
hL
n
, ·
·
·
i
n
n
¿ À
a, b ∈ A
a 4 b ⇔ a ∨ b = b ⇔ a ∧ b = a ⇔ a ∧ b = 0 ⇔ a ∨ b = 1;
a 4 b ⇔ b 4 a.
hS, ∪, ∩,
c
, ∅, Ui
A, B ∈ S
A ⊂ B ⇔ A ∪ B = B ⇔ A ∩ B = A ⇔ A ∩ B = 0 ⇔ A ∪ B = 1;
A ⊂ B ⇔ B ⊂ A.
A, ∨, ∧, , 0, 1
®
A
a ⊕ b = (a ∧ b) ∨ (a ∧ b);
a · b = a ∧ b.
hA, ⊕, ·i 1 ∈ A
hA, ⊕, ·i
1 0
A, ∨, ∧, , 0, 1
®
a = −a
a ⊕ a = 0
hA, ⊕, ·i
1 ∈ A a, b, c ∈ A
(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
a ⊕ b = b ⊕ a
a ⊕ 0 = a
a ⊕ a = 0
(a · b) · c = a · (b · c)
(a ⊕ b) · c = a · c ⊕ b · c c · (a ⊕ b) = c · a ⊕ c · b
a
2
= a
a · 1 = 1 · a = a
¿
∧
À
¿
·
À
hA, ⊕, ·i
¿
⊕
À ¿
·
À
¿
⊕
À
¿
·
À ¿
⊕
À
(a ⊕ b) ⊕ c = ((a ∧ b) ∨ (a ∧ b)) ⊕ c =
=
¡
((a ∧ b) ∨ (a ∧ b)) ∧ c
¢
∨
³
((a ∧ b) ∨ (a ∧ b)) ∧ c
´
=
=
¡
(a ∧ b ∧ c) ∨ (a ∧ b ∧ c)
¢
∨
¡
((a ∨ b) ∧ (a ∨ b)) ∧ c
¢
=
= (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨
( (a ∧ a)
| {z }
=0
∨(a ∧ b) ∨ (b ∧ a) ∨ (b ∧ b)
|{z }
=0
) ∧ c
=
= (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨
¡
((a ∧ b) ∨ (a ∧ b)) ∧ c
¢
=
= (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) =
= (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ c).
a b
c
¿
⊕
À
(b⊕c)⊕a (b⊕c)⊕a
(a⊕b)⊕c
a b c
¿
·
À
(a ⊕ b) · c = ((a ∧ b) ∨ (a ∧ b)) ∧ c = (a ∧ b ∧ c) ∨ (a ∧ b ∧ c);
a · c ⊕ b · c = ((a ∧ c) ∧ (b ∧ c)) ∨ ((a ∧ c) ∧ (b ∧ c)) =
= (a ∧ c ∧ (b ∨ c)) ∨ ((a ∨ c) ∧ b ∧ c) = (a ∧ c ∧ b) ∨ (a ∧ b ∧ c)
¿
·
À
hA, ⊕, ·i 1 ∈ A A
¿
∨
À ¿
∧
À ¿ À
a ∨ b = a ⊕ b ⊕ a · b;
a ∧ b = a · b;
a = 1 ⊕ a.
A, ∨, ∧, , 0, 1
®
0, 1 ∈ A
hA, ⊕, ·i
a ∨ b = b ∨ a a ∧ b = b ∧ a
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ 0 = a a ∧ 1 = a
a ∨ a = 1 a ∧ a = 0
¿
∧
À ¿
∨
À ¿ À
¿
⊕
À ¿
·
À
a ∨ (b ∧ c) = a ∨ (b · c) = a ⊕ b · c ⊕ a · b · c;
(a ∨ b) ∧ (a ∨ c) = (a ⊕ b ⊕ a · b) · (a ⊕ c ⊕ a · c) =
= a
2
⊕ a · c ⊕ a
2
· c ⊕ b · a ⊕ b · c ⊕ b · a · c ⊕ a
2
· b ⊕ a · b · c ⊕ a
2
· b · c =
= a ⊕ a · c ⊕ a · c ⊕ a · b ⊕ b · c ⊕ a · b · c ⊕ a · b ⊕ a · b · c ⊕ a · b · c =
= a ⊕ b · c ⊕ a · b · c;
a ∧ (b ∨ c) = a · (b ⊕ c ⊕ b · c) = a · (b ⊕ a · c ⊕ a · b · c);
(a ∧ b) ∨ (a ∧ c) = a · b ⊕ a · c ⊕ a · b · a · c = a · b ⊕ a · c ⊕ a · b · c.
hA, ⊕, ·i
A, ∨, ∧, , 0, 1
®
hA, ⊕, ·i
A,
ˆ
⊕,
ˆ
·
®
A, ∨, ∧, , 0, 1
®
a
ˆ
⊕ b = (a ∧ b) ∨ (a ∧ b);
a
ˆ
· b = a ∧ b.
¿
ˆ
⊕
À ¿
ˆ
·
À ¿
⊕
À
¿
·
À
a
ˆ
⊕ b = a ⊕ b, a
ˆ
· b = a · b (a, b ∈ A).
a
ˆ
· b = a · b
¿
∧
À
a
ˆ
⊕ b = (a ∧ b) ∨ (a ∧ b) = (a · (1 ⊕ b)) ⊕ ((1 ⊕ a) · b) ⊕ a · b · a · b
| {z }
=0
=
= a ⊕ a · b ⊕ b ⊕ a · b = a ⊕ b
x · x = x ∧ x = 0 x ∈ A
A, ∨, ∧, , 0, 1
®
hA, ⊕, ·i
A, ∨, ∧, , 0, 1
®
D
A,
ˆ
∨,
ˆ
∧,
b
, 0, 1
E
hA, ⊕, ·i
a
ˆ
∨ b = a ⊕ b ⊕ a · b;
a
ˆ
∧ b = a · b;
b
a = 1 ⊕ a.
¿
ˆ
∨
À ¿
ˆ
∧
À ¿
b
À
¿
∨
À ¿
∧
À ¿ À
a
ˆ
∨ b = a ∨ b, a
ˆ
∧ b = a ∧ b,
b
a = a (a, b ∈ A).
a
ˆ
∧ b a ∧ b
¿
·
À
b
a = 1 ⊕ a = (1 ∧ a) ∨ (1 ∧ a) = a ∨ 0 = a.
a ∨ b = a ∧ b = a
ˆ
∨ b.
A, ∨, ∧, , 0, 1
®
↔ hA, ⊕, ·i ,
¿ À ¿
À
{0, 1}, ∨, ∧, , 0, 1
®
h{0, 1}, ⊕, ·i 1
0 1
¿
∨
À
¿
∧
À ¿ À ¿
⊕
À
2
¿
·
À
¿
∧
À
h{0, 1}, ⊕, ·i
Z
2
hS, ∪, ∩,
c
, ∅, Ui
hS, M, ∩i U
¿
∩
À
A M B = (A ∩ B
c
) ∪ (A
c
∩ B);
A ∪ B = A M B M (A ∩ B);
A
c
= U M A.
A, ∨, ∧, , 0, 1
®
A
a ∈ A
A, ∨, ∧, , 0, 1
®
a 0
A A
1
U
2
U
, ∪, ∩,
c
, ∅, U
®
(2
U
)
1
= {{a}: a ∈ U}
hL
n
, ·
·
·
i
n = p
1
p
2
· · · p
m
p
1
p
2
p
m
p
k
k = 1, 2, . . . , m
(L
n
)
1
= {p
1
, p
2
, . . . , p
m
}
{0, 1}, ∨, ∧, , 0, 1
®
1
A B C
A c ∈ A c 6= 0
a ∈ A
1
a 4 c
1
0
A
1
= {1}
1
a
b
0
B
1
= {a, b}
1
e
f
b
d
a
c
0
C
1
= {a, b, c}
c c ∈ A
1
c 4 c c c
c
1
6= 0 c
1
≺ c c
1
c
1
c
2
6= 0 c
2
≺ c
1
¿
≺
À
c
2
≺ c
c
k
≺ c c
k
6= 0 c
k
/∈ A
1
c
k +1
6= 0 c
k+1
≺ c
k
≺ c
A c  c
1
 c
2
· · · Â c
k
 c
k +1
n
c  c
1
 c
2
· · · Â c
n
c
n
∈ A
1
a
1
, a
2
∈ A
1
a
1
6= a
2
a
1
∧ a
2
= 0
c = a
1
∧ a
2
= inf{a
1
, a
2
}
c 4 a
1
c 4 a
2
a
a 0 c
a
1
a
2
a
1
6= a
2
c = a
1
∧a
2
= 0