Слайд 1Основы математической логики
ИНФОРМАТИКА
Лекция № 6
Слайд 2Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со
стороны их логических значений (истинности или ложности) и логических операций
над ними.
Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.
Слайд 3Понятие высказывания
Высказывание - это повествовательное предложение,
относительно которого можно определенно сказать, истинно оно или ложно.
Например:
"Луна - спутник Земли" - истинное высказывание, "Два больше трех" - ложное высказывание. "Как вы себя чувствуете?", "Будь внимателен!" — не являются высказываниями и в алгебре высказываний не рассматриваются.
Высказывания принято обозначать буквами латинского алфавита. Так, высказывание "Трава — зеленая" можно обозначить буквой А, "Лев -птица" - буквой В и т. д.
Слайд 4Значения истинности высказываний
В алгебре высказываний отвлекаются от конкретного содержания высказывания
и интересуются лишь вопросом, является ли оно истинным или ложным..
Каждому верному высказыванию присваивается значение истинности 1 (истинно), каждому неверному - значение истинности 0 (ложно).
Например, А = 1, В = 0.
Слайд 5Операции над высказываниями
Над высказываниями можно производить логические операции.
В результате
выполнения операций получаются новые высказывания, истинность которых определяется истинностью исходных
высказываний и характером логических операций.
Слайд 6Операция логического умножения
Соединение двух высказываний союзом И называется логическим умножением,
или конъюнкцией.
Эта операция обозначается знаками: Λ , • , &.
Сложное высказывание А & В считается истинным только в том случае, если истинны оба входящих в него простых высказывания А и В.
Результат логического произведения легко обобщается на любое число сомножителей (самостоятельно сформулируйте правило).
Слайд 7Операция логического сложения
Соединение двух высказываний союзом ИЛИ называется логическим сложением,
или дизъюнкцией.
Операция обозначается знаками: V, +.
Сложное высказывание A
V В считается истинным в том случае, если истинно хотя бы одно из входящих в него простых высказываний А и В.
Результат логического сложения легко обобщается на любое число слагаемых (самостоятельно сформулируйте правило).
Слайд 8Операция отрицания
Присоединение частицы НЕ к высказыванию А называется отрицанием, или
инверсией.
Операция обозначается ~А или А ,
(читается: не А).
Если высказывание истинно, то его отрицание ложно, и наоборот.
Слайд 9Операция импликации
Импликация выражается словосочетанием « если…, то…». По определению импликация
А В истинна всегда за исключением случая, когда А
истинно, а В ложно.
Слайд 10Операция эквивалентности
Операция «Эквивалентность» обозначается знаками ,.
Сложное высказывание А
В( читается А эквивалентно В) истинно тогда и только тогда,
когда А – истинно и В истинно или А – ложно и В – ложно. В остальных случаях А В ложно.
Слайд 11A | B = (A&B)
Операция штрих Шеффера
Слайд 13Операция «Сложение по модулю два»
A B = A&
B A& B
Слайд 14ЛОГИЧЕСКИЕ ФОРМУЛЫ
Логическая формула –
это логические переменные, связанные логическими
операциями.
Слайд 16Порядок выполнения логических операций
Отрицание - операция первой ступени.
Конъюнкция (логическое умножение)
операция второй ступени.
Дизъюнкции (логического сложения) операция третьей ступени.
Скобки
используются для изменения порядка выполнения операций.
Слайд 17Тавтология
Если формула на всех наборах значений высказываний принимает значение истина,
то это тождественно истинная формула или тавтология.
Пример: F = (А
V B) V ( A & B)
Слайд 18Противоречие
Если формула на всех наборах значений высказываний принимает значение ложь,
то это тождественно ложная формула или противоречие.
Пример: F = (
А V B ) V ( A & B )
Слайд 19Выполнимая формула
Если формула на некоторых наборах значений высказываний принимает
значение истина, то это выполнимая формула.
Пример: F
= (АVB)V(A&B).
Слайд 22Пример доказательства закона дистрибутивности
Слайд 23Преобразования логических выражений
Формулы для отрицания:
Формулы для дизъюнкции:
Формулы для конъюнкции:
Правило
действия со скобками:
Операция поглощения:
Операция склеивания:
Формулы де Моргана:
Слайд 25КАК УПРОСТИТЬ ЛОГИЧЕСКУЮ ФОРМУЛУ?
Равносильные преобразования логических формул имеют то
же назначение, что и преобразования формул в обычной алгебре. Они
служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
Слайд 26Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают
равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению
с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Слайд 27ПРИЕМЫ И СПОСОБЫ, ПРИМЕНЯЕМЫЕ ПРИ УПРОЩЕНИИ ЛОГИЧЕСКИХ ФОРМУЛ
Законы алгебры
логики применяются в следующей последовательности: правило де Моргана, сочетательный закон,
правило операций переменной с её инверсией и правило операций с константами.
Слайд 28Примеры упрощения формул
Пример 1.
(применяется правило де Моргана, выносится за скобки
общий множитель, используется правило операций переменной с её инверсией).
Пример 2.
(повторяется
второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания).
Слайд 29Пример 3.
(вводится вспомогательный логический сомножитель ( ); затем комбинируются
два крайних и два средних логических слагаемых и используется закон
поглощения);
Слайд 30Какая связь между алгеброй логики и двоичным кодированием?
Математический аппарат алгебры
логики очень удобен для описания того, как функционируют аппаратные средства
компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.
Слайд 31Из этого следует два вывода:
- одни и те же
устройства компьютера могут применяться для обработки и хранения как числовой
информации, представленной в двоичной системе счисления, так и логических переменных;
- на этапе конструирования аппаратных средств алгебра логики позволяет значительно упростить логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить число элементарных логических элементов, из десятков тысяч которых состоят основные узлы компьютера.
Слайд 32В электронных устройствах компьютера двоичные единицы чаще всего кодируются более
высоким уровнем напряжения, чем двоичные нули (или наоборот), например:
Слайд 33ЛОГИЧЕСКИЙ ЭЛЕМЕНТ КОМПЬЮТЕРА
Логический элемент компьютера — это часть электронной
логичеcкой схемы, которая реализует элементарную логическую функцию.
Логическими элементами компьютеров являются
электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие (называемые также вентилями), а также триггер.
Слайд 34ФУНКЦИИ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ
Схема «И» реализует операцию логического умножения двух или
более логических значений.
Схема «ИЛИ» реализует логическое
сложение двух или более логических значений.
Схема «НЕ» реализует логическое отрицание логического значения.
Схема «И-НЕ» реализует отрицание результата схемы «И».
Схема «ИЛИ-НЕ» реализует отрицание схемы «ИЛИ».
Слайд 35Обозначение логических элементов
Слайд 36Построение электронной схемы по логическому выражению
Найдем группу операций одного типа
выполняемых в последнюю очередь. Обозначим количество операций группы через k.
Выберем
логический элемент. Соответствующий логическим операциям группы.
Свяжем с выходом логического элемента результат логического выражения.
Определим количество входов логического элемента.
Установим порядок выполнения логических операций.
Удалим из исходного логического выражения операции найденной группы.
Сопоставим каждому полученному выражению один из входов выбранного логического элемента.
Слайд 37Логический элемент НЕ (инвертор).
Слайд 39Логический элемент ИЛИ
Рис.2.10. Временные диаграммы
сигналов на входе и
выходе
логического элемента ИЛИ
Слайд 40Логические элементы И-НЕ и ИЛИ-НЕ
Слайд 41ПРИМЕР ПОСТРОЕНИЯ ЭЛЕКТРОННОЙ СХЕМЫ
Исходное логическое выражение:
E = D + B
С + D(A + B),
E = D + F+
G,
Разбиение исходного выражения:
D
F = B С,
G= D(A + B).
Слайд 44 Триггеры – элементы памяти цифровых автоматов, в свою очередь
являются элементарными цифровыми автоматами (автоматами Мура) с двумя устойчивыми состояниями.
Слайд 45Основные типы триггеров
триггер с раздельной установкой состояний (RS-триггер),
триггер "защелка"
(D - триггер),
универсальный триггер (JK - триггер),
триггер со счетным входом
(T - триггер)
Слайд 46
Основу триггера - кольцевая схема из
двух инверторов
Слайд 47Переходы асинхронного триггера RS-триггер
Слайд 48
Структурная схема и обозначение RS-триггера
Слайд 49Схема синхронного RS-триггера и его обозначение на функциональных схемах
Слайд 51Схема, условное обозначение на функциональных схемах D-триггера
Слайд 52D-триггер с дополнительными RS входами
Слайд 53Схема двухтактного синхронного D-триггера и его обозначение на функциональных схемах
Слайд 54Схема асинхронного и синхронного Т-триггеров и обозначение синхронного Т-триггера
Слайд 55Схема Т-триггера 8 на основе D-триггера
Слайд 56Обозначение JK-триггера с инверсным динамическим входом
Слайд 57Вопросы по лекции
В чем отличие конечного автомата от комбинационных схем?
Как
различаются автоматы Мура и Мили?
Сколько состояний имеет элементарный автомат?
Что такое
триггер?
Почему Т-триггер называют триггером со счетным входом?
В какое состояние перейдет Т-триггер при входном сигнале Т = 1?
Какая запрещенная комбинация входных сигналов для RS-триггера?
В какое состояние перейдет RS-триггер при сигнале S = 1?
В какое состояние перейдет JK -триггер при сигнале К = 1?
В какое состояние перейдет JK -триггер при сигнале J = K = 1?
