ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.06.2021
Просмотров: 1835
Скачиваний: 5
16
В =
{Процессор – устройство хранения информации},
С = {Монитор – устройство вывода информации},
D
= {Клавиатура – устройство обработки информации}.
Сначала на основании знания устройства компьютера устанавливаем истинность простых
высказываний:
А =
1,
В =
0, С = 1,
D
= 0.
Определим теперь истинность составного высказывания, используя таблицы истинности логических
операций:
( &
0) = 0
Составное высказывание ложно.
Таблицу, показывающую, какие значения принимает составное высказывание при всех сочетаниях
(наборах) значений входящих в него простых высказываний, называют
таблицей истинности
составного высказывания.
Составные высказывания в алгебре логики записываются с помощью логических выражений. Для
любого логического выражения достаточно просто построить таблицу истинности
Алгоритм построения таблицы истинности:
1) подсчитать количество переменных
n
в логическом выражении;
2) определить число строк в таблице, которое равно
m =
2
n
;
3) подсчитать количество логических операций в логическом выражении и определить количество
столбцов в таблице, которое равно количеству переменных плюс количество операций;
4) ввести названия столбцов таблицы в соответствии с последовательностью выполнения
логических операций с учетом скобок и приоритетов;
5) заполнить стобцы входных переменных наборами значений;
6) провести заполнение таблицы истинности по столбцам, выполняя логические операции в
соответствии с установленной в п.4 последовательностью.
3.
Элементарные функции алгебры логики
Существует несколько синонимов по отношению к
функциям алгебры
логики:
1.
функции алгебры
логики (ФАЛ);
2.
переключательные
функции
;
3.
булевские
функции
;
4.
двоичные
функции
.
По мере необходимости будем пользоваться всеми этими синонимами.
Рассмотрим некоторый набор
аргументов
:
<X
1
,X
2
,X
3
,...Х
i
,...X
n
>
и будем считать, что каждый из
аргументов
принимает только одно из двух возможных значений,
независимо от других
Чему равно число различных наборов?
X
i
= {0, 1}
Поставим каждому набору в соответствие некоторое двоичное число:
X
1
,X
2
,...........X
n
0, 0,...........,0 нулевой набор
0, 0,...........,1 первый набор
0, 0,..........1,0 второй набор
...................
1, 1,...........,1 (2
n
-1)-ый набор
Очевидно, что количество различных
X
1
,X
2
,...........X
n
n
-разрядных чисел в позиционной двоичной
системе есть
2
n
.
Допустим, что некоторая
функция
F(X
1
,X
2
,....X
n
)
задана на этих наборах и на каждом из них она
принимает либо '
0
'-ое, либо '
1
'-ое значение.
Такую
функцию
называют
функцией алгебры
логики или переключательной
функцией
.
Чему равно число различных переключательных
функций
'
n
'
аргументов
?
Т.к.
функция
на каждом наборе может принять значение '
0
' или '
1
', а всего различных наборов
2
n
, то
общее число различных
функций
'
n
'
аргументов
есть:
2^2n
.
По сравнению с аналитической
функцией
непрерывного
аргумента
даже для одного
аргумента
существует множество различных
функций
.
17
Число
аргументов
1
2
3
4
5
10
Число различных перекл. ф-ций
4
16
256
65536
~4*10
9
~10
300
Различные устройства ЭВМ содержат десятки и сотни переменных (
аргументов
), поэтому понятно,
что число различных устройств, отличающихся друг от друга, практически бесконечно.
Итак, нужно научиться строить эти сложные
функции
(а стало быть, и устройства), а также
анализировать их.
Задача
синтеза
более сложных
функций
заключается в представлении их через простые на основе
операций
суперпозиции
и подстановки
аргументов
.
Таким образом, вначале необходимо изучить эти элементарные
функции
, чтобы на их основе строить
более сложные.
ФАЛ одного аргумента
Чтобы задать ФАЛ, нужно задать ее значения на всех наборах
аргументов
.
Аргумент
Х
значение
Наименование
функции
0
1
F
0
(x)
0
0
константа '
0
'
F
1
(x)
0
1
переменная '
х
'
F
2
(x)
1
0
инверсия
'
х
' (отрицание
х
)
F
3
(x)
1
1
константа '
1
'
Будем у
функции
ставить индекс, эквивалентный набору ее значений для соответствующих значений
аргумента
, начиная с
0,0,....,n,....
. и т.д. в порядке возрастания.
Эти
функции
можно реализовать на 4-х элементах, каждый из которых имеет максимум один вход.
Таким образом, принципом подстановки
аргументов
для построения более сложных
функций
нельзя
воспользоваться.
Необходимо рассмотреть более сложные
функции
, т.е. ФАЛ 2х
аргументов
.
Дадим такие определения:
1.
ФАЛ, принимающие одинаковые значения на всех наборах
аргументов
, называются равными.
2.
ФАЛ существенно зависит от
аргумента
Х
i
, если
В противном случае она зависит не существенно, а соответствующий
аргумент
наз. фиктивным.
Например:
Х
1
Х
2
Х
3
F(X
1
,X
2
,Х
3
)
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
Видно, что
Х
3
– фиктивный
аргумент
. Это показывает, что в
функцию
можно ввести любое число
фиктивных
аргументов
, от которых она существенно не зависит. Этот прием в дальнейшем потребуется
для выполнения ряда преобразований.
Все ФАЛ от 2-х
аргументов
. Сведем их в единую таблицу 2.1.
Таблица 2.1.
Таблица 2.1.
№
функции
Значение
функции
на наборах
логических переменных
Наименование
функции
Обозначение
функции
18
X
1
0
0
1
1
X
2
0
1
0
1
f
0
(X
1
,X
2
)
0
0
0
0
Константа "ноль"
f(X
1
,X
2
)=0
f
1
(X
1
,X
2
)
0
0
0
1
Конъюнкция
, произведение
f
2
(X
1
,X
2
)
0
0
1
0
Запрет по
X
2
f
3
(X
1
,X
2
)
0
0
1
1
Переменная
X
1
f(X
1
,X
2
)= X
1
f
4
(X
1
,X
2
)
0
1
0
0
Запрет по
X
1
f
5
(X
1
,X
2
)
0
1
0
1
Переменная
X
2
f(X
1
,X
2
)= X
2
f
6
(X
1
,X
2
)
0
1
1
0
Сложение по mod2
(неравнозначность)
f
7
(X
1
,X
2
)
0
1
1
1
Дизъюнкция
f
8
(X
1
,X
2
)
1
0
0
0
Стрелка Пирса
f
9
(X
1
,X
2
)
1
0
0
1
Равнозначность
f
10
(X
1
,X
2
)
1
0
1
0
Инверсия
X
2
f(X
1
, X
2
)=^X
2
f(X
1
, X
2
)=X
2
f
11
(X
1
,X
2
)
1
0
1
1
Импликация
от
X
2
к
X
1
f(X
1
, X
2
)= X
2
-> X
1
f
12
(X
1
,X
2
)
1
1
0
0
Инверсия
X
1
f(X
1
, X
2
)=^X
1
f(X
1
, X
2
) = X
1
f
13
(X
1
,X
2
)
1
1
0
1
Импликация
от
X
1
к
X
2
f(X
1
, X
2
)= X
1
-> X
2
f
14
(X
1
,X
2
)
1
1
1
0
Штрих Шеффера
f(X
1
, X
2
)= X
1
|X
2
f
15
(X
1
,X
2
)
1
1
1
1
Константа "единица"
f(X
1
, X
2
)=1
Эти
функции
введены формально. Однако им можно придавать определенный "логический" смысл.
Алгебра
логики часто называется исчислением высказываний.
При этом под высказываниями понимается всякое предложение, относительно которого можно
утверждать, что оно истинно или ложно.
2 Основные законы алгебры логики и правила преобразования логических выражений
В алгебре логики имеются законы, которые записываются в виде соотношений. Логические законы
позволяют производить равносильные (эквивалентные) преобразования логических выражений.
Преобразования называются равносильными, если истинные значения исходной и полученной после
преобразования логической функции совпадают при любых значениях входящих в них логических
переменных.
Для простоты записи приведем основные законы алгебры логики для двух логических
переменных
А
и
В.
Эти законы распространяются и на другие логические переменные.
1. Закон противоречия:
2. Закон исключенного третьего:
3. Закон двойного отрицания:
19
4. Законы де Моргана:
5. Законы повторения:
A & A = A; A v A = A; В & В = В; В v В = В.
6. Законы поглощения:
A ? (A & B) = A; A & (A ? B) = A.
7. Законы исключения констант:
A ? 1 = 1; A ? 0 = A; A & 1 = A; A & 0 = 0; B ? 1 = 1; B ? 0 = B; B &
1 = B; B & 0 = 0.
8. Законы склеивания:
9. Закон контрапозиции:
(A ? B) = (B ? A).
Для логических переменных справедливы и общематематические законы. Для простоты записи
приведем общематематические законы для трех логических переменных
A, В и С:
1. Коммутативный закон:
A & B = B & A; A ? B = B ? A.
2.
Ассоциативный закон:
A & (B & C) = (A & B) & C; A ? (B ? C) = (A ? B) ? C.
3. Дистрибутивный закон:
A & (B ? C) = (A & B) ? (A & C).
Как уже отмечалось, с помощью законов алгебры логики можно производить равносильные
преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого
соглашения установлены следующие правила (приоритеты) для выполнения логических операций:
первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание),
конъюнкция ( & ), дизъюнкция (v), импликация (?), эквиваленция (?)
Выполним преобразование, например, логической функции
применив соответствующие законы алгебры логики.
Основные логические элементы компьютера
Данные и команды представляются в виде двоичных последовательностей различной структуры и
длины. Существуют различные физические способы кодирования двоичной информации. Мы уже
рассмотрели способы записи двоичной информации на магнитных дисках и на CD-ROM. В
электронных устройствах компьютера двоичные единицы чаще всего кодируются более высоким
уровнем напряжения, чем двоичные нули (или наоборот), например:
Что такое логический элемент компьютера?
Логический элемент компьютера
— это часть электронной логической схемы, которая реализует
элементарную логическую функцию.
Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ
и другие (называемые также вентилями), а также триггер.
С помощью этих схем можно реализовать любую логическую функцию, описывающую работу
устройств компьютера. Обычно у вентилей бывает от двух до восьми входов и один или два выхода.
Чтобы представить два логических состояния — “1” и “0” в вентилях, соответствующие им входные и
выходные сигналы имеют один из двух установленных уровней напряжения. Например, +5 вольт и 0
вольт. Высокий уровень обычно соответствует значению “истина” (“1”), а низкий — значению “ложь”
(“0”).
Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую
функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает
запись и понимание сложных логических схем. Работу логических элементов описывают с помощью
таблиц истинности.
Связь между алгеброй логики и двоичным кодированием. Математический аппарат алгебры логики
очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку
20
основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а
значений логических переменных тоже два: “1” и “0”.
Из этого следует два вывода:
1.
одни и те же устройства компьютера могут применяться для обработки и хранения как числовой
информации, представленной в двоичной системе счисления, так и логических переменных;
2.
на этапе конструирования аппаратных средств алгебра логики позволяет значительно упростить
логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить
число элементарных логических элементов, из десятков тысяч которых состоят основные узлы
компьютера.
Работу логических элементов описывают с помощью таблиц истинности.
Таблица истинности
это табличное представление логической схемы (операции), в котором
перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со
значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний.
Ниже приведены условные обозначения (схемы) базовых логических элементов, реализующих
логическое умножение (конъюнктор), логическое сложение (дизъюнктор) и отрицание (инвертор).
Рис. 3.1. Конъюнктор, дизъюнктор и инвертор
Устройства компьютера (сумматоры в процессоре, ячейки памяти в оперативной памяти и др.)
строятся на основе базовых логических элементов.
5.Триггеры, сумматор.
.
Триггер
—
это электронная схема, широко применяемая в регистрах компьютера для надёжного
запоминания одного разряда двоичного кода. Триггер имеет два устойчивых состояния, одно из
которых соответствует двоичной единице, а другое — двоичному нулю.
Термин
триггер
происходит от английского слова
trigger
— защёлка, спусковой крючок. Для
обозначения этой схемы в английском языке чаще употребляется термин
flip-flop
, что в переводе
означает "хлопанье". Это звукоподражательное название электронной схемы указывает на её
способность почти мгновенно переходить ("перебрасываться") из одного электрического состояния в
другое и наоборот.
Самый распространённый тип триггера — так называемый RS-триггер (S и R, соответственно, от
английских
set
— установка, и
reset
— сброс). Условное обозначение триггера — на рис.
Он имеет два симметричных входа S и R и два симметричных выхода Q и
, причем выходной сигнал
Q является логическим отрицанием сигнала
.
На каждый из двух входов S и R могут подаваться входные сигналы в виде кратковременных
импульсов (
).
Наличие импульса на входе будем считать единицей, а его отсутствие — нулем.
???????На рис. показана реализация триггера с помощью вентилей ИЛИ—НЕ и соответствующая
таблица истинности.