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


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

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

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

 

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