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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Х₁

Y

X_N

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

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

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

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

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

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

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

Х₁

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. Представим зависимость значений этих функций от значений аргументов булевых функций в виде таблицы истинности.

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

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

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

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

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

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

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

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