Минимальные формы булевых многочленов (стр. 2 из 4)

1. АÚВ=В

2. АÙВ=А

3. АÚВ=U

4. АÙВ`=Æ

Любая конечная булева алгебра может содержать лишь 2 в степени nэлементов, где n– натуральное число.

Пример 2. 1)Множество делителей 70-ти D=<1,2,5,7,10,14,35,70>. Множество A=<2,5,7> -множество атомов решетки D.

10=2Ú5

14=2Ú7

35=5Ú7

70=(2Ú 5) Ú 7

70

10

14 35

2 5 7

1

2) Множество А={2,5,7}

Отношение вложенности.

{2,5,7}

{2,5} {2,7} {5,7}

{2} {5} {7}

Æ

Эта решетка изоморфна предыдущей.

Алгебра множеств и алгебра высказываний являются моделями абстрактной булевой алгебры. Все абстрактные булевы алгебры (которые состоят из одинакового числа элементов) изоморфны.

1.3Минимальные формы булевых многочленов

Определение. Понятие булева многочлена определяется рекурсивно. Пусть Х_n= {x₁,…, x_n} – множество из n символов (называемых неизвестными или переменными), которое не содержит символов 0 и 1. Булевы многочлены над Х_n суть объекты, которые могут быть получены последовательным применением следующих правил:

(I) х₁, х₂, …, х_n, 0,1 – булевы многочлены;

(II) если p и q – булевы многочлены, то таковыми являются и

(p) Ù (q), (p) Ú (q), (p)¢.

Обозначим множество всех булевых многочленов над Х_nчерез Р_n.

Пример. Вот несколько примеров булевых многочленов над {х₁, х₂}:0,1, х₁, х_2, х₁ Ù х₂, х₁ Ú х₂, х₁¢,х₁¢Ù х₂.

Так как любой булев многочлен над x₁,…, x_nмодно рассматривать как булев многочлен над x₁,…, x_n, x_n+1, мы имеем

Р₁Ì Р₂Ì… Ì Р_nÌ Р_n+1 Ì…

Булев многочлен можно упростить с помощью аксиом булевой алгебры. В процессе упрощения часто трудно решить, какие аксиомы и в каком порядке должны быть использованы. Но существуют некоторые систематические методы упрощения булевых многочленов. Недостатком большинства этих методов является возможность их практического внедрения, когда число переменных слишком велико. Соответствующая проблематика в теории булевых алгебр носит общее название проблема оптимизации или минимизации булевых многочленов; она важна для таких приложений, как упрощение переключательных схем.

Определение. Назовем литералом любую переменную х_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’