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

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

By 29.11.2007 No Comments

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

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

Вопрос 11 Упрощение булевых формул
Для упрощения булевых формул используются рассмотренные выше законы и тождества булевой алгебры. Их успешное применение зависит от навыка и искусства обращения с ними, что достигается после приобретения некоторого опыта в подобных преобразованиях. Однако существуют некоторме стандартные приемы, которые во многих случаях позволяют успешно проводить упрощение сложной формулы.
Упрощение булевых формул следует начинать с отыскания одной из следующих форм:
f/\неg\/f/\g, (f\/неg)/\(f\/g); f\/f/\g,, f/\(f\/g); f\/неf/\g, f/\(неf V g) .
где f и g означают или сами логические переменные или некоторые булевы функции нескольких переменных. Каждое из указанкых выражений можно записать в более простом виде:
f/\неg\/f/\g=f, (f\/неg)/\(f\/g)=f (закон склеивания),(3.13)
f\/f/\g =f, f/\(f\/g) =f (закон поглощения),(3.14)
f\/неf/\g=f\/g, f/\(неf\/g)=f/\g (тождества 7би7а п.3.9). (3.15)
Это, соответственно, приводит к упрощению всей исходной булевой формулы. При упрощении логических формул всегда следует иметь в виду тождество идемпотентности f\/f=f, из которого следует, что каждое из слагаемых можно использовать в комбинациях с другими слагаемыми неоднократно.
Слагаемое называется лишним, если на любом из наборов переменных, на котором оно обращается в единицу, в единицу же обращается какая-либо группа других слагаемых. Из всех форм, не содержащих лишних слагаемых, методом полного перебора отыскивается простейшая. Таких форм может быть несколько.

Leave a Reply