Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf

60
Определение 2.29. Множество
M
логических функций называется замкнутым, если любая суперпозиция функций из
M
снова принадлежит
M
Всякая система  логических функций порождает некоторый замкнутый класс, а именно класс, состоящий из всех функций, которые можно получить суперпозициями из .
Такой класс называется замыканием  и обозначается
[

]
Очевидно, что если M – замкнутый класс, то
[
M
]
= M, а если M – функционально полная система, то
[
M
]
= P
2
Пример
1. Множество всех дизъюнкций является замкнутым классом.
2. Важным примером замкнутых классов являются классы Поста.
3. Классы функций, сохраняющих 0 и сохраняющих 1, являются замкнутыми, что проверяется подстановкой констант в суперпозиции.

61
Теорема:
Множество всех монотонных функций является замкнутым классом.
Следствие:
Класс монотонных функций является замыканием системы функций:
2.2.7. Две теоремы о функциональной полноте
Лемма 1 (о немонотонных функциях):
Если функция ????(????
1
, … , ????
????
) немонотонна, то подстановкой констант из нее можно по- лучить отрицание. Точнее, существует такая подстановка
n –1
константы, что функция оставшейся одной переменной является отрицанием.
Лемма 2 (о нелинейных функциях):
Если функция ????(????
1
, … , ????
????
) нелинейна, то подстановкой констант и использования от- рицаний из нее можно получить дизъюнкцию и конъюнкцию. Точнее, существует пред- ставление дизъюнкции и конъюнкции в виде суперпозиции констант, отрицаний и функции
????(????
1
, … , ????
????
) .
Эти две леммы позволяют получить все булевы функции с помощью немонотонных функций, нелинейных функций и констант.
Это еще не функциональная полнота в обычном смысле, так как константы с самого начала предполагались данными. Однако такое предположение часто бывает оправданным в различных приложениях и прежде всего в синтезе логических схем.
Первая теорема о функциональной полноте:
Для того чтобы система логических функций была функционально полной в слабом
смысле, необходимо и достаточно, чтобы она содержала:
1) хотя бы одну немонотонную функцию;
2) хотя бы одну нелинейную функцию.

62
Вторая теорема о функциональной полноте:
Для того чтобы система функций была функционально полной в сильном смысле, необходимо и достаточно, чтобы она содержала:
1) хотя бы одну немонотонную функцию;
2) хотя бы одну нелинейную функцию;
3) хотя бы одну несамодвойственную функцию;
4) хотя бы одну функцию, не сохраняющую 0;
5) хотя бы одну функцию, не сохраняющую 1.
Как видим, в каждом столбце таблицы имеется не менее одного минуса.
Следовательно, делаем вывод, что система функций
A
полна в сильном смысле.
Контрольные вопросы
1. Какие функции называются двойственными?
2. Какая функция называется самодвойственной?
3. В чем заключается принцип двойственности в алгебре логики (в булевой алгебре)?
4. Как по таблице истинности можно проверить двойственность и самодвойственность функций?
5. Какая структура называется алгеброй Жегалкина?
6. Что является типом алгебры Жегалкина?

63 7. Какая элементарная конъюнкция называется монотонной?
8. Что такое полином Жегалкина?
9. Какие существуют способы построения полинома Жегалкина?
10. Каким должен быть п олином Жегалкина линейной функции?
11. Какая функция называется монотонной?
12. Какими способами можно проверить монотонность функции?
13. Какие функции называются сохраняющими 0 и сохраняющими 1?
14. Что называется классами Поста?
15. Какая система логических функций называется полной?
16. Какое множество логических функций называется замкнутым?
17. Что такое замыкание системы логических функций?
18. О чем гласят леммы о немонотонных и нелинейных функциях?
19. В чем заключается функциональная полнота системы в слабом смысле?
20. В чем заключается полнота системы логических функций в сильном смысле?

64
Тема 2.3. Минимизация функций алгебры логики
2.3.1. Сокращенная и минимальная ДНФ
Рассмотрим булевы функции ????(????
1
, … , ????
????
) и ????(????
1
, … , ????
????
).
Определение 2.30. Булева функция ????(????
1
, … , ????
????
) называется импликантой функции
????(????
1
, … , ????
????
), если:
????(????
1
, … , ????
????
) ⊃ ????(????
1
, … , ????
????
) = 1.

65
Определение 2.31. Импликанта ????(????
1
, … , ????
????
) булевой функции ????(????
1
, … , ????
????
) и называ- ется простой, если при удалении любой буквы из нее она перестает быть импликантой.
Определение 2.32. Сокращенной ДНФ называется ДНФ, состоящая из всех простых импликант данной булевой функции.
Пример
Для рассматриваемой функции сокращенная ДНФ имеет вид:
Получение сокращенных ДНФ является первым этапом отыскания минимальных форм булевых функций. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая эквивалентности исходной функции. Такие простые им- пликанты назовем лишними. Исключение лишних простых импликант из сокращенных
ДНФ – второй этап минимизации.

66
Определение 2.32. Ядровой импликантой называется такая импликанта, удаление ко- торой из ДНФ функции ????(????
1
, … , ????
????
) приводит к ДНФ, не равносильной ????(????
1
, … , ????
????
) .
Определение 2.33. Минимальной ДНФ (МДНФ) функции ????(????
1
, … , ????
????
) называется ДНФ функции ????, содержащая минимальное число символов переменных из всех ДНФ, задающих функцию ????.
Определение 2.35. Тупиковой ДНФ функции ????(????
1
, … , ????
????
) называется такая ее ДНФ, со- стоящая из простых импликант, что удаление из нее любой конъюнкции нарушает равно- сильность ДНФ данной функции.
Определение 2.36. Сложностью ДНФ (КНФ) называется количество символов пере- менных, использованных в записи формулы.
Утверждение
Всякая функция f реализуется своей сокращенной ДНФ.
Для всякой функции, не равной тождественно нулю, существует единственная сокра- щенная ДНФ.
2.3.2. Метод
Квайна
Теорема (Квайна)
Если в СДНФ функции ???? провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокра- щенная ДНФ функции ????.
Алгоритм Квайна построения сокращенной и минимальной ДНФ
I этап. Построение сокращенной ДНФ из СДНФ на основе использования формулы неполного склеивания (12) и поглощения (11):
1) выпишем единичные наборы данной булевой функции в таблицу, разбив их на группы в соответствии с количеством единиц в наборах. Тогда для применения формулы неполного склеивания достаточно просмотреть всевозможные пары наборов, входящих в соседние группы;
2) результаты склеивания наборов из I полосы поместим во II полосе, а наборы, участвующие в склеиваниях, пометим крестиком;
3) во II полосе снова применяем, насколько возможно, операцию склеивания, запи- сывая результаты в III полосу и т. д.;
4) после завершения процедуры склеивания все простые импликанты не будут по- мечены крестиком, они и составят сокращенную ДНФ (помеченные же конъюнкции погло- тятся на этапе применения формулы поглощения).

67
II этап. Построение минимальной ДНФ из сокращенной ДНФ на основе использова- ния импликантной матрицы Квайна:
5) строим импликантную матрицу: в строки вписываем минтермы (члены СДНФ) заданной функции, а в столбцы – простые импликанты (члены сокращенной ДНФ);
6) если в некоторый минтерм входит какая-либо из простых импликант, то на пере- сечении соответствующего столбца и строки ставим метку (+);
7) если в какой-либо из строк стоит единственная метка, то соответствующая ей про- стая импликанта – ядровая, и она войдет в минимальную ДНФ;
8) далее из импликантной матрицы исключаются столбцы ядровых импликант, и строки минтермов, покрываемых этими импликантами;
9) если в полученной матрице имеются две одинаково помеченные строки, то одна из них вычеркивается;
10) если после удаления некоторых строк появляются непомеченные столбцы, то со- ответствующие им простые импликанты исключаются из дальнейшего рассмотрения;
11) в полученной матрице выбирается такая совокупность простых импликант, кото- рая включает метки во всех строках. При нескольких вариантах такого выбора предпочте- ние отдается варианту покрытия с минимальной сложностью;
12) дизъюнкция всех выбранных простых импликант (тупиковых) является мини- мальной ДНФ.
Все непомеченные конъюнкции являются простыми импликантами, поэтому сокра-
щенная ДНФ для данной логической функции имеет вид:

68

69
Сложность этих двух ДНФ равна 9, поэтому они обе представляют собой минималь-
ные ДНФ.
2.3.3. Метод минимизации по картам Карно
Карта Карно рассматривается как перестроенная соответствующим образом таб- лица истинности функции, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит пяти. С помощью этой карты реализуются операции попарного неполного склеивания и элементарного поглощения.
Карты Карно для функций, зависящих от n переменных, представляет собой таблицу из 2
n
клеток. Каждой клетке ставится в соответствие двоичный n-мерный набор значений переменных, причем наборы двух соседних клеток отличаются значениями одной перемен- ной. При этом соседними являются не только рядом стоящие клетки, но и крайние правые с крайними левыми, и крайние нижние с крайними верхними.
Рассмотрим примеры разметок карты Карно для функций, зависящих от 2 до 5 пере- менных. В разметках карты Карно ячейки заполнены наборами значений переменных функ- ции, которые составлены из меток соответствующего столбца и соответствующей строки,

70
Необходимо обратить внимание, что в процессе нахождения минимальной ДНФ в таб- лицу будут вноситься не наборы значений переменных, как в примере, а значения функции на этих наборах. При этом нулевые значения обычно не вписываются в соответствующие клетки таблицы, а оставляются пустыми. Другими словами, заполненные клетки соответ- ствуют минтермам, а пустые – макстермам.
Алгоритм построения минимальной ДНФ с помощью карты Карно:
1) построим пустую карту Карно и расположим переменные, от которой зависит функция, и их значения по краям таблицы;
2) заполняем карту Карно единицами в соответствии с таблицей истинности;
3) объединяем в прямоугольные области смежные клетки, содержащие только еди- ницы, так, чтобы одна область содержала 2
k
клеток
(
k = 0,1,,
)
. При этом:
а) область должна охватывать как можно больше единиц, а количество областей должно быть как можно меньше; б) области могут пересекаться;

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

72
Анализируем область S
2
. Для этой области переменная x не меняет своего значения, она равна 0 и войдет в конъюнкцию с отрицанием. Переменная z также не меняет своего значения, она равна 1 и войдет в конъюнкцию без изменения. Переменная y меняет свое значение, значит, она не войдет в конъюнкцию. Таким образом, области соответствует конъюнкция ¬???? ∙ ????.
Полученные конъюнкции (импликанты) соединяем дизъюнкцией и получаем следую- щую минимальную ДНФ со сложностью, равной 3:
f
(
x y z, ,
)
= y Ú x z×
Анализ каждой из областей дает следующие импликанты:

73
Таким образом, минимальная ДНФ функции
g
имеет вид:
Примечание:
Для построения минимальной КНФ делается все то же самое, только рассматриваем клетки с нулями, неменяющиеся переменные в пределах одной области объединяем в дизъ- юнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию.
2.3.4. Метод неопределенных коэффициентов
Метод применим для минимизации функций алгебры логики от любого числа пере- менных. Но метод является громоздким, поэтому практически не используется.
Исходную логическую функции можно записать в виде ДНФ с неопределенными ко- эффициентами, в которой элементарные конъюнкции представляют собой всевозможные комбинации из переменных и их отрицаний. Неопределенные коэффициенты, фигурирую- щие в конъюнкциях, принято снабжать двумя наборами индексов – нижним и верхним.
Нижний набор указывает на то, из каких переменных составлена конъюнкция, а верхний – о том, взята сама переменная или ее отрицание.
Для простоты описания метода рассмотрим минимизацию функции, зависящей от трех переменных.
Представим в общем виде функцию ????(????
1
, … , ????
????
) следующей ДНФ, составленной из всевозможных конъюнкций:
Если подставить значения наборов переменных в формулу и приравнять полученные выражения значению функции на выбранных наборах, то получим систему уравнений из 2
n
уравнений, где в данном случае
n = 2.

74
Очевидно, что в правой части каждого уравнения будет стоять ноль или единица. Для решения уравнения, в правой части которого стоит ноль, необходимо приравнять нулю все коэффициенты, входящие в это уравнение, что вытекает из определения дизъюнкции.
В остальных уравнениях удаляются нулевые коэффициенты. Затем выбирают в си- стеме самые короткие уравнения, в которых приравнивают единице коэффициенты, опре- деляющие конъюнкции наименьшего возможного ранга. При этом надо выбрать такие конъюнкции, которые чаще встречаются в уравнениях системы. Остальные коэффициенты можно положить равными 0 или 1. Затем рассматривают оставшиеся уравнения и в них выбирают коэффициенты, соответствующие конъюнкциям наименьшего ранга по тому же принципу, и т. д.
Найденные единичные коэффициенты определяют конъюнкции с наименьшим ран- гом, а форма, записанная с этими коэффициентами, определяет минимальную ДНФ функ- ции.

75
Контрольные вопросы
1. Что называется импликантой булевой функции?
2. Что такое простая импликанта?
3. Какая ДНФ называется сокращенной?
4. Как влияет ядровая импликанта на ДНФ?
5. Чем характеризуется минимальная ДНФ?
6. Что такое тупиковая ДНФ?
7. Какие ДНФ дает метод Квайна?
8. Что представляет собой импликантная матрица Квайна, для чего она используется?
9. Как соотносятся карта Карно и таблица истинности функции?

76 10. Какие свойства булевых операций реализуются методами Квайна и Карно?
11. Какую ДНФ дает метод Карно?
12. Какую ДНФ дает метод неопределенных коэффициентов?
13. Почему метод неопределенных коэффициентов используется редко для миними- зации логических функций?

77