Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 17 стр.

UptoLike

ВУЗ: 

РУДН | Москва

Составители: 

Рубрика: 

17
1
1
1
1
*
11
111 1 1
111 1 1
**
111 1 1
** *
111 1 1
(,,) (,,)
((,, ),, ( ,, ))
( ( , , ),..., ( , , ))
( ( ,..., ),..., ( ,..., ))
( ( ,..., ),..., ( ,..., ))).
m
m
m
m
nn
mm mn
n
nmmmn
nmmmn
nmmmn
xx xx
ffx x f x x
ffx x f x x
ff x x f x x
ffx x fx x
ϕϕ
==
=
=
=
=
=
……
…… …
……
Из теоремы вытекает
Принцип двойственности.
Если формула F=F(f
1
,…,f
m
) реализует
функцию
ϕ
(x
1
,…,x
n
), то формула F*=F(f
1
*,…,f
m
*) полученная из F
заменой функций f
1
,…,f
m
на f
1
*,…,f
m
*, реализует функцию
ϕ
*(x
1
,…,x
n
).
Формулу F* будем называть формулой, двойственной
к F.
Для формул над (0,1,
∨
,&,) принцип двойственности может быть
сформулирован так: для получения формулы F*, двойственной к
формуле F, нужно в формуле F всюду заменить 0 на 1, 1 на 0, & на
∨
,
∨
на &.
Пример 4.1.
Пусть F
1
(f
1
)=f
1
(х
1
,x
2
)=x
1
&x
2
.
Тогда F
1
*(f
1
)=F
1
(f
1
*)=f
1
*(x
1
,x
2
)=x
1
∨
x
2
.
Пусть
.)))(),((),,((),,(
21212313121123212
xxxxxfxffxxfffffF ∨
=
=
Здесь
f
1
– конъюнкция, f
2
– дизъюнкция, f
3
– отрицание.
Тогда
)(&)()))(),((),,((
),,(),,(
*****
****
2121231312112
32123212
xxxxxfxffxxff
fffFfffF
∨∨==
==
Из принципа двойственности вытекает, что если
F(f
1
,…,f
m
) =
Φ
(g
1
,…,g
n
), то F
*
(f
1
,…,f
m
) =
Φ
*(g
1
,…,g
n
)
Пример 4.2.
Из равенства
)(
2121
xxxx ∨= вытекает равенство
2121
xxxx =∨ .
Принцип двойственности позволяет почти в два раза сокращать
усилия на вывод равенств при рассмотрении свойств булевых
функций.

Страницы