- •Часть 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 Реверсивный регистр сдвига
- •Список литературы
5.1.1 Представление лф в совершенной дизъюнктивной нормальной форме
Для изложения метода и алгоритма перехода от таблицы задания цифрового автомата к аналитическому представлению его с помощью функции алгебры логики, рассмотрим следующую теорему[1,2]:
Теорема. Любой таблично - заданный ЦА может быть представлен в виде логической функции совершенной дизъюнктивной нормальной формы ( СДНФ)
f (x1, x2, …, хn) = F1 + F2 + F3 + ... + Fn = Fi, (5.1)
где i - номера наборов, на которых функция равна 1, т.е.
- знак всеобщности совершенной дизъюнктивной нормальной формы, объединяющий все минтермы Fi, равные 1.
В самом деле, если на каких-либо наборах функция f(x1,x2,…,хn)=1, а на других наборах f(x1,x2,…,хn)=0 то, вследствие того, что х+1+…+1+0+…+0=1, в правой части объединения нулевые термы исчезают и всегда найдется хотя бы один минтерм, равный 1.
Поэтому, аналитическая запись 5.1 однозначно отображает таблицу истинности любого ЦА без элементов памяти для конечного числа переменных.
5.1.2 Дизъюнктивная нормальная форма лф
Дизъюнктивная нормальная форма (ДНФ) логических функций обычно получается после аналитических преобразований совершенной дизъюнктивной нормальной формы, например, минимизации. При этом, могут сократится некоторые термы, переменные, логические операции. Все это приведет к более сокращенной форме записи логической функции, по своей значимости, равносильной исходной СДНФ.
Дизъюнктивная нормальная форма (ДНФ) -дизъюнктивное объединение термов, включающее минтермы переменного ранга.
Например. Записать в аналитическом виде ЛФ заданную таблицей 5.1.
Таблица 5.1-Задание функции
x1 |
x2 |
х3 |
f(x) |
х1 |
x2 |
x3 |
f(x) |
0 0 0 0 |
0 0 1 1 |
0 1 0 1 |
1 0 0 1 |
1 1 1 1 |
0 0 1 1 |
0 1 0 1 |
1 0 0 0 |
Количество всех термов, входящих в аналитическую запись равно количеству конституэнт единицы (т.е. f(x) = l).
Тогда запишем функцию таблицы 5.1 в СДНФ:
f(x1, x2, x3) = + x2 x3 + x1 . Склеивая 1 и 3 минтермы, получим ДНФ
f(x1, x2, x3) = ( + x1)+ x2 x3= + x2 x3.
Следствие теоремы 5.1. Любая таблично заданная ЛФ может быть представлена в следующей аналитической форме:
f(xl, x2, ... ,xn) = F1 F2 ... Fn = Fi, (5.2)
Для того чтобы выполнялось это соотношение, необходимо, чтобы при обращении любого терма Fi в единицу все выражение обращалось в единицу, а при обращении всех термов в нуль все выражение также становится равным нулю. Функция сложения по mod2 отвечает этому требованию.
Представление ЛФ в виде 5.1 называют дизъюнктивным представлением, а 5.2 полиномиальным представлением.
5.1.3 Представление лф в совершенной конъюнктивной нормальной форме
Для получения представлений конъюнктивного типа рассмотрим функции Fi(xl, x2, ... ,xn), определяемые, как
Такие функции называют характеристическими функциями нуля.
Теорема. Любой таблично заданный ЦА может быть представлен в следующей совершенной конъюнктивной нормальной форме (СКНФ):
f(xl, x2, ... ,xn) = Fi1 · Fi2 · ... ·Fik = & Fi, i T0, (5.3)
где Т0 есть множество номеров наборов (кортежей) на которых функция f обращается в нуль. Доказательство теоремы аналогично. Если на каком-нибудь наборе функция f равна нулю, то этого достаточно, чтобы хоть один терм Fi равнялся нулю. А если f равна единице, то для этого все термы должны быть равными единице.
Следствие. Любая таблично заданная ФАЛ может быть представлена в следующей аналитической форме:
f(xl, x2, ... ,xn) = Fi1 ~ Fi2 ~ ... ~ Fik, (5.4)
где ij T0 принадлежит нулевым термам.
Представление функции в виде 5.3 называют конъюнктивным представлением, а в виде 5.4 называют равнозначностью. Можно показать представление ФЛ через штрих Шеффера, стрелку Пирса
Определение конъюнктивная. нормальная форма (КНФ) - обьединение термов, включающее в себя макстермы разных рангов.
Например: (х1 + х2 + )(х1 + х2)(х2 + ).