Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf

Введем следующие обозначения:

Anl = xl V х2. V *■■V

^ /1 2 = %\Х2 V *И'3V ‘ ‘ ‘ V ^н—l-’Oj»

Теорема. Если на каком-либо множестве симметричных наборов

щие всем наборам множества (а), то среди них найдется и такая конъюнкция, у которой s, = ViТаким образом, согласно соотноше­

ниям (2.42), левая часть выражения (4.24) на наборе у принимает

значение / (s). В свою очередь, поскольку

A \r ~ = Pi,

т\х—у

правая часть выражения (4.24) также принимает значение / (s) на

выбранном наборе.

—* —►

Пусть теперь х = у не совпадает ни с одним из наборов множест-

ва {а}. Тогда левая часть соотношения (4.24) равна Ь. Но так как

V 6 {а}, то -у не может быть решением системы уравнений (4.23). Поэтому найдется такое г, для которого

99

Следовательно, правая часть (4.24) также равна Ь. Поскольку набор у был выбран произвольно, то теорема доказана.

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

На любом наборе из множества {а} симметричная функция прини­

мает одно и то же значение / (ос). Поэтому симметричную функцию мож­ но полностью определить, если известны ее значения на всех N (п, к) множествах симметричных наборов. Следовательно, число различных симметричных функций равно kN{n-kK

Назовем базовой симметричной функцией S n (ос, х) такую функцию,

которая равна а на всех наборах а ( (а) и b на всех остальных на­ борах, то есть

-» - \а при х = сс £ (ос),

(Ь при х = а £ {а}.

Каждому множеству симметричных наборов соответствует одна базо­ вая симметричная функция. Следовательно, число различных функций

S n(ос, х) равно N (п, k). Для любой из них

f (х) можно представить в виде дизъюнкции базовых симметричных функций

100

Теорема. Произвольную симметричную функцию можно предста­ вить канонической формой

Доказательство теоремы легко вывести из выражений (4.25) и

лютно минимальное представление сумму по mod 2 в булевой алгебре

ные теоремы справедливы при простом k. Если же k не является простым числом, то некоторые решения системы (4.23) могут принад­ лежать различным множествам симметричных наборов и в таком слу­

101

Таким образом, представление симметричной функции, согласно (4.27), содержит

дизъюнктивных членов, в то время как совершенная ДНФ содержит

Следовательно, использование формулы (4.27) позволяет уже на уровне канонического представления значительно упростить схемы, реализу­ ющие симметричные многозначные функции.

§ 4.4. Минимизация симметричных многозначных функций

Форма представления симметричной многозначной функции со­ гласно (4.27), как и ее совершенная ДНФ, является избыточной фор­ мой представления функций и ее можно минимизировать [1 0 ].

Введем некоторые определения. Назовем симметричным аналогом совершенной ДНФ выражение (4.27). Функции А т-, введенные в

предыдущем параграфе, назовем симметричными аналогами аргумен­ тов xt.

Есть две возможности минимизации симметричных функций. ВоперЕых, можно минимизировать известными методами [191 совершен­ ную ДНФ симметричной функции, а затем с помощью соотношений, аналогичных соотношению (4.26), в минимальной ДНФ заменять ар­ гументы х( их симметричными аналогами. Во-вторых, как и для обыч­ ных совершенных ДНФ, можно ввести понятия симметричных анало­ гов элементарных произведений, импликант, а также сокращенных, тупиковых и минимальных ДНФ, которые будут отличаться от обыч­ ных только тем, что в роли аргументов выступают их симметричные аналоги Ащ.

Первый способ не всегда дает симметричный аналог минимальной ДНФ симметричной функции. Действительно, совершенная ДНФ функции

/ (х, i/) = 1А (х) J 3 (у) V 2А (X) J 3 (у) V ЗА (X) j 3 (У) V

V 1А (х) J 1 (у) V 2Уз (х) А (у)

при к > 5 совпадает с ее минимальной ДНФ, в то время как симмет­ ричный аналог ДНФ этой функции

f (•*->у ) = lA (Ai) А (Аг) V 2A (АО J2 (АО V ЗА (АО А (Аг)

можно упростить и записать как

} (х, у) = АгА (АО-

102

Остановимся на втором способе минимизации симметричных функ­ ций. Выпишем для дальнейшего рассмотрения главные соотношения (здесь и далее вместо A nt подставим А {).

либо k — 1 , то есть, буква х может быть или не быть в соответствую­ щем выражении. Соотношения (4.30) — (4.32) позволяют по симмет­ ричному аналогу ДНФ восстановить симметричный аналог совершен­ ной ДНФ любой симметричной функции.

Как уже отмечалось, задача минимизации симметричной функции сводится к отысканию ее простых импликант (в данном случае их сим­ метричных аналогов), так как найти тупиковые и минимальные ДНФ можно известными методами, например с помощью импликантных матриц. Для отыскания простых импликант необходимы соотношения склеивания и поглощения. Как и в [191, будем считать, что функция /i поглощает функцию /2, если на всех наборах > /2. В дальнейшем слова «симметричный аналог» будем опускать, так как речь будет идти только о симметричных функциях.

Простой импликантой называют такое элементарное произведение, являющееся импликантой, которое не поглощается другим элементар­ ным произведением, также являющимся импликантой данной функ­ ции. Если же два элементарных произведения — это импликанты, равны друг другу и не поглощаются никаким третьим элементарным произведением, являющимся импликантой, то простой импликантой считают произведение, содержащее меньше букв. Например, если

A (-А) А (Л) и A (-A) J 1 {A-А J 1 (^з)

являются импликантами симметричной функции, то простой импликан­ той считают первую из них. Рассмотрим выражения

103