Файл: Локальные и глобальные сети эвм основы компьютерной коммуникации. Принципы построения сетей. Компьютерная сеть.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 520
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
9 устройство называется одноразрядным, полным сумматором. Его условное обозначение показано на рисунке 17.
Рассмотренные выше функциональные элементы являются основными при построении схем компьютерных систем.
Рисунок 9 – Условное обозначение полного одноразрядного сумматора
Sum
a i bi
Pi-1
P
i
S
i
1
Основные
понятия алгебры логики. Простые и сложные высказывания.
Основные
операции алгебры логики. Законы Морганы.
Изучив
материал, студент должен знать:
основные понятия формальной логики;
высказывание и суждение;
истинность и ложность высказываний;
основные логические операции, таблицы истинности, логические формулы.
Изучив
материал, студент должен уметь:
определять истинность и ложность высказываний;
применять логические операции;
представлять логические выражения в виде формул;
выполнять упрощение формул.
Для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании широко используется математический аппарат алгебры логики (булевой алгебры).
Основное понятие булевой алгебры — выказывание. Высказывания бывают простые и сложные.
Под
простым
высказыванием
понимается повествовательное предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каждое высказывание или истинно или ложно и не может быть одновременно и истинным и ложным
(третьего не дано).
Высказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (значение 0) или ИСТИНА (значение 1).
Например, содержание высказывания А: «дважды два равно четырем»
ИСТИНА А = 1, высказывание В: «три больше пяти» всегда есть ЛОЖЬ В=0, а высказывание «сейчас идет снег» может быть истинным или ложным.
Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.
Содержание высказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить
2 любые действия, предусмотренные алгеброй высказываний. Если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре логики операции, то результаты операций также будут элементами этой алгебры.
Сложное
высказывание можно построить из простых с помощью логических операций: отрицания, конъюнкции, дизъюнкции, импликации и логических выражений, представляющих собой комбинации логических операций. Рассмотрим их подробней.
Операцией отрицания А называют высказывание
À
(или –А, или
∀
говорят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. Например, если событие А состоит в том, что «завтра экзамен», то
À
«завтра НЕ будет экзамена», истинность одного утверждения автоматически означает ложность второго. Отрицание — унарная (т.е. для
одного операнда) логическая операция. Ей соответствует языковая конструкция, использующая частицу НЕ.
Это правило можно записать в виде следующей таблицы:
А
À
0
1
1
0
Такая таблица называется таблицей истинности.
Конъюнкцией
(логическим умножением) двух высказываний А и В
является новое высказывание С, которое истинно только тогда, когда
истинны
оба высказывания, записывается С = А
∧
В
или С = А&В, или С =
А
*В (при этом говорят С равно А И В). Например, пусть высказывание А состоит в том, что «высота шкафа меньше высоты двери», событие В
«ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, если ширина шкафа меньше ширины двери И высота шкафа меньше высоты двери», т.е. данная операция применяется, если два высказывания связываются союзом И.
Таблица истинности этой операции, как следует из определения, имеет вид
3
А
В
А
&В
0 0
0 0
1 0
1 0
0 1
1 1
Т.е. результатом конъюнкции (логического умножения) будет 1 только в том случае, когда значения обоих операндов 1.
Дизъюнкцией
(логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы
одно
высказывание. Записывается С = A
∨
В
, или, правда очень редко, может быть записано С = A+В (при этом говорят: С равно А ИЛИ В). Например, пусть высказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллейбусе», событие С «студент добрался домой на автобусе ИЛИ троллейбусе», т.е. данная операция применяется, если два высказывания связываются союзом
ИЛИ
Таблица истинности такой операции следующая:
А
В
A
∨
B
0 0
0 0
1 1
1 0
1 1
1 1
Т.е. результатом дизъюнкции (логического сложения) будет 1, если
хотя
бы один из операндов имеет значение 1.
Импликацией
двух высказываний А (А называется посылкой) и В (В
называется
заключением) является новое высказывание С, которое ложно
только
тогда, когда посылка истинна, а заключение ложно, записывается
С
= А
→
В
(при этом говорят: из А следует В). Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, например, «если идет дождь, то на небе тучи».
Очевидно, операция не симметрична, т.е. из В
→
А
не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.
4
Таблица истинности импликации имеет вид
А
В
А
→
В
0 0
1 0
1 1
1 0
0 1
1 1
Т.е. результатом импликации будет 0 только тогда, когда посылка 1,
а
заключение 0.
Импликация
имеет следующие свойства:
А
→
В
≠
В
→
А
А
→
А
= 1
0
→
А
= 1
1
→
А
=А
А
→
1 =1
А
→
0 =
À
Эквиваленцией
двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда оба высказывания
имеют
одинаковые значения истинности, записывается С = А
↔
В
(.С = А
= В). Примером такой операции может быть любое высказывание типа: событие А равносильно событию В. Например, «идет дождь» равносильно
«капает из тучи».
Таблица истинности:
А
В
А
↔
В
0 0
1 0
1 0
1 0
0 1
1 1
Т.е. результатом эквиваленции будет 1 тогда, когда оба высказывания
имеют
одинаковые значения (либо 0, либо 1).
Эквиваленция
имеет следующие свойства:
А
↔
В
= В
↔
А
А
↔
В
=
Â
↔
À
5
А
↔
1 = А
А
↔
0 =
À
С помощью логических операций из простых высказываний
(логических переменных и констант) можно построить логические выражения, которые также называются булевскими функциями. Например,
С
= ((
À
∨
В
)
→
В
)
∨
А
.
Чтобы избежать большого количества скобок в булевских функциях, принято следующее соглашение о старшинстве операций.
Первыми
выполняются операции в скобках, затем операции в
следующем
порядке: отрицание, конъюнкция и дизъюнкция слева
направо
, импликация, эквиваленция.
Зависимости
между
логическими
операциями
Операции не являются независимыми; одни из них могут быть выражены через другие. Можно доказать с помощью таблиц истинности следующие равносильности:
À =
А
–
закон
двойного отрицания
А
&
В
=
В
&
А
–
коммутативный
закон для конъюнкции
A
∨
B = B
∨
A –
коммутативный
закон для дизъюнкции
(
А
&
В
)&
С
=
А
&(
В
&
С
) –
ассоциативный
закон для конъюнкции
(A
∨
B)
∨
C = A
∨
(B
∨
C) –
ассоциативный
закон для дизъюнкции
дистрибутивные
законы
А
&(
В
∨
С
) = (
А
&
В
)
∨
(
А
&
С
)
A
∨
(
В
&
С
) = (A
∨
В
)&(A
∨
С
)
законы
де Моргана
Â
À
&
=
À
∨
Â
Â
À
∨
= À
&
Â
6
A&A = A – закон идемпотенции для конъюнкции
A
∨
A = A – закон идемпотенции для дизъюнкции
A&1 = A – закон единицы для конъюнкции
A&0 = 0 – закон нуля для конъюнкции
A
∨
1 = 1 – закон единицы для дизъюнкции
A
∨
0 = A – закон нуля для дизъюнкции
A
∨
À = 1 –
закон
исключения третьего
A& À = 0 –
закон
противоречия
A
→
В
= À
∨
В
А
↔
В
= (
А
→
В
)&(
В
→
А
) = ( À
∨
В
)&(A
∨
Â)=
(A
&
В
)
∨
(
À & Â)
законы
поглощения
A
∨
(
А
&
В
) =
А
А
&(A
∨
В
) =
А
А
&(
À
∨
В
) =
А
&
В
A
∨
(
À &B) = A
∨
В
Одну и ту же зависимость между логическими переменными можно выразить различными формулами. Поэтому важно иметь возможность приводить формулы с помощью эквивалентных преобразований к некоторому стандартному виду. Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований.
Первая из них — дизъюнктивная нормальная форма (ДНФ), имеет вид
Al
∨
A2
∨
...
∨
An
, где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний, например:
В
= ( 1
À &
А
2 & A3)
∨
(
А
4 &
А
5)
7
Вторая — конъюнктивная нормальная форма (КНФ), имеет вид
1 ... 19 20 21 22 23 24 25 26 27
А
1
∧
А
2
∧
...
∧
An, где каждое из составляющих есть дизъюнкция простых высказываний и их отрицаний, например:
В
= (
1
À
∨
А
2
∨
3
À
) & (
А
4
∨
А
5) &
А
6.
Задать булевскую функцию можно, определяя ее значения для всех наборов значений аргументов. Каждый аргумент может иметь два значения:
0 и 1, следовательно, n аргументов могут принимать 2
n различных наборов.
Пусть, например, булевская функция имеет три аргумента: X
1
, Х
2
, Х
3
. Общее число наборов 2 3
= 8; зададим таблицу истинности функции, указав для каждого набора значение функции.
№
X
1
X
2
X
3
F
1 0
0 0
0 2
0 0
1 1
3 0
1 0
0 4
0 1
1 1
5 1
0 0
0 6
1 0
1 1
7 1
1 0
0 8
1 1
1 1
Для составления алгебраической формы по результатам таблицы сделаем следующее. В комбинациях, где функция принимает значение 1, единицу заменим именем функции, а нуль – именем с отрицанием (т.е. комбинации 0 0 1 поставим в соответствие выражение
1
Õ &
2
Õ &
Х
3
), все элементы соединим знаками дизъюнкции, для рассматриваемого примера получим
F(X
1
, X
2
,
Х
3
) = (
1
Õ &
2
Õ &
Х
3
)
∨
(
1
Õ &
Х
2
&
Х
3
)
∨
(
Х
1
&
2
Õ &
Х
3
)
∨
(
Х
1
&
Х
2
&
Х
3
).
Как нетрудно заметить, построенная функция удовлетворяет заданной таблице истинности. Функция представляет дизъюнктивную нормальную форму. Кроме того, заметим, что в каждую группу дизъюнкций входят все аргументы функции. Такая ДНФ называется совершенной, а каждая группа дизъюнкций называется конституэнтой единицы.
8
Аналогично, для комбинаций, где функция принимает значение нуля, можно построить алгебраическую форму F(X
1
,X
2
,X
3
) = (X
1
∨
X
2
∨
X
3
)& (X
1
∨
2
Õ
∨
X
3
)&(
1
Õ
∨
X
2
∨
X
3
)&(
1
Õ
∨
2
Õ
∨
X
3
), которая также удовлетворяет заданной таблице истинности и представляет собой конъюнктивную нормальную форму, в данном случае совершенную. Каждая конъюнкция называется
конституэнтой
нуля.
Таким образом, любая функция может быть разложена на
конституэнты
(составляющие). Эти соотношения используются для синтеза логических функций и вычислительных схем.
Далее будет показано, как, основываясь на булевой алгебре, создаются цифровые устройства.