Основы булевой алгебры

2 глава. Логические основы ЭВМ.

Теоретической основой построения ЭВМ являются специальные математические дисциплины. Одной из них является булевая алгебра, названная в честь основоположника этой дисциплины, английского математика 19-го века Дж. Буля. Этот математический аппарат, созданный Дж. Булем, нашёл широкое применение для описания, создания и оптимизации структуры устройств ЭВМ.

Основные элементы булевой алгебры.

Элементами БА являются: числа, операции и функции булевой алгебры.

Числа в булевой алгебре принимают значения из множества {0, 1}. Числа могут быть как переменными, так и постоянными значениями.

Операции в булевой алгебре – действия над числами.

А) Операция отрицания (инверсии). В результате этой операции переменная принимает противоположное значение.

Пример. А=1 – переменная имеет значение равное «1₂».

А=0 – при инверсии переменная принимает значение равное «0₂».

Отметим, что для выполнения этой операции нужно использовать только одну переменную А.

О перацию отрицания выполняют на устройстве, которое на схеме принято обозначать следующим образом:

Б) Операция конъюнкции (логическое умножение, логическая операция «И»).

Операция конъюнкции записывается следующим образом:

С=А*В=АВ=АВ, где А, В – логические переменные.

С- результат конъюнкции.

Правила логического умножения.

А	В	С
0	0	0
1	1	1
1	0	0

Операцию конъюнкции выполняют на устройстве, которое на схеме принято обозначать следующим образом:

Х₁

Y

X_N

Следует отметить, что в отличии от операции инверсии, для выполнения конъюнкции нужно использовать минимум две логические переменные.

В) Операция дизъюнкции (логическое сложение, логическая операция «ИЛИ»).

Операция дизъюнкции записывается следующим образом:

С=А+В=АВ= где А, В – логические переменные.

С- результат конъюнкции.

Правила логического умножения.

А	В	С
0	0	0
1	1	1
1	0	1

Операцию дизъюнкции выполняют на устройстве, которое на схеме принято обозначать следующим образом:

Х₁

Y

X_N

Для выполнения операции конъюнкции также необходимо использовать минимум две логические переменные.

Старшинство операций. 1 очередь – инверсия, 2 очередь – умножение, 3 очередь – сложение.

Булевой или логической функцией вида F(x₁,x₂……..x_N), называется функция, аргументами которой являются булевые переменные x_i и которая принимает значения из множества {0,1}.

Любая булевая функция состоит из n-го числа булевых переменных, соединённых между собой логическими операциями.

Пример. Y=F(x₁,x₂)= x₁x₂, где n=2 – число аргументов функции.

x₁,x₂ – аргументы функции.

 - операция дизъюнкции, соединяющая аргументы x₁ и x₂.

Отметим, что используя три логические операции (,,) и n-е число булевых переменных можно создать булевые функции любой сложности.

Количество всевозможных функций N от n-го числа аргументов булевой функции выражается зависимостью:

N=(2)ⁿ

Так при n=0 число функций N=2. Такими функциями с n=0 аргументов являются функции не зависящие от аргументов функции.

Пример. F₀( _ )=0 или const=0

F₁( _ )=1 или const=1

При n=1 число функций N=4. Представим зависимость значений этих функций от значений аргументов булевых функций в виде таблицы истинности.

Таблица истинности функций от одной переменной.

Значение аргумента	Значение функции
	Y0	Y1	Y2	Y3
0	0	0	1	1
1	0	1	0	1

Y₁ – функция аналогичная F₀ (смотри предыдущий пример).

Y₃ – функция аналогичная F₁ (смотри предыдущий пример).

Y₂ – функция, выполняющая инверсию аргумента. (Y=X)

Y₁– функция повторения аргумента. (Y= X).

Таблицы истинности получили своё название, так как они определяют зависимость всех значений булевой функции от всех наборов аргументов. Количество наборов аргументов определяет математическая зависимость:

M=2ⁿ., где n – число аргументов.

Так при n=1 M=2 (смотри таблицу истинности от 1 аргумента).

Способы задания булевых функций.

Существует 4 способы задания булевых функций.

1. Аналитический. При этом способе функция Y=F(x₁,x₂……..x_N) будет записана в следующем виде:

Y= x₁+x₂x₃……, то есть аналитическая форма представления функции получается при помощи соединения логическими операциями (,,) переменных. Добавим, что эта форма наиболее часто употребляется для представления логических функций.

2. Табличный. При этом способе функцию описывают при помощи таблиц истинности, описывая таким образом все значения, которые она может принять.

Пример. Функция Y=F(x₁,x₂) – принимает значения 1 при равенстве двух аргументов. Количество наборов M=2ⁿ=2²=4. Тогда таблица истинности будет иметь вид:

Значение аргументов		Значение функции	Примечания
x1	x2	Y
0	0	1	Аргументы равны
0	1	0	Аргументы не равны
1	0	0	Аргументы не равны
1	1	1	Аргументы равны

2. Числовой.

3. Графический.