Спекторський І.Я. Дискретна математика
Подождите немного. Документ загружается.
{0, 1}
×n−m
(z, t) (1, 0) z ∧ t
x yÙ
x yÙ
x yÙ
x yÙ
x yÙ
x yÙ
x yÙ
x yÙ
z tÙ
z tÙ
z tÙ
z tÙ
x
y
z
x
y
z
x
y
=1
=1
x
y
=1
=1
z
t
=1
=1
z
t
=0
=1
z
t
=0
=0
z
t
=1
=0
x=1
y=1
z=1
y=0
z=0
x=0
x
y
=0
=1
x
y
=0
=1
x
y
=0
=0
x
y
=0
=0
x
y
=1
=0
x
y
=1
=0
n = 2, 3, 4
1
E(x, y) = x ∨ y E(x, y, z) = x ∨ (y ∧ z) E(x, y, z, t) = x ∨ (x ∧ y ∧ z ∧ t)
x
y
x
y
1
1
1
x ∨ y
x yÙ
x yÙ
x yÙ x yÙ
z
z
1 1
1
1
1
x ∨ (y ∧ z)
x yÙ
x yÙ
x yÙ
x yÙ
z tÙ
z tÙ
z tÙ
z tÙ
1
1
1
1
1
1
1
1
1
x ∨ (x ∧ y ∧ z ∧ t)
n
K n − 1
x K = (K∧x)∨(K∧x)
K K ∧ x K ∧ x
x
K K
x
K
K
1
(x, y) = x y
x∧y x∧y
x
x ∧ y x ∧ y K
2
(x, y, z) = x ∧ z
y x ∧ y ∧ z x ∧ y ∧ z
x
x ∧ y ∧ z x ∧ y ∧ z
x
y
x
x=(x y x y) ( )Ù Ú Ù
y
1
1
x yÙ
x yÙ
K
1
(x, y) = x
z
z
1
1
x yÙ Ùz
x x y x yÙ Ù Ù Ú Ù Ùz z z=( ) ( )
x yÙ Ùz
x yÙ x yÙ
x yÙ x yÙ
K
2
(x, y, z) = x ∧ z
k ≥ 0
n − k
2
k
¿ À
K
1
(x, y, z, t) = t K
2
(x, y, z, t) = x ∧ z
z
x yÙ
x yÙ
x yÙ
x yÙ
x yÙ
x yÙ
x yÙ
x yÙ
z tÙ
z tÙ
z tÙ
z tÙ
z tÙ
t
z tÙ
z tÙ
z tÙ
1
1
1
1
1
1
1
1
1
1
1
1
x zÙ
K
1
(x, y, z, t) = t K
2
(x, y, z, t) = x ∧ z
x
j
x
j
= 1 x
j
= 0
x
j
K
x K
K x
x K K
x x
K K
x
K
x
K
1
(x, y, z, t) = t
K
2
(x, y, z, t) = x ∧ z K
1
(x, y, z, t) = t
t
x, y, z
2
3
= 8
K
2
(x, y, z, t) = x∧z
x z
y, z
2
2
= 4
n−k
2
k
2
k
n−k
x
x
x
x
x
x x
n − k
2
k
K
E
E K
2
k
E(x, y, z, t) = x ∨ (x ∧ y ∧ z ∧ t)
E
x y ∧ z ∧ t x ∧ y
x
x yÙ
x zÙ
x yÙ
x yÙ
x yÙ
z tÙ
z tÙ
z tÙ
yÙ Ùz t
z tÙ
1
1
1
1
1
1
1
1
1
E(x, y, z, t) = x ∨ (x ∧ y ∧ z ∧ t)
• 2
k
k ∈ N ∪ {0}
•
2
k
k ∈ N ∪ { 0}
•
E(x, y) = x ∨ (x ∧ y)
x ∨ y x y
E(x, y, z) = x ∨ (x ∧ y ∧ z)
x∨(y ∧z) x y ∧z
x
y
y
x
x
y
1
1
1
E(x, y) = x ∨ (x ∧ y)
x yÙ
y zÙ
x yÙ
x
x yÙ x yÙ
z
z
1 1
1
1
1
E(x, y, z) = x ∨ (x ∧ y ∧ z)
(1101111010000100)
(x∧y∧t)∨(y∧z∧t)∨(y∧z∧t)∨(x∧y∧t)
x∧z
x yÙ
x yÙ
x yÙ
x yÙ
z tÙ
z tÙ
z tÙ
yÙ Ùz t
xÙ Ùy t
yÙ Ùz t
xÙ Ùy t
z tÙ
1
1
1
1
1
1
11
(1101111010000100)
(10111001)
(y ∧z)∨(y ∧z)∨(x∧z) (y ∧z)∨(y ∧z)∨(x∧y)
y ∧ z y ∧ z
x ∧ y ∧ z
x ∧ z x ∧ y
x yÙ
y zÙ
y zÙ
x zÙ
x yÙ
x yÙ x yÙ
z
z
1 1
1 1 1
x yÙ
y zÙ
y zÙ
x yÙ
x yÙ
x yÙ x yÙ
z
z
1 1
1 1 1
(10111001)
(01111110)
n
E(x
1
, . . . , x
n
) n ≥ 2
5
58
n
E
E
n = 0 n = 1
n = 2
(1101)
x ∨ y
(1101111010000100)
(x ∧ y ∧ t) ∨ (y ∧ z ∧ t) ∨ (y ∧ z ∧ t) ∨ (x ∧ y ∧ t) ∨ (x ∧ z)
E
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∧ a = a x ∧ x = 0 0 ∧ a = 0
o ∨ a = a a ∨ (a ∧ b) = a
(x ∨ y) ∧ (y ∨ z)
(x ∨ y) ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ y) ∨ (y ∧ z).
0
(x ∨ y) ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z).
(x ∧ z)
(x ∨ y) ∧ (y ∨ z)
(x ∨ y) ∧ (x ∨ z) = (x ∧ x) ∨ (x ∧ z) ∨ (y ∧ x) ∨ (y ∧ z).
(x ∨ y) ∧ (x ∨ z) = x ∨ (y ∧ z).
(01111110)
(x ∨ y ∨ z) ∧ (x ∨ y ∨ z)
(x ∨ y ∨ z) ∧ (x ∨ y ∨ z) =
= (x ∧ x) ∨ (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ x) ∨ (y ∧ y) ∨ (y ∧ z) ∨
∨(z ∧ x) ∨ (z ∧ y) ∨ (z ∧ z) =
= (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ x) ∨ (y ∧ z) ∨ (z ∧ x) ∨ (z ∧ y).
(A ∧ x) ∨ (A ∧ x) = (A ∧ x) ∨ (A ∧ x) ∨ A
(A ∧ B) ∨ A = A
K
K
1
K
2
E(x, y) = (x ∧ y) ∨ (x ∧ y) ∨ (x ∧ y)
1
(x ∧ y) ∨
2
(x ∧ y) ∨
3
(x ∧ y) = (x ∧ y) ∨ (x ∧ y) ∨ (x ∧ y) ∨
1,2
x ∨
2,3
y ,