Спекторський І.Я. Дискретна математика
Подождите немного. Документ загружается.
2
1
E(x, y) = x ∨ y
n n − 1
n − 1
n − 2
E(x, y, z) = (x∧y)∨(x∧z)∨(y ∧z)
E(x, y, z) =
1
(x ∧ y ∧ z) ∨
2
(x ∧ y ∧ z) ∨
3
(x ∧ y ∧ z) ∨
4
(x ∧ y ∧ z) ∨
5
(x ∧ y ∧ z).
2
x ∧ y
y ∧ z
y ∧ z
x ∧ z
x ∧ y
2
y
y y
x ∧ z y
E(x, y, z) = (x ∧ z) ∨ y.
¿
∗
À
E(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (x ∧ y ∧ z)
E(x, y, z) =
1
(x ∧ y ∧ z) ∨
2
(x ∧ y ∧ z) ∨
3
(x ∧ y ∧ z) ∨
4
(x ∧ y ∧ z);
x ∧ y
y ∧ z
x ∧ z
E(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z).
x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z
x ∧ y ∗ ∗
x ∧ z ∗ ∗
y ∧ z ∗ ∗
x∧y x∧z
x ∧ y ∧ z x ∧ y x ∧ y ∧ z
x ∧ z
E (x ∧ y) ∨ (x ∧ z)
(10111001)
E(x, y, z) =
1
(x ∧ y ∧ z) ∨
2
(x ∧ y ∧ z) ∨
3
(x ∧ y ∧ z) ∨
4
(x ∧ y ∧ z) ∨
5
(x ∧ y ∧ z);
y ∧ z
y ∧ z
x ∧ y
x ∧ z
x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z
y ∧ z ∗ ∗
y ∧ z ∗ ∗
x ∧ y ∗ ∗
x ∧ z ∗ ∗
y ∧ z y ∧ z
x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z
x ∧ y ∧ z
x ∧ y ∗
x ∧ z ∗
(y ∧ z) ∨ (y ∧ z) ∨ (x ∧ y) (y ∧ z) ∨ (y ∧ z) ∨ (x ∧ z)
S
A
S
= ( S )
K
B
K
= (K )
A
S
S
K
B
K
(10111001)
A B
x ∧ y ∧ z
A x ∧ y ∗
B x ∧ z ∗
A + B
¿
+
À
(y∧z)∨(y∧z)∨(x∧y)
(y ∧ z) ∨ (y ∧ z) ∨ (x ∧ z)
(01111110)
E(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (x ∧ y) ∨ (y ∧ z) ∨ (x ∧ z) ∨ (y ∧ z).
x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z x ∧ y ∧ z
A x ∧ y ∗ ∗
B x ∧ z ∗ ∗
C x ∧ y ∗ ∗
D y ∧ z ∗ ∗
E x ∧ z ∗ ∗
F y ∧ z ∗ ∗
A F
(E + F )&(C + D)&(C + E)&(A + B)&(A + F )&(B + D),
¿
+
À ¿
&
À
¿
&
À
ADE + BCF + ABCE + ABCF + ABDE + ACDE + ACDF + ADEF +
+BCDF + BCEF + BDEF + ABCDE + ABCDF + ABCEF +
+ABDEF + ACDEF + BCDEF + ABCDEF.
ADE + BCF + ABCE + ACDF + BDEF,
(x ∧ y) ∨ (y ∧ z) ∨ (x ∧ z),
(x ∧ z) ∨ (x ∧ y) ∨ (y ∧ z),
(x ∧ y) ∨ (x ∧ z) ∨ (x ∧ y) ∨ (x ∧ z),
(x ∧ y) ∨ (x ∧ y) ∨ (y ∧ z) ∨ (y ∧ z),
(x ∧ z) ∨ (y ∧ z) ∨ (x ∧ z) ∨ (y ∧ z).
E(x
1
, . . . , x
n
) x
k
¿ À
x
k
E
¿ À
x
k
E
¿ À
x
k
E E(x, y, z, t) = x ∧ z ∧ t
1 − 01
(A∧x)∨(B∧x) = (A∧x)∨(B∧x)∨(A∧B)
(A ∧ B) ∨ A = A
K
K
1
K
2
K
1
K
2
(x∧y)∨(x∧z)∨(y∧z)
E(x, y, z) =
1
(x ∧ y) ∨
2
(x ∧ z) ∨
3
(y ∧ z);
y ∧ z
x ∧ y
y
y
y x∧z
E(x, y, z) = (x ∧ z) ∨ y
f : {0, 1}
×n
→ {0, 1} n ≥ 0
¿ À
{0, 1} n
f(x
1
, . . . , x
n
) x
1
, . . . , x
n
∈ {0, 1} n
f
f
(n)
n = 0
{0, 1} 0 1
n = 1 f
(1)
: {0, 1} → {0, 1}
x 01
f
(1)
0
00 0 0
f
(1)
1
01 x
f
(1)
2
10 x
f
(1)
3
11 1 1
n = 2 f
(2)
: {0, 1}
×2
→ {0, 1}
x
y
0011
0101
f
(2)
0
0000 0 0
f
(2)
1
0001 x ∧ y
f
(2)
2
0010 x → y
f
(2)
3
0011 x
f
(2)
4
0100 y → x
f
(2)
5
0101 y
f
(2)
6
0110 x ⊕ y 2
¿ À
f
(2)
7
0111 x ∨ y
f
(2)
8
1000 x ↓ y
f
(2)
9
1001 x ↔ y
f
(2)
10
1010 y
f
(2)
11
1011 y → x
f
(2)
12
1100 x
f
(2)
13
1101 x → y
f
(2)
14
1110 x|y
f
(2)
15
1111 1 1
n ≥ 0 2
2
n
n
A B
n
1
n
2
n
2
n
1
A B
f g h x y z
P
2
1 0
{0, 1}, ∨, ∧, , 0, 1
®
h{0, 1}, ⊕, ·i
¿
·
À
f
(n)
(x
1
, . . . , x
j
, . . . , x
n
)
x
j
g
(n−1)
f
(n)
(x
1
, . . . , x
j
, . . . , x
n
) = g
(n−1)
(x
1
, . . . , x
j−1
, x
j+1
, . . . , x
n
)
x
k
∈ {0, 1} 1 ≤ k ≤ n
f(x, y) = (x ∧ y) ∨ y = y
x y
f(x) = x∧x = 0
x
f(x, y, z) = y
g(x) = x g(y) = y
f(x) = x ∨ x = 1
1
K ∈ P
2