Лекция дискрет 10
.pdfПример построения СДНФ для f (w, x, y, z) = (w x) & (y z) |
|||||||||||||||||||
f (x1, … , xn) = |
|
|
|
σ1 |
& … & xn |
σn |
) |
|
|
(▼▼▼) |
|||||||||
f(σ1,…,σn) = 1 |
(x1 |
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
w |
|
x |
|
y |
z |
|
f(w,x,y,z) |
||
w |
x |
y |
z |
|
|
f(w,x,y,z) |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
|
|
0 |
|
|
|
|
1 |
|
0 |
|
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
0 |
1 |
|
1 |
|
|
0 |
0 |
0 |
1 |
|
|
0 |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
|
|
0 |
|
|
|
1 |
|
0 |
1 |
0 |
|
1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
|
|
0 |
|
|
|
1 |
|
0 |
1 |
1 |
|
1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
|
|
0 |
|
|
|
|
1 |
|
1 |
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
|
|
1 |
|
|
|
1 |
|
1 |
|
0 |
1 |
|
1 |
|
|
0 |
1 |
1 |
0 |
|
|
1 |
|
|
|
1 |
|
1 |
|
1 |
0 |
|
1 |
|
|
0 |
1 |
1 |
1 |
|
|
1 |
|
|
|
1 |
|
1 |
|
1 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
w |
x |
y |
z |
|
f(w,x,y,z) |
|
f (w, x , y, z) = |
|
|
|
|
|
|
|
= ( w & x & y & z) |
0 |
1 |
0 |
1 |
|
1 |
|
|
0 |
1 |
1 |
0 |
|
1 |
|
( w & x & y & z) |
0 |
1 |
1 |
1 |
|
1 |
|
( w & x & y & z) |
1 |
0 |
0 |
1 |
|
1 |
|
(w & x & y & z) |
1 |
0 |
1 |
0 |
|
1 |
|
(w & x & y & z) |
|
|
|
|
|
|
|
(w & x & y & z) |
1 |
0 |
1 |
1 |
|
1 |
|
|
1 |
1 |
0 |
1 |
|
1 |
|
(w & x & y & z) |
|
|
|
|
|
|
|
(w & x & y & z) |
1 |
1 |
1 |
0 |
|
1 |
|
|
1 |
1 |
1 |
1 |
|
1 |
|
(w & x & y & z) |
|
|
|
|
|
|
|
|
Th.3.1.2 Всякая логическая функция f (x1, x2, … , xn) может
|
быть представлена в виде |
|
|||
f (x1, x2, … , xm, xm+1, … , xn) = |
|
||||
|
& (x1 |
α1 … |
|
αm f (α1, … , αm, xm+1, … , xn)) |
(▲) |
|
|
||||
= |
xm |
||||
|
α1...αm |
|
Здесь: m n; конъюнкция берётся по всем 2m наборам значений переменных α1, … , αm
Формула
& (x1α1 … xmαm f (α1, … , αm, xm+1, … , xn)) α1...αm
- конъюнктивная нормальная форма (КНФ) ф-ии f (x1, … , xn)
Доказательство Th.3.1.2
Подставим в левую и правую части равенства (▲) произвольный набор значений (σ1, … , σm, σm+1, … , σn):
f (σ1, σ2, … , σm, σm+1, … , σn) = |
|
|
|
|
|
(▲▲) |
||||
|
|
|
|
|
|
|
|
|
|
|
= |
& (σ |
α1 |
… σ |
αm f (α |
, … , α , σ |
m+1 |
, … , σ |
)) |
||
|
α1...αm |
1 |
|
m |
1 |
|
m |
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В правой части (▲▲) присутствуют 2m дизъюнкций, каждая из которых соответствует набору значений α1, … , αm, в том числе ровно одна дизъюнкция такая, что αi = σi для всех i=1…m, т.е. в результате вычисления будет получено σ1α1 … σmαm = 0
В каждой из остальных (2m- 1) дизъюнкций хотя бы для
одного значения j=1…m имеет место αj σj, значит, σjαj = 1, следовательно, σ1α1 … σmαm = 1
В результате вычисления значений σ1α1 & … & σmαm для всех наборов α1...αm равенство (▲▲) принимает вид
f (σ1, σ2, … , σm, σm+1, … , σn) =
=σ1α1 … σmαm f (α1, … , αm, σm+1, … , σn)
ас учётом равенства αi = σi для всех i=1…m и того, что при x = α имеет место xα = 0, получаем:
f(σ1, σ2, … , σm, σm+1, … , σn) =
=σ1σ1 … σmσm f (σ1, … , σm, σm+1, … , σn) =
=f (σ1, σ2, … , σm, σm+1, … , σn)
Набор значений (σ1, σ2, … , σm, σm+1, … , σn) – произвольный, поэтому разложение (▲) доказано
Доказано Th.3.1.2
Пример Разложение функции f(w,x,y,z) = (w x) & (y z)
по переменным w и x |
|
|
||
|
Согласно (▲): |
|
|
|
|
α1 |
α2 |
||
f (w, x, y, z) = |
|
(w x f (0, 0, y, z)) & |
0 |
0 |
|
& (w x f (0, 1, y, z)) & |
0 |
1 |
|
|
& ( w x f (1, 0, y, z)) & |
1 |
0 |
|
|
& ( w x f (1, 1, y, z)) |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Как и ранее, f (w, x, y, z) = (w x) & (y z) =
=(w x ((0 0)&(y z))) & (w x ((0 1)&(y z))) &
&( w x ((1 0)&(y z))) & ( w x ((1 1)&(y z))) =
=(w x) & (w x y z) & ( w x y z) & ( w x y z)
f (x1, x2, … , xm, xm+1, … , xn) = |
|
|
|
|
|
|||||||
= & |
|
|
α1 |
… |
|
|
αm f (α |
, … , α , x |
|
, … , x |
)) (▲) |
|
(x |
|
x |
|
m+1 |
||||||||
α1...αm |
1 |
|
|
m |
1 |
m |
n |
|
||||
|
|
|
|
|
|
|
|
|
|
|
В равенстве (▲) положим m = n:
f (x1, … , xn) = & |
(x1α1 … |
xnαn f (α1, … , αn)) = |
||||
α1...αn |
|
|||||
= & |
|
α1 … |
xnαn) |
(▲▲▲) |
||
|
||||||
(x1 |
||||||
f( 1,…, n) = 0 |
|
Здесь: конъюнкция берётся по всем наборам значений переменных (1,…, n), для которых выполнено f(1,…, n)= 0
Равенство (▲▲▲) – совершенная конъюнктивная
нормальная форма (СКНФ) функции f (x1, … , xn)
Из (▲▲▲) очевидно: не имеет СКНФ единственная
функция – та, для которой f (x1, … , xn) 1, т.е. константа 1
Пример построения СКНФ для |
f (w, x, y, z) = (w x) & (y z) |
||||||||||||
f (x1, … , xn) = |
& |
(x1 |
σ1 |
|
|
σn |
) |
|
|
(▲▲▲) |
|||
f(σ1,…,σn) = 0 |
|
… xn |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
w |
x |
y |
z |
f(w,x,y,z) |
|
|
|
w |
x |
y |
z |
f(w,x,y,z) |
|
0 |
0 |
0 |
0 |
0 |
|
|
|
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
|
|
|
1 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
|
|
|
1 |
0 |
1 |
0 |
1 |
|
0 |
0 |
1 |
1 |
0 |
|
|
|
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
|
|
|
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
1 |
1 |
|
|
|
1 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
|
|
|
1 |
1 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
|
|
|
1 |
1 |
1 |
1 |
1 |
w |
x |
y |
z |
|
f(w,x,y,z) |
|
f (w, x , y, z) = |
|
|
|
|
|
= (w x y z) & |
||
0 0 0 |
0 |
|
0 |
|
|||
|
|
|
|
|
|
|
& (w x y z) & |
0 |
0 |
0 |
1 |
|
0 |
|
|
0 |
0 |
1 |
0 |
|
0 |
|
& (w x y z) & |
|
|
|
|
|
|
|
& (w x y z) & |
0 |
0 |
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
& (w x y z) & |
0 |
1 |
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
& ( w x y z) & |
1 |
0 |
0 |
0 |
|
0 |
|
|
1 |
1 |
0 |
0 |
|
0 |
|
& ( w x y z) |
|
|
|
|
|
|
|
|
Задача
Девушки собираются на дискотеку и, как положено, капризничают:
Алла: Если я пойду, то пойдёт и Бэлла
Бэлла: Если я пойду, то пойдёт Валя или Алла не пойдёт
Валя: Если Галя не пойдёт, то пойдёт Алла, а я не пойду
Галя: Если я пойду, то пойдёт и Алла
Смогут ли девушки договориться?