Основы булевой алгебры
.doc2 глава. Логические основы ЭВМ.
Теоретической основой построения ЭВМ являются специальные математические дисциплины. Одной из них является булевая алгебра, названная в честь основоположника этой дисциплины, английского математика 19-го века Дж. Буля. Этот математический аппарат, созданный Дж. Булем, нашёл широкое применение для описания, создания и оптимизации структуры устройств ЭВМ.
Основные элементы булевой алгебры.
Элементами БА являются: числа, операции и функции булевой алгебры.
Числа в булевой алгебре принимают значения из множества {0, 1}. Числа могут быть как переменными, так и постоянными значениями.
Операции в булевой алгебре – действия над числами.
А) Операция отрицания (инверсии). В результате этой операции переменная принимает противоположное значение.
Пример. А=1 – переменная имеет значение равное «12».
А=0 – при инверсии переменная принимает значение равное «02».
Отметим, что для выполнения этой операции нужно использовать только одну переменную А.
О перацию отрицания выполняют на устройстве, которое на схеме принято обозначать следующим образом:
Б) Операция конъюнкции (логическое умножение, логическая операция «И»).
Операция конъюнкции записывается следующим образом:
С=А*В=АВ=АВ, где А, В – логические переменные.
С- результат конъюнкции.
Правила логического умножения.
А |
В |
С |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
Операцию конъюнкции выполняют на устройстве, которое на схеме принято обозначать следующим образом:
Х1
Y
XN
Следует отметить, что в отличии от операции инверсии, для выполнения конъюнкции нужно использовать минимум две логические переменные.
В) Операция дизъюнкции (логическое сложение, логическая операция «ИЛИ»).
Операция дизъюнкции записывается следующим образом:
С=А+В=АВ= где А, В – логические переменные.
С- результат конъюнкции.
Правила логического умножения.
А |
В |
С |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
Операцию дизъюнкции выполняют на устройстве, которое на схеме принято обозначать следующим образом:
Х1
Y
XN
Для выполнения операции конъюнкции также необходимо использовать минимум две логические переменные.
Старшинство операций. 1 очередь – инверсия, 2 очередь – умножение, 3 очередь – сложение.
Булевой или логической функцией вида F(x1,x2……..xN), называется функция, аргументами которой являются булевые переменные xi и которая принимает значения из множества {0,1}.
Любая булевая функция состоит из n-го числа булевых переменных, соединённых между собой логическими операциями.
Пример. Y=F(x1,x2)= x1x2, где n=2 – число аргументов функции.
x1,x2 – аргументы функции.
- операция дизъюнкции, соединяющая аргументы x1 и x2.
Отметим, что используя три логические операции (,,) и n-е число булевых переменных можно создать булевые функции любой сложности.
Количество всевозможных функций N от n-го числа аргументов булевой функции выражается зависимостью:
N=(2)n
Так при n=0 число функций N=2. Такими функциями с n=0 аргументов являются функции не зависящие от аргументов функции.
Пример. F0( _ )=0 или const=0
F1( _ )=1 или const=1
При n=1 число функций N=4. Представим зависимость значений этих функций от значений аргументов булевых функций в виде таблицы истинности.
Таблица истинности функций от одной переменной.
Значение аргумента |
Значение функции |
|||
Y0 |
Y1 |
Y2 |
Y3 |
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
Y1 – функция аналогичная F0 (смотри предыдущий пример).
Y3 – функция аналогичная F1 (смотри предыдущий пример).
Y2 – функция, выполняющая инверсию аргумента. (Y=X)
Y1– функция повторения аргумента. (Y= X).
Таблицы истинности получили своё название, так как они определяют зависимость всех значений булевой функции от всех наборов аргументов. Количество наборов аргументов определяет математическая зависимость:
M=2n., где n – число аргументов.
Так при n=1 M=2 (смотри таблицу истинности от 1 аргумента).
Способы задания булевых функций.
Существует 4 способы задания булевых функций.
-
Аналитический. При этом способе функция Y=F(x1,x2……..xN) будет записана в следующем виде:
Y= x1+x2x3……, то есть аналитическая форма представления функции получается при помощи соединения логическими операциями (,,) переменных. Добавим, что эта форма наиболее часто употребляется для представления логических функций.
-
Табличный. При этом способе функцию описывают при помощи таблиц истинности, описывая таким образом все значения, которые она может принять.
Пример. Функция Y=F(x1,x2) – принимает значения 1 при равенстве двух аргументов. Количество наборов M=2n=22=4. Тогда таблица истинности будет иметь вид:
Значение аргументов |
Значение функции |
Примечания |
|
x1 |
x2 |
Y |
|
0 |
0 |
1 |
Аргументы равны |
0 |
1 |
0 |
Аргументы не равны |
1 |
0 |
0 |
Аргументы не равны |
1 |
1 |
1 |
Аргументы равны |
-
Числовой.
-
Графический.