Спекторський І.Я. Дискретна математика
Подождите немного. Документ загружается.
f
(n)
∈ K f(x
1
, . . . , x
n
)
K
f
(n)
∈ K E
1
, . . . , E
n
K
f
(n)
(E
1
, . . . , E
n
) K
K
K = {→, ∨}
x → y x → x x → (y ∨ z) x → (y ∨ x)
x ∨ y ∨(x, y) x → y →(x, y)
K ⊂ P
2
f
K f K
K ⊂ P
2
K = {→, 0} 1
x → x 0 → x 0 → (x → x)
K ⊂ P
2
K K [K]
[{x}] = {x, x} [{x}]
x x x
[{x, 0}] = {x, x, 0, 1}
K = {∨} [K] x
x
1
∨x
2
x
1
∨x
2
∨x
3
x
x ∨ x
{∨, ∧, x} P
2
0 = x ∧ x 1 = x ∨ x
¿
∨
À
¿
→
À ¿ À ¿
x∨ y
À ¿
x → y
À ¿
x
À
K ⊂ P
2
f(x) = x [K]
g
(n)
1
, . . . , g
(n)
m
∈ K g
(m)
0
∈ K [K] h
(n)
h
(n)
(x
1
, . . . , x
n
) = g
(m)
0
(g
(n)
1
(x
1
, . . . , x
n
), . . . , g
(n)
m
(x
1
, . . . , x
n
)).
g
k
1 ≤ k ≤ m
[[K]] = [K]
[K
1
∩ K
2
] ⊂ [K
1
] ∩ [K
2
]
K
1
= {x, 0} K
2
= {x, 1}
[K
1
∪K
2
] ⊃ [K
1
]∪[K
2
]
K
1
= {x} K
2
= {∨}
K ⊂ P
2
[K] = K
K ⊂ P
2
K
¿ À
K
P
2
{0} {0, 1} {x} {x, x} {x, 1} {x, x, 0, 1}
{x, x, 0} 1 = 0 ∈ [{x, x, 0}]
{x
1
∨ · · · ∨ x
n
: n ≥ 1}
0 1
K ⊂ P
2
K 6= ∅ [K]
K
1
, K
2
⊂ P
2
K
1
∩ K
2
6= ∅
K
1
∩ K
2
K
1
= {x, x} K
1
= {0}
K ⊂ P
2
[K] = P
2
K ⊂ P
2
K
P
2
{∨, ∧, x}
0 = x ∧ x 1 = x ∨ x
{∨, x} {∧, x}
x ∨ y = x ∧ y, x ∧ y = x ∨ y.
{∧, ⊕, 1}
P
2
P
2
P
2
f ∈ P
2
0
f(0, 0, . . . , 0) = 0 f ∈ P
2
1
f(1, 1, . . . , 1) = 1 0
T
0
1 T
1
x x ∨ y x ∧ y
T
0
T
1
0 ∧ 0 = 0 1 ∧ 1 = 1
x ∧ y ∈ T
0
x ∧ y ∈ T
1
x → y x ↔ y T
1
T
0
0 → 0 = 1 6= 0 1 → 1 = 1 x → y /∈ T
0
x → y ∈ T
1
x ⊕ y ∈ T
0
x ⊕ y /∈ T
1
x /∈ T
0
x /∈ T
1
T
0
T
1
T
0
g
(n)
1
, . . . , g
(n)
m
∈ T
0
g
(m)
0
∈ T
0
T
0
h
(n)
(x
1
, . . . , x
n
) = g
(m)
0
(g
(n)
1
(x
1
, . . . , x
n
), . . . , g
(n)
m
(x
1
, . . . , x
n
)).
g
(n)
k
(0, 0, . . . , 0) = 0 1 ≤ k ≤ m h
h
(n)
(0, 0, . . . , 0) = g
(m)
0
(0, 0, . . . , 0) = 0,
h
(n)
∈ T
0
T
0
T
1
0 1
f /∈ T
0
f ∈ T
1
1 ∈ [{f}] 1
f
f /∈ T
1
f ∈ T
0
0 ∈ [{f}] 0
f
f /∈ T
0
f /∈ T
1
x ∈ [{f}] x
f
f
(n)
/∈ T
1
f
(n)
∈ T
0
g(x) = f(x, x, . . . , x) ∈ [{f}] f 0
1
g(0) = f(0, 0, . . . , 0) = 0, g(1) = f(1, 1, . . . , 1) = 0,
g(x) = 0 x ∈ {0, 1} g
0
f /∈ T
0
f ∈ T
1
g(x) = f(x, x, . . . , x)
g(x) = 1
x ∈ {0, 1} g 1
f /∈ T
0
f /∈ T
1
g(x) = f(x, . . . , x)
f 0 1
g(0) = f(0, 0, . . . , 0) = 1, g(1) = f(1, 1, . . . , 1) = 0,
g(x) = x x ∈ {0, 1}
f
f(x, y) = x ⊕ y f /∈ T
1
f ∈ T
0
0
g(x) = x ⊕ x = 0
f(x, y) = x → y f /∈ T
0
f ∈ T
1
1 g(x) = x → x = 1
f(x, y) = x ↓ y = x ∨ y
f /∈ T
0
f /∈ T
1
g(x) = x ↓ x = x
{0, 1}
×n
n ≥ 1
¿ À
∈ {0, 1}
×n
∈ {0, 1}
×n
k
≤
k
k = 1, . . . , n 0 < 1
4
1
0
h{0, 1}, 4i
(1, )1
(1,0)
(0,1)
( ,0)0
h{0, 1}
×2
, 4i
(1,1, )1
(1,1,0)
(1,0, )1
(0,1,0)
(0,1, )1
(1,0,0)
(0,0,1)
(0,0,0)
h{0, 1}
×3
, 4i
{0, 1}
×1
= {0, 1} {0, 1}
×2
{0, 1}
×3
n ≥ 2
(0, 1) (1, 0)
f
(n)
n ≥ 1
f
(n)
( ) ≤ f
(n)
( ) 4 , ∈ {0, 1}
×n
0 0 1
0
1
M
x, x∨y, x∧y ∈ M
x → y /∈ M 0 → 0 = 1 1 → 0 = 0
(0, 0) 4 (1, 0)
, ∈ {0, 1}
×n
M
f /∈ M
x ∈ [{f, 0, 1}] x
f 0 1
f
(n)
/∈ M n ≥ 1
0 1 f /∈ M
, ∈ {0, 1}
×n
4 f( ) > f( )
0 1 f( ) = 1 f( ) = 0
g
k
(x) k = 1, 2, . . . , n
g
k
(x) =
0,
k
=
k
= 0,
1,
k
=
k
= 1,
x,
k
= 0,
k
= 1
g
k
(x) c ∈ {0, 1}
k
=
k
= c
x
k
6=
k
k
= 0
k
= 1
k
= 1
k
= 0
k
≤
k
k = 1, 2, . . . , n
g(x) = f(g
1
(x), . . . , g
n
(x))
g(0) = f(g
1
(0), g
2
(0), . . . , g
n
(0)) = f(
1
,
2
, . . . ,
n
) = f( ) = 1
g
k
(0) =
(
0,
k
= 0,
k
∈ {0, 1},
1,
k
=
k
= 1,
g
k
(0) =
k
1 ≤ k ≤ n g
k
(1) =
k
1 ≤ k ≤ n
g(1) = f(g
1
(1), . . . , g
n
(1)) = f( ) g(0) = 1 g(1) = 0
g(x) = x x ∈ {0, 1}
g
k
(x) 1 ≤ k ≤ n
f(x
1
, . . . , x
n
) x 0 1
g(x) = x {f, 0, 1}
x
0 1
f(x
1
, x
2
) = x
1
→ x
2
= (0, 0) = (1, 0)
g
1
(x) = x
1
= 0
1
= 1
1
6=
1
g
2
(x) = 0
2
=
2
= 0
g(x) = g
1
(x) → g
2
(x) = x → 0 = x
f(x
1
, x
2
) = x
1
⊕ x
2
= (1, 0) = (1, 1)
0 ⊕ 1 = 1 Â 1 ⊕ 1 = 0 g
1
(x) = 1 g
2
(x) = x g(x) = 1 ⊕ x = x
f : {0, 1}
×n
→ {0, 1}
f
∗
(x
1
, . . . , x
n
) = f(x
1
, x
2
, . . . , x
n
).
(x)
∗
= x = x
(x)
∗
= x = x
(x ∨ y)
∗
= x ∨ y = x ∧ y
0
∗
= 0 = 1 1
∗
= 1 = 0
x ⊕ y = x ↔ y x = x ⊕ 1
¿
⊕
À
(x ↔ y)
∗
= x ↔ y = x ⊕ y = (x ⊕ 1) ⊕ (y ⊕ 1) = x ⊕ y.
(x → y)
∗
= x → y = x ∧ y
(f
∗
)
∗
= f
(f
∗
= g) ⇒ (g
∗
= f) (∨
∗
= ∧) ⇒ (∧
∗
= ∨)
(↔
∗
= ⊕) ⇒ (⊕
∗
=↔)
f(x
1
, . . . , x
n
) = h(g
1
(x
1
, . . . , x
n
), . . . , g
m
(x
1
, . . . , x
n
)),
f
f
∗
(x
1
, . . . , x
n
) = h
∗
(g
∗
1
(x
1
, . . . , x
n
), . . . , g
∗
m
(x
1
, . . . , x
n
))
g
k
1 ≤ k ≤ m
f E f
∗
E
∗
E
E
x → y = x ∨ y
(x → y)
∗
= x ∧ y x ∧ y
x ∨ y
x x
f(x, y, z) = (x ∨ y) ⊕ z ∨
∗
= ∧ ⊕
∗
= ↔
f
∗
(x, y, z) = ((x ∨ y) ⊕ z)
∗
= (x ∧ y) ↔ z
f
f
∗
= f S
x x
M(x, y, z) = (x ∨ y) ∧ (x ∨ z) ∧ (y ∨ z)
M
∗
(x, y, z) = m(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z)
M(x, y, z) = m(x, y, z)
{0, 1}, ∨, ∧, , 0, 1
®
M(x, y, z) = m(x, y, z) ∈ S
f
(n)
(
1
, . . . ,
n
) ∈ {0, 1}
×n
(
1
, . . . ,
n
) ∈ {0, 1}
×n
n = 2
(0, 0) (0, 1) (1, 0) (1, 1)
(0, 0) (1, 1) (0, 1) (1, 0)
n
f
(n)
(c
0
, c
1
, . . . , c
2
n−1
−1
, c
2
n−1
−1
, c
1
, c
0
)
3 (01110000)
0
n 2
2
n−1
2
n−1
2
2
2−1
= 4
(0011) (0101) (1010) (1100)
f
3
(x, y) = x f
5
(x, y) = y f
10
(x, y) = y f
12
(x, y) = x
S
f /∈ S
0, 1 ∈ [{f, x}] 0 1
f x
f
(n)
/∈ S
f x 0 1
n = 0
f 0 1 n ≥ 1
f
(n)
/∈ S ∈ {0, 1}
×n
f( ) 6= f
∗
( )
f(
1
, . . . ,
n
) 6= f(
1
, . . . ,
n
).