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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

27
Первая и третья конъюнкции дают
xyzt
∨
x y zt = xzt. Вторая и
третья конъюнкции дают
xyzt
∨
x yzt = xyz. Полученные
выражения являются простыми импликантаим и, следовательно,
f=xzt
∨
x yz.
Алгоритм Куайна и Мак-Клоски (перечисления простых
импликантов)
Систематизируем изложенную выше идею.
1) Выпишем для функции
f СДНФ
Φ
.
2) В каждой элементарной конъюнкции все переменные будем
записывать в одинаковом порядке.
3) Каждую конъюнкцию будем представлять в виде
последовательности из
1, 0 и -, ставя на i-м месте 1, если i-я
переменная входит в конъюнкцию без отрицания,
0 - если с
отрицанием и
-, если не входит.
Например,
x
yz xz xt∨∨ запишем в виде 111-
∨
1-0-
∨
1- -0.
4) Образуем из элементарных конъюнкций группы, включая в
одну группу наборы с одинаковым числом единиц (группы, в
которых число единиц отличается на 1, называются соседними
);
расположим группы в порядке возрастания числа единиц.
Например, для функции
(, ,,)
f
x y z t xyzt xyzt xyzt xyzt xyzt xyzt xyzt=∨∨∨ ∨∨∨
элементарные конъюнкции представляются как
1101, 1001, 1100,
1000, 0010, 0001, 0000,
а список групп будет следующим:
0000
0001
0010
1000
1001
1100
1101
5) Равенство
γ
γ
γ
=
∨
x
x
может быть применимо только к
подходящим
парам наборов из соседних групп. Подходящая пара
образуется двумя наборами, отличающимися в одной позиции, и в
этой позиции не стоит черточка. Подходящие пары будем
отмечать звездочками (*).

Страницы