Если F(y1, y2, …, ym ) и fi (x1, x2, …, xn ) – формулы алгебры логики, то (F| yi fi )(x1, x2, …, xn ) также является формулой.

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

Правило подстановки

Если в равносильных формулах: F(y1, y2, …, ym ) ºG(y1, …, ym ) – вместо всех вхождений некоторой переменной yi подставить одну и ту же формулу, то получатся равносильные формулы.

Правило замены

Если в формуле F заменить некоторую подформулу yi на равносильную gi, то получатся равносильные формулы.

ФАЛ, при образовании которых используются только операции отрицания, конъюнкции и дизъюнкции, называются булевыми формулами.

Теорема 4.3 Для любой формулы алгебры логики существует равносильная ей булева формула.

4.1.4 Булевы функции и булева алгебра

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

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

Аксиомы булевой алгебры:

1. Операции с константами:
1) A Ú 1 º 1; A & 1 º A; 2) A Ú 0 º A; A & 0 º 0.

2. Противоречие: A & ØA º 0.

3. Исключение третьего: A Ú ØA º 1.

4. Идемпотентность: A & A º A; A Ú A º A.

5. Двойное отрицание: Ø ØA º A.

6. Коммутативность: A & B º B & A; A Ú B º B Ú A.

7. Ассоциативность:
(AÚB)ÚC º AÚ(BÚC); (A&B)&C º A&(B&C).

8. Дистрибутивность:
A & (B Ú C) º (A & B) Ú (A & C); A Ú (B & C) º (A Ú B) & (A Ú C).

9. Законы де Моргана: Ø(A&B) º ØA Ú ØB; Ø(AÚB) º ØA & ØB.

Используя приведенные аксиомы, возможно выполнять равносильные преобразования, выводить и доказывать новые законы. В частности, при выполнении преобразований часто используются законы поглощения:
1) A & (A Ú B) º A; A Ú A & B º A;
2) ØA & (A Ú B) º ØA & B; A Ú ØA & B º A Ú B.

Эти законы несложно доказать с помощью аксиом.

4.1.5 Принцип двойственности

Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция f*(x1, x2, …, xn ) º f (`x1,`x2, …,`xn ). Из определения видно, что двойственность инволютивна: f**=f.

Если двойственная функция f* совпадает с исходной функцией f, то такая функция f называется самодвойственной.

Пример 4.3 (0)* º`0º1; (x)*= (`x) º x Þ Функция, тождественно равная своему аргументу, является самодвойственной.

Теорема 4.4 (Общий принцип двойственности)

Если G(x1, …, xn ) получена подстановкой fi из F(y1, …, ym ): G(x1, …, xn )º (F| yi fi )(x1, …, xn ), то G*(x1, …, xn )º (F*| yi f*i )(x1, …, xn ).

Теорема 4.5 (Принцип двойственности для булевых функций)

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

x y f=xÚy x y f*

Пример 4.4 (x`y Ú z)* º (xÚ`y) & z., (xÚy)* º x&y Þ в таблице истинности значения функции и переменных меняются на противоположные

4.1.6 Алгебра Жегалкина

Булевы функции с операциями умножения и сложения по модулю 2 образуют алгебру Жегалкина.

Аксиомы алгебры Жегалкина:

1. Операции с константами: A×1 º A; A×0 º 0; A Å 0 º A.

2. Идемпотентность: A×A º A; A Å A º 0.

3. Коммутативность: A×B º B×A; A Å B º B Å A.

4. Ассоциативность: (A Å B) Å C º AÅ (B Å C); (A×B)×C º A×(B×C).

5. Дистрибутивность: A×(B Å C) º A×B Å A×C.

Можно перейти от алгебры Буля к алгебре Жегалкина, используя следующие соотношения: A Å 1 º`A; AÚB=A Å B Å A×B.

И наоборот, от алгебры Жегалкина к алгебре Буля: A Å B =`A×BÚ A×`B

Пример 4.5 Перейти к выражению булевой алгебры: (x Å 1)×yÅ (x Å 1) = `x×y Å`x = `xy×`x Ú x×`xy = (x Ú`y)×`x Ú 0 =`x`y.

4.1.7 Контрольные вопросы

1. Какие высказывания являются равносильными? Приведите пример.

2. Какие существуют логические операции?

3. Какие логические операции дают в результате их применения к двум аргументам только одно истинное (ложное) значение? На каких наборах переменных достигается это значение?

4. Какие операции на всех наборах значений переменных имеют взаимно противоположные значения?

5. Какие существуют формулы, позволяющие выразить одну операцию через другую?

6. Каков порядок логических операции в соответствии с их приоритетом?

7. Что такое переключательная функция?

8. Сколько существует различных наборов аргументов для функции 5 переменных?

9. Какая функция является полностью определенной?

10. Что такое булева алгебра? Что представляют собой аксиомы?

11. Какая функция является самодвойственной?

12. В чем состоит принцип двойственности для булевых функций?

13. Какие операции определяют алгебру Жегалкина?

14. Как связаны алгебры Буля и Жегалкина?

4.2 Способы представления булевых функций

4.2.1 Нормальные формы

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

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

Элементарной дизъюнкцией (произведением) называется дизъюнкция (произведение) переменных или их отрицаний, в котором каждая переменная встречается только один раз.

ДНФ – это дизъюнкция элементарных произведений. КНФ – это произведение элементарных дизъюнкций. Как ДНФ, так и КНФ функции не единственна. Обычно предполагают, что входящие в ДНФ (КНФ) элементарные конъюнкции (дизъюнкции) попарно различны.

ДНФ (КНФ) называется совершенной, если каждая переменная формулы входит в каждую элементарную конъюнкцию (дизъюнкцию) ровно один раз.

Ñ СДНФ (СКНФ) функции единственна.

Пример 4.6 Элементарные дизъюнкции: xÚ`y, z. Элемент. конъюнкции: x×`y×z, x. f(x,y,z) = xyz Ú`xy – ДНФ ; f(x,y,z) = (x Ú`y)×z – КНФ.

Введем обозначения:

Теорема 4.6 О разложении булевой функции по k переменным (знак È ºÚ).

Пример 4.7 n=3, k=2.

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

Выберем какой-либо набор значений для переменных x1, …, xn. Пусть это будет s1, …, sn.. Заметим, что (11=1, 00=1, 10=1=0, 01=0)

Подставим в правую часть формулировки теоремы вместо x1, …, xn набор s1, …, sn. Получим . Поскольку коэффициент перед функцией равен 1 только при равных значениях si и ai, в разложении останется только один член: , и si =ai, т.е. . Получена левая часть формулы теоремы 4.6. Поскольку набор был выбран произвольно, получаем, что утверждение верно " набора x1, …, xn. ■

Следствие 1: Разложение Шеннона

Следствие 2: При k=n получаем: , т.е. выбираем те слагаемые, на которых функция равна 1. Полученная формула представляет собой СДНФ.

4.2.2 Построение совершенных нормальных форм

Построение СДНФ

1. Построение по таблице истинности

1) Найти строки в ТИ, где f = 1.

2) " найденному набору s1, …, sn. поставить в соответствие произведение , где

3) Составить дизъюнкцию из произведений п.2.

2. Получение из ДНФ.

Если некоторое произведение ДНФ не содержит какой-либо переменной (пусть xk), то необходимо домножить это произведение на дизъюнкцию этой переменной и ее отрицания (т.е. на единицу, равную xk Ú`xk) и применить дистрибутивный закон.

Построение СКНФ

1. Построение по ТИ.

1) Найти строки в ТИ, где f = 0.

2) " найденному набору s1, …, sn. поставить в соответствие дизъюнкцию , где

3) Составить произведение дизъюнкций из п.2.

2. Получение из КНФ.

Если некоторая элементарная дизъюнкция КНФ не содержит какой-либо переменной (пусть xk), то необходимо дизъюнктивно добавить в нее произведение этой переменной и ее отрицания (т.е. xk×`xk) и применить дистрибутивный закон.

x y z f

Пример 4.8 1) Получим СДНФ и СКНФ по ТИ:

2) Получим СДНФ и СКНФ из ДНФ и КНФ:

Произведения в СДНФ называются минтермами, а дизъюнкции в СКНФ – макстермами.

Может использоваться запись , которая означает, что в качестве минтермов берутся произведения, соответствующие двоичному представлению чисел . Аналогично, запись означает, что в качестве макстермов берутся дизъюнкции, соответствующие двоичному представлению чисел .

Пример 4.9 Пусть заданы функции f и g: ; . f: 1 ® 001; 3 ® 011; 5 ® 101; 6 ® 110 Þ . g: 2 ® 010, 4 ® 100; 5 ® 101 Þ .

4.2.3 Карты Карно

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

Пусть дана булева функция f(x1, x2, …, xn), определенная на 2n наборах переменных. Наборы, отличающиеся значением только одной переменной xi, называются соседними.

Множество тех наборов, на которых f(x1, x2, …, xn) = 1, называется прообразом единицы, множество наборов, на которых f(x1, x2, …, xn) = 0 – соответственно прообразом нуля.

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

Булева функция может быть представлена на карте Карно выделением клеток, соответствующих прообразу 1. В этих клетках будем писать 1 и называть их p-клетками. Незаполненные ячейки соответствуют нулям функции. 2k соседних p-клеток, расположенных в виде прямоугольника или квадрата, образуют k-мерный p-подкуб. Он называется покрытием размерности k и соответствует произведению n–k переменных. Одна p-клетка образует 0-мерный p-подкуб (или 0-куб), две – одномерный (1-куб, покрытие размерности 1 – произведение n–1 переменной – все кроме той, которая отличается для этих наборов), четыре – двумерный, и т.п.

Для функции трех переменных карту Карно можно представить в следующем виде:

Все клетки, отмеченные скобкой xi (по строке и столбцу), представляют наборы с xi = 1, а в неотмеченных строках и столбцах клетки соответствуют наборам с xi = 0.

В случае четырех переменных карта Карно имеет следующий вид:

Пример 4.10 Заполним карту Карно для функции

4.2.4 Контрольные вопросы

1. Какое представление функции называется ее нормальной формой?

2. Что такое ДНФ? В чем ее отличие от КНФ?

3. Какая нормальная форма называется совершенной?

4. Какой формой является функция xÚy? Почему?

5. Запишите разложение Шеннона для функции от 4 переменных f(x1,x2,x3,x4) по переменной x3.

6. Какие существуют способы построения СДНФ и СКНФ? В чем их различие при построении по таблице истинности?

7. Как можно получить СДНФ (СКНФ) посредством преобразований?

8. Что называется минтермами (макстермами)?

9. Что такое карта Карно?

10. Какова особенность соседних клеток на карте Карно?

11. Из какого количества клеток состоит карта Карно функции трех переменных? А функции 5 переменных?

12. Что такое покрытие на карте Карно?

13. Сколько клеток карты Карно составляют покрытие размерности 2? А покрытие размерности 4?

14. Как построить карту Карно функции, представленной в ДНФ?

4.3 Контактные схемы

Контактная цепь (схема) – устройство из проводов и контактов, связывающих два полюса. Любой контакт может быть либо замкнут, либо разомкнут. Контакты будем обозначать x1, x2, x3, …

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

Схема Булева операция

x1x2

`x1

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

Пример 4.11 Пусть задана контактная схема. Упростить ее до пяти контактов.
Составим булеву функцию для исходной схемы и упростим ее. . По упрощенной формуле составим схему:

4.3.1 Контрольные вопросы

1. Что такое контактная схема?

2. Какая логическая операция соответствует последовательному соединению контактов? А параллельному соединению?

3. Как можно построить булеву функцию по контактной схеме?

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

4.4 Минимизация булевых функций

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

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

Пример 4.12 1) . – импликанта, причем простая; – импликанта, но не простая, т.к. удаление x3 снова дает импликанту (которая является простой).
2) Найдем импликанты и простые импликанты для функции . Всего имеется 8 элементарных конъюнкций с переменными x1, x2. Приведем их таблицы истинности.

x1 x2 x1®x2 x1x2 x1 x2

Из таблицы истинности заключаем, что , , x1x2, , x2 являются импликантами функции f. Из них простыми являются и x2.

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

Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет значения функции.

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

Минимальных ДНФ может быть несколько.

Процесс нахождения минимальной ДНФ из СДНФ можно разбить на следующие этапы:

1) нахождение сокращенной ДНФ (она единственна);

2) нахождение всех тупиковых ДНФ (их м.б. несколько);

3) выбор из всех тупиковых минимальной ДНФ (их тоже м.б. несколько).

Известны аналитические и графические способы построения минимальной ДНФ. Графический способ использует представление на картах Карно.

4.4.1 Применение карт Карно

Этот метод используется для формул с малым числом переменных.

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

Для построения минимальной ДНФ следуют двум правилам:

1. Выбирают покрытия наибольшего размера, содержащие клетки, которые не могут быть ни в каком другом покрытии.

2. Для оставшихся клеток выбирают покрытие наибольшей размерности.

Пример 4.13 Найдем минимальную ДНФ для функции
= . Выпишем двоичные номера всех 0-кубов: 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1011, 1111. Построим карту Карно и покроем все единицы на карте Карно покрытиями наибольшего размера. Порядок построения минимальной ДНФ будет таким:
1) Выбираем покрытие наибольшего размера для ячейки, соответствующей x1x2x3x4. Это импликанта x3x4.
2) Выбираем покрытие для ячейки – импликанта . 3) Выбираем покрытие для ячейки – импликанта . Непокрытых ячеек не осталось Þ минимальная ДНФ имеет вид .

4.4.2 Метод Квайна-Мак-Класки

Будем предполагать, что функция представлена в СДНФ. Метод Квайна-Мак-Класки позволяет получить минимальную ДНФ независимо от количества аргументов. На первом этапе выполняется построение сокращенной ДНФ (т.е. поиск всех простых импликант), на втором – получение из нее минимальной ДНФ.

Этап 1. Нахождение сокращенной ДНФ.

1) Каждому дизъюнктивному члену ставим в соответствие двоичный набор. Полученное множество 0-кубов обозначим K0 и разобьем его на группы по количеству единиц, обозначив группу с i единицами через K0i.

2) Нахождение простых импликант.
а) Применяем операцию склеивания к 0-кубам из соседних подмножеств, которые различаются одной переменной: . Склеивание возможно только между элементами соседних групп (только они могут различаться ровно одной переменной). Элементы, участвующие в склеивании, помечаем. Результат склеивания – набор 1-кубов (импликант) и, возможно, простые импликанты, которые остались не помеченными. Для 1-кубов на месте отсутствующей переменной будем писать знак x.
б) Разбиваем 1-кубы на подмножества по расположению x и производим склеивание внутри каждого подмножества (принцип тот же – склеиваются 1-кубы, отличающиеся ровно одной переменной). Склеенные 1-кубы помечаем, результат склеивания – 2-кубы. Неотмеченные 1-кубы – простые импликанты.
в) Аналогично склеиваем 2-кубы, 3-кубы и т.п., пока это возможно. По окончании процесса все оставшиеся непомеченными элементы являются простыми импликантами, т.е. получена сокращенная ДНФ.

Пример 4.14 Результат склеивания наборов 0110 и 1110 – набор x110, который соответствует импликанте . Результат склеивания 1-кубов x110 и x100 – 2-куб x1x0, который соответствует импликанте .

Этап 2. Нахождение минимальной ДНФ.

3) Построение импликантной таблицы.

По найденным на предыдущем этапе простым импликантам составляем импликантную таблицу, заголовки строк которой – простые импликанты, заголовки столбцов – 0-кубы из исходной СДНФ. В таблице помечаем пересечение строки и столбца, если импликанта покрывает 0-куб.

4) Нахождение существенных импликант.

Если в столбце имеется только одна пометка, то импликанта, соответствующая этой строке, называется существенной, и она обязательно должна присутствовать в минимальной ДНФ Þ она включается в ответ. Если не включить ее в ответ, в нем будет потеряна единица, соответствующая рассматриваемому столбцу. Включив эту импликанту в минимальную ДНФ, можно устранить из дальнейшего рассмотрения строку и все столбцы с пометками для этой импликанты Þ вычеркиваем столбец с одной пометкой и все остальные столбцы, имеющие пометки в этой строке, а также саму строку.

5) Вычеркивание доминируемых строк.

Если в j-ой строке имеются все пометки i-ой строки и может быть, еще некоторые, то j-я строка доминирует над i-ой, и i-ую строку можно исключить из дальнейшего рассмотрения. Из таблицы вычеркиваются все доминируемые строки (с меньшим числом пометок – в частности, строки без пометок).

6) Вычеркивание столбцов.

Если в m-ом столбце таблицы имеются все пометки k-го столбца и может быть, еще некоторые, то m-ый столбец доминирует над k-ым и m-ый столбец можно исключить из дальнейшего рассмотрения (т.е. вычеркивается столбец с большим числом пометок, в отличие от строки).

7) Этапы 4–6 повторяются до тех пор, пока это возможно. Полученная после таких преобразований таблица называется циклической.

8) Выбор минимального покрытия в циклической таблице.

Используется процедура ветвления:

а) выбирают столбец с минимальным количеством пометок (таких столбцов может быть несколько);

б) используя эти столбцы, выбирают из строк, содержащих пометки в выбранном столбце, ту, которая содержит максимальное количество пометок, и включают ее в минимальную ДНФ (в ответ). Если таких строк несколько, то берется любая.

в) исключают строку, соответствующую найденной импликанте, и все помеченные в этой строке столбцы из дальнейшего рассмотрения. Если появилась строка, в которой во всех столбцах стоят пометки, то эту импликанту включают в минимальную ДНФ и на этом процесс нахождения минимальной ДНФ закончен. В противном случае выполняется возврат на п.4.

В результате описанных преобразований таблицы будет получена минимальная ДНФ.

Пример 4.15 Найдем минимальную ДНФ для функции = .
1) Выпишем все наборы, на которых функция принимает значение 1 (т.е. 0-кубы функции): 0000, 0011, 0100, 0110, 0111, 1001, 1110, 1111. Разобьем наборы на группы по количеству единиц. Первая группа состоит из наборов, не содержащих единиц: {0000}; вторая – из наборов, содержащих одну единицу: {0100}, третья – две единицы: {0011, 0110, 1001}, четвертая – три {0111, 1110}, пятая – четыре {1111}. Выполним все возможные склеивания между наборами соседних групп, помечая участвующие в склеивании наборы: Результаты склеивания – 1-кубы 0x00, 01x0, 0x11, 011x, x110, x111, 111x. Импликанта 1001 – простая. Разобьем все полученные в результате склеивания импликанты по положению x на группы: 1-я группа: ; 2-я: ; 3-я: ; 4-я: .
Произведем все возможные склеивания внутри каждой группы, помечая наборы, участвующие в склеивании.
Результат склеивания – импликанта, соответствующая x11x, и набор простых импликант, соответствующих 0x00, 0x11, 01x0. Дальнейшее склеивание осуществить нельзя, поэтому x11x соответствует простой импликанте. Можно переходить к составлению импликантной таблицы.

 
          v    
0x00 v   v          
01x0     v v        
0x11   v     v      
x11x       v v   v v

Импликанты, соответствующие 0x00, 0x11, 1001, x11x – существенные, поэтому они обязательно входят в минимальную ДНФ. Удалим строки и столбцы для этих импликант из таблицы. Вычеркнутся все столбцы, следовательно, на этом процесс поиска минимальной ДНФ закончен.

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

Можно построить карту Карно и проверить полученный результат.

4.4.3 Минимизация частично определенных функций

Для минимизации неполностью определенных функций вводят в рассмотрение две дополнительных функции: j0(x1,x2,...,xn)=0 и j1(x1,x2,...,xn)=1 на всех наборах, на которых функция f не определена, и j0(x1,x2,...,xn)=j1(x1,x2,...,xn)=f там, где f определена. Для построения минимальной ДНФ нужно выбрать наименьшее покрытие 0-кубов функции j0 простыми импликантами функции j1.

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

Пример 4.16 Рассмотрим функцию , заданную Т.И.

x1 x2 x3 x4 f j0 j1
*
*
*
*
*
*
*
*

Дополним ее функциями j0 и j1. Нужно найти сокращенную ДНФ для j1, а затем все покрытия 0-кубов j0.
Выпишем наборы, на которых функция j1 принимает значение 1: 0000, 0001, 0010, 0100, 0110, 0111, 1000, 1001, 1011, 1101, 1110, 1111. Разобьем наборы на группы по количеству единиц. K00={0000}; K01={0001,0010,0100,1000}; K02={0110,1001}; K03={0111,1011,1101,1110}, K04={1111}. Выполним все возможные склеивания между наборами соседних групп, помечая участвующие в склеивании наборы: Результаты склеивания – 1-кубы 000x, 00x0, 0x00, x000, x001, 01x0, 100x, 011x, x110, 10x1, 1x01, x111, 1x11, 11x1, 111x. Разобьем все полученные в результате склеивания импликанты по положению x на группы:
K11= ; K12= ; K13= ; K14= .
Произведем все возможные склеивания внутри каждой группы, помечая наборы, участвующие в склеивании. Получим: x00x, x11x, 1xx1, 0xx0, 1xx1, x00x, x11x. После устранения дубликатов получим: x00x, x11x, 1xx1, 0xx0.
Результат склеивания – простая импликанта – 1-куб, соответствующая 0x00, и набор 2-кубов импликант, соответствующих x00x, x11x, 1xx1, 0xx0. Дальнейшее склеивание осуществить нельзя Þ это простые импликанты. Можно переходить к составлению импликантной таблицы, столбцы которой – 0-кубы функции j0.

 

0x00 v      
x00x v   v  
x11x   v   v
1xx1     v  
0xx0 v v    

Импликанта x11x – существенная для 1110, вычеркиваем столбец 1110 и строку x11x, а также столбец 0110, который она покрывает, при этом импликанту x11x включаем в ответ. Больше существенных импликант нет, а строка x00x доминирует над всеми остальными Þ доминируемые строки вычеркиваем, а импликанту x00x выписываем в ответ. В итоге в ответ вошли импликанты x11x и x00x, т.е. функция имеет вид f = x2×x3 Ú `x2×`x3. Проверка: Построенная карта Карно подтверждает полученный результат. Для включения в покрытия всех единиц, используя при необходимости символы d и выбирая покрытия наибольшей размерности, достаточно покрытий x11x и x00x. Остальные символы d, не вошедшие в эти покрытия, заменяются нулями.

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

4.4.4 Контрольные вопросы

1. Что является импликантой функции? В чем отличие простой импликанты?

2. Что соответствует импликанте (простой импликанте) на карте Карно?

3. Что такое сокращенная ДНФ?

4. Каков алгоритм нахождения сокращенной ДНФ?

5. Как можно получить минимальную ДНФ с помощью карт Карно?

6. Что позволяет найти метод Квайна-Мак-Класки? Каковы основные этапы этого метода? Что является результатом каждого из этапов?

7. Что такое 0-кубы? 1-кубы?

8. Что представляет операция склеивания? Какие наборы возможно склеить?

9. Как строится импликантная таблица? Что является ее строками, а что – столбцами? Какие строки и какие столбцы удаляются при упрощении импликантной таблицы?

10. В чем состоит процедура ветвления?

11. Единственна ли минимальная ДНФ?

12. Что такое частично определенная функция?

13. Чем отличается минимизация частично определенной функции?