Метод Квайна

Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Южно-Уральский Государственный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Семестровая.docx

Скачиваний:

Добавлен:

15.07.2019

Размер:

280.69 Кб

Скачать

☆

<<< < Предыдущая 12 / 42 3 4 > Следующая >>>

Метод Квайна

1 шаг. Нахождение из совершенной дизъюнктивной нормальной формы сокращенную дизъюнктивную нормальную форму.

1 итерация. Доопределим функцию нулями. Выполняются все возможные операции неполного попарного склеивания и элементарного поглощения для элементарных конъюнкций длины 6(конституенты 1).

Построим таблицу 1.1 в которой укажем все конституенты единицы исходной функции и отметим являются ли эти импликанты поглощенными.

Таблица 1.1

№	Элементарные конъюнкции(конституенты 1)	Отметка о поглощении
1	x₁x₂x₃x₄x₅x₆	+
2	x₁x₂x₃x₄x₅x₆	+
3	x₁x₂x₃x₄x₅x₆	+
4	x₁x₂x₃x₄x₅x₆	+
5	x₁x₂x₃x₄x₅x₆	+
6	x₁x₂x₃x₄x₅x₆	+
7	x₁x₂x₃x₄x₅x₆	+
8	x₁x₂x₃x₄x₅x₆	+
9	x₁x₂x₃x₄x₅x₆	-
10	x₁x₂x₃x₄x₅x₆	+
11	x₁x₂x₃x₄x₅x₆	+
12	x₁x₂x₃x₄x₅x₆	+
13	x₁x₂x₃x₄x₅x₆	+
14	x₁x₂x₃x₄x₅x₆	+
15	x₁x₂x₃x₄x₅x₆	+
16	x₁x₂x₃x₄x₅x₆	+
17	x₁x₂x₃x₄x₅x₆	+
18	x₁x₂x₃x₄x₅x₆	+
19	x₁x₂x₃x₄x₅x₆	+
20	x₁x₂x₃x₄x₅x₆	+
21	x₁x₂x₃x₄x₅x₆	+
22	x₁x₂x₃x₄x₅x₆	+
23	x₁x₂x₃x₄x₅x₆	+
24	x₁x₂x₃x₄x₅x₆	+
25	x₁x₂x₃x₄x₅x₆	+
26	x₁x₂x₃x₄x₅x₆	+
27	x₁x₂x₃x₄x₅x₆	+
28	x₁x₂x₃x₄x₅x₆	+
29	x₁x₂x₃x₄x₅x₆	+
30	x₁x₂x₃x₄x₅x₆	+
31	x₁x₂x₃x₄x₅x₆	+
32	x₁x₂x₃x₄x₅x₆	+
33	x₁x₂x₃x₄x₅x₆	+
34	x₁x₂x₃x₄x₅x₆	+

Выполним операции неполного попарного склеивания. Запишем в таблицу 1.2 результат операции.

Таблица 1.2

Номера склеиваемых конъюнкций	Результат склеивания
1-2	x₁x₂x₃x₄x₅
1-4	x₁x₂x₃x₅x₆
1-10	x₁x₃x₄x₅x₆
1-20	x₂x₃x₄x₅x₆
2-3	x₁x₂x₃x₄x₆
2-5	x₁x₂x₃x₅x₆
2-8	x₁x₂x₄x₅x₆
2-11	x₁x₃x₄x₅x₆
3-7	x₁x₂x₃x₅x₆
3-22	x₂x₃x₄x₅x₆
4-5	x₁x₂x₃x₄x₅
4-6	x₁x₂x₃x₄x₆
4-12	x₁x₃x₄x₅x₆
4-23	x₂x₃x₄x₅x₆
5-7	x₁x₂x₃x₄x₆
5-13	x₁x₃x₄x₅x₆
6-7	x₁x₂x₃x₄x₅
6-24	x₂x₃x₄x₅x₆
7-25	x₂x₃x₄x₅x₆
8-15	x₁x₃x₄x₅x₆
8-26	x₂x₃x₄x₅x₆
10-11	x₁x₂x₃x₄x₅
10-12	x₁x₂x₃x₅x₆
10-14	x₁x₂x₄x₅x₆
11-13	x₁x₂x₃x₅x₆
11-15	x₁x₂x₄x₅x₆
12-13	x₁x₂x₃x₄x₅
12-17	x₁x₂x₄x₅x₆
13-18	x₁x₂x₄x₅x₆
14-15	x₁x₂x₃x₄x₅
14-17	x₁x₂x₃x₅x₆
14-32	x₂x₃x₄x₅x₆
15-16	x₁x₂x₃x₄x₆
15-18	x₁x₂x₃x₅x₆
16-19	x₁x₂x₃x₅x₆
16-33	x₂x₃x₄x₅x₆
17-18	x₁x₂x₃x₄x₅
18-19	x₁x₂x₃x₄x₆
19-34	x₂x₃x₄x₅x₆
20-21	x₁x₂x₃x₄x₆
20-23	x₁x₂x₃x₅x₆
21-22	x₁x₂x₃x₄x₅
21-24	x₁x₂x₃x₅x₆
22-25	x₁x₂x₃x₅x₆
22-27	x₁x₂x₄x₅x₆
23-24	x₁x₂x₃x₄x₆
23-28	x₁x₂x₄x₅x₆
24-25	x₁x₂x₃x₄x₅
24-30	x₁x₃x₄x₅x₆
25-31	x₁x₃x₄x₅x₆
26-27	x₁x₂x₃x₄x₆
26-29	x₁x₂x₃x₅x₆
27-33	x₁x₃x₄x₅x₆
28-29	x₁x₂x₃x₄x₅
30-31	x₁x₂x₃x₄x₅
31-34	x₁x₂x₄x₅x₆
33-34	x₁x₂x₃x₅x₆

В результате на 1 итерации 33 импликанты участвовали в операции склеивания и поглотились своими собственными частями. Одна импликанта не участвовала в операции склеивания, она образует множество Z₀ – множество простых импликант 0-ранга.

Z₀={ x₁x₂x₃x₄x₅x₆}

2 итерация. Выполняются все возможные операции неполного попарного склеивания и элементарного поглощения для элементарных конъюнкций длины 5(полученные в результате операции склеивания на 1 итерации).

Построим таблицу 1.3 в которой укажем элементарные конъюнкции длины 5, полученные в результате операции склеивания на 1 итерации и отметим являются ли они поглощенными.

Таблица 1.3

№	Элементарные конъюнкции длины 5	Отметка о поглощении
1	x₁x₂x₃x₄x₅	+
2	x₁x₂x₃x₅x₆	+
3	x₁x₃x₄x₅x₆	+
4	x₂x₃x₄x₅x₆	+
5	x₁x₂x₃x₄x₆	+
6	x₁x₂x₃x₅x₆	+
7	x₁x₂x₄x₅x₆	+
8	x₁x₃x₄x₅x₆	+
9	x₁x₂x₃x₅x₆	+
10	x₂x₃x₄x₅x₆	+
11	x₁x₂x₃x₄x₅	+
12	x₁x₂x₃x₄x₆	+
13	x₁x₃x₄x₅x₆	+
14	x₂x₃x₄x₅x₆	+
15	x₁x₂x₃x₄x₆	+
16	x₁x₃x₄x₅x₆	+
17	x₁x₂x₃x₄x₅	+
18	x₂x₃x₄x₅x₆	+
19	x₂x₃x₄x₅x₆	+
20	x₁x₃x₄x₅x₆	+
21	x₂x₃x₄x₅x₆	-
22	x₁x₂x₃x₄x₅	+
23	x₁x₂x₃x₅x₆	+
24	x₁x₂x₄x₅x₆	+
25	x₁x₂x₃x₅x₆	+
26	x₁x₂x₄x₅x₆	+
27	x₁x₂x₃x₄x₅	+
28	x₁x₂x₄x₅x₆	+
29	x₁x₂x₄x₅x₆	+
30	x₁x₂x₃x₄x₅	+
31	x₁x₂x₃x₅x₆	+
32	x₂x₃x₄x₅x₆	-
33	x₁x₂x₃x₄x₆	+
34	x₁x₂x₃x₅x₆	+
35	x₁x₂x₃x₅x₆	+
36	x₂x₃x₄x₅x₆	+
37	x₁x₂x₃x₄x₅	+
38	x₁x₂x₃x₄x₆	+
39	x₂x₃x₄x₅x₆	+
40	x₁x₂x₃x₄x₆	+
41	x₁x₂x₃x₅x₆	+
42	x₁x₂x₃x₄x₅	+
43	x₁x₂x₃x₅x₆	+
44	x₁x₂x₃x₅x₆	+
45	x₁x₂x₄x₅x₆	-
46	x₁x₂x₃x₄x₆	+
47	x₁x₂x₄x₅x₆	-
48	x₁x₂x₃x₄x₅	+
49	x₁x₃x₄x₅x₆	+
50	x₁x₃x₄x₅x₆	+
51	x₁x₂x₃x₄x₆	-
52	x₁x₂x₃x₅x₆	-
53	x₁x₃x₄x₅x₆	-
54	x₁x₂x₃x₄x₅	-
55	x₁x₂x₃x₄x₅	+
56	x₁x₂x₄x₅x₆	-
57	x₁x₂x₃x₅x₆	+

Выполним операции неполного попарного склеивания. Запишем в таблицу 1.4 результат операции.

Таблица 1.4

Номера склеиваемых конъюнкций	Результат склеивания
1-11	x₁x₂x₃x₅
1-22	x₁x₃x₄x₅
2-6	x₁x₂x₃x₅
2-23	x₁x₃x₅x₆
2-41	x₂x₃x₅x₆
3-8	x₁x₃x₄x₅
3-13	x₁x₃x₅x₆
4-14	x₂x₃x₅x₆
5-15	x₁x₂x₃x₆
6-9	x₁x₂x₃x₆
6-25	x₁x₃x₅x₆
7-26	x₁x₄x₅x₆
8-16	x₁x₃x₅x₆
8-20	x₁x₄x₅x₆
9-44	x₂x₃x₅x₆
10-19	x₂x₃x₅x₆
11-17	x₁x₂x₃x₄
11-27	x₁x₃x₄x₅
12-15	x₁x₂x₃x₄
12-46	x₂x₃x₄x₆
13-16	x₁x₃x₄x₅
14-18	x₂x₃x₄x₆
17-48	x₂x₃x₄x₅
18-19	x₂x₃x₄x₅
22-27	x₁x₂x₃x₅
22-30	x₁x₂x₄x₅
23-25	x₁x₂x₃x₅
23-31	x₁x₂x₅x₆
24-26	x₁x₂x₄x₅
24-28	x₁x₂x₅x₆
25-34	x₁x₂x₅x₆
26-29	x₁x₂x₅x₆
27-37	x₁x₂x₄x₅
28-29	x₁x₂x₄x₅
30-37	x₁x₂x₃x₅
31-34	x₁x₂x₃x₅
33-38	x₁x₂x₃x₆
34-35	x₁x₂x₃x₆
35-57	x₂x₃x₅x₆
36-39	x₂x₃x₅x₆
40-46	x₁x₂x₃x₆
41-43	x₁x₂x₃x₆
42-48	x₁x₂x₃x₅
43-44	x₁x₂x₃x₅
48-55	x₁x₃x₄x₅
49-50	x₁x₃x₄x₅

В результате на 2 итерации 48 импликант участвовали в операции склеивания и поглотились своими собственными частями. Девять импликант не участвовали в операции склеивания, они образуют множество Z₁ – множество простых импликант 1-ранга.

Z₁={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₆}

3 итерация. Выполняются все возможные операции неполного попарного склеивания и элементарного поглощения для элементарных конъюнкций длины 4(полученные в результате операции склеивания на 2 итерации).

Построим таблицу 1.5 в которой укажем элементарные конъюнкции, полученные в результате операции склеивания на 2 итерации и отметим, являются ли они поглощенными.

Таблица 1.5

№	Элементарные конъюнкции длины 4	Отметка о поглощении
1	x₁x₂x₃x₅	+
2	x₁x₃x₄x₅	+
3	x₁x₃x₅x₆	+
4	x₂x₃x₅x₆	-
5	x₁x₂x₃x₆	-
6	x₁x₃x₅x₆	+
7	x₁x₄x₅x₆	-
8	x₂x₃x₅x₆	-
9	x₁x₂x₃x₄	-
10	x₁x₃x₄x₅	+
11	x₂x₃x₄x₆	-
12	x₂x₃x₄x₅	-
13	x₁x₂x₃x₅	+
14	x₁x₂x₄x₅	+
15	x₁x₂x₅x₆	+
16	x₁x₂x₅x₆	+
17	x₁x₂x₄x₅	+
18	x₁x₂x₃x₅	+
19	x₁x₂x₃x₆	-
20	x₂x₃x₅x₆	-
21	x₁x₂x₃x₆	-
22	x₁x₂x₃x₅	-
23	x₁x₃x₄x₅	-

Выполним операции неполного попарного склеивания. Запишем в таблицу 1.6 результат операции.

Таблица 1.6

Номера склеиваемых конъюнкций	Результат склеивания
1-13	x₁x₃x₅
2-10	x₁x₃x₅
3-6	x₁x₃x₅
13-18	x₁x₂x₅
14-17	x₁x₂x₅
15-16	x₁x₂x₅

В результате на 3 итерации 11 импликант участвовали в операции склеивания и поглотились своими собственными частями. 12 импликант не участвовали в операции склеивания, они образуют множество Z₂ – множество простых импликант 2-ранга.

Z₂={ 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₅}

После 3 итерации остались две конъюнкции длины 3, которые не склеиваются друг с другом. Они образуют множество Z₃– множество простых импликант 3-ранга.

Z₃={ x₁x₃x₅; x₁x₂x₅}

Множество простых импликант: Z= Z₀∪Z₁∪Z₂∪Z₃

Z={ 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₅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₅}

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

Таким образом СкДНФ:

f(x)=x₁x₂x₃x₄x₅x₆v x₂x₃x₄x₅x₆ v x₂x₃x₄x₅x₆ v x₁x₂x₄x₅x₆ v x₁x₂x₄x₅x₆ v x₁x₂x₃x₄x₆ v x₁x₂x₃x₅x₆v x₁x₃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₆ v x₁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₃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₅ v x₁x₂x₅

2 шаг. Нахождение множества тупиковых форм.

1 итерация.

Построим импликантную матрицу(Таблица 1.7) для нахождения ядра функции. Столбцы матрицы – конституенты 1(K), строки - простые импликанты(П.И). В соответствующие клетки ставится «+» если соответствующая простая импликанта накрывает эту единицу функции.

Находятся такие единицы функции, которые накрываются только какой-то одной простой импликантой. Эти простые импликанты образуют ядро функции. Простые импликанты входящие в ядро функции, отмечаются знаком «*», а соответствующие им строки выделяются цветом.

Знаком «v» отмечается единица функции, накрываемая ядром функции.

Согласно Таблице 1.7:

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

Результат 1 итерации: ядро функции, множество непокрытых ядром единиц функции и множество оставшихся простых импликант без ядра.

2 итерация. Строится новая импликантная матрица. Столбцы – множество непокрытых единиц функции, строки – множество оставшихся простых импликант. Заполнение матрицы происходит таким же образом. Исключаются те простые импликанты, которые не накрывают ни одной единицы функции. Далее происходит упорядочивание системы простых импликант по следующим правилам:

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

Длина u не меньше чем длина v.
Все единицы функции, накрываемые простой импликантой u, накрываются простой импликантой v.

В матрице исключаемые после упорядочивания импликанты отмечены знаком «^» .

Для новой импликантной матрицы применяется способ, изложенный в 1 итерации. Импликанты, покрывающие только одну единицу функции образуют псевдоядро первого уровня. Эти импликанты отмечаются «*», соответствующие им строки отмечаются цветом. Единицы, накрываемые псевдоядром отмечаются «v».

П.И

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₂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₂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₆.

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

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₂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₃x₄x₆

x₁x₂x₃x₆

x₁x₂x₃x₅

x₁x₃x₅

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

выбранная простая импликанта входит в приведенную систему простых импликант;
выбранная простая импликанта не входит в приведенную систему простых импликант.

Обе гипотезы должны быть обработаны.

Выдвигаем гипотезу: пусть простая импликанта x₁x₃x₅ не входит в ТДНФ. Строим новую импликантную матрицу. Столбцы – множество непокрытых единиц функции. Строки – множество оставшихся простых импликант без импликанты x₁x₃x₅. Импликанты, покрывающие только одну единицу функции образуют псевдоядро второго уровня. Эти импликанты отмечаются «*», соответствующие им строки отмечаются цветом. Единицы, накрываемые псевдоядром отмечаются «v».

П.И

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₄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₆ .

Результат 3 итерации: псевдоядро второго уровня , множество непокрытых псевдоядром единиц функции и множество оставшихся простых импликант без псевдоядра.

4 итерация. Строим новую импликантную матрицу. Столбцы – множество непокрытых единиц функции. Строки – множество оставшихся простых импликант без псевдоядра второго уровня.

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

П.И

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₂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₄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₅.

Результат 4 итерации: псевдоядро третьего уровня, множество непокрытых псевдоядром единиц функции и множество оставшихся простых импликант без псевдоядра.

5 итерация. Строим новую импликантную матрицу. Столбцы – множество непокрытых единиц функции. Строки – множество оставшихся простых импликант без псевдоядра третьего уровня.

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

K П.И	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₆ ^		+

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

K П.И	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₆.

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

6 итерация. Строим новую импликантную матрицу. Столбцы – множество непокрытых единиц функции. Строки – множество оставшихся простых импликант без псевдоядра четвертого уровня.

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

П.И

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₆.

После 6 итерации все оставшиеся единицы функции были накрыты псевдоядром пятого уровня. Дизъюнкция простых импликант, входящих в ядро и псевдоядра соответствующего уровня даёт нам тупиковую форму.

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

Цена: 52.

3.1 итерация. Возвращаемся к 3 итерации и выдвигаем обратную гипотезу: пусть простая импликанта x₁x₃x₅ входит в ТДНФ. Строим новую импликантную матрицу. Столбцы – множество непокрытых единиц функции, без единиц, накрываемых импликантой x₁x₃x₅. Строки – множество оставшихся простых импликант без импликанты x₁x₃x₅. Импликанты, покрывающие только одну единицу функции образуют псевдоядро второго уровня. Эти импликанты отмечаются «*», соответствующие им строки отмечаются цветом. Единицы, накрываемые псевдоядром отмечаются «v».

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

П.И

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₃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₅

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₆.

Результат 3.1 итерации: псевдоядро второго уровня , множество непокрытых псевдоядром единиц функции и множество оставшихся простых импликант без псевдоядра.

4.1 итерация. Строится новая импликантная матрица. Столбцы – множество непокрытых единиц функции. Строки – множество оставшихся простых импликант без псевдоядра второго уровня.

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

K П.И	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₁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₆ имеют одинаковую цену и накрывают одни и те же единицы функции. Следовательно, исключается любая из этих импликант. Исключим одну из них и доведём алгоритм до конца, затем вернемся к этой итерации и исключим другую импликанту, также доведя алгоритм до конца.

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

K П.И	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₃x₄x₆ *	+

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

Результат 4.1 итерации: псевдоядро третьего уровня , множество непокрытых псевдоядром единиц функции и множество оставшихся простых импликант без псевдоядра.

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₄x₅x₆

x₁x₄x₅x₆ *

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

После 5.1 итерации все оставшиеся единицы функции были накрыты псевдоядром пятого уровня. Дизъюнкция простых импликант, входящих в ядро и псевдоядра соответствующего уровня(полученных на 1,2, 3.1, 4.1, 5.1 итерациях), а также импликанта x₁x₃x₅, которая входит в ТДНФ согласно выдвинутой гипотезе, даёт нам тупиковую форму.

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

Цена: 51.

4.2 итерация. Вернемся к 4.1 итерации. Теперь исключается простая импликанта x₂x₃x₄x₆.

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

K П.И	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₁x₂x₃x₄x₅					+	+
x₁x₄x₅x₆		+
x₁x₂x₃x₄	+
x₂x₃x₄x₆ ^	+
x₁x₂x₃x₅

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

K П.И	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₂x₃x₄ *	+

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

Результат 4.2 итерации: псевдоядро третьего уровня , множество непокрытых псевдоядром единиц функции и множество оставшихся простых импликант без псевдоядра.

5.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₆.

После 5.2 итерации все оставшиеся единицы функции были накрыты псевдоядром пятого уровня. Дизъюнкция простых импликант, входящих в ядро и псевдоядра соответствующего уровня(полученных на 1, 2, 3.1, 4.2, 5.2 итерациях), а также импликанта x₁x₃x₅, которая входит в ТДНФ согласно выдвинутой гипотезе, даёт нам тупиковую форму.

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

Цена: 51.

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

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

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

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

<<< < Предыдущая 12 / 42 3 4 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
08.05.201553.92 Кб3семенар.docx
#
08.05.2015149.27 Кб57Семенова диплом.docx
#
01.12.20181.76 Mб0Семестровая работа I (МН-108, МН-184) Кунгурцев....doc
#
06.08.2019174.59 Кб1семестровая работа по ЭП.doc
#
24.08.2019505.13 Кб1Семестровая ТОТТ_ - Кобяков Г.Ф..docx
#
15.07.2019280.69 Кб3Семестровая.docx
#
02.09.20191.69 Mб1Семестровое задание 2 сем МН-108, МН-184 2012.doc
#
08.05.20152.34 Mб20семестровое задание №3.docx
#
08.05.2015146.94 Кб6Семестровое задание.doc
#
22.09.20192 Mб2Семестровое задание.doc
#
23.11.2019435.71 Кб1Семестровое задание.doc