Минимизация методом Квайна-МакКласки

Выписываем все термы, в которых функция принимает значение 1. Нумерация переменных в термах – слева направо, т.е. будет записано как 1101.

0000, 1000, 0100, 1100, 1010, 0110, 0001, 1001, 0101, 1101, 0011, 1011, 0111, 1111.

Далее классифицируем термы по количеству единиц.

0) 00001

1) 10002, 01003, 00014

2) 11005, 10106, 01107, 10018, 01019, 001110

3) 110111, 101112, 011113

4) 111114.

Проводимо попарное склеивание.

0) –000(1-2), 0–00(1-3), 000–(1-4)

1) 1–00(2-5), 10–0(2-6), 100–(2-8), –100(3-5), 01–0(3-7), 010–(3-9), –001(4-8), 0–01(4-9),
00–1(4-10)

2) 110–(5-11), 1–01(8-11), –101(9-11), 101–(6-12), 011–(7-13), 10–1(8-11), 01–1(9-13), –011(10-12),

0–11(10-13)

3) 11–1(11-14), 1–11(12-14), –111(13-14)

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

+

+

+

+

+

+

+

+

+

+

+

+

+

+

Все термы участвовали в склеиваниях. В результат ничего не включается.

Следующий этап попарного склеивания. Перегруппировываем термы по количеству единиц и заново их нумеруем.

0) –0001, 0–002, 000–3

1) 1–004, 10–05, 100–6, –1007, 01–08, 010–9, –00110, 0–0111, 00–112

2) 110–13, 1–0114, –10115, 101–16, 011–17, 10–118, 01–119, –01120, 0–1121

3) 11–122, 1–1123, –11124

Проводимо попарное склеивание.

0) – –00(1-7), –00–(1-10), – –00(2-4), 0–0–(2-11), –00–(3-6), 0–0–(3-9)

(повторяющиеся термы, т.е. ненужные, выделено цветом)

1) 1–0–(4-14), 1–0–(6-13), 10– –(6-16), 10– –(5-19), –10–(7-15), –10–(9-13), 01– –(8-18),
01– –(9-17), – –01(10-15), – –01(11-14), 0– –1(11-19), 0– –1(12-19), –0–1(10-20), –0–1(12-18)

2) 1– –1(14-21), 1– –1(18-20), – –11(19-22), – –11(21-23), –1–1(19-22), –1–1(15-24)

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

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+	+	+	+	+	+	+	+	+	+

Все термы участвовали в склеиваниях. В результат ничего не включается.

Следующий этап попарного склеивания. Перегруппировываем термы по количеству единиц и заново их нумеруем.

0) – –001, –00–2, 0–0–3

1) 1–0–4, 10– –5, –10–6, 01– –7, – –018, 0– –19, –0–110

2) 1– –111, –1–112, – –1113

Проводимо попарное склеивание.

0) – –0–(1-8), – –0–(2-6), – –0–(3-4)

(повторяющиеся термы, т.е. ненужные, выделено цветом)

1) – – –1(9-10), – – –1(10-12), – – –1(13-18)

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

+	+	+	+		+		+	+	+	+	+

Термы 5 и 7 в склеивании не участвовали. Они сразу записываются в результат. Дальнейшие склеивания невозможны. Следовательно, тупиковая ДНФ будет иметь такой вид