2. Метод карт Карно.

1 итерация. Доопределим функцию единицами. Построим карты Карно для шести аргументов.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

По картам Карно выделяются компактные группы наибольшей размерности:

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

Компактных групп размерности 5 и 4 нет.

Компактные группы размерности 3: x₁x₅x₆, x₄x₅x₆, x₂x₅x₆, x₃x₅x₆, x₁x₃x₅, x₁x₂x₅, x₁x₂x₅, x₂x₄x₅, x₂x₃x₆, x₁x₂x₃, x₁x₂x₃, x₁x₄x₅, x₂x₃x₅, x₂x₃x₄.

Компактные группы размерности 2: x₃x₄x₅x₆, x₁x₃x₄x₅, x₂x₃x₄x₅, x₁x₃x₄x₆, x₁x₃x₄x₆, x₁x₂x₄x₆, x₁x₃x₄x₅, x₂x₃x₄x₆, x₁x₂x₄x₆, x₂x₃x₅x₆.

Компактные группы размерности 1: x₁x₃x₄x₅x₆, x₁x₂x₄ x₅x₆.

2 итерация. Находятся такие р-клетки, которые входят только в одну компактную группу. Компактные группы, в которые входят эти р-клетки, соответствуют ядру функции.

Ядро функции: x₃x₅x₆, x₂x₃x₆, x₁x₂x₃, x₁x₂x₃, x₂x₃x₄, x₃x₄x₅x₆, x₁x₃x₄x₆, x₁x₂x₄x₆.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

1

- р-клетки, накрываемые ядром функции.

3 итерация.

Пусть u и v – компактные группы. Компактная группа u исключается из дальнейшего рассмотрения, если:

1. размерность компактной группы u не больше чем размерность компактной группы v;

2. в компактную группу v входят все единицы компактной группы u.

В компактную группу x₁x₃x₅ входят все единицы компактной группы x₁x₂x₅, и она имеет такую же размерность.

В компактную группу x₂x₄x₅ входят все единицы компактной группы x₁x₄x₅, и она имеет такую же размерность.

Следовательно исключаются компактные группы x₁x₂x₅ и x₁x₄x₅.

Компактные группы x₁x₃x₅ и x₂x₄x₅ соответствуют псевдоядру первого уровня.

Псевдоядро первого уровня: x₁x₃x₅, x₂x₄x₅.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

1

- р-клетки, накрываемые ядром функции и псевдоядром первого уровня.

4 итерация. Никакие компактные группы нельзя исключить из рассмотрения. Выдвигаются гипотезы относительно любой компактной группы:

1. компактная группа не входит в тупиковую форму;

2. компактная группа входит в тупиковую форму.

Пусть компактная группа x₁x₃x₄x₅x₆ не входит в тупиковую форму. Находятся такие p-клетки, которые входят только в одну компактную группу(после исключения x₁x₃x₄x₅x₆). Компактные группы, в которые входят эти p-клетки соответствуют псевдоядру второго уровня

Псевдоядро второго уровня: x₂x₃x₅x₆, x₁x₂x₄x₆.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

1

- р-клетки, накрываемые ядром функции и псевдоядрами первого и второго уровней.

5 итерация.

В компактную группу x₁x₃x₄x₅ входят все единицы компактной группы x₁x₂x₄x₅x₆, и она имеет большую размерность.

В компактную группу x₁x₃x₄x₅ входят все единицы компактных групп x₂x₃x₄x₅, x₂x₃x₄x₆ и она имеет такую же размерность.

Следовательно, исключаются из рассмотрения компактные группы x₁x₂x₄x₅x₆, x₂x₃x₄x₅, x₂x₃x₄x₆.

Компактные группы x₁x₃x₄x₅ и x₁x₃x₄x₅ соответствуют псевдоядру третьего уровня.

Псевдоядро третьего уровня: x₁x₃x₄x₅ и x₁x₃x₄x₅

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

1

- р-клетки, накрываемые ядром функции и псевдоядрами первого, второго и третьего уровней.

6 итерация.

В компактную группу x₄x₅x₆ входят все единицы компактной группы x₁x₃x₄x₆, и она имеет большую размерность.

Следовательно, исключается из рассмотрения компактная группа x₁x₃x₄x₆,

Компактная группа x₄x₅x₆ соответствует псевдоядру четвертого уровня.

Псевдоядро четвертого уровня: x₄x₅x₆.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

На 6 итерации оставшиеся p-клетки были накрыты псевдоядром четвертого уровня.

Дизъюнкция, записанных в аналитическом виде, компактных групп(входящих в ядро и псевдоядра соответствующего уровня, полученных на 3-6 итерациях) дает тупиковую дизъюнктивную нормальную форму.

F₁(x)= x₃x₅x₆ v x₂x₃x₆ v x₁x₂x₃ v x₁x₂x₃ v x₂x₃x₄ v x₃x₄x₅x₆ v x₁x₃x₄x₆ v x₁x₂x₄x₆ v x₁x₃x₅ v x₂x₄x₅ v x₂x₃x₅x₆ v x₁x₂x₄x₆ v x₁x₃x₄x₅ v x₁x₃x₄x₅ v x₄x₅x₆.

Цена:52.

4.1 итерация. Возвращаемся к 4 итерации и выдвигаем обратную гипотезу: пусть компактная группа x₁x₃x₄x₅x₆ входит в ТДНФ.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

1

- р-клетки, накрываемые ядром функции, псевдоядром первого уровня(полученным на 3 итерации) и компактной группой x₁x₃x₄x₅x₆.

Никакие компактные группы нельзя исключить из рассмотрения. Выдвигаются гипотезы относительно любой компактной группы.

Пусть компактная группа x₁x₂x₄x₅x₆ не входит в тупиковую форму. Находятся такие p-клетки, которые входят только в одну компактную группу(после исключения x₁x₂x₄x₅x₆). Компактные группы, в которые входят эти p-клетки соответствуют псевдоядру второго уровня

Псевдоядро второго уровня: x₁x₃x₄x₅.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

1

- р-клетки, накрываемые ядром функции, псевдоядрами первого и второго уровней(полученных на 3,4.1 итерациях) и компактной группой x₁x₃x₄x₅x₆.

5.1 итерация.

В компактную группу x₂x₃x₄x₆ входят все единицы компактной группы x₂x₃x₅x₆, и она имеет такую же размерность.

Следовательно, исключается из рассмотрения компактная группа x₂x₃x₅x₆,

Компактная группа x₂x₃x₄x₆ соответствует псевдоядру третьего уровня.

Псевдоядро третьего уровня: x₂x₃x₄x₆.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

1

- р-клетки, накрываемые ядром функции, псевдоядрами первого, второго и третьего уровней(полученных на 3,4.1,5.1 итерациях) и компактной группой x₁x₃x₄x₅x₆.

6.1 итерация.

В компактную группу x₁x₂x₅ входят все единицы компактной группы x₁x₃x₄x₅, и она имеет большую размерность.

В компактную группу x₄x₅x₆ входят все единицы компактной группы x₁x₃x₄x₆, и она имеет большую размерность.

Следовательно, исключаются из рассмотрения компактные группы x₁x₃x₄x₅ и x₁x₃x₄x₆.

Компактные группы x₁x₂x₅ и x₄x₅x₆ соответствуют псевдоядру четвертого уровня.

Псевдоядро четвертого уровня: x₁x₂x₅ и x₄x₅x₆.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

На 6.1 итерации оставшиеся p-клетки были накрыты псевдоядром четвертого уровня.

Дизъюнкция, записанных в аналитическом виде, компактных групп(входящих в ядро и псевдоядра соответствующего уровня, полученных на 3,4.1,5.1,6.1 итерациях и компактная группа x₁x₃x₄x₅x₆, входящая в ТДНФ согласно выдвинутой гипотезе), дает тупиковую дизъюнктивную нормальную форму.

F₂(x)= x₃x₅x₆ v x₂x₃x₆ v x₁x₂x₃ v x₁x₂x₃ v x₂x₃x₄ v x₃x₄x₅x₆ v x₁x₃x₄x₆ v x₁x₂x₄x₆ v x₁x₃x₅ v x₂x₄x₅ v x₁x₃x₄x₅x₆ v x₁x₃x₄x₅ v x₂x₃x₄x₆ v x₁x₂x₅ v x₄x₅x₆

Цена:52.

4.2 итерация. Возвращаемся к 4.1 итерации и выдвигаем обратную гипотезу: пусть компактная группа x₁x₂x₄x₅x₆ входит в ТДНФ.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

1

- р-клетки, накрываемые ядром, псевдоядром первого уровня(полученным на 3 итерации), компактной группой x₁x₃x₄x₅x₆ и компактной группой x₁x₂x₄x₅x₆.

В компактную группу x₁x₃x₄x₆ входят все единицы компактной группы x₁x₃x₄x₅, и она имеет такую же размерность.

В компактную группу x₁x₃x₄x₅ входят все единицы компактных групп x₂x₃x₄x₅, x₂x₃x₄x₆ и она имеет такую же размерность.

Следовательно, исключаются из рассмотрения компактные группы x₁x₃x₄x₅, x₂x₃x₄x₅ и x₂x₃x₄x₆.

Компактные группы x₁x₃x₄x₆ и x₁x₃x₄x₅ соответствуют псевдоядру второго уровня.

Псевдоядро второго уровня: x₁x₃x₄x₆, x₁x₃x₄x₅.

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1	1	1	1
01	1	1		1
11		1	1	1
10	1	1		1

x1x2 x3x4	00	01	11	10
00	1	1		1
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

x₅x₆ x₅x₆

x1x2 x3x4	00	01	11	10
00	1			1
01	1		1	1
11		1	1
10		1	1	1

x1x2 x3x4	00	01	11	10
00		1		1
01	1		1	1
11		1
10	1	1

На 4.2 итерации оставшиеся p-клетки были накрыты псевдоядром второго уровня.

Дизъюнкция, записанных в аналитическом виде, компактных групп(входящих в ядро и псевдоядра соответствующего уровня, полученных на 3,4.2 итерациях и компактные группы x₁x₃x₄x₅x₆, x₁x₂x₄x₅x₆ входящие в ТДНФ согласно выдвинутым гипотезам), дает тупиковую дизъюнктивную нормальную форму.

F₃(x)= x₃x₅x₆ v x₂x₃x₆ v x₁x₂x₃ v x₁x₂x₃ v x₂x₃x₄ v x₃x₄x₅x₆ v x₁x₃x₄x₆ v x₁x₂x₄x₆ v x₁x₃x₅ v x₂x₄x₅ v x₁x₃x₄x₅x₆ v x₁x₂x₄x₅x₆ v x₁x₃x₄x₆ v x₁x₃x₄x₅.

Цена:51.

Оцениваются все полученные тупиковые формы: F₁(x), F₂(x), F₃(x). МДНФ – тупиковые формы, цена которых минимальна.

Минимальные дизъюнктивные нормальные формы:

F₃(x)= x₃x₅x₆ v x₂x₃x₆ v x₁x₂x₃ v x₁x₂x₃ v x₂x₃x₄ v x₃x₄x₅x₆ v x₁x₃x₄x₆ v x₁x₂x₄x₆ v x₁x₃x₅ v x₂x₄x₅ v x₁x₃x₄x₅x₆ v x₁x₂x₄x₅x₆ v x₁x₃x₄x₆ v x₁x₃x₄x₅.

Цена:51.

III Метод кубических покрытий.

1 шаг. Нахождение множества простых импликант. Исходным является псевдокомплекс K=L ∪D, где L – подмножество единичных значений функций, D – подмножество неопределенных значений функций.

L={000000, 000001, 000011, 000100, 000101, 000110, 000111, 001001, 001010, 010000, 010001, 010100, 010101, 011000, 011001, 011011, 011100, 011101, 011111, 100000, 100010, 100011, 100100, 100110, 100111, 101001, 101011, 101100, 101101, 110110, 110111, 111000, 111011, 111111}

D={001000, 001100, 010010, 011010, 011110, 100001, 100101, 101000, 110001, 110100, 111100, 111101}

Таким образом K={000000, 000001, 000011, 000100, 000101, 000110, 000111, 001000, 001001, 001010, 001100, 010000, 010001, 010010, 010100, 010101, 011000, 011001, 011010, 011011, 011100, 011101, 011110, 011111, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111, 101000, 101001, 101011, 101100, 101101, 110001, 110100, 110110, 110111, 111000, 111011, 111100, 111101, 111111}

С₀ – исходный комплекс, являющийся покрытием псевдокомплекса K функции f.

C₀={000000, 000001, 000011, 000100, 000101, 000110, 000111, 001000, 001001, 001010, 001100, 010000, 010001, 010010, 010100, 010101, 011000, 011001, 011010, 011011, 011100, 011101, 011110, 011111, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111, 101000, 101001, 101011, 101100, 101101, 110001, 110100, 110110, 110111, 111000, 111011, 111100, 111101, 111111}

1 итерация.

1) Выполняется операция С₀ *С₀( Операция “*” над всеми 0-кубами).

Результат операции C₀*C₀ см. Таблица 2.1

2) По результатам операции C₀*C₀ находится множество простых импликант 0-ранга(Z₀).

Z₀={c⁰ _∈C₀ | c⁰*C₀ не даёт никакой 1-куб}

Множество Z₀ – такие 0-кубы, которые в результате операции “*” не дают никакой 1-куб.

Z₀=Ø

3) Строится Ĉ₁=C₀∪(C₀*C₀)

Затем из Ĉ₁ удаляются кубы, которые содержатся в кубах большей размерности и удаляется Z₀

C₁=Ĉ₁ – {c | c ⊆d, c,d ∈ Ĉ₁} – Z₀

C₁={00000x, 000x00, 00x000, 0x0000, x00000, 0000x1, 000x01, 00x001, 0x0001, x00001, 000x11, x00011, 00010x, 0001x0, 00x100, 0x0100, x00100, 0001x1, 0x0101, x00101, 00011x, x00110, x00111, 00100x, 0010x0, 001x00, 0x1000, x01000, 0x1001, x01001, 0x1010, 0x1100, x01100, 01000x, 0100x0, 010x00, 01x000, 010x01, 01x001, x10001, 01x010, 01010x, 01x100, x10100, 01x101, 01100x, 0110x0, 011x00, x11000, 0110x1, 011x01, 01101x, 011x10, 011x11, x11011, 01110x, 011x0, x11100, 0111x1, x11101, 01111x, x11111, 10000x, 1000x0, 100x00, 10x000, 1000x1, 100x01, 10x001, 1x0001, 10001x, 100x10, 100x11, 10x011, 10010x, 1001x0, 10x100, 1x0100, 1001x1, 10x101, 10011x, 1x0110, 1x0111, 10100x, 101x00, 1x1000, 1010x1, 101x01, 1x1011, 10110x, 1x1100, 1x1101, 1101x0, 11x100, 11011x, 11x111, 111x00, 111x11, 11110x, 1111x1}

2 итерация.

1) Выполняется операция С₁*С₁. Результат операции см. Таблица 2.2.

2) По результатам операции C₁*C₁ находится множество простых импликант 1-ранга(Z₁).

Z₁={c¹ _∈C₁ | c¹*C₁ не даёт никакой 2-куб}

Множество Z₁ – такие 1-кубы, которые в результате операции “*” не дают никакой 2-куб.

Z₁={1x1011, 11x111}

3) Строится Ĉ₂=C₁∪(C₁*C₁)

Затем из Ĉ₂ удаляются кубы, которые содержатся в кубах большей размерности и удаляется Z₁

C₂=Ĉ₂ – {c | c ⊆d, c,d ∈ Ĉ₂} – Z₁

C₂={000x0x, 00x00x, 0x000x, x0000x, 00xx00, 0x0x00, x00x00, 000xx1, x000x1, 0x0x01, x00x01, 0xx001, x0x001, xx0001, x00x11, 0001xx, 0x010x, x0010x, x001x0, 0xx100, x0x100, xx0100, x001x1, x0011x, 0x100x, x0100x, 0x10x0, 0x1x00, x01x00, xx1000, xx1100, 010x0x, 01x00x, 01x0x0, 01xx00, 01xx01, 01x10x, x1x100, 0110xx, 011x0x, 011xx0, x11x00, 011xx1, 011x1x, x11x11, 0111xx, x1110x, x111x1, 1000xx, 100x0x, 10x00x, 100xx0, 10xx00, 100xx1, 10x0x1, 10xx01, 100x1x, 1001xx, 10x10x, 1x01x0, 1xx100, 1x011x, 101x0x, 1x1x00, 1x110x}

3 итерация.

1) Выполняется операция С₂*С₂. Результат операции см. Таблица 2.3.

2) По результатам операции C₂*C₂ находится множество простых импликант 2-ранга(Z₂).

Z₂={c² _∈C₂ | c²*C₂ не даёт никакой 3-куб}

Множество Z₂ – такие 2-кубы, которые в результате операции “*” не дают никакой 3-куб.

Z₂={xx0001, 0x10x0, 01x0x0, x11x11, x1110x, x111x1, 10x0x1, 1x01x0, 1x011x, 1x110x}

3) Строится Ĉ₃=C₂∪(C₂*C₂)

Затем из Ĉ₃ удаляются кубы, которые содержатся в кубах большей размерности и удаляется Z₂

C₃=Ĉ₃ – {c | c ⊆d, c,d ∈ Ĉ₃} – Z₂

C₃={0x0x0x, x00x0x, 0xx00x, x0x00x, 0xxx00, x0xx00, x00xx1, x001xx, xxx100, xx1x00, 01xx0x, 011xxx, 100xxx, 10xx0x}

4 итерация.

1) Выполняется операция С₃*С₃. Результат операции см. Таблица 2.4.

2) По результатам операции C₃*C₃ находится множество простых импликант 3-ранга(Z₃).

Z₃={c³ _∈C₃ | c³*C₃ не даёт никакой 4-куб}

Множество Z₃ – такие 3-кубы, которые в результате операции “*” не дают никакой 4-куб.

Z₃={0x0x0x, x00x0x, 0xx00x, x0x00x, 0xxx00, x0xx00, x00xx1, x001xx, xxx100, xx1x00, 01xx0x, 011xxx, 100xxx, 10xx0x}

3) Строится Ĉ₄=C₃∪(C₃*C₃)

Затем из Ĉ₄ удаляются кубы, которые содержатся в кубах большей размерности и удаляется Z₃

C₄=Ĉ₄ – {c | c ⊆d, c,d ∈ Ĉ₄} – Z₃

С₄=Ø

На 4 итерации множество С – пустое. Множество простых импликант

Z=Z₀∪Z₁∪Z₂∪Z₃

Z={1x1011, 11x111, xx0001, 0x10x0, 01x0x0, x11x11, x1110x, x111x1, 10x0x1, 1x01x0, 1x011x, 1x110x, 0x0x0x, x00x0x, 0xx00x, x0x00x, 0xxx00, x0xx00, x00xx1, x001xx, xxx100, xx1x00, 01xx0x, 011xxx, 100xxx, 10xx0x }

2 шаг. Нахождение из полученного множества Z подмножества кубов, которое является покрытием исходного псевдокомплекса и цена покрытия должна быть минимальна.

1 итерация. Исходные данные:

Z₀={1x1011, 11x111, xx0001, 0x10x0, 01x0x0, x11x11, x1110x, x111x1, 10x0x1, 1x01x0, 1x011x, 1x110x, 0x0x0x, x00x0x, 0xx00x, x0x00x, 0xxx00, x0xx00, x00xx1, x001xx, xxx100, xx1x00, 01xx0x, 011xxx, 100xxx, 10xx0x }

L₀={000000, 000001, 000011, 000100, 000101, 000110, 000111, 001001, 001010, 010000, 010001, 010100, 010101, 011000, 011001, 011011, 011100, 011101, 011111, 100000, 100010, 100011, 100100, 100110, 100111, 101001, 101011, 101100, 101101, 110110, 110111, 111000, 111011, 111111}

1) Выполняется операция e#(Z₀-e), e∈Z₀

Т.е берется простая импликанта e и и из неё вычитаются оставшиеся простые импликанты(без e). Если e#(Z-e)≠Ø тогда простая импликанта e является кандидатом на экстремаль. Чтобы получить множество экстремалей 0-ранга(E₀) необходимо выполнить операцию: (e#(Z₀-e))∩L₀, где e – кандидат на экстремаль. Если (e#(Z₀-e))∩L₀≠Ø тогда e является экстремалью.

Выполнение операции e#(Z₀-e)

v – отмечены строки, соответствующие кандидатам на экстремаль(e).

см. Таблица 2.5.

2) Выполняется (e#(Z₀-e))∩L₀≠Ø

E₀={0x10x0, x00xx1, x001xx, xx1x00, 100xxx} – множество экстремалей 0-ранга

3) Получение L₁=L₀#E₀. См Таблица 6.

L₁={000000, 001001, 010000, 010001, 010100, 010101, 011001, 011011, 011101, 011111, 101001, 101011, 101101, 110110, 110111, 111011, 111111}

4)

Ž₁=Z₀ – E₀. Ž₁={1x1011, 11x111, xx0001, 01x0x0, x11x11, x1110x, x111x1, 10x0x1, 1x01x0, 1x011x, 1x110x, 0x0x0x, x00x0x, 0xx00x, x0x00x, 0xxx00, x0xx00, xxx100, 01xx0x, 011xxx, 10xx0x}

Производится упорядочивание Ž₁=>Z₁.

^ - отмечены кубы исключающиеся из дальнейшего рассмотрения.

До упорядочивания:

000000

001001

010000

010001

010100

010101

011001

011011

011101

011111

101001

101011

101101

110110

110111

111011

111111

1x1011

+

+

11x111

+

+

xx0001^

+

01x0x0^

+

x11x11

+

+

+

+

x1110x^

+

x111x1

+

+

+

10x0x1

+

+

1x01x0^

+

1x011x

+

+

1x110x^

+

0x0x0x

+

+

+

+

+

x00x0x^

+

0xx00x

+

+

+

+

+

x0x00x

+

+

+

0xxx00^

+

+

+

x0xx00^

+

xxx100^

+

01xx0x

+

+

+

+

+

+

011xxx

+

+

+

+

10xx0x

+

+

После упорядочивания:

000000

001001

010000

010001

010100

010101

011001

011011

011101

011111

101001

101011

101101

110110

110111

111011

111111

1x1011

+

+

11x111

+

+

x11x11

+

+

+

+

x111x1

+

+

+

10x0x1

+

+

1x011x

+

+

0x0x0x

+

+

+

+

+

0xx00x

+

+

+

+

+

x0x00x

+

+

+

01xx0x

+

+

+

+

+

+

011xxx

+

+

+

+

10xx0x

+

+

Z₁={ 1x1011, 11x111, x11x11, x111x1, 10x0x1, 1x011x, 0x0x0x, 0xx00x, x0x00x, 01xx0x, 011xxx, 10xx0x}

2 итерация. Исходные данные:

Z₁={ 1x1011, 11x111, x11x11, x111x1, 10x0x1, 1x011x, 0x0x0x, 0xx00x, x0x00x, 01xx0x, 011xxx, 10xx0x}

L₁={000000, 001001, 010000, 010001, 010100, 010101, 011001, 011011, 011101, 011111, 101001, 101011, 101101, 110110, 110111, 111011, 111111}

1) Выполняется операция e#(Z₁-e), e∈Z₁

Выполнение операции e#(Z₁-e) см. Таблица 7.

v – отмечены строки, соответствующие кандидатам на экстремаль(e).

2) Выполняется (e#(Z₁-e))∩L₁≠Ø

E₁={1x011x, 10xx0x}

3) Получение L₂=L₁#E₁.

			1x011x			10xx0x
000000	001001	010000	000000	001001	010000	000000	001001	010000
010001	010100	010101	010001	010100	010101	010001	010100	010101
011001	011011	011101	011001	011011	011101	011001	011011	011101
011111	101001	101011	011111	101001	101011	011111	Ø	101011
101101	110110	110111	101101	Ø	Ø	Ø	110110	110111
111011		111111	111011		111111	111011		111111

L₂={000000, 001001, 010000, 010001, 010100, 010101, 011001, 011011, 011101, 011111, 101011, 111011, 111111}

4)

Ž₂=Z₁ – E₁. Ž₂={1x1011, 11x111, x11x11, x111x1, 10x0x1, 0x0x0x, 0xx00x, x0x00x, 01xx0x, 011xxx,}

Производится упорядочивание Ž₂=>Z₂.

До упорядочивания:

000000

001001

010000

010001

010100

010101

011001

011011

011101

011111

101011

111011

111111

1x1011

+

+

11x111 ^

+

x11x11

+

+

+

+

x111x1

+

+

+

10x0x1

+

0x0x0x

+

+

+

+

+

0xx00x

+

+

+

+

+

x0x00x ^

+

+

01xx0x

+

+

+

+

+

+

011xxx

+

+

+

+

После упорядочивания:

000000

001001

010000

010001

010100

010101

011001

011011

011101

011111

101011

111011

111111

1x1011

+

+

x11x11

+

+

+

+

x111x1

+

+

+

10x0x1

+

0x0x0x

+

+

+

+

+

0xx00x

+

+

+

+

+

01xx0x

+

+

+

+

+

+

011xxx

+

+

+

+

Z₂={1x1011, x11x11, x111x1, 10x0x1, 0x0x0x, 0xx00x, 01xx0x, 011xxx}

3 итерация. Исходные данные:

Z₂={1x1011, x11x11, x111x1, 10x0x1, 0x0x0x, 0xx00x, 01xx0x, 011xxx}

L₂={000000, 001001, 010000, 010001, 010100, 010101, 011001, 011011, 011101, 011111, 101011, 111011, 111111}

1) Выполняется операция e#(Z₂-e), e∈Z₂

	1x1011	x11x11	x111x1	10x0x1	0x0x0x	0xx00x	01xx0x	011xxx
1x1011	-	101011	101011	Ø	Ø	Ø	Ø	Ø
x11x11	x11111 011x11	-	011011	011011	011011	011011	011011	Ø
x111x1	x111x1	x11101	-	x11101	x11101	x11101	111101	111101	v
10x0x1	10x001 1000x1	10x001 1000x1	10x001 1000x1	-	10x001 1000x1	10x001 1000x1	10x0011000x1	10x0011000x1	v
0x0x0x	0x0x0x	0x0x0x	0x0x0x	0x0x0x	-	0x010x	00010x	00010x	v
0xx00x	0xx00x	0xx00x	0xx00x	0xx00x	0x100x	-	00100x	00100x	v
01xx0x	01xx0x	01xx0x	01xx00 01x00x 010x0x	01xx00 01x00x 010x0x	011x00 01100x	011100	-	Ø
011xxx	011xxx	011xx0011x0x	011xx0 011x00 01100x	011xx0 011x00 01100x	011xx0 011x00 01100x	011x10 0111x0 011100	011x10011110	-	v

v – отмечены строки, соответствующие кандидатам на экстремаль(e).

2) Выполняется (e#(Z₂-e))∩L₂≠Ø

E₂={0xx00x}

3) Получение L₃=L₂#E₂.

			0xx00x
000000	001001	010000	Ø	Ø	Ø
010001	010100	010101	Ø	010100	010101
011001	011011	011101	Ø	011011	011101
011111	101011	111011	011111	101011	111011
	111111			111111

L₃={010100, 010101, 011011, 011101, 011111, 101011, 111011, 111111}

4)

Ž₃=Z₂ – E₂. Ž₃={1x1011, x11x11, x111x1, 10x0x1, 0x0x0x, 01xx0x, 011xxx}

Производится упорядочивание Ž₃=>Z₃.

До упорядочивания:

	010100	010101	011011	011101	011111	101011	111011	111111
1x1011						+	+
x11x11			+		+		+	+
x111x1				+	+			+
10x0x1						+
0x0x0x ^	+	+
01xx0x	+	+		+
011xxx			+	+	+

После упорядочивания:

	010100	010101	011011	011101	011111	101011	111011	111111
1x1011						+	+
x11x11			+		+		+	+
x111x1				+	+			+
10x0x1						+
01xx0x	+	+		+
011xxx			+	+	+

Z₃={1x1011, x11x11, x111x1, 10x0x1, 01xx0x, 011xxx}

4 итерация. Исходные данные:

Z₃={1x1011, x11x11, x111x1, 10x0x1, 01xx0x, 011xxx}

L₃={010100, 010101, 011011, 011101, 011111, 101011, 111011, 111111}

1) Выполняется операция e#(Z₃-e), e∈Z₃

	1x1011	x11x11	x111x1	10x0x1	01xx0x	011xxx
1x1011	-	101011	101011	Ø	Ø	Ø
x11x11	x11111 011x11	-	011011	011011	011011	Ø
x111x1	x111x1	x11101	-	x11101	111101	111101	v
10x0x1	10x001 1000x1	10x001 1000x1	10x001 1000x1	-	10x001 1000x1	10x001 1000x1	v
01xx0x	01xx0x	01xx0x	01xx00 01x00x 010x0x	01xx00 01x00x 010x0x	-	010x00 01000x 010x0x	v
011xxx	011xxx	011xx0 011x0x	011xx0 011x00 01100x	011xx0 011x00 01100x	011x10	-	v

v – отмечены строки, соответствующие кандидатам на экстремаль(e).

2) Выполняется (e#(Z₃-e))∩L₃≠Ø

E₃={01xx0x}

3) Получение L₄=L₃#E₃.

	01xx0x
010100	Ø
010101	Ø
011011	011011
011101	Ø
011111	011111
101011	101011
111011	111011
111111	111111

L₄={011011, 011111, 101011, 111011, 111111}

4)

Ž₄=Z₃ – E₃. Ž₄={1x1011, x11x11, x111x1, 10x0x1, 011xxx}

Производится упорядочивание Ž₄=>Z₄.

До упорядочивания:

	011011	011111	101011	111011	111111
1x1011			+	+
x11x11	+	+		+	+
x111x1^		+			+
10x0x1			+
011xxx	+	+

После упорядочивания:

	011011	011111	101011	111011	111111
1x1011			+	+
x11x11	+	+		+	+
10x0x1			+
011xxx	+	+

Z₄={1x1011, x11x11, 10x0x1, 011xxx}

5 итерация. Исходные данные:

Z₄={1x1011, x11x11, 10x0x1, 011xxx }

L₄={011011, 011111, 101011, 111011, 111111}

1) Выполняется операция e#(Z₄-e), e∈Z₄

	1x1011	x11x11	10x0x1	011xxx
1x1011	-	101011	Ø	Ø
x11x11	x11111 011x11	-	x11111 011x11	111111	v
10x0x1	10x001 1000x1	10x001 1000x1	-	10x001 1000x1	v
011xxx	011xxx	011xx0 011x0x	011xx0 011x0x	-	v

v – отмечены строки, соответствующие кандидатам на экстремаль(e).

2) Выполняется (e#(Z₄-e))∩L₄≠Ø

E₄={x11x11}

3) Получение L₅=L₄#E₄.

	x11x11
011011	Ø
011111	Ø
101011	101011
111011	Ø
111111	Ø

L₅={101011}

4)

Ž₅=Z₄ – E₄. Ž₅={1x1011, 10x0x1, 011xxx}

Производится упорядочивание Ž₅=>Z₅.

До упорядочивания:

	101011
1x1011^	+
10x0x1	+
011xxx

После упорядочивания:

	101011
10x0x1	+

Z₅={10x0x1}

6 итерация. Исходные данные:

Z₅={10x0x1}

L₅={101011}

1) Выполняется операция e#(Z₅-e), e∈Z₅

	10x0x1
10x0x1	-

E₅={10x0x1}

2 ) Получение L₆=L₅#E₅

	10x0x1
101011	Ø

L₆=Ø

3) Ž₆=Z₅ – E₅=Ø; Ž₆=>Z₆=Ø

На 6 итерации подмножество единичных значений(L) стало пустым. Множество экстремалей:

E=E₀∪E₁∪E₂∪E₃∪E₄∪E₅

E={0x10x0, x00xx1, x001xx, xx1x00, 100xxx, 1x011x, 10xx0x, 0xx00x, 01xx0x, x11x11, 10x0x1}

Дизъюнкция, записанных в аналитическом виде, всех полученных экстремалей, дает нам тупиковую дизъюнктивную нормальную форму.

F₁(x)=x₁x₃x₄x₆ v x₂x₃x₆ v x₂x₃x₄ v x₃x₅x₆ v x₁x₂x₃ v x₁x₃x₄x₅ v x₁x₂x₅ v x₁x₄x₅ v x₁x₂x₅ v x₂x₃x₅x₆ v x₁x₂x₄x₆. Цена:37.

Оцениваются все полученные тупиковые формы. МДНФ – тупиковые формы, цена которых минимальна.

Минимальные дизъюнктивные нормальные формы:

F₁(x)=x₁x₃x₄x₆ v x₂x₃x₆ v x₂x₃x₄ v x₃x₅x₆ v x₁x₂x₃ v x₁x₃x₄x₅ v x₁x₂x₅ v x₁x₄x₅ v x₁x₂x₅ v x₂x₃x₅x₆ v x₁x₂x₄x₆. Цена:37.