85990 (Математическая логика), страница 4
Описание файла
Документ из архива "Математическая логика", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "математика" в общих файлах.
Онлайн просмотр документа "85990"
Текст 4 страницы из документа "85990"
5. Проверим принадлежность заданной функции f1 классу монотонных функций. Из таблицы видно: 001< 010, но 
. Следовательно, функция 
.
Рассмотрим функцию 
.
1. Принадлежность функции классу К0:
.
Следовательно, 
.
2. Принадлежность функции классу К1:
.
Следовательно, 
.
3. Принадлежность функции классу К л.
Предполагаем, что
.
Фиксируем набор 0000:
,
, 
.
Фиксируем набор 1000:
,
.
Фиксируем набор 0100:
,
.
Фиксируем набор 0010:
,
.
Фиксируем набор 0001:
.
.
Окончательно получаем
.
Это равенство на других 11 наборах не выполняется. Действительно, для набора 1111 имеем
, 
, т.е. 
.
Следовательно, 
.
4. Принадлежность функции классу самодвойственных функций.
Строим таблицу:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
Из таблицы видно, что на наборах 1 и 14, 2 и 13, 7 и 8 функция принимает одинаковые значения. Следовательно, 
.
5. Принадлежность функции классу монотонных функций.
Из таблицы видно, что 1000>0000, а 
. Следовательно, 
.
Строим критериальную таблицу:
| К 0 | К 1 | К л | К с | К м | |
| f 1 | + | - | - | - | - |
| f 2 | - | - | - | - | - |
В таблице в каждом столбце стоит хотя бы один минус. Следовательно, система булевых функций является полной.
Найдем все возможные базисы. По критериальной таблице составим к.н.ф. К, в которой элементарные дизъюнкции соответствуют столбцам таблицы и включают в качестве слагаемых символы тех функций, которые не входят в класс, соответствующий столбцу. В данном случае имеем
.
Используя законы и свойства дизъюнкции и конъюнкции, приведем к.н.ф. К к д.н.ф. D, в которой упрощение 
невозможно. В нашем случае получим
.
По полученной д.н.ф. D выпишем подмножества функций, соответствующие слагаемым д.н.ф. D. Это и будут искомые базисы. В нашем случае имеется два базиса:
.
Минимальная форма представления ФАЛ содержит минимальное количество термов и переменных в термах (т.е. не допускает никаких упрощений).
Пример.
,
- минимальная форма.
4 Способы представления функций алгебры логики
Для булевых функций существуют различные способы представления: таблица истинности, числовой, аналитический.
Пример.
Пусть функция 
задана таблицей истинности:
| № набора | х1 | х2 | х3 |
|
| 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 0 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 0 |
В таблице в первом столбце под номером набора понимается десятичный эквивалент соответствующего двоичного набора.
Тогда запись 
или 
является числовым представлением этой функции, где в скобках показаны номера наборов, на которых функция принимает значение 1.
Запись
представляет собой аналитическое представление булевой функции.
Можно в выражении функции вместо конъюнкций термов записать соответствующие двоичные наборы. Тогда получим:
.
Булеву функцию можно задать с помощью единичного п – мерного куба (рис. 7).
Рис. 7
Единичным п – мерным кубом называется граф, каждая вершина которого взаимно однозначно соответствует двоичному набору. Две вершины соединены ребром, если соответствующие наборы отличаются только в одном разряде (в одной координате).
На рис. 7 показаны п-мерные кубы для булевых функций: двух переменных (а), трех переменных (б), четырех переменных (в).
Отметив вершины, в которых булева функция принимает единичные значения, получим геометрическое представление булевой функции. Так функция
примет вид:
Рис. 8
Часто для изображения булевых функций двух и трех переменных используют прямоугольную систему координат:
Рис. 9
Изображение булевых функций числа переменных более трех в этом случае невозможен.
В методе минимизации булевых функций Квайна – Мак-Класки используется кубическое представление булевых функций (аналог п-мерных кубов).
Терм максимального ранга принято называть 0-кубом и обозначать К 0. Если два 0-куба из комплекса К 0 различаются только по одной координате, то они образуют куб (отрезок) K 1.
Пример.
Для
.
5. Минимизация булевых функций
Импликантой функции называют некоторую логическую функцию, которая обращается в ноль на том же наборе переменных, на котором равна нулю сама функция.
Любой конъюнктивный терм (элементарная конъюнкция) или группа термов, соединенных знаками дизъюнкции, входящие в СДНФ, являются импликантами исходной функции
Элементарная конъюнкция (конъюнктивный терм), в которой удален один или несколько первичных термов, называется простой импликантой.
Методов минимизации булевых функций в настоящее время существует довольно много. Все они, как правило, состоят из двух этапов. На первом этапе получают список всех простых импликант, т.е. сокращенную ДНФ. На втором этапе, используя таблицу покрытий, удаляют “лишние” импликанты, покрывемые другими импликантами. В результате получают ДНФ, из которой нельзя удалить ни одной импликанты. Такую ДНФ называют тупиковой.
5.1 Метод Квайна
На первом этапе в методе Квайна попарно сравнивают все импликанты, входящие в СДНФ, в целях выявления возможности поглощения какой-то переменной на основе закона склеивания:
.
Процедура продолжается до тех пор, пока не останется ни одного члена, допускающего поглощение с другим термом. В результате получают некоторое количество простых импликант. Дизъюнкция этих импликант является сокращенной ДНФ.
На втором этапе строится таблица покрытий.В строках этой таблицы указываются найденные простые импликанты, а в столбцах – термы исходного выражения функции. Клетки таблицы отмечаются, если простая импликанта входит в состав какого-либо терма. В итоге минимизация булевой функции сводится к тому, чтобы найти такое минимальное количество простых импликант, которые покрывают все столбцы. В результате получают тупиковую ДНФ.
Недостаток метода–необходимость попарного сравнении всех конъюнктивных термов на первом этапе при нахождении простых импликант. С ростом числа исходных термов увеличивается количество попарных сравнений, что усложняет решение задачи минимизации.
5.2 Метод Квайна с применением п-мерных кубов
Данный метод устраняет недостаток предыдущего метода, т.е. устраняет необходимость попарного сравнения всех термов на первом этапе при нахождении простых импликант. Для этого строится п-мерный куб, по которому визуально можно определить те конъюнктивные термы, склеивание которых порождают простые импликанты.
При решении задачи минимизации булевой функции удобно вместо конъюнктивных термов использовать, соответствующие им, двоичные наборы.
Пример.
Минимизировать булеву функцию
.
Здесь в скобках стоят десятичные эквиваленты соответствующих двоичных наборов.
