Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Булева функция Печать
Для формального описания узлов ЭВМ при их анализе и синтезе используется аппарат алгебры логики. Основные положения алгебры логики разработал в XIX в. английский математик Джордж Буль. Алгебру логики называют также булевой алгеброй.

В булевой алгебре различают двоичные переменные и булевы функции.

Двоичные переменные могут принимать два значения: 0 и 1. Они называются также логическими или булевыми переменными и обозначаются символами x1, x2, x3,…

Булевы функции зависят от двоичных переменных. Они, как и аргументы, могут принимать лишь два значения: 0 или 1. Булевы функции называют также логическими или переключательными функциями. Будем обозначать переключательные функции в виде f(x1, x2, x3, …) указывая в скобках аргументы, либо в виде y1, y2, y3,…

Булевы функции в свою очередь могут служить аргументами еще более сложных логических функций. Следовательно, можно построить переключательные функции любой заранее заданной сложности, пользуясь ограниченным числом логических связей.

Булевы функции принято задавать таблицами истинности, в которых для всех наборов переменных указываются соответствующие им значения булевых функции. Формирование значений в таблице истинности выполняется в соответствии с логикой работы устройства (сумматора, сдвигателя, преобразователя кодов и т. д.).

Набор переменных — это совокупность значений двоичных переменных, каждая из которых может быть равна 0 или 1. Если число аргументов (независимых переменных) переключательных функций равно n (т. е.x1, x2, x3,…xn), то существует два различных сочетаний этих переменных, т. е. наборов.

x1
x2
x3
f1
f2
0
0
0
01
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
1
0
0
0
0
1
0
1
1
0
1
1
0
0
1
1
1
1
0
1


Эта представляет собой таблицу истинности для некоторых переключательных функций f1 и f2, зависящих от двоичных переменных x1, x2, x3. Так как n = 3 (три переменных), таблица содержит 8 строк, соответствующих 23 = 8 наборам переменных x1, x2, x3. Для каждого набора в таблице записаны значения булевых функций f1 и f2, равные 0 или 1. По таблице истинности записывается аналитическое выражение для булевых функции.

Произвольная булева функция может быть выражена в форме функции от двоичных переменных (либо от других функций) с помощью ограниченного числа элементарных логических функций. Рассмотрим эти функции.

Логическое отрицание

Логическим отрицанием переменной x называется такая булева функция f1(x), которая имеет значение 1, когда x = 0 и значение 0, когда x = 1. Булева функция НЕ обозначается в виде f1 = x и читается: «f1 есть (эквивалентно) не x».

Эта таблица представляет собой таблицу истинности логической функции НЕ.

x
f1
0
1
1
0

Функцию НЕ выполняет физический элемент (электронная схема), который называется элементом НЕ или инвертором.

Логическое умножение (конъюнкция)

Конъюнкция двух (или любого другого числа) переменных x1 и x2 принимает значение 1 только на наборе, в котором все переменные имеют значения 1. На остальных наборах эта функция имеет значение 0.

x1
x2
f2
0
0
0
0
1
0
1
0
0
1
1
1

Эта таблица представляет собой таблицу истинности конъюнкции двух переменных x1 и x2. Булева конъюнкция обозначается в виде f2 = x1x2 и читается: «f2 есть (эквивалентно) x1 и x2».

Для обозначения конъюнкции можно использовать символ &. Конъюнкция называется также функцией И, так как она имеет значение 1, только если первый и второй аргументы имеют значения 1.

Функция И выполняется электронной схемой, которая называется элементом И или коньюнктором. Число входов элемента И равно числу переменных, участвующих в операции умножения.

Логическое сложение (дизъюнкция)

Дизъюнкция двух (или любого другого числа) переменных x1 и x2 имеет значение 0 только на наборе, в котором все переменные имеют значение 0. Если хотя бы одна из переменных равна 1, функция будет иметь значение 1.

x1
x2
f3
0
0
0
0
1
1
1
0
1
1
1
1

Эта таблица есть таблица истинности для дизъюнкции двух переменных x1 и x2. Булева дизъюнкция записывается в виде f3 = x1 + x2 и читается: «f3 есть (эквивалентно) x1 или x2». Кроме символа + , для дизъюнкции употребляется символ &.

Операция ИЛИ реализуется электронной схемой, которая называется элементом ИЛИ или дизъюнктором. Число входов элемента ИЛИ равно числу переменных, участвующих в операции дизъюнкции.

Элементарные логические функции НЕ, И, ИЛИ являются основными логическими функциями. Имеется еще несколько логических функций, производных от основных функций (т. е. выражающихся через функции НЕ, И, ИЛИ), которые реализуются соответствующими электронными элементами.