- •Конспект лекций по информатике и программированию
- •Часть 1. Основы информатики
- •1. Проблемы информатизации современного общества
- •1.1 Информация и время
- •1.2. Информатика
- •1.3. Как развивалась информатика
- •1.4. Рождение эвм
- •1.5. Современная информатика
- •1.6. Компьютеризация общества
- •1.7. Информационная технология
- •Литература
- •2. Основные понятия информатики
- •2.1. Определение информации
- •2.2. Количество информации
- •2.3. Кодирование информации
- •2.4. Участники процесса передачи информации
- •2.5. Ценность информации
- •2.6. Формы представления информации
- •2.7. Размерность информационных множеств
- •2.8. Параметрическая информация
- •2.9. Элементы теории информации
- •3. Арифметические основы эвм
- •3.1. Системы счисления
- •3.2. Позиционные и непозиционные системы счисления
- •3.3. Двоичная система счисления
- •3.4. Арифметические действия и коды чисел
- •3.5. Представление информации в форме с фиксированной и плавающей точкой
- •3.6. Прямая, обратная и дополнительная форма представления двоичных чисел в эвм
- •4. Логические основы эвм
- •4.1. Алгебра логики
- •4.2 Логические операции
- •4.3. Аксиомы алгебры логики
- •4.4. Законы (теоремы и тождества) алгебры логики
- •4.5. Логические функции
- •4.6. Область определения логических функций
- •4.6. Таблица истинности
- •4.7. Логические функции одной переменной
- •4.8. Логические функции двух переменных
- •4.9. Теоремы разложения
- •4.10. Представление логической функции в виде сднф и скнф
- •4.10.1. Первичные термы
- •4.10.2. Минтермы и макстермы
- •4.10.3. Запись функции в виде сднф и скнф
- •4.10.4. Совершенные нормальные формы в базисах и-не и или-не
- •4.11. Минимизация логических функций
- •4.11.2. Правила минимизации логических функций
- •4.11.3. Минимизация функции с помощью карты Карно
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.