Лекционный курс по основам информатики, страница 10
Описание файла
Документ из архива "Лекционный курс по основам информатики", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "информатика" в общих файлах.
Онлайн просмотр документа "Лекционный курс по основам информатики"
Текст 10 страницы из документа "Лекционный курс по основам информатики"
аналитический, весьма трудоемок и требует не тривиального подхода, который не всегда виден;
графический, наиболее нагляден, прост в использовании, но может иметь некоторые ограничения.
Очевидно, что любой метод минимизации может основываться только на тождественном преобразовании логических выражений.
4.11.1. Конъюнктивные и дизъюнктивные термы
Конъюнктивным термом (контермом) называется: конъюнкция любого числа первичных термов, если каждый первичный терм с индексом p входит в него не более одного раза.
- функция 
представляет собой конъюнкцию первичных термов.
Дизъюнктивным термом (дизтермом) называется: дизъюнкция любого числа первичных термов, если каждый первичный терм с индексом p входит в нее не более одного раза.
- функция
представляет собой дизъюнкцию первичных термов.
Пример: Возьмем две точки области определения функции трех переменных i=110 (001)2и j=510 (101)2. Выразим эти точки через термы 
.
Для точки i - 
Для точки j - 
1. Сложим первичные термы с одинаковыми индексами точки i и точки j соответственно.
, 
, 
- перемножим полученные результаты 
получим: 
- контерм точек 1 и 5 области определения функции трех переменных.
2. Перемножим первичные термы с одинаковыми индексами точки i и точки j соответственно, при этом проведем инверсию каждого терма, 
, 
, 
сложим полученные результаты, 
получим: 
- дизтерм точек 1 и 5 области определения функции трех переменных.
4.11.2. Правила минимизации логических функций
Общие правила можно установить только для случаев, когда в результате минимизации получаются так называемые минимальные нормальные формы (МНФ) функций.
Есть понятие соседних минтермов (макстермов): - два минтерма 
и 
будем называть соседними, если они различаются только одним первичным термом 
, т.е. для одного из минтермов ep=0, а для другого ep=1 (все же остальные первичные термы одинаковые)
Например: если n=3, то минтермы 
и 
являются соседними, так как они различаются только одним первичным термом 
. Для минтерма 
соседними являются также минтермы 
и 
. Отсюда можно сказать, что каждый минтерм n переменных имеет по n соседних минтермов из общего числа 2n минтермов.
Рассмотрим контерм n переменных 
, не зависящий от одной переменной, т.е. случай, когда контерм является конъюнкцией (n-1)-го первичного терма. Данный контерм можно представить в виде
. Очевидно, что полученные минтермы и 
являются соседними, так как они различаются только одним первичным термом . Отсюда следует правило минимизации: дизъюнкцию двух соседних минтермов можно заменить одним контермом, независящим от одной переменной.
Если минтерм имеет два соседних минтерма, то их можно заменить двумя контермами независящих от соответствующих переменных, так как согласно закону 1.6 (x+x=x) минтерм, который соседний с двумя другими, можно заменить на дизъюнкцию любого числа равных ему минтермов. В результате такого объединения можно получить контермы соседние друг с другом. Их так же можно объединить, получая из двух соседних контермов, независящих от одной переменной, один контерм, независящий од двух переменных. Такая процедура проводится до тех пор пока функция будет состоять только из не соседних контермов или минтермов.
Исходя из выше сказанного, можно установить общее правило минимизации: одним контермом n переменных , не зависящим от m переменных 
, можно заменить дизъюнкцию 2m минтермов, если каждый из них имеет по m соседних минтермов среди остальных 2m-1 минтермов.
В результате таких операций получается функция: 
- такая форма представления функции называется ДНФ, а если она содержит минимально возможное число первичных термов , то она называется минимальной ДНФ (МДНФ).
Получение минимальной конъюнктивной нормальной формы (МКНФ) сводится к нахождению двойственной функции от МДНФ, в результате чего получаем: 
4.11.3. Минимизация функции с помощью карты Карно
Карты Карно представляют собой один из табличных способов задания функций, и состоит из клеток, каждая из которых соответствует определенной точки vi области определения функций. Карты Карно для функции n переменных состоит из 2n клеток, которые нумеруются числами от 0 до 2n-1. Чтобы с помощью такой карты задать функцию f(v), необходимо в каждую клетку с номером i занести значение функции f(vi)= 0 или 1, которое оно принимает в точке vi.
