Курсовая работа: Минимальные формы булевых многочленов

Определение. Назовем литералом любую переменную х _i и ее дополнение х _i ¢ , а также 0 и 1 . Под произведением понимается произведение нескольких литералов, т.е. булев многочлен, в котором нет знака + . Дизъюнктивным выражением или просто выражением назовем буле многочлен, являющийся суммой произведений. Слагаемые в таком выражении назовем дизъюнктами.

Обсуждая упрощение булевых многочленов, мы ограничимся важным случаем сведения дизъюнктивных выражений к «минимальным выражениям» относительно специального условия минимальности. Обозначим через d_f общее число литералов в выражении f , а через e_f – число дизъюнктов. Мы говорим, что выражение f проще выражения j , если d_f £ d_g , e_f £ e_g и хотя бы одно из этих неравенств строгое. Выражение f называется минимальным, если не существует выражения, которое было бы эквивалентно f и проще f . Таким образом, мы будем искать «кратчайшее» выражение с наименьшим возможным числом литералов, которое было бы эквивалентно f . Такое минимальное выражение не всегда определено однозначно. Я опишу один из нескольких существующих методов упрощения. Он основан на работе Куайна и был улучшен Мак-Класки, поэтому называется методом Куайна - Мак-Класки.

Определение. многочлен p влечет многочлен q, если для любых b ₁ ,…., b_n Î В

р_в ( b ₁ , …, b_n ) = 1 влечет q _в ( b ₁ , …, b_n ) = 1;

в этом случае р называется импликантом для q . Простым импликантом многочлена р называется произведение , которое влечет р , но если в вычеркнуть хотя бы один сомножитель, то результат уже не влечет р . Произведение, сомножители-литералы которого образуют подмножество сомножителей-литералов другого произведения, называется подпроизведением последнего.

Пример. Произведение х₁ х₃ является подпроизведением как х₁ х₂ х_{3 ,} так и х₁ х₂ ¢ х₃ , и влечет выражение

р = х₁ х₂ х₃ + х₁ х₂ ¢ х₃ + х₁ ¢ х₂ ¢ х₃ ¢ ,

поскольку (х₁ х₃ )(1, i ₂ , 1) = 1 и р(1, i ₂ , 1) = 1 , а для других значений аргументов х₁ х₃ дает 0. Ни х_{1 ,} ни х₃ не влекут р ; например, х₁ (1, 1, 0) = 1 , но р(1, 1, 0) = 0 , поэтому х₁ х₃ – простой импликант для р.

Теорема. Любой многочлен р Î P_n эквивалентен сумме всех своих простых импликантов.

Выражение, являющееся суммой простых импликантов для р , называется неприводимым, если оно эквивалентно р , но пересекает быть таковым, если удалить хотя бы одно слагаемое. Минимальное выражение должно быть неприводимым. Поэтому, чтобы определить минимальное выражение, мы находим все неприводимые выражения, а среди них ищем выражение с наименьшим числом литералов. Изложим теперь принадлежащий Куайну метод определения простых импликантов.

Простые импликанты получаются из дизъюнктивной нормальной формы d булева многочлена р применением (слева направо) правила

yz + yz ¢ ~ y ,

когда это возможно. Более общо, мы используем правило

(*)

где и - произведения. следующий пример поможет понять смысл описываемой процедуры.

Пример. Пусть р – булев многочлен, имеющий следующую дизъюнктивную нормальную форму:

d = wxyz ’ + wxy ’ z ’ + wx ’ yz + wx ’ yz ’ + w ’ x ’ yz + w ’ x ’ yz ’ + w ’ x ’ y ’ z

Мы используем правило и законы идемпотентности для тех (из общего числа () = 21 ) пар дизъюнктов в d , для которых это возможно, тем самым «укорачивая» произведения. например, превый и второй дизъюнкты при использовании (*) дают wxz ’ . Если в процессе упрощения слагаемые используются хотя бы один раз, то оно помечается. Так как знак + стоит вместо Ú , выражение может быть использовано любое число раз, но помечается не более одного раза. Таким образом, все помеченные произведения содержат более короткие произведения и поэтому не могут быть простыми импликантами. В целом в первом раунде этого процесса мы переходим

от wxyz ’ и wxy ’ z ’ к wxz ’

от wx ’ yz и wx ’ yz ’ к wx ’ y

от wxyz ’ и wx ’ yz ’ к wyz ’

от w ’ x ’ yz и w ’ x ’ yz ’ к w ’ x ’ y

от w ’ x ’ yz и w ’ x ’ y ’ z к w ’ x ’ z

от wx ’ yz и w ’ x ’ yz к x ’ yz

от wx ’ yz ’ и w ’ x ’ yz ’ к x ’ yz ’

Здесь использованы, и потому должны быть помечены, все семь слагаемых.

В общем, эта процедура повторяется снова и снова с использованием только помеченных выражений (которые становятся короче). Прочие произведения суть простые импликанты и остаются неизменными.

В нашем примере второй раунд упрощения осуществляет переход

от wx ’ y и w ’ x ’ y к x ’ y