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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

29
них такое подмножество, что
)...(
r1
α
α
∨∨
Φ
, т.к. в этом случае
из того, что
Φ
∨∨ )...(
r1
α
α
следует, что
Φ
≡
f . Выбранное
подмножество должно быть минимальным (в смысле сделанных
ранее определений).
)...(
r1
α
α
∨∨Φ
, если каждая k
i
покрывается подходящим
α
j
.
т.к. в противном случае существовали бы такие значения
переменных, что непокрытая
k
i
(и, следовательно,
Φ
) принимали
бы значение
1, а
α
1
∨
…
∨α
r
принимало бы значение 0.
Задача нахождения минимального подмножства простых
импликантов решается с помощью таблиц, столбцы которых
перенумерованы
k
i
, строки простыми импликантами
α
1,
...,
α
m
.
Из примера предыдущей лекции получаем следующую таблицу
простых импликантов:
0000 0001 0010 1000 1001 1100 1101
00-0
×
×
-00-
×
×
×
×
1-0-
×
×
×
×
Крестики стоят в тех позициях, где импликант покрывает
элементарную конъюнкцию.
Правило.
Если в столбце имеется лишь один крестик, то
соответствующая строка (т.е. импликант) должна быть выбрана
обязательно (т.к. только этот импликант покрывает
соответствующую конъюнкцию). Множество таких строк (т.е.
импликантов) отражает ядро
задачи. Далее, вычеркиваем все
столбцы, у которых на пересечении с данной строкой есть крестик
(т.е. конъюнкция покрывается импликантом).
В нашем примере в ядро задачи входят все импликанты.
Следовательно, минимальным представлением для функции
f(x,y,z,t) является zxzytyx ∨∨ , т.е.
zxzytyxtzyxf ∨∨=),,,(.
Возможны варианты:
1) после выделения ядра еще остаются элементарные
конъюнкции, подлежащие покрытию;
2) может оказаться, что останутся простые импликанты,

Страницы