- •Часть 2
- •Введение
- •1 Объем учебной программы
- •1.1 Объем теоретической части
- •1.2 Перечень вопросов по защите контрольной работы
- •1.2.1 Основные логические операции.
- •2 Теоретические основы
- •2.1 Конечный автомат
- •2.2 Основные логические операции
- •2.2.1 Операция отрицания
- •2.2.2 Операция логического умножения
- •2.2.3 Операция логического сложения
- •2.2.4 Операция эквиваленция
- •2.2.5 Операция импликация
- •2.2.6 Сумма по модулю 2
- •2.2.7 Штрих Шеффера
- •2.2.8 Стрелка Пирса
- •2.3 Функции одной переменной
- •2.4 Функции двух переменных
- •2.5 Выражение одних элементарных функций через другие
- •2.6 Законы и правила конъюнкции, дизъюнкции и отрицания
- •2.7 Аналитические формы представления лф
- •2.7.1 Представление лф в совершенной дизъюнктивной форме
- •2.7.2 Дизъюнктивная нормальная форма
- •2.7.3 Представление лф в совершенной конъюнктивной форме
- •2.8 Аналитический метод минимизации фл
- •2.9 Метод минимизации фл с помощью карт Карно
- •2 .9.1 Правила минимизации по картам Карно
- •2.9.2 Соседние клетки карт Карно
- •2.9.3 Правило объединения соседних клеток
- •2.9.4 Определение простых импликант
- •2.9.5 Не определенные логические функции в картах Карно
- •2.10 Синтез комбинационных схем
- •2.11 Построение преобразователя кодов
- •2.12 Программируемые логические матрицы
- •3.1.5 Задание 5
- •Пример решения.
- •3.2 Вариантное задание
- •3.2.1 Задание 6
- •Пример решения.
- •4 Требования к оформлению контрольной работы
- •4.1 Перечень технической литературы
2.5 Выражение одних элементарных функций через другие
Анализ таблиц функций для одной и двух переменных показывает, что между функциями имеются зависимости
yi = 3-i, где i = 0, 1,2,3; (2.1)
yi = 15-i, где i = 0, 1, ... ,15.
На основании этих зависимостей можно записать соотношения, выражающие одни элементарные функции через другие.
Для одной переменной:
0 = ; 1 = ; х = . (2.2)
Для двух переменных:
x1x2 = ; x1 ← x2 = ;
x1 x2 = ; x1+x2 = ; (2.3)
x1 / x2 = ; x1 → x2 = ; (2.4)
или
x1 ~ x2 = ; x1 ↓ x2 = .
По таблицам соответствия (истинности) можно доказать следующее равенство, получившее наибольшее распространение.
x1 → x2 = +x2; x1 ~ x2 = ( + x2)( x1 + ).
Из подстановки в 2.3 последнего равенства эквиваленции получим:
x1 x2 = ; (2.5)
С помощью таблиц истинности легко доказать равенства
x1 + x2 = ; x1x2 = . (2.6)
Как обобщение 2.6 получаем следующие формулы, названные правилом де Моргана:
x1+x2 +x3+…+ xn = ; (2.7)
x1x2x3 ·…· xn = . (2.8)
Закон де Моргана построен на принципе двойственности.
Определение: логическое сложение n-переменных равно отрицанию логического умножения отрицаний этих переменных.
Логическое умножение n-переменных равно отрицанию логического сложения отрицаний этих переменных.
Операции + и & являются взаимно двойственными.
Для лучшего усвоения правила де-Моргана важно запомнить следующее:
логический знак между переменными изменяется, а черта общего отрицания делится на все переменные.
, .
Если теперь над левой и правой частями уравнений поставить общее отрицание, что не изменит знак равенства, то получим следствие правила де-Моргана
, .
Учтя взаимно уничтожающие двойные отрицания, получим то же определение
, .
Это можно записать в более сокращенном виде как обобщенный закон дуальности (закон де-Моргана –Шеннона), который выражается:
= , = ,
= , = .
Правило де Моргана и его следствие широко используется в аналитических преобразованиях логических функций при их минимизации.
2.6 Законы и правила конъюнкции, дизъюнкции и отрицания
Алгебра Буля, основана на логических операциях конъюнкции, дизъюнкции и отрицания, базируется на следующих основных законах:
- переместительный (свойство коммутативности);
- сочетательный (свойство ассоциативности);
- распределительный (свойство дистрибутивности);
- идемпотенции (свойство сохранять степень и постоянство коэффициента);
-инверсии (правило де Моргана).
В таблице 2.3 приведена интерпретация свойств этих законов для операций булевой алгебры конъюнкции, дизъюнкции и отрицания Следствие 5а получено из 5 путем общего отрицания левой и правой части равенства.
Доказать эти соотношения можно, например, посредством составления таблиц истинности для правой и левой части уравнений.
Используя основные законы, получим ряд очевидных правил (см. таблицу 2.4).
2.7 Аналитические формы представления лф
Для описания ЦА используют аналитическую запись функций в виде логических формул, получаемых из тех же таблиц истинности по установленным правилам их записи. Рассмотрим некоторые определения.
Определение. Дизъюнктивный терм (макстерм) - терм, связывающий переменные, представленные в прямой или инверсной форме, знаком дизъюнкции. Например: F(x) = + х2 + х3 + х4.
Определение. Конъюнктивный терм (минтерм) - терм, связывающий переменные, представленные в прямой или инверсной форме, знаком конъюнкции. Например: F(x) = x1 х2 .