Схемная реализация базовых логических элементов.
Лекция 6.
Логические основы алгоритмизации
Элементарные логические операции.
ИСТОРИЯ:
Начало исследований в области формальной логики было положено Аристотелем в IV в. до н.э. Однако математические подходы к этим вопросам были впервые указаны Джорджем Булем, который положил в основу математической логики алгебру логики (булеву, а логические значения называют булевыми). Алгебра логики используется при построении основных узлов ЭВМ, например, таких как шифратор, сумматор и др.
Итак, алгебра логики оперирует с высказываниями, т.е. повествовательными предложениями, о которых можно сказать (И) - Истинно оно или (Л) - Ложно. Например: «4< 3» -ложно, «Москва больше Саратова»- истинно. Высказывания обозначают большими латинскими буквами и пишут A= 1(t,true) ,B= 0 (f, false).
Над высказываниями можно производить определенные логические операции, в результате которых получаются новые высказывания. Их истинность зависит от истинности исходных выражений и вида логической операции.
Наиболее часто используются логические операции, выражаемые словами «и», «или», «не». А именно:
1. Конъюнкция (логическое умножение).
Опред .Соединение двух (или несколько) высказываний в одно спомощью союза И (AND) называется конъюнкцией (илиоперацией логического умножения). Обозначаются Л, &, х. Значения логических операций определяются по правилам,задаваемым в таблице истинности.
|
|
|
Истинность конъюнкции задается следующей таблицей.
| А | В | А & В |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2. Дизъюнкция (логическое сложение).
Опред . Соединение двух (или несколько) высказываний в одно с помощью союза ИЛИ (OR) называется дизъюнкцией (или логического сложения). Обозначаются I, V, +.
Таблица истинности
| А | В | А V В | А хor В |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
Xor-модифицированная операция «ИЛИ» исключающее или (хor), от обычного «ИЛИ» отличается последней строкой.
3. Отрицание (инверсия)
Опред . Присоединение частицы НЕ (NOT) к данному высказываниюназывается операцией отрицания (инверсии). Ā, А – «не А»
Таблица истинности
| А | А |
| 1 | 0 |
| 0 | 1 |
Существует помимо этих 3-х и ряд других операций.
Например:
4.Эквивалентности. Обозначаются А ~ В (А ≡ В, А eqv В)
Таблица истинности
| А | В | А ~ В |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
|
|
|
5. Операция импликации (логического следования). Обозначаются А→ В,
(А imp В). Объединяет высказывания словами «если…, то …».
Таблица истинности
| А | В | А→ В |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Логические операции можно применять многократно.
Импликация
Операция, выражаемая связками ⌠если ..., то■, ⌠из ... следует■, ⌠... влечет ...■, называется импликацией (лат. implico ≈ тесно связаны) и обозначается знаком ╝. Высказывание А ╝ В ложно тогда и только тогда, когда А истинно, а В ≈ ложно.
Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: ⌠данный четырёхугольник ≈ квадрат■ (А) и ⌠около данного четырёхугольника можно описать окружность■ (В). Рассмотрим составное высказывание А ╝ В, понимаемое как ⌠если данный четырёхугольник квадрат, то около него можно описать окружность■. Есть три варианта, когда высказывание А ╝В истинно:
А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;
А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);
A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.
Ложен только один вариант: А истинно и В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.
|
|
|
В обычной речи связка ⌠если ..., то■ описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться ⌠бессмысленностью■ импликаций, образованных высказываниями, совершенно не связанными по содержанию.
Например, такими:
⌠если президент США ≈ демократ, то в Африке водятся жирафы■,
⌠если арбуз ≈ ягода, то в бензоколонке есть бензин■.
Опред . Высказывания, образованные с помощью логических операций называются сложными. Истинность их устанавливают, используя таблицы истинности соответствующих операций.
_
|
|
|
Пример: определим истинность сложного высказывания. Ā & В
| А | В | Ā | _ В | _ Ā & В |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 |
Опред . Высказывания, у которых таблицы истинности совпадают, называются равносильными. Для обозначения используют знак = (А=В).
Пример: рассмотрим сложное высказывание (А& В) V (Ā& В) и составим таблицу истинности.
| А | В | Ā | _ В | А& В | _ Ā& В | _ (А& В)V(Ā& В) |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 |
=>если сравнить с таблицей истинности, для эквивалентности, то видно:
_
(А& В) V (Ā& В) = А~ В
Следовательно, можно в алгебре логики проводить тождественные преобразования, заменяя высказывания равносильными, а это упрощение выражения.
Следствием самих определений логической операции является ряд свойств.
1. коммутативность (перестановочность)
А& В = В& А
А V В = В V А
2. закон идемпотентности
А& А= А, А V А= А
3. ассоциативные законы
АV (ВV С)= (АV В) V С= А V В V С
А & (В& С)= (А& В) & С= А& В & С
дистрибутивные законы
А & (В V С)= (А& В) V (А& С)
А V (В& С)= (А V В) & (А V С)
4. законы де Моргана
(А&В)= А V В
(А V В)= А & В
5. закон универсального множества
Х V 1= 1
Х & 1= Х
6. закон нулевого множества
Х V О = Х
Х& О = О
Схемная реализация базовых логических элементов.
Любую цифровую систему можно описать при помощи набора булевых функций. Средством обработки двоичных сигналов в ЭВМ являются логические элементы. На практике ИСТИНА =1 - это наличие напряжения, ЛОЖЬ= 0 - отсутствие.
Логические элементы - это электронные микросхемы с одним или несколькими входами и одним выходом, через которые проходят электрические сигналы, представляющие 0,1.
Для реализации любой логической операции над двоичными сигналами достаточно элементов трех типов: И, ИЛИ, НЕ. Существуют микросхемы, реализующие более сложные логические функции: И-НЕ, называемая операцией Шеффера (ĀВ), и ИЛИ- НЕ, называемая Стрелка Пирса (А+В). Из логических элементов путем их комбинации стоятся основные схемы компьютера. Любую достаточно сложную логическую функцию можно реализовать, имея относительно простой набор базовых логических операций.
Первоначально были разработаны и выпускались микросхемы, соответствующие основным логическим действиям. Довольно быстро стало ясно, что это не может удовлетворить практическим потребностям. Появились более сложные типовые узлы (триггера, регистры, сумматоры и т.п.), дающие возможность реализовывать еще более сложные логические устройства.
Триггер - электронный прибор, имеющий два устойчивых состояния, является типичным запоминающим элементом, способным хранить 1 бит информации.
Регистр- совокупность триггеров, предназначенных для хранения числа в двоичном коде.
Сумматор- устройство, обеспечивающее суммирование двоичных чисел с учетом переноса из предыдущего разряда.
Дата добавления: 2020-12-12; просмотров: 107; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!