Вычислительная техника. Захаров Н.Г - 21 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

21
в которых функция может быть записана единственным образом. Такие формы назы-
вают совершенными дизъюнктивными нормальными формами (СДНФ).
СДНФ определяется как сумма элементарных произведений, в которых каждая
переменная встречается ровно один раз либо с отрицанием, либо без него.
Для преобразования функции (2.2) в СДНФ необходимо дополнить каждое
элементарное произведение недостающими переменными так, чтобы тождествен-
ность преобразования не была нарушена:
f(x
l,
x
2
, x
3
) = )хх(хххх)хх(хххх
332132112132
.
После раскрытия скобок и приведения подобных членов, получим функцию,
записанную в СДНФ:
.ххххххххх
)хххххххххххх ) x, x,f(x
321321321
32132132132132l
(2.3)
Здесь каждая переменная (или ее отрицание) содержится по одному разу в каж-
дом элементарном произведении. Функция (2.3) обращается в логическую единицу
при трех различных комбинациях значений входных переменных:
х
1
= 1, х
2
= 0, х
3
= 1 – первая комбинация;
х
1
= 0, х
2
= 0, х
3
= 1 – вторая комбинация;
х
1
= 1, х
2
= 0, х
3
= 0 – третья комбинация.
Для каждой комбинации соответствующее элементарное произведение равно
единице, для всех остальных комбинаций входных переменных – нулю.
Таблица истинности такой функции (таблица 2.3) содержит три строки, в кото-
рых функция равна 1.
Таблица 2.3
x
l
х
2
x
3
f(x
l,
x
2
, x
3
)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0

Страницы