- •Конспект лекций по информатике и программированию
- •Часть 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.10.3. Запись функции в виде сднф и скнф
Возьмем функцию двух переменных x1x0. Применим к ней терему разложения для переменной x1.
Далее каждую из функций и разложим по переменной x0.
Такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ).
В общем виде представление функции в СДНФ:
Так как значение функции то если и если отсюда СДНФ можно представить в виде:
где i1 – номера точек, в которых функция .
СДНФ можно получить аналогичным способом с помощью теоремы разложения. Но можно пойти более легким путем.
Возьмем инверсию СДНФ: из данного соотношения на основании закона двойственности получим: а так как общий вид СКНФ:
Так как значение функции то если и если отсюда СКНФ можно представить в виде:
где i0 – номера точек, в которых функция .
4.10.4. Совершенные нормальные формы в базисах и-не и или-не
Совокупность элементарных функций, с помощью которых можно записать любую функцию , называется функционально полной системой функций или базисом. Из выше приведенного параграфа можно сделать вывод, что для представления любой функции , в СДНФ и СКНФ достаточно использовать только функции (операции) И, ИЛИ и НЕ, т.е. совокупность этих функций является базисом.
Преобразуем СДНФ функции с помощью законов двойного отрицания и де Моргана:
Данная форма представления функции называется совершенной нормальной формой (СНФ) в базисе И-НЕ, так как она требует использования только функций (операций) И-НЕ.
Проведем аналогичные действия с СКНФ:
Данная форма представления функций называется СНФ в базисе ИЛИ-НЕ, так как она требует использования только функций (операций) ИЛИ-НЕ.
4.11. Минимизация логических функций
Одной из основных задач, возникающих при синтезе комбинационных схем (КС), является минимизация логических функций, которые эти КС реализуют. Чем проще логическое выражение, описывающее функцию, тем проще и дешевле реализующая ее КС.
В качестве критерия сложности логического выражения, описывающего функцию, целесообразно принять числи первичных термов , в него входящих.
Существуют два метода минимизации:
аналитический, весьма трудоемок и требует не тривиального подхода, который не всегда виден;
графический, наиболее нагляден, прост в использовании, но может иметь некоторые ограничения.
Очевидно, что любой метод минимизации может основываться только на тождественном преобразовании логических выражений.
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 области определения функции трех переменных.