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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

25
Пусть f(x,y,z,t) = x
yz
∨
x yt и пусть K = x y = x
1
y
0
. К=1
⇔
x=1,
y=0. Поскольку f(1,0,z,t) = z
∨
t
≡
/
1, т.к. если z=0 и t=0, то z
∨
t=0,
т.е. К=x
y не является импликантом f.
Теорема 6.1.
Если формула
Φ
, реализующая функцию f, имеет
вид
i
n
1i
k
=
∨=Φ , - ДНФ, то
Φ
i
k , 1,in= .
Доказательство. Пусть в ДНФ функции k
i
=1. Тогда
1k1kkkk
n1ni1
=
∨∨∨∨
=
∨∨∨∨=Φ ............
и, следовательно,
f=1.
Определение.
Импликант P функции f называется простым,
если при удалении любой переменной из P полученная
элементарная конъюнкция не является импликантом.
В примере 6.1.
yx - простой импликант, т.к. ни x ни y
импликантами не являются.
Теорема 6.2.
Каждая функция 0f
≡
/
представима в виде
i
i
Pf ∨= , где P
i
- простые импликанты.
Доказательство
. Нужно показать, что f=1 тогда и только тогда,
когда
1P
i
i
=∨ . Очевидно, что если 1P
i
i
=
∨ , то f=1.
Пусть теперь для некоторого набора значений переменных
1kf
i
i
=
∨= . В этом случае 1k
i
=
, а из теоремы 6.1. следует, что k
i
- импликант. Сокращаем этот импликант до простого. Данную
процедуру повторяем для всех наборов значений переменных, для
которых
f=1.
Определение.
ДНФ
i
i
k∨
=
Φ
функции f называют неизбыточной
если:
1)
все k
i
- простые импликанты;
2)
удаление любой k
i
из
Φ
нарушает равенство f=
Φ
.
Очевидно, что минимальная ДНФ является неизбыточной.
Поэтому минимальные ДНФ следует искать среди неизбыточных.
Таким образом задача минимизации может быть разделена на
следующие этапы:
1) нахождение всех простых импликантов функции
f;
2) нахождение неизбыточных ДНФ функции
f;

Страницы