Утверждение о максимальных интервалах и тупиковых покрытиях

 

 

Утверждение 1 : Любая минимальная ДНФ может состоять только из максимальных интервалов.

Утверждение 2 : Любая минимальная ДНФ - есть тупиковое покрытие.

Докажем утверждение 1:

Допустим противное, что некоторая минимальная ДНФ k₁Ú k₂Ú ...Ú k_s содержит немаксимальный интервал k₁ . Это означает, что из интервала k₁ можно удалить множитель , так что полученный интервал k₁^/ так же будет допустимым.

Заменим интервал k₁ на k₁^/ в начальной ДНФ функции f. Нетрудно видеть, что полученная ДНФ k₁^/ Ú k₂Ú ...Ú k_s также представляет функцию f.

Действительно, в силу одного из предыдущих утверждений интервал k₁ Í k₁^/ . Это означает, что любая единица, которая была покрыта интервалом k₁, будет покрыта интервалом k₁^/. Все остальные единицы были покрыты оставшимися интервалами. Они же покрыты интервалами (оставшимися) в полученной ДНФ. Таким образом, все единицы функции f покрыты полученными интервалами. И все интервалы данного набора являются допустимыми. Поэтому полученная ДНФ является покрытием и поэтому представляет функцию f. Но сложность полученной ДНФ меньше, чем сложность первоначальной, т. к. в интервале k₁ был удален некоторый множитель.

Отсюда следует противоречие. Мы получили ДНФ, сложность которой меньше чем сложность первоначальной.

 

Пример: Рассмотрим булеву функцию x₁ x₃ Ú x₂ x₃ Ú x₁ и рассмотрим покрытие соответствующее данной функции.

 

x1x3

x2x3

Действительно, это покрытие, но данное покрытие не можетсоответствовать минимальной ДНФ из-за того что интервалы x₁x₃ и x₁ не являются максимальными.

Действительно, из интервала x₁x₃ можно удалить множитель x₃ и получится допустимый интервал x₁. И сложность ДНФ, которая так же является покрытием, уменьшится на 1.

Поэтому первоначальное покрытие не может быть минимальным. В данном примере минимальная ДНФ есть x₁ Ú x₂ x₃ . Д/з.

Докажем утверждение 2:

Любая минимальная ДНФ есть тупиковое покрытие.

Допустим противное, что есть минимальная ДНФ k₁Ú k₂Ú ...Ú k_s, которая не является тупиковым покрытием. Это означает, что в ДНФ есть интервал k₁ (для определенности), удаление которого все равно приведет к покрытию k₂Ú ...Ú k_s, т. е. полученное покрытие будет представлять булеву функцию, но сложность полученной ДНФ для данного покрытия меньше чем сложность первоначальной ДНФ на величину ранга удаленной конъюнкции. Поэтому первоначальная ДНФ не может является минимальной.

 

Из данных двух утверждений следует, что минимальная ДНФ содержится в множестве всевозможных тупиковых, состоящих из максимальных интервалов.

 

Замечание: Тупиковая ДНФ не обязательно является минимальной.

Например: x₁ x₃ Ú x₂ x₃ Ú x₁ . Действительно, данные интервалы составляют тупиковое покрытие. Но данная ДНФ не является минимальной.

Данное утверждение не верно даже если предполагать, что тупиковая ДНФ состоит только из максимальных интервалов.

Пример:

Максимальными интервалами являются 6 ребер: k₁ , k₂ , k₃, k₄, k₅, k₆. Они действительно являются максимальными, ни одно из ребер не содержится в допустимой грани. Допустимых граней здесь нет.

Не трудно видеть, что k₁ , k₂ , k₄ , k₅ является тупиковым покрытием. Действительно, все интервалы допустимы и максимальны, и при удалении любого интервала получаем не покрытие. Но данное тупиковое покрытие максимальными интервалами минимальным не является. В данном примере существует покрытие меньшей сложности, которое покрывает все вершины, а сложность этого покрытия меньше: k₁, k₃, k₅,.

Ответ: Минимальные ДНФ следующие:

 

Таким образом, алгоритм нахождения минимальной ДНФ будет проводиться в два этапа: на первом найдем все максимальные интервалы функции f, а на втором — все тупиковые покрытия максимальными интервалами, и выделим из них покрытия минимальной сложности. Это и будут все минимальные ДНФ функции f.

 

Геометрический метод нахождения всех минимальных ДНФ функции f.

001 011

 

101 111

 

 

000 010

 

100 110

 

Первый этап:

Рассмотрим пример. В нем максимальные интервалы x₁ и x₂ . Действительно, x₁ является допустимым, он состоит целиком из единиц функции f, удаление множителя x₁ из данного интервала дает интервал константу 1. Это все вершины булевого куба. Вершина 000 единицей не является. Поэтому const 1 — весь булев куб допустимым интервалом не является. Поэтому интервал x₁ является максимальным.

Интервал x₂ так же является максимальным.

 

 

Второй этап:

Найдем все тупиковые покрытия. Получаем единственное покрытие, состоящее из всех максимальных интервалов. Действительно, интервал x₂ обязательно должен принадлежать покрытию, т.к. только данный максимальный интервал покрывает вершину 011.

Интервал x₁ также обязан принадлежать покрытию, т.к. только данный максимальный интервал покрывает вершину 100.

Таким образом, множество всех тупиковых покрытий максимальными интервалами состоит из единственного покрытия, которое и является единственным минимальным.

Поэтому получаем единственную минимальную ДНФ .

 

Рассмотрим функцию от трех переменных.

 

1 этап:

Находим максимальные интервалы данной функции. Их будет 4. Это четыре ребра: x₁ , x₁ x₂ , x₂ x₃ , x₃ .

K4

K3

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

Первый этап завершен.

 

2 этап:

Найти все тупиковые покрытия.

 

; .

И других тупиковых покрытий нет.

Действительно, интервал обязан входить в любое покрытие , т.к. только он покрывает вершину 100. Интервал обязан входить в любое покрытие, т.к. только он покрывает вершину 001. Остаются два интервала ; , из которых достаточно взять только один интервал , чтобы покрыть вершину 111. Сложность тупиковых покрытий одинакова. Это и есть все минимальные ДНФ данной функции.

Ответ: