Вопросы к зачету часть1 (Вопросы к зачету (ответы)), страница 7

С ростом числа аргументов число неизбыточных покрытий для абсолютного большинства функций растет чрезвычайно быстро ([11], раздел 3), поэтому описанный метод минимизации применим лишь к функциям от небольшого числа аргументов.

При большом числе аргументов наиболее трудоемким является этап, связанный с отысканием наилучшего покрытия (система простых импликантов находится сравнительно просто). Для осуществления этого этапа обычно используются приближенные методы, не гарантирующие минимальности построенной д. н. ф. Одни из них состоит в следующем. Если в импликантной таблице имеются строки, содержащие по одному символу* (см. строки 0011, 0110, 1011 и 1101 табл. 2.10), то покрывающие их импликанты (в данном случае А4, А1, A5) входят в любую д. н. ф. Они включаются в покрытие и соответствующие им столбцы, и покрываемые ими строки вычеркиваются из таблицы. Дальнейший выбор импликантов осуществляется с использованием следующей пошаговой процедуры. В новой таблице берется столбец с наибольшим числом символов * (если таких столбцов несколько, то любой из них). Этот столбец и строки, в которых он содержит *, из таблицы вычеркиваются, а соответствующий импликант включается в покрытие. К полученной таблице применяется та же операция и т. д., пока все строки не окажутся

Таблица 2.14

Импликантная таблица для данного примера приведена в таблице 2.14. Образуем функцию

F == (a1Va2) (a1Va2Va3) a4(a5Va6V a7).

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

f =A1VA4VA5=x1x4Vx2x3Vx3x4.

Н а практике построение д. н. ф. обычно является промежуточным этапом, после чего осуществляется упрощение формулы путем группировки и вынесения за скобки. В данном случае группировка приводит к формуле х1х4Vx3(х2Vx4), содержащей 5 символов переменных (ср. с реализациями (2.5) и (2.6), полученными в §2.2).

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

Сложность м.д.н.ф.

Рассмотрим вопрос о том, сколь сложными могут быть м. д. н. ф. функций от n аргументов (под сложностью д. н. ф. будем понимать число входящих в нее символов переменных).

Рассмотрим линейную функцию l_n (x₁, x₂, . . ., x_n) = x₁? x₂?…? x_n.

На соседних наборах (различающихся в одной компоненте) она принимает разные значения. Поэтому никакие два единичных набора этой функции не склеиваются, и ее м. д. н. ф. совпадает с с. д. н. ф. Функция l_n(x₁,x₂, ..,x_n) принимает 2^n-1 единичных значений (на всех наборах длины n с нечетным числом единиц), и каждому из них в с. д. н, ф. соответствует конъюнкция длины n.

Поэтому с. д. н. ф. (а следовательно, и м. д. н. ф.) этой функции содержит n2^n-1 символов переменных. Покажем, что м. д. н. ф. любой функции f(x₁, x₂,...,x_n) от n аргументов не сложнее, чем у l_n (x₁, x₂,...,x_n). Рассмотрим все единичные наборы функции f. Отбрасыванием последней компоненты образуем из них укороченные наборы длины n-1. Каждому укороченному набору (σ_1,….,σ_n-1) следующим образом сопоставим конъюнкцию. Если функция f имеет единственный единичный набор (σ_1,….,σ_n-1,σ_n) , совпадающий с укороченным в первых n-1 компонентах, то в качестве конъюнкции возьмем x^σ1_1…x^σn_in, а если таких единичных наборов два, то возьмем x^σ1_1…x^σn-1_in-1. Дизъюнкции всех полученных конъюнкций совпадает с f, ибо каждый единичный набор (σ_1,….,σ_n-1,σ_n), не имеющий соседнего по последней компоненте, реализуется индивидуально конъюнкцией x^σ1_1…x^σn_in, а всякая пара соседних наборов (σ_1,….,σ_n-1,σ_n,0) и (σ_1,….,σ_n-1,σ_n,1)-укороченной конъюнкцией x^σ1_1…x^σn-1_in-1. Число конъюнкций в полученной д.н.ф. совпадает с числом укороченных наборов и не превосходит 2^n-1 (общего числа наборов длины n-1). Поэтому сложность этой д.н.ф. (а следовательно, и м. д. н. ф.) не выше n2^n-1. Из процесса доказательства нетрудно заключить, что м. д. н. ф. максимальной сложности n2^n-1 имеют лишь две линейные функции от n аргументов:

l_n (x₁, x₂, . . ., x_n) = x₁? x₂?…? x_n.

Определение 1. Дизъюнктивная нормальная форма называется минимальной (сокращенно МДНФ), если она имеет наименьшую длину среди всех равносильных ей ДНФ.

Определение 2. Элементарная конъюнкция вида

, (1)

где и и для всех s , называется импликантой функции , если она входит в какую-нибудь ДНФ, представляющую функцию

Заметим, что последнее условие можно сформулировать иначе. Например, оно равносильно каждому из условий:

а)

б)

В общем случае, если

то говорят, что функция поглощается функцией , или поглощается .

Следовательно, можно сказать, что импликанта функции есть элементарная конъюнкция вида (1), которая поглощается функцией .

Определение 3. Импликанта функции называется простой, если никакая ее собственная часть не является импликантой функции . Импликанту функции , вида

назовем совершенной.

Лемма 1. Пусть , - импликанты функции . Импликанта поглощает тогда и только тогда, когда является частью импликанты .

Пусть есть часть , т. е. = ’. Тогда по закону поглощения ’ , т. е.

. (2)

Обратно, пусть имеет место (2) и не есть часть . Тогда содержит сомножитель , который не входит в . Возможны два случая:

а) не содержит переменного ;

б) содержит множитель .

Так как содержит , то может принимать значение 1 лишь при . В то же время из условий “а” и “б” видно, что существует набор значений переменных, в котором = и ( ) = 1. Таким образом, = 1, а = 0, что противоречит условию (2).

Значение простых импликант объясняется следующим утверждением.

Теорема 1. Всякая импликанта функции содержащаяся в какой-либо МДНФ функции , является простой.

В самом деле, пусть

… (3)

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

f. (4)

Из леммы 1 следует, что

(5)

Из равенств (3)-(5) имеем:

= ( .

Так как ( ) < ( ), то (3) не есть МДНФ функции . Полученное противоречие доказывает теорему 1.

Таким образом, всякая МДНФ функции составляется из ее простых импликант.

Определение 4. Дизъюнкция всех простых импликант функции называется сокращенной ДНФ функции .

Так как каждая импликанта функции поглощается некоторой ее простой импликантой, то сокращенная ДНФ функции f представляет функцию .

Определение 5. ДНФ

функции f называется тупиковой если - простые импликанты и

при любом .

Из всего сказанного виден путь нахождения МДНФ функции сначала находим сокращенную ДНФ, затем все тупиковые ДНФ. Тупиковые ДНФ наименьшей длины и будут минимальными ДНФ.

Ниже будет показано, как найти сокращенную ДНФ и все тупиковые ДНФ функции.

Заметим, что при небольших значениях n (например, при n = 2, 3, 4, 5) МДНФ функции можно находить из следующих наглядных соображений.

Назовем множество

: 1}

n-мерным единичным кубом, а каждый набор ( ) – вершиной этого куба. Каждой функции f( ) сопоставим множество

N

В частности, множество сопоставленное элементарной конъюнкции

где при ,назовем гранью размерности или ранга . Ясно, что грань состоит из всех наборов значений переменных , в которых а значения остальных переменных произвольны: .