- •Часть 2
- •8.091501–«Компьютерные системы и сети» и
- •7.091503–«Специализированные компьютерные системы»
- •Содержание
- •Введение
- •1 Основные понятия и определения алгебры логики и цифрового конечного автомата
- •1.1 Основные определения алгебры логики
- •1.2 Конечный автомат
- •1.3 Основные логические операции
- •1.3.1 Операция отрицания
- •1.3.2 Операция логического умножения
- •1.3.3 Операция логического сложения
- •1.3.4 Операция эквиваленция
- •1.3.5 Операция импликация
- •1.3.6 Сумма по модулю 2
- •1.3.7 Штрих Шеффера
- •1.3.8 Стрелка Пирса
- •2 Зависимость состава функций от числа переменных
- •2.1 Состав функций при отсутствии входных переменных
- •2 .2 Функции одной переменной
- •2.3 Функции двух переменных
- •2.4 Действительные и фиктивные функции
- •2.5 Определение общего числа функций
- •3 Суперпозиция функций
- •3.1 Методы суперпозиции
- •3.2 Выражение одних элементарных функций через другие
- •4 Свойства законов и правила алгебры логики
- •4.1 Свойства операций конъюнкции, дизъюнкции и отрицания
- •4.2 Свойства суммы по модулю 2, импликации, функции Шеффера и Пирса
- •5.1.1 Представление лф в совершенной дизъюнктивной нормальной форме
- •5.1.2 Дизъюнктивная нормальная форма лф
- •5.1.3 Представление лф в совершенной конъюнктивной нормальной форме
- •5.2 Основные свойства и алгоритм получения сднф, скнф
- •5.2.1 Общие свойства сднф
- •5.2.2 Алгоритм записи сднф
- •5.2.3 Свойства скнф
- •5.2.4 Алгоритм записи скнф
- •5.3 Способы преобразования днф и кнф в сднф и скнф
- •6 Полные системы функций
- •6.1 Функционально полные базисы
- •6.2 Теорема Поста
- •7 Методы минимизации функций алгебры логики
- •7.1 Аналитический метод минимизации фл
- •7.2 Числовое и геометрическое представление фл
- •7.3 Минимизация фл с помощью комплекса кубов
- •7.3.1 Построение комплекса кубов и его минимального покрытия
- •7.3.2 Цена покрытия кубов
- •7.4 Метод неопределенных коэффициентов
- •8 Метод квайна-мак-класки
- •9 Метод минимизации фл с помощью карт карно
- •9.1 Правила минимизации по картам Карно
- •9.1.1 Соседние клетки
- •9.1.2 Правило объединения соседних клеток
- •9.1.3 Определение простых импликант
- •9 .2 Не полностью определенные логические функции в картах Карно
- •10 Анализ и структурный синтез цифровых автоматов
- •10.1 Задачи анализа и синтеза
- •10.2 Синтез элементов логических схем
- •10.3 Особенности схем логических элементов
- •10.3.1 Базовый логический элемент
- •10.3.2 Элемент с открытым коллектором
- •10.3.3 Элементы и - или – не и расширители
- •10.3.4 Трисабильные элементы
- •10.4 Временные параметры логических микросхем
- •10.5 Переходные процессы в логических схемах микросхем
- •11 Комбинационные схемы
- •11.1 Построение преобразователя кодов
- •11.2 Сумматоры
- •11.3 Временные логические функции
- •12 Способы задания цифровых конечных автоматов
- •12.1 Математические модели ца
- •12.2 Табличный способ задания ца
- •12.3 Задание цифрового автомата графом
- •12.4 Минимизация абстрактных автоматов
- •13 Методы структурного синтеза автоматов
- •13.1 Канонический метод синтеза автомата
- •13.1.1 Пример синтеза ца каноническим методом
- •13.2 Структурный синтез ца по методу графа автомата
- •13.3 Метод синтеза ца по граф–схеме алгоритма
- •13.4 Синтез автомата с жесткой логикой управления
- •13.4.1 Принцип работы микропрограммного автомата с жесткой логикой управления
- •13.4.2 Проектирование микропрограммного автомата с жесткой логикой управления
- •14 Язык задания поведения цу - vhdl и синтезатор leonardo
- •15 Программируемые логические матрицы
- •16 Схемы основных логических устройств
- •16.1 Элементы памяти последовательностных логических схем
- •16.1.1 Триггер
- •16.1.1.1 Асинхронный rs - триггер
- •16.1.1.2 Синхронный rs - триггер
- •16.1.2 Универсальный jk-триггер
- •16.2 Регистры
- •16.2.1 Параллельные и последовательные регистры
- •16.2.2 Реверсивный регистр сдвига
- •Список литературы
1.3.4 Операция эквиваленция
Называется – эквиваленция (равнозначность, эквивалентность, взаимозависимость). Логико-математическая символика для двух переменных имеет несколько видов:
y=x1~x2, y = x1 ≡ x2, y = x1↔x2. Читается: x1 как х2.
Операцией эквиваленции называется такая функция нескольких переменных, которая истинна тогда, когда все переменные или истинны или ложны.
Обычно логический элемент эквиваленции строят на элементах И, ИЛИ, НЕ (см. рисунок 1.5), например, на основе эквивалентности функций.
1.3.5 Операция импликация
Называется импликация (разделение с запретом, следование, селекция).
Логико-математическая символика для двух переменных имеет вид:
y=x1→x2, y =x1 x2 y=x1> x2. Читается: если x1 ..., то х2.
Логическая операция двуместная. Простое высказывание x1 называется посылкой импликации, х2 - ее заключением.
В случае импликации несоответствие между обычным пониманием истинности сложного высказывания и точкой зрения смысла высказываний еще заметнее, чем для других логических операций.
Например. Если в Запорожье идет дождь, то все дороги грязные.
Главное отличие состоит в том, что смысловое содержание подразумевает причинную связь между посылкой и заключением.
Операцией импликации называется такая функция f(x1,x2), которая ложна тогда и только тогда, когда x1 истинно, а х2 ложно.
На рисунке 1.6 представлены две схемы логической функции импликации построенной на элементах И, ИЛИ, НЕ для двух эквивалентных функций.
1.3.6 Сумма по модулю 2
Называется: сумма по модулю 2 (сложение по модулю 2, неравнозначность, антиэквивалентность).
Логико-математическая символика для двух переменных имеет несколько видов:
y = x1 x2, y = x1 x2,y =x1+x2, y =f(x1, x2,..., xn)∙mod2.
Читается: сложение x1 и х2 по модулю 2.
Функцией сложения переменных по mod2 называется функция, которая ложна тогда, когда число истинных переменных четно или равно нулю и наоборот.
Очень часто применяется в технике цифровых автоматов для контроля правильности передачи информации по информационному каналу.
Для функции y=x1 x2 строится техническая реализация (см. рисунок 1.7) с помощью следующего соответствия:
x1 x2 = x1 + x2 = (x1 + x2)( + ).
1.3.7 Штрих Шеффера
Называется: штрих Шеффера (отрицание конъюнкции, несовместимость, логическое НЕ-И). Эта функция названа по имени немецкого математика Шеффера, который на основе этой функции создал свою алгебру логики. Логико-математическая символика:
Читается: x1 и х2 не.
Функцией штрих Шеффера называется функция которая ложна только тогда, когда x1 и х2 истинны.
Для функции строится техническая реализация (см. рисунок 1.8) с помощью следующего соответствия .
1.3.8 Стрелка Пирса
Называется: стрелка Пирса (функция Вебба, отрицание дизъюнкции, логическое НЕ-ИЛИ).
Математики Пирс и Вебб, независимо друг от друга изучавшие свойства этой функции, создали алгебру логики, названную алгеброй Пирса. Логико-математическая символика:
y=x1↓x2, y=x1◦x2, y= . Читается: x1 или x2 не.
Функцией стрелка Пирса (Вебба) называется функция f(x1,x2,…,xn), которая истинна только тогда, когда ложны все переменные.
Мы рассмотрели основные логические функции от одной, двух и более переменных, которые нашли наибольшее применение в технике цифровых автоматов. Проведем анализ этих функций и их зависимость от числа входных переменных.