- •Часть 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 Основные понятия и определения алгебры логики и цифрового конечного автомата
1.1 Основные определения алгебры логики
Логика - это наука о законах и формах мышления.
Математическая логика - это наука о применении математических методов логики при анализе и синтезе логических задач в вопросах изучения основ математики.
Идея построения универсального языка математики выдвигалась еще в 17 веке Лейбницем. Но только в 19 веке Дж. Буль [1847г.], Пирс [1885г.], де Морган [1958г.] ввели в язык математической логики предикаты, предметные переменные и кванторы, после чего была предпринята попытка сведения всей математики к логике (Пост, Шеннон, Шестаков, Глушков, Яблонский и др.). Попытка, однако, не увенчалась полным успехом, т.к. оказалось не всегда возможным вывести из чисто логических аксиом существование некоторых понятий на бесконечном множестве 1.
Мы будем рассматривать наиболее элементарный раздел математической логики, который носит название алгебра логики. Другие наиболее часто употребляемые названия: булева алгебра, алгебра высказываний, бинарная логика.
Алгебра логики - раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений [истинности или ложности], и логическими операциями над ними.
Под высказываниями понимаются предложения, относительно смысла которых, можно утверждать, истинны они или ложны. Например, высказывание "кот - животное" - истинно, "все углы прямые "- ложно.
Для обозначения истинности вводится символ "И", обозначения ложности - символ "Л". Затем вместо этих символов стали употреблять числа {1,0}, как двоичные переменные, т.е. логическая 1 (Лог.1), логический 0 (Лог.0).
Закон исключения третьего - каждое высказывание может быть истинным или ложным (третьего не дано). При этом, высказывание не может быть одновременно истинным и ложным (закон противоречия).
Истинность высказывания устанавливается на основе анализа его смысла и обстоятельств, которыми руководствуются при его истолковании.
Например: "Киев - столица Украины" - истинно, а "100<10" - ложно. Однако. Первое утверждение перестает быть истинным, когда речь идет о периоде, когда столицей УССР был Харьков. Второе станет истинным, если 100 записано в двоичной системе, а 10 - в десятичной (4 < 10).
Абсолютно истинное высказывание - если высказывание не может быть ложным при любых условиях. Обозначается - Const 1.
Например: "Земля крутится".
Абсолютно ложное высказывание - если высказывание не может быть истинным при любых условиях. Обозначается - Const 0.
Например: "Земля - спутник Марса".
Абсолютно истинные (ложные) высказывания называются логическими константами.
Принятие закона исключения третьего позволяет полностью использовать в логике высказываний математический аппарат двузначной логики {1, 0}.
Интересно, что развивающийся сейчас математический аппарат многозначной логики позволяет исследовать высказывания при нескольких значениях, например, "истина", "ложь" и "неопределенность". Применяется при исследовании динамики переходных процессов. В рамках нашего курса не рассматривается.
Если истинность предложений определяется с некоторой вероятностью, то логика высказываний превращается в вероятностную логику.
В алгебре высказываний рассматриваются вопросы, связанные с образованием сложных высказываний. Если у нас имеется несколько простых высказываний, то при помощи логических связок и отрицаний из них можно образовать новые сложные высказывания. Конечно, простота и сложность высказываний относительны.
Например: "На улице светит солнце", "В аудитории идет занятие". Из этих высказываний можно образовать более десяти сложных, в том числе и бессмысленные высказывания, например: "Если в аудитории идут занятия, то на улице светит солнце".
Особенность алгебры высказываний - допускаются только грамматически правильные способы образования сложных высказываний и совершенно игнорируется смысл получившегося высказывания. В алгебре высказываний интересуются лишь истинностью или ложностью высказываний. Более того: в ней исследуется вопрос об истинности сложного высказывания в зависимости от истинности входящих в него простых высказываний и, с этой точки зрения, исследуются различные логические связки.
Например. "На улице светит солнце и в аудитории идут занятия - нормальный учебный процесс". Сложное высказывание может быть истинным, только если первое и второе - истины.
Один из главных вопросов, который нас интересует, заключен в получении истинного сложного высказывания из простых с помощью логических связок.
Наряду с простыми словесными высказываниями, примеры которых приводились выше, стали использовать буквенные обозначения переменных высказываний, т.е. такие переменные х, у, z, x1, x2 ... , значениями которых могут быть символы из множества {0,1} и обозначают заранее заданные индивидуальные высказывания.
Например: Х1=1 может обозначать высказывание: "Подан сигнал управления Х1 с уровнем напряжения +4,5В", что соответствует Лог.1.
Х1=0 может обозначать высказывание: "Подан сигнал управления Х1 с уровнем напряжения ≤0,3В", что соответствует Лог.0.
Х2-"Подан сигнал управления Х2".
Х3-"Подан сигнал управления Х3".
Таким образом, с помощью двузначных переменных Х1,Х2,... мы переходим к булевым переменным составляющим основу бинарной алгебры логики.
Булевыми переменными называются переменные, принимающие одно из двух значений множества {0,1}.
Логическая функция (ЛФ) - функция f(x1,x2,…,хn), принимающая значение из множества {0,1} на любых наборах логических переменных x1,x2,…,хn, также принимающих значения из множества {0,1}.