Diskretka2
.pdfГрафическая интерпретация булевых функций Монотонные функции
Пример–домашнее задание
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1.Сокращенная ДНФ = ?
2.Тупиковые ДНФ = ?
3.Минимальная ДНФ = ?
Графическая интерпретация булевых функций Монотонные функции
Булевы функции как подмножества Rn
I B = f0; 1g R и Bn Rn:
Графическая интерпретация булевых функций Монотонные функции
Булевы функции как подмножества Rn
IB = f0; 1g R и Bn Rn:
IОтождествим функци f : Bn ! B с множеством
f(x1; x2; : : : ; xn) 2 Bnjf (x1; x2; : : : ; xn) = 1g
Графическая интерпретация булевых функций Монотонные функции
Булевы функции как подмножества Rn
IB = f0; 1g R и Bn Rn:
IОтождествим функци f : Bn ! B с множеством
f(x1; x2; : : : ; xn) 2 Bnjf (x1; x2; : : : ; xn) = 1g
z
(0; 0; 1) (0; 1; 1)
(1; 0; 1) (1; 1; 1)
(0; 1; 0)
(0; 0; 0)
y
(1; 0; 0)
x(1; 1; 0)
Графическая интерпретация булевых функций Монотонные функции
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Графическая интерпретация булевых функций Монотонные функции
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Полные конъюнкты вершины:
z
xyz xyz
xyz xyz
xyz
xyz
y
xyz
xxyz
Графическая интерпретация булевых функций Монотонные функции
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Конъюнкты длины n 1 ребра:
z
xz
|
|
|
|
|
|
|
|
|
|
|
yz |
xy |
yz |
|
|
||
|
|
|
|
|
|
xy |
||
|
|
|
|
|
xz |
|
|
|
|
|
|
|
|
|
xy |
|
|
|
|
|
|
|
|
|
|
|
xy |
|
|
|
|
|
|
y |
yz yz
xxz
Графическая интерпретация булевых функций Монотонные функции
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Конъюнкты длины n 2 грани: z
z
y
z
x
Графическая интерпретация булевых функций Монотонные функции
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Конъюнкты длины n 2 грани: z
xx
y
x
Графическая интерпретация булевых функций Монотонные функции
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Конъюнкты длины n 2 грани: z
yy
y
x