Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - вопрос 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) могут быть использованы как при упрощении булевых формул, так и, особенно, при написании булевых формуя, соответствующих заданной комбинационной схеме. Очевидно, что они могут применяться многократно к разным переменным.

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным