Кафедра информационных систем

Основы дискретной математики — вопрос 10

By 29.11.2007 No Comments

Вопрос 10
Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 10
Построение булевой формулы по комбинационной схеме

При построении булевой формулы по разветвленной комбинационной схеме прямая запись этой формулы с учетом параллельных и последовательных соединений контактов может привести к громоздкому выражению, которое затем необходимо упростить. В некоторых случаях оказывается весьма эффективной описываемая ниже процедура, которая позволяет сразу получить более простое выражение. Более того, ее использование дает возможность написать булеву формулу и для таких комбинационных схем, которые не могут быть выражены через последовательное и параллельное соединение контактов (например, мостовых). В этом последнем случае прямое написание булевой формулы по схеме оказывается невозможным.
Обратимся к совершенной дизъюнктивной нормальной форме представления булевой функции. Для булевой функции п переменных f(x1,x2,…xn) имеет вид логической суммы f(x1, х2,…, хn) = с1\/с2 \/…\/сk, где число слагаемых равно числу строк таблицы истинности, в которых f=1. Каждое слагаемое представляет собой логическое произведение, содержащее ровно п сомножителей, т.е. всех переменных, записанных либо без черты, либо с чертой Отсюда следует, что в каждом слагаемом обязательно имеется либо х1, либо нех1 и нет ни одного слагаемого, где присутствуют либо отсутствуют одновременно обе эти величины.

Применяя коммутативный закон, перенесем все слагаемые, в которые входит x1 (без черты), в начало формулы, а слагаемые, в которые входит нех1 (с чертой) — в ее оставшуюся часть:
f(x1,x2,…,xn) = (x1/\неx2/\…./\xn)\/…\/(x1/\неx2/\…./\неxn)\/…\/(неx1/\неx2/\…./\неxn)V…V \/(неx1/\неx2/\…./\неxn).
Здесь, как и ранее, через нех1, обозначено либо х1, либо неx1.
Применяя дистрибутивный закон, последнюю формулу можно записать как
f(x1,x2,…,xn)=x1/\f1(x2,..,xn)\/неx1/\f2(x2,…xn). (3.10)
Здесь логические функции f1 и f2 не зависят ни от x1, ни от нех1i. Они просто могут’ быть найдены из формулы (3.10). Действительно, полагая X1 = 1, обращаем в нуль ее второе слагаемое и имеем f1(x2,…,xn)=f(1,x2,…,xn).(3.11) Аналогично, полагая x1=0, получим f2(x2,….xn)=f(0,x2,…,xn). (3.11)
Соотношения (3.10) — (3.12) могут быть использованы как при упрощении булевых формул, так и, особенно, при написании булевых формуя, соответствующих заданной комбинационной схеме. Очевидно, что они могут применяться многократно к разным переменным.

Leave a Reply