№ случаяАВF=A&B
1000
2100
3010
4111
Операция, выражаемая связками “если ..., то”, “из ... следует”, “... влечет
...”, называется импликацией (лат. implico — тесно связаны) и обозначается
знаком→ .
Высказывание А→ В ложно тогда и только тогда, когда А истинно, а В — ложно.
№
случаяABA⊃B
1001
2011
3100
Операция, выражаемая связками “тогда и только тогда”, "необходимо и достаточно”,
“... равносильно ...”, называется эквиваленцией и обозначается знаком↔ или ~ .
Высказывание А↔ В истинно тогда и только тогда, когда значения А и В совпадают.
ABА↔ В
001
010
100
111
Импликацию можно выразить через дизъюнкцию и отрицание:
А → В = v В.
Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:
А ↔ В = ( v В).• ( v А).
Порядок выполнения логических операций задается круглыми скобками. Но для
уменьшения числа скобок договорились считать, что сначала выполняется операция
отрицания (“не”), затем конъюнкция (“и”), после конъюнкции — дизъюнкция (“или”)
и в последнюю очередь — импликация.
Логическая формула.
С помощью логических переменных и символов логических операций любое
высказывание можно формализовать, то есть заменить логической формулой.
Определение логической формулы:
Всякая логическая переменная и символы “истина” (“1”) и “ложь” (“0”) — формулы.
Если А и В — формулы, то , (А • В), (А v В), (А→B), (А↔ В) — формулы.
Никаких других формул в алгебре логики нет.
Некоторые формулы принимают значение “истина” при любых значениях истинности
входящих в них переменных. Такие формулы называются тождественно истинными
формулами или тавтологиями.
Некоторые формулы принимают значение “ложно” при любых значениях истинности
входящих в них переменных. Такие формулы называются тождественно ложными
формулами или противоречиями.
Если две формулы при одинаковых наборах значений входящих в них переменных,
принимают одинаковые значения, то они называются равносильными.
Связь между алгеброй логики и двоичным кодированием
Математический аппарат алгебры логики очень удобен для описания того, как
функционируют аппаратные средства компьютера, поскольку основной системой
счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а
значений логических переменных тоже два: “1” и “0”.
Из этого следует два вывода:
- одни и те же устройства компьютера могут применяться для обработки и хранения
как числовой информации, представленной в двоичной системе счисления, так и
логических переменных;
- на этапе конструирования аппаратных средств алгебра логики позволяет
значительно упростить логические функции, описывающие функционирование схем
компьютера, и, следовательно, уменьшить число элементарных логических элементов,
из десятков тысяч которых состоят основные узлы компьютера.
Существуют различные физические способы кодирования двоичной информации, но чаще
всего единица кодируется более высоким уровнем напряжения, чем ноль.
Элементы математической логики. Законы логики. Упрощение логических формул.
Тождества и законы алгебры логики
Тождества
логического сложения (дизъюнкции)логического умножения (конъюнкции)
А Ú 0 = АА Ù 0 = 0
А Ú 1 = 1А Ù 1 = А
А Ú А = АА Ù А = А
А Ú ØА = 1А Ù ØА = 0
Ø(ØА) = А
Законы
Переместительный закон
А Ú В = В Ú АА Ù В = В Ù А
Сочетательный закон
(А Ú В) Ú С = А Ú (В Ú С)(А Ù В) Ù С = А Ù (В Ù С)
Распределительный закон
(А Ú В) Ù С = (А Ù С) Ú (В Ù С)(А Ù В) Ú С = (А Ú С) Ù (В Ù С)
Закон де Моргана (закон отрицания)
Ø(А Ú В) = ØА Ù ØВØ(А Ù В) = ØА Ú ØВ
Упростите выражения:
1 Ú А Ù 0 = 1Ú0 = 1
А Ù А Ù 1 = А
0 Ù А Ú 0 = 0 Ú 0 = 0
0 Ú А Ù 1 = 0 Ú А = А
А Ú (ØА Ù В) = (А Ú ØА) Ù (А Ú В) = 1 Ù (А Ú В) = А Ú В
АВØАØА Ù ВА Ú (ØА Ù В)
00100
01111
10001
11001
ØА Ù (Ø(ØВ Ú А)) = ØА Ù (В ÙØА) = (ØА Ù ØА) Ù В = ØА Ù В
АВØАØВØВÚАØ(ØВÚА)ØА Ù (Ø(ØВ Ú А))
0011100
0110011
1001100
1100100
АВØАØА Ù В
0010
0111
1100
Билет 9
Логические элементы и схемы. Типовые логические устройства компьютера:
полусумматор, сумматор, триггеры, регистры.
Так как любая логическая операция может быть представлена в виде комбинации трех
основных (инверсии, конъюнкции и дизъюнкции), то любые устройства компьютера,
которые производят обработку или хранение информации, могут быть собраны из
базовых логических элементов.
Логический элемент – это преобразователь, который после обработки входных
двоичных сигналов выдает на выходе сигнал, являющийся значением одной из
логических операций.
Логические элементы компьютера используют сигналы, представляющие электрические
импульсы. Есть импульс – логический смысл сигнала 1, нет импульса – 0. На входе
логического элемента поступают сигналы - значения аргументов, на выходе
появляется сигнал – значение функции.
Преобразование сигнала логическим элементом задается таблицей истинности,
соответствующей логической функции.
ABF=A&B
000
Для максимального упрощения работы компьютера все математические операции в
процессоре сводятся к сложению двоичных чисел. Поэтому главной частью процессора
являются сумматоры, которые и обеспечивают сложение
Сумматор – это электронная логическая схема, выполняющая сложение двоичных
чисел.
Сумматор служит центральным узлом арифметико-логического устройства компьютера.
Многоразрядный двоичный сумматор, предназначенный для сложения многоразрядных
двоичных чисел, представляет собой набор одноразрядных сумматоров.
Простейший одноразрядный двоичный сумматор (полусумматор)
При сложении двоичных чисел в каждом разряде образуется сумма и при этом
возможен перенос в старший разряд. Обозначим слагаемые А, В, перенос – Р0 и
сумму – S. Таблица сложения одноразрядных двоичных чисел с учетом переноса в
старший разряд выглядит так:
P0 = A Ù B
S =(A В) Ù ( )
ПОЛУСУММАТОР ДВОИЧНЫХ ЧИСЕЛ
Полный одноразрядный двоичный сумматор
При сложении чисел в каждом разряде приходится иметь дело с тремя цифрами:
• Цифрой первого слагаемого;
• Цифрой второго слагаемого;
• Цифрой переноса из младшего разряда.
В результате сложения получаются две цифры:
• Цифра суммы;
• Цифра переноса в старший разряд.
Таким образом одноразрядный двоичный сумматор – это устройство с тремя входами и
двумя выходами.
Многоразрядный сумматор
Многоразрядный сумматор процессора состоит из полных одноразрядных сумматоров.
На каждый разряд ставится одноразрядный сумматор, причем выход «перенос»
сумматора младшего разряда подключается ко входу сумматора старшего разряда.
Триггер
Триггер – это электронная логическая схема, являющаяся важнейшей структурной
единицей оперативной памяти компьютера, которая необходима для хранения 1 бита
информации (trigger – защелка, спусковой крючок).
Триггер может находиться в одном из двух устойчивых состояний, которые
соответствуют логической 1 и логическому 0.
Самый распространенный тип триггера – RS-триггер (Set – установка, Reset –
сброс).
Условное обозначение триггера:
Триггер имеет два входа S и R и два выхода Q и , причем выходной сигнал
является логическим отрицанием сигнала Q.
Входы триггера расшифровываются следующим образом — S (Set - установка) и R
(Reset - сброс). Они используются для установки триггера в единичное состояние и
сброса в нулевое. В связи с этим триггер называется RS-триггер.
Рассмотрим, как работает эта схема.
Пусть для определенности на вход S подан единичный сигнал, а R=0. Тогда
независимо от состояния другого входа, который подсоединен к выходу Q (иначе
говоря, вне зависимости от предыдущего состояния триггера) верхний по схеме
элемент ИЛИ-НЕ получит на выходе 0 (результат ИЛИ , естественно, равен 1, но его
инверсия - 0). Этот нулевой сигнал передается на вход другого логического
элемента, где на втором входе R тоже установлен 0. В итоге после выполнения
логических операций ИЛИ-НЕ над двумя входными нулями этот элемент получает на
выходе 1, которую возвращает первому элементу на соответствующий вход. Последнее
обстоятельство очень важно: теперь, когда на этом входе установилась 1,
состояние другого входа (S) больше не играет роли. Иными словами, если даже
теперь убрать входной сигнал S, внутреннее распределение уровней сохранится 6ез
изменений». Поскольку согласно нашим рассуждениям Q = l, триггер перешел в
единичное состояние, и, пока не придут новые внешние сигналы, сохраняет его.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22
