Спекторський І.Я. Дискретна математика
Подождите немного. Документ загружается.
x y
(x ∧ y) = (x ∧ y ∧ z) ∨ (x ∧ y ∧ z).
z x y
z = (x ∧ z) ∨ (x ∧ z) = (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z).
(x ∧ y ∧ z)
E(x, y, z) = (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ ( x ∧ y ∧ z).
E(x, y) = 1
E(x, y) = x ∨ x = (x ∧ y) ∨ (x ∧ y) ∨ (x ∧ y) ∨ (x ∧ y).
x ∨ y (x ∨ y) ∨ z x y
x ∧ y
(x ∨ y) ∨ z x ∨ (y ∨ z)
(x ∨ y) ∨ z x ∨ (y ∨ z) x ∨ y ∨ z
x ∨ y ∨ z
x ∨ z ∨ y z ∨ y ∨ x
0 0
E(x
1
, . . . , x
n
) n
x∨y
x, y x, y, z
E
1
∧ E
2
∧ · · · ∧ E
k
E
1
, E
2
, . . . , E
k
E
1
E
2
E
k
(x ∨ y) ∧ (y ∨ z) ∧ (x ∨ y ∨ z) 2 2 3
x ∨ y 2
x ∧ y 1
0
1
x∨((x ∧ y) ∨ x ∨ z) = x ∨((x∨y) ∧(x∨z)) = (x∨x ∨ y)∧(x∨ x∨z) = x ∨z
x ∧ (y ∨ x ∨ z) = x ∧ (y ∨ (x ∧ z)) = x ∧ (y ∨ x) ∧ (y ∨ z).
x = x ∧ (x ∨ y) = (x ∨ y) ∧ (x ∨ y)
E(x, y) = (x ∨ y) ∧ (x ∨ y)
E(x, y, z) = (x ∨ y ∨ z) ∧ (x ∨ y ∨ z)
E(x) = x
x
x x, y
1
E(x, y) = (x ∨ y) ∧ x
y
E(x, y) = (x ∨ y) ∧ x = (x ∨ y) ∧ (x ∨ y) ∧ (x ∨ y).
E(x, y, z) = (x ∨ y) ∧ z
z
x y
(x ∨ y) = (x ∨ y ∨ z) ∧ (x ∨ y ∨ z).
z x y
z = (x ∨ z) ∧ (x ∨ z) = (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z).
(x ∨ y ∨ z)
E(x, y, z) = (x ∨ y ∨ z) ∧ ∧(x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z).
E(x, y) = 1
E(x, y) = x ∧ x = (x ∨ y) ∧ (x ∨ y) ∧ (x ∨ y) ∧ (x ∨ y).
E(x
1
, . . . , x
n
)
A, ∨, ∧, , 0, 1
®
E : A
×n
→ A
0 1 x
k
∈ {0, 1} k = 1, 2, . . . , n
E 0 1
E(x
1
, . . . , x
n
) ∈ {0, 1} A, B ∈ {0, 1} A∨B ∈ {0, 1}
A ∧ B ∈ {0, 1} A ∈ { 0, 1} E(x
1
, . . . , x
n
) ∈ {0, 1}
E(x
1
, . . . , x
n
)
¿ À
E : { 0, 1}
×n
→ {0, 1}
E(x
1
, . . . , x
n
)
A, ∨, ∧, , 0, 1
®
E(x
1
, . . . , x
n
) 2
n
(x
1
, x
2
, . . . , x
n
) ∈ {0, 1}
×n
E(x
1
, . . . , x
n
) 1
1 E(x, y) = x ∧ y 1
(1, 0) x = 1, y = 0
E(x, y) = x ∧ y
x y x ∧ y
0 0 0
0 1 0
1 0 1
1 1 0
E(x
1
, . . . , x
n
)
(a
1
, a
2
, . . . , a
n
) ∈ {0, 1}
×n
E(a
1
, a
2
, . . . , a
n
) = 1
(a
1
, a
2
, . . . , a
n
) ∈ { 0, 1}
×n
E(x
1
, . . . , x
n
)
1
{0, 1}
×n
E(x
1
, . . . , x
n
)
0 1 1
E(x, y, z) = x ∧ y ∧ z (1, 0, 1)
E(x
1
, x
2
, x
3
, x
4
) = x
1
∧ x
2
∧ x
3
∧ x
4
(0, 0, 1, 0)
E(x
1
, . . . , x
n
) n − 1
1 {0, 1}
×n
E(x
1
, . . . , x
n
) 0 1
E(x
1
, . . . , x
n
) n − k
0 ≥ k ≥ n − 1 1 2
k
{0, 1}
×n
2
k
k E(x
1
, . . . , x
n
)
E(x, y, z) = x 1 = 3 − 2 1 2
2
= 4
{0, 1}
×n
(0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1)
E(x
1
, . . . , x
n
) = 1
0 = n − n 1 2
n
{0, 1}
×n
E(x
1
, . . . , x
n
) m
E
i
(x
1
, . . . , x
n
) i = 1, 2, . . . , m E(x
1
, . . . , x
n
)
1 {0, 1}
×n
1 E
i
(x
1
, . . . , x
n
) i = 1, 2, . . . , m
1 m m
{0, 1}
×n
E(x
1
, . . . , x
n
) 1
E(x, y, z) = (x∧y∧z)∨(x∧y∧z) 1 (1, 0, 1)
(0, 0, 0) E(x
1
, . . . , x
n
)
¿ À
{0, 1}
×n
1
0 1 0
E(x, y, z) = x ∨ y ∨ z (0 , 1, 0)
E(x
1
, . . . , x
n
) m 0
m {0, 1}
×n
0
E(x, y, z) = (x∨y∨z)∧(x∨y∨z)
0 (0, 1, 0) (1, 1, 1) E(x
1
, . . . , x
n
)
¿ À
{0, 1}
×n
0
E(x
1
, . . . , x
n
) {0, 1}
×n
E : A
×n
→ A
E(x
1
, . . . , x
n
)
A, ∨, ∧, , 0, 1
®
E(x
1
, . . . , x
n
) {0, 1}
×n
E : A
×n
→ A
{0, 1}
×2
n
{0, 1}
×n
(0, . . . , 0, 0) (0, . . . , 0, 1) (0, . . . , 0, 1) (0, . . . , 1, 0)
(0, . . . , 1, 1) (1, . . . , 1, 1)
E(x, y, z)
(11100101)
¿ À
E(x, y, z)
1
¿
À
0
x y z E(x, y, z, x
4
)
0 0 0 1 x ∧ y ∧ z
0 0 1 1 x ∧ y ∧ z
0 1 0 1 x ∧ y ∧ z
0 1 1 0 x ∨ y ∨ z
1 0 0 0 x ∨ y ∨ z
1 0 1 1 x ∧ y ∧ z
1 1 0 0 x ∨ y ∨ z
1 1 1 1 x ∧ y ∧ z
(x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z);
(x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z).
f : A → A
A A
0 1
A A
1
a
b
0
x 0 x x
x ∨x = 1 f : A → A
f(0) = 0 f(1) = 1 f(a) = b f(b) = a
A A
0 1
A = {0, 1}
A
¿ À
x ∨ y
¿ À
x ∨ (x ∧ y)
E
1
(x
1
, . . . , x
n
)
E(x
1
, . . . , x
n
) E(x
1
, . . . , x
n
)
1 {0, 1}
×n
1
E
1
(x
1
, . . . , x
n
)
E
1
E
E
1
→ E 1
0 1
E E
x ∨ (x ∧ y) x x ∧ y
E
1
E
E E
1
E
1
E ∨ E
1
E
1
E
E
1
E
1
1
E(x, y) = x ∨ (x ∧ y) x
y x ∧ y x y x ∧ y
x y
E
E
E
E
0 1 x x x ∨ y (x ∧ y) ∨ (x ∧ y) x ∨ (y ∧z)
x ∨ (x ∧ y)
x ∨ (x ∧ y) = x ∨ y
(x∧ y)∨(x∧z) ∨(y ∧z)
y∧z (x∧y)∨(x∧z)∨(y∧z) = (x∧y)∨(x∧z)
•
•
E(x
1
, . . . , x
n
) n = 2, 3, 4
n = 0 n = 1
E(x
1
, x
2
, . . . , x
n
)
{x
1
, . . . , x
n
} {x
1
, . . . , x
m
}
{x
m+1
, . . . , x
n
}
E(x
1
, x
2
, . . . , x
n
)
{0, 1}
×n
{0, 1}
×m
{x
1
, . . . , x
m
} {0, 1}
×n−m
{x
m+1
, . . . , x
n
} n = 2
E(x, y) x
y
n = 3 E(x, y, z)
z (x, y)
(x, y)
z
n = 4
E(x, y, z, t)
(x, y) (z, t)
, ∈ {0, 1}
k
n = 2 (0, 0) (0, 1) (0, 1) (1, 0)
∈ {0, 1}
k
k
k
(1, 0) (0, 0) (1, 1)
{0, 1}
×m