1 Основы математической логики ИНФОРМАТИКА Лекция № 6
2 Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.
3 Понятие высказывания Высказывание - это повествовательное предложение, относительно которого можно определенно сказать, истинно оно или ложно. Например: "Луна - спутник Земли" - истинное высказывание, "Два больше трех" - ложное высказывание. "Как вы себя чувствуете?", "Будь внимателен!" — не являются высказываниями и в алгебре высказываний не рассматриваются. Высказывания принято обозначать буквами латинского алфавита. Так, высказывание "Трава — зеленая" можно обозначить буквой А, "Лев -птица" - буквой В и т. д.
4 Значения истинности высказываний В алгебре высказываний отвлекаются от конкретного содержания высказывания и интересуются лишь вопросом, является ли оно истинным или ложным.. Каждому верному высказыванию присваивается значение истинности 1 (истинно), каждому неверному - значение истинности 0 (ложно). Например, А = 1, В = 0.
5 Операции над высказываниями Над высказываниями можно производить логические операции. В результате выполнения операций получаются новые высказывания, истинность которых определяется истинностью исходных высказываний и характером логических операций.
6 Операция логического умножения Соединение двух высказываний союзом И называется логическим умножением, или конъюнкцией. Эта операция обозначается знаками: Λ, •, &. Сложное высказывание А & В считается истинным только в том случае, если истинны оба входящих в него простых высказывания А и В. Результат логического произведения легко обобщается на любое число сомножителей (самостоятельно сформулируйте правило). А В А & В 0 0 0 0 1 0 1 0 0 1 1 1
7 Операция логического сложения Соединение двух высказываний союзом ИЛИ называется логическим сложением, или дизъюнкцией. О перация обозначается знаками: V, +. Сложное высказывание A V В считается истинным в том случае, если истинно хотя бы одно из входящих в него простых высказываний А и В. Результат логического сложения легко обобщается на любое число слагаемых (самостоятельно сформулируйте правило). А В А v В 0 0 0 0 1 1 1 0 1 1 1 1
8 Операция отрицания А А 0 1 1 0 Присоединение частицы НЕ к высказыванию А называется отрицанием, или инверсией. О перация обозначается ~ А или А, (читается: не А ). Если высказывание истинно, то его отрицание ложно, и наоборот.
9 Операция импликации Импликация выражается словосочетанием « если…, то…». По определению импликация А В истинна всегда за исключением случая, когда А истинно, а В ложно. А В А В 0 0 1 0 1 1 1 0 0 1 1 1
10 Операция эквивалентности Операция «Э квивален тность» обозначается знаками , . Сложное высказывание А В( читается А эквивалентно В) истинно тогда и только тогда, когда А – истинно и В истинно или А – ложно и В – ложно. В остальных случаях А В ложно. А В А В 0 0 1 0 1 0 1 0 0 1 1 1
11 А В А | В 0 0 1 0 1 1 1 0 1 1 1 0 A | B = (A&B) Операция штрих Шеффера
12 Операция стрелка Пирса А В А В 0 0 1 0 1 0 1 0 0 1 1 0 A B = (AVB)
13 Операция «Сложение по модулю два» A B = A& B A& B А В А В 0 0 0 0 1 1 1 0 1 1 1 0
14 ЛОГИЧЕСКИЕ ФОРМУЛЫ Логическая формула – это логические переменные, связанные логическими операциями.
15
16 Порядок выполнения логических операций О трицани е - операция первой ступени. Конъюнкция (логическое умножени е) операция второй ступени. Дизъюнкции (логического с ложения ) операция третьей ступени. Скобки используются для изменения порядка выполнения операций.
17 Тавтология Если формула на всех наборах значений высказываний принимает значение истина, то это тождественно истинная формула или тавтология. Пример: F = (А V B) V ( A & B) A B AVB A&B (A&B) F 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1
18 Противоречие Если формула на всех наборах значений высказываний принимает значение ложь, то это тождественно ложная формула или противоречие. Пример: F = ( А V B ) V ( A & B ) 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 F (A&B) A&B B A
19 Выполнимая формула Если формула на некоторых наборах значений высказываний принимает значение истина, то это выполнимая формула. Пример: F = (А VB)V(A&B). A B AVB (A&B) F 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1
20
21 Законы математической логики Закон Для ИЛИ Для И Коммутативный X V Y = Y V X X&Y=Y&X Ассоциативный XV(YVZ)=(XVY)VZ X&(Y&Z)=(X&Y)&Z Дистрибутивный X&(XVZ)=X&YVX&Z XVY&Z=(XVY)&(XVZ) де Моргана ( XVY)= X& Y (X&Y)= XV Y Идемпотенции XVX=X X&X=X
22 Пример доказательства закона дистрибутивности x+y*z=(x+y)*(x+z) x y z yz x+y z x+y x+z (x+y) (x+z) 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
23 Формулы для отрицания : Формулы для дизъюнкции : Формулы для конъюнкции : Правило действия со скобками : Операция поглощения : Операция склеивания : Формулы де Моргана : Законы математической логики
24 КАК УПРОСТИТЬ ЛОГИЧЕСКУЮ ФОРМУЛУ? Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
25 ПРИЕМЫ И СПОСОБЫ, ПРИМЕНЯЕМЫЕ ПРИ УПРОЩЕНИИ ЛОГИЧЕСКИХ ФОРМУЛ Законы алгебры логики применяются в следующей последовательности: правило де Моргана; сочетательный закон; правило операций переменной с её инверсией; правило операций с константами.
26 Примеры упрощения формул Пример 1. (применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией). Пример 2. ( повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания).
27 Пример 3. (вводится вспомогательный логический сомножитель ( ); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);
28 Какая связь между алгеброй логики и двоичным кодированием? Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.
29 Из этого следует два вывода: - одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных; - на этапе конструирования аппаратных средств алгебра логики позволяет значительно упростить логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить число элементарных логических элементов, из десятков тысяч которых состоят основные узлы компьютера.
30 В электронных устройствах компьютера двоичные единицы чаще всего кодируются более высоким уровнем напряжения, чем двоичные нули (или наоборот), например:
31 ЛОГИЧЕСКИЙ ЭЛЕМЕНТ КОМПЬЮТЕРА Логический элемент компьютера — это часть электронной логичеcкой схемы, которая реализует элементарную логическую функцию. Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие (называемые также вентилями), а также триггер.
32 ФУНКЦИИ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ Схема «И» реализует операцию логического умножения двух или более логических значений. Схема «ИЛИ» реализует логическое сложение двух или более логических значений. Схема «НЕ» реализует логическое отрицание логического значения. Схема «И-НЕ» реализует отрицание результата схемы «И». Схема «ИЛИ-НЕ» реализует отрицание схемы «ИЛИ».
33 Обозначение логических элементов & 1 & 1 A A&B B AVB B A A A B A 1 (AVB) B A (A&B)
34 Построение электронной схемы по логическому выражению Найдем группу операций одного типа выполняемых в последнюю очередь. Обозначим количество операций группы через k. Выберем логический элемент. Соответствующий логическим операциям группы. Свяжем с выходом логического элемента результат логического выражения. Определим количество входов логического элемента. Установим порядок выполнения логических операций. Удалим из исходного логического выражения операции найденной группы. Сопоставим каждому полученному выражению один из входов выбранного логического элемента.
35 Логический элемент НЕ (инвертор).
36 Логический элемент И
37 Логический элемент ИЛИ t t t U вх U вх U вых х 1 у х 2 Рис.2.10. Временные диаграммы сигналов на входе и выходе логического элемента ИЛИ
38 Логические элементы И-НЕ и ИЛИ-НЕ
39 ПРИМЕР ПОСТРОЕНИЯ ЭЛЕКТРОННОЙ СХЕМЫ Исходное логическое выражение: E = D + B С + D (A + B), E = D + F+ G, Разбиение исходного выражения: D F = B С, G= D (A + B).
40 1 Е F G D Выбор логического элемента F = B С, G= D (A + B).
41 Результат построения 1 Е & F G & 1 D В C A G= D (A + B ). F = B С
42 Триггеры – элементы памяти цифровых автоматов, в свою очередь являются элементарными цифровыми автоматами (автоматами Мура) с двумя устойчивыми состояниями. Триггеры
43 Основные типы триггеров триггер с раздельной установкой состояний (RS-триггер), триггер "защелка" (D - триггер), универсальный триггер (JK - триггер), триггер со счетным входом (T - триггер)
44 Структурная схема и обозначение RS -триггера Вход S – set – установка триггера в состояние «1» Вход R – reset – установка триггера в состояние «0»
45 Переходы асинхронного триггера RS-триггер
46 Схема синхронного RS -триггера и его обозначение на функциональных схемах
47 Схема, условное обозначение на функциональных схемах D -триггера При подачи синхроимпульса в D- триггер записывается состояние входа D.
48 D -триггер с дополнительными RS входами При подачи синхроимпульса в D- триггер записывается состояние входа D. Вход R =1 – переводит триггер в состояние «1», вход S=1 устанавливает триггер в состояние «0».
49 Схема двухтактного синхронного D -триггера и его обозначение на функциональных схемах Двухтактный триггер
50 Обозначение JK-триггера с инверсным динамическим входом
51 Вопросы по лекции В чем отличие конечного автомата от комбинационных схем? Как различаются автоматы Мура и Мили? Сколько состояний имеет элементарный автомат? Что такое триггер? Почему Т-триггер называют триггером со счетным входом? В какое состояние перейдет Т-триггер при входном сигнале Т = 1? Какая запрещенная комбинация входных сигналов для RS -триггера? В какое состояние перейдет RS -триггер при сигнале S = 1? В какое состояние перейдет JK -триггер при сигнале К = 1? В какое состояние перейдет JK -триггер при сигнале J = K = 1?
52 Вопросы по лекции
53 Устройства ЦВМ ЛЕКЦИЯ №
54 Дешифратор адреса Дешифратор адреса предназначен для опознавания адрес а устройства A. ДШ A 0 A 1 A 2 A 3 F A 3 A 2 A 1 A 0 (2) – запись адреса в двоичной системе счисления A 10 = A 3 * 2 3 + A 2 * 2 2 + A 1 * 2 1 + A 0 * 2 0 - адрес в десятичной системе счисления Если значение адреса A совпадает с значением адреса на входе устройства A, то на выходе дешифратора формируется сигнал равный 1, в противном случае сигнал равный нулю.
55 Пример дешифратора Допустим, адрес устройства, которое подключается к адресной шине, равен 5 10 (0 l 0 l 2 ). По сигналу с дешифратора это устройство должно активизироваться, если на адресной шине появляется сигнал, равный пяти (Аз = 0, A 2. = 1, А 1 = 0, А 0 = 1), т. е. дешифратор распознает адресный код, равный пяти, и при этом на выходе дешифратора вырабатывается сигнал, равный логической единице. При любом другом значении адресного кода на выходе дешифратора вырабатывается сигнал, равный логическому нулю. Шина - это канал передачи электрических сигналов, который может состоять из нескольких параллельных проводников. Шина, предназначенная для передачи адреса устройства называется шиной адреса.
56 Правило построения дешифратора адреса 1. Произведем перевод адресного кода из десятичной системы счисления в двоичную систему счисления и дополним полученное двоичное число слева нулями до необходимой разрядности n+1. 2. Сопоставим с каждым разрядом адресной шины высказывания : А i, ( i =0,..., n ): А n, …, А 2, А 1, А 0.
57 Правило построения дешифратора адреса 3. Запишем логическое выражение в виде логического произведения высказываний B i ( i = 0,..., n ), количество которых совпадает с количеством разрядов адресной шины n+1. При этом каждый сомножитель B i ( i = 0,..., n ) равен: A i (i = 0,..., n ), если соответствующий разряд двоичного числа равен 1; А i (i = 0,..., n ), если соответствующий разряд двоичного числа равен 0. 4. Применим алгоритм построения логических схем.
58 Пример построения дешифратора адреса & А 3 А 2 А 1 А 0 А 3 & А 2 & А 1 & А 0 Адрес равен 5 10 = 101 2 = 0101 2
59 Дешифратор кода операции Д ешифраторы, преобразующие n -разрядное входное двоичное число (код) в единичный сигнал на одном из 2 n их выходов. Такие дешифраторы могут использоваться, например, для определения исполняемых машинных команд в устройстве управления ЭВМ.
60 Пример дешифратора ( n=2) DC 1 2 0 1 2 3 X Y F 3 F 2 F 1 F 0 Х Y F o F 1 F 2 F 3 X Y F o F 1 F 2 F 3 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 1
61 Схема дешифратора & & & & F 3 = X&Y F 2 = X&Y F 1 = X&Y F 0 = X&Y Y X
Дешифратор – это устройство, которое имеет n входов и 2 n выходов, причем каждой i -ой комбинации сигналов на входе соответствует сигнал на одном определенном 2 i -ом выходе. Другими словами, дешифратор – это устройство, которое дешифрирует число в позицию. Дешифраторы предназначены для декодирования (распознавания) кодовых комбинаций (адрес устройства, код операции и т. д.). 62
63
64
65 Полусумматор Полусумматор осуществляет сложение двоичных одноразрядных чисел по следующим правилам: 0+0=00; 0;+1=01; 1+0=01; 1+1=10. Полусумматор имеет два входа : А -.первое слагаемое, В - второе слагаемое, и два выхода : S — значение суммы в данном разряде, Р - значение переноса в старший разряд. В этом устройстве отсутствует третий вход для переноса единицы из младшего разряда.
66 Обозначение и функции полусумматора ПОС P S А В А В P S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0
67 Построение полусумматора Логические выражения, определяющие состояние выходов S и Р, имеют следующий вид: S=A • B+ A • B (*), Р = А • В. Преобразуем логическое выражение для выхода S, сложим выражение (*) с тождественно ложным высказыванием А• А + В• В: S = A • B+ A • B + А• А + В• В : А В P S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0
68 Воспользуемся коммуникативными и дистрибутивными свойствами : S = ( А + В) • (А+В). С учетом закона де Моргана имеем: S = (А • В) • (А+В).
69 Схема полусумматора А & Р 1 В & S 1 Р = А • В. (А+В). S = (А • В) • (А+В).
70 Обозначение одноразрядного сумматора SM A В P 0 S P
71 Функции одноразрядного сумматора Значение разряда первого слагаемого А Значение разряда второго слагаемого В Значение переноса из младшего раз ряда P 0 Значение разряда суммы S Значение переноса в старший разряд Р 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1
72 Схема одноразрядного сумматора ПОС P S А В ПОС P Р 0 1 Р S
73 Схема многоразрядного сумматора А В Р 0 SM 0 P S А 0 В 0 S 0 Р 0 А В Р 0 SM 1 P S А 1 В 1 S 1 Р 1 А В Р 0 SM n P S А n В n S n Р n Р n-1
74 Регистры Регистры — это набор простейших запоминающих устройств (например, триггеров) для временного хранения двоичной информации в устройствах обработки информации. Основные виды регистров : Параллельные Последовательные
75
76 /- означает срабатывание по переднему фронту импульса; \ - по заднему фронту импульса.
77 D -триггер с дополнительными RS входами
78
В асинхронном Т -триггере смена состояний происходит по заднему фронту входного сигнала, поскольку двухступенчатый триггер можно рассматривать как схему, состоящую из двух триггеров: 79
80
81
82 Мультиплексор Мультиплексор ( MX, MUL ), –это электронное устройство, которое имеет несколько информационных D-входов и один выход F, осуществляющее последовательное подключение входов к выходу в соответствии с адресным кодом, поступающим на управляющие (адресные) входы (х1, х2).
83 Mультиплексор Mультиплексор — устройство, имеющее несколько сигнальных входов, один или более управляющих входов и один выход. Мультиплексор позволяет передать сигнал с одного из входов на выход; при этом выбор желаемого входа осуществляется подачей соответствующей комбинации управляющих сигналов. Аналоговые и цифровые мультиплексоры значительно различаются по принципу работы. Первые электрически соединяют выбранный вход с выходом (при этом сопротивление между ними невелико — порядка единиц/десятков ом). Вторые же не образуют прямого электрического соединения между выбранным входом и выходом, а лишь «копируют» на выход логический уровень ('0' или '1') с выбранного входа. Аналоговые мультиплексоры иногда называют ключами. Устройство, противоположное мультиплексору по своей функции, называется демультиплексором.
84
Демультиплексор – это устройство, имеющее один информационный вход D и несколько выходов, осуществляющее передачу сигнала с информационного входа на один из выходов в соответствии с управляющим (адресным) кодом, поступающим на управляющие входы. В простейшем случае, в качестве демультиплексора может использоваться дешифратор, у которого вместо сигнала OE подается информационный сигнал X. Например, если на входы подать код a 1 a 0 =10( 2 )=2( 10 ), то сигнал X появится на выходе y 2, а на остальных выходах y i =0. 85
86 Обозначение демультиплексора на функциональных схемах a0 a1 Y0 Y1 Y2 Y3 0 0 X 0 0 0 0 1 0 X 0 0 1 0 0 0 X 1 1 0 0 X
87
88 Конец
Mультиплексор — устройство, имеющее несколько сигнальных входов, один или более управляющих входов и один выход. Мультиплексор позволяет передавать сигнал с одного из входов на выход; при этом выбор желаемого входа осуществляется подачей соответствующей комбинации управляющих сигналов. Устройство, противоположное мультиплексору по своей функции, называется демультиплексором. 89
Мультиплексор - коммутатор цифровых сигналов. Мультиплексор представляет собой комбинационное устройство с m информационными, n управляющими входами и одним выходом. Функционально мультиплексор состоит из m элементов конъюнкции, выходы которых объединены дизъюнктивно с помощью элемента ИЛИ с m входами. На одни входы всех элементов конъюнкции подаются информационные сигналы, а другие входы этих элементов соединены с соответствующими выходами дешифратора с n 90
91
92
93
Мультиплексоры обозначают сочетанием MUX ( от англ multiplexer ), а также MS ( от англ multiplexer selector ). 94
Мультиплексоры могут использоваться в делителях частоты, сдвигающих устройствах и др. Мультиплексоры часто используют для преобразования параллельного двоичного кода в последовательный. Для такого преобразования достаточно подать на информационные входы мультиплексора параллельный двоичный код, а сигналы на адресные входы подавать в такой последовательности, чтобы к выходу поочередно подключались входы, начиная с первого и заканчивая последним. 95
