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

Доказательство.

Убедимся вначале, что простые импликанты монотонной (функции f не содержат отрицаний переменных). Предположим противное, что имеется

п ростой импликант x^σ1_i1,… ,x_ij,..., x^σp_ip, содержащий отрицание некоторой переменной x_ij. На всех таких наборах, что x_i1=σ1,…., x_ij=0_,…., x_ip= σp этот импликант равен 1 и по определению импликанта f=1.

И з монотонности f вытекает, что она обращается в 1 и на всех наборах, у которых x_i1=σ1,…., x_ij=1_,…., x_ip=σp. Это означает, что x^σ1_i1…x_ij…x^σp_ip также является импликантом. К паре конъюнкций x^σ1_i1…x_ij…x^σp_ip и x^σ1_i1…x_ij…x^σp_ip

применима операция склеивания, приводящая к удалению переменной x_ij. Поэтому импликант x^σ1_i1…x_ij…x^σp_ip не может быть простым.

Докажем теперь утверждение теоремы. Рассмотрим произвольный простой импликант g= x_i1…x_ip. Образуем набор σ, положив x_i1==…=x_ip, а остальные

переменные - равными 0. На наборе σ импликант g обращается в 1, поэтому и

f(σ)=1. Любой другой простой импликант x_i1…x_iq на наборе σ равен 0. В противном случае все переменные x_i1,…,x_iq должны содержаться среди x_i1…x_ip и импликант x_i1…x_ip не будет простым (вычеркиванием из него можно образовать x_i1…x_iq). Таким образом, на наборе σ дизъюнкция всех простых импликантов, отличных от g , равна 0 и, поскольку f(σ)=1, простой импликант g необходимо включить в м. д. н. ф. Теорема доказана.

Приведем некоторые с л е д с т в и я.

1. Из процесса доказательства следует, что функция (тождественно не равная 0 и 1) является монотонной тогда и только тогда, когда она может быть представлена формулой в базисе {&, V}. Действительно, если функция монотонна, то ее м. д. н. ф. не содержит отрицаний переменных и является формулой в базисе {&, V}. Обратно, поскольку функции x1&x2 и х1Vх2 монотонны, их суперпозиция, задаваемая произвольной формулой в базисе

{&, V}, также монотонна (класс монотонных функций замкнут).

2. Если функция f представлена в виде д. н. ф., конъюнкции которой не содержат отрицаний переменных, и ни одна из этих конъюнкций не поглощает другую (не может быть получена из другой вычеркиванием переменных), то это представление совпадает c м. д. н.ф. Действительно, любая конъюнкция Ki, входящая в представление, является импликантои. Если из Ki вычеркнуть некоторую переменную, то полученная конъюнкция Ki` импликантом не будет (положив все переменные, входящие в Ki`, равными 1, а остальные - равными 0, получим набор, на котором Ki`==l, a f=0). Таким образом, все конъюнкции, содержащиеся в рассматриваемом представлении, являются простыми импликантами. По предыдущему следствию функция f монотонна и в силу теоремы 2.2 это представление совпадает с м. д. н. ф.

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

Формирование м. д. н. ф.

Перейдем к описанию метода построения м. д. н. ф. из простых импликантов для произвольной функции f. Обозначим через A1, А2,…,АS все простые импликанты функции f. Будем говорить, что импликанты А_i1, А_i2,…., А_it образуют покрытие функции f, если А_i1 VА_i2 V …. V А_it = f.

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

Б удем говорить, что конъюнкция К покрывает набор ά, если на наборе ά она обращается в 1. Заметим, что в этом случае представляющий набор конъюнкции получается из ά заменой некоторых компонент прочерками. Так, например, конъюнкция x1x3, задаваемая набором 1 - 0 -, покрывает наборы 1OOO, 1001, 1100 и 1101. Ясно, что множество импликантов образует покрытие функции f тогда и только тогда, когда для каждого набора ά такого, что f(ά)=1, в этом множестве содержится импликант, покрывающий ά. Построим по функции f импликантную таблицу. Ее строки соответствуют единичным наборам функции f, а столбцы - простым импликантам. В пересечении строки ά и столбца Аi; проставляется *, если импликант Аi покрывает набор ά (в противном случае клетка оставляется пустой), Множество импликантов образует покрытие функции f, если столбцы, соответствующие имиликантам этого множества, содержат * в каждой строке.

В качестве примера рассмотрим функцию f(x1,x2,x3,x4), задаваемую таблицей 2.8. Как мы видели (см. табл. 2.9), ее простыми импликантами являются конъюнкции A1 == x1x2x4, А2=x2x3, А3=x3x4, A4=x2x4 и A5=x1x3.

Импликантная таблица функции f приведена в таблице 2.10.

С импликантом Аi, будем связывать логическую переменную аi: (принимающую значения 0 и 1). Каждому множеству импликантов приписывается набор значений

Таблица 2.10

переменных ai: если импликант Ai входит в множество, то ai = 1, если нет, то

ai=0. Рассмотрим строку таблицы покрытий, соответствующую некоторому набору ά. Пусть в этой строке символы * находятся в столбцах А_i1, А_i2,…., А_iv.

Строка ά будет покрытой тогда и только тогда, когда в множество включен хотя бы один из импликантов А_i1, А_i2,…., А_iv , т. е. когда дизъюнкция

a_i1 Va_i2 V …. V a_iv равна 1. Составим такую дизъюнкцию для каждой строки импликантной таблицы и возьмем их произведение по всем строкам. Полученную функцию обозначим через F. В частности, функция,

соответствующая таблице 2.10, имеет вид

F = (а2Va3) (а2Vа4)а4(a1Va3)a1(a2Va3Va5)& (a2Va4Va5)a4(a3Va5).

Множество импликаптов образует покрытие тогда и только тогда, когда набор значений переменных аi, соответствующий этому покрытию, обращает функцию F в единицу, ибо равенство F=1 имеет место тогда и только тогда, когда все скобки равны 1, т. с. когда все строки покрыты.

Преобразуем формулу, задающую функцию F. Вначале с использованием правила поглощения (Ф1VФ2)Ф1=Ф1 удалим более длинные скобки (т.е. такие, что из них вычеркиванием некоторых членов можно получить другие скобки). Затем на основе свойства дистрибутивности раскроем все скобки, в результате чего получим выражение вида дизъюнкции конъюнкций. И, наконец, пользуясь правилом поглощения Ф1VФ1Ф2=Ф1, удалим более длинные конъюнкции

(т. е. такие, что из них вычеркиванием некоторых переменных можно получить другие конъюнкции). В результате придём к представлению

F = V a_i1a _i2… a _ip,

(i₁, i₂,…, i_p)?I

в котором отсутствуют поглощения конъюнкций (дизъюнкция берется по некоторому множеству I наборов (i₁, i₂,…, i_p). По следствию 1 к теореме 2.2 (функция F является монотонной, а по следствию 2 представление (2.11) совпадает с м.д.н.ф. и является дизъюнкцией всех простых импликантов). Отсюда вытекает, что функция F имеет единственное представление вида (2.11).

Осуществим указанные преобразования применительно к функции F из рассматриваемого примера. Вычеркивание более длинных скобок дает выражение F =(a2Va3)а4а1а5. Раскрывая скобки, получаем представление вида (2.11)

F = а1а2а4а5 V а1а3а4а5. (2.12)

Теорема 2.3. Всякой конъюнкции a_i1a _i2… a _ip, входящей в представление (2.11) функции F, соответствует неизбыточное покрытие {A_i1A _i2… A_ip} функции f и, наоборот, всякому неизбыточному покрытию {A_i1A _i2… A_ip} соответствует конъюнкция a_i1a _i2…a _ip представления (2.11).

Доказательство.

Рассмотрим произвольную конъюнкцию a_i1a _i2… a _ip из представления (2.11).

Согласно сказанному выше она является простым импликантом функции F.

Полагая a_i1=a _i2=_…=a _ip=1, остальные переменные равными 0, получаем F = 1.

Отсюда заключаем, что множество {A_i1A_i2…A_ip}образует покрытие. Предположим, что оно избыточно и при удалении из A_ip, например, снова получается покрытие. Тогда на наборе a_i1=a_i2=_…=a_ip-1=1, a_i=0 (i?i₁,… i_p-1) функция F обращается в 1. В силу монотонности она равна 1 и на всяком другом наборе, где a_i1=a_i2=_…=a_ip-1=1 . Поэтому конъюнкция a_i1=a_i2=_…=a_ip-1 является импликантом, а это противоречит тому, что импликант a_i1=a_i2=_…=a_ip простой. Таким образом, покрытие {A_i1A_i2…A_ip} неизбыточно.

Обратно, пусть имеется неизбыточное покрытие {A_i1A_i2…A_ip}.

Полагая a_i1=a_i2=_…=a_ip=1, а остальные переменные равными 0, получаем F=1 (поскольку {A_i1A_i2…A_ip}- покрытие). В силу монотонности F обращается в 1 на всех наборах, где a_i1=a_i2=_…=a_ip=1. Поэтому a_i1…a_ip является импликантом. Если бы он не был простым, и в нем можно было вычеркнуть, например, a_ip, то на наборе a_i1=a_i2=_…=a_ip-1=1 функция F равнялась бы 1 и множество

{A_i1A_i2…A_ip-1}образовывало бы покрытие. Это противоречит неизбыточности покрытия {A_i1A_i2…A_ip}.

Теорема доказана.

Таким образом, представление (2.11) задает все неизбыточмые покрытия функции f. Из них могут быть выбраны покрытия, соответствующие м.д.н.ф.

Продолжим рассмотрение примера. Представление (2.12) показывает, что имеются 2 неизбыточных покрытия: {A1,А2,А4,А5} и {A1,А3,А4,А5}. Им соответствуют д.н.ф., содержащие по 9 вхождений символов переменных, поэтому каждая из них является минимальной.

Таким образом, f имеет две м. д. н. ф.:

f = A1VA2V A4VA5=x1x2x4Vx2x3Vx2x4Vx1x3,

f = A1VA3V A4VA5=x1x2x4Vx3x4Vx2x4Vx1x3.

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

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