Логические схемы. Булевы выражения

Логические константы, переменные и функции

Элементы алгебры логики

Для описания логики функционирования аппаратных ипрограммных средств ЭВМ используетсяалгебра логики, или булева алгебра [1] (по имени создателя — английского математика XIX в. Дж. Буля — G. Вооlе).Два элемента алгебры логики — ee константы — будем обозначать: 0 и 1 (ложь иистина — false и true), т. е. логический 0 и логическая 1. Алгебра логики оперирует с логическими переменными, которые могут принимать только два значения; истина илиложь — логический 0 и логическая 1 (не путать с двоичными!).

X=0, если X 1

Х=1, если X 0— это булева (логическая) переменная

Во всех схемах ЭВМ используются сигналы двух видов. Таким образом, сигналы можно интерпретировать как двоичные числа, или логические переменные.

Логической функцией F от набора логических переменных xi,-..Xn называется функция, которая может принимать только два значения: логический 0 и логическая 1

Область определения логической функции конечна и зависит от количества возможных наборов аргументов. Если п — число аргументов, то количество возможных наборов аргументов равно 2 ⁿ. Множество значений функции F(xi,...,Xn) — это множество {0,1}, т. е. F=0 либо 1.

Элементарные логические операции. Таблицы истинности

1. Логическое умножение - конъюнкция - операция И -AND. Обозначается: &, , • или совсем опускается:

х • у, или х & у, или х  у или ху.

Постулаты операции И представлены в виде таблицы истинности функции F(x,y)=x • у:

X	Y	X • Y

Функция F(x,y) принимает значение 1 только в том случае, когда оба аргумента - и первый, и второй - равны 1.

2. Логическое сложение - дизъюнкция - операция ИЛИ - OR.

Обозначается: v или +:

X v Y или х+у

X	Y	X v Y

Функция F принимает единичное значение, когда хотя бы один из аргументов, или первый, или второй, или п-й, равен 1.

3. Отрицание - инверсия - операция НЕ - NOT. Обозначение: not X:

Постулаты операции НЕ представлены в виде таблицы истинности функции F(x)=x:

X	not X

Булева алгебра — математическая система с элементами логический 0 и логическая 1 и операциями И, ИЛИ и НЕ с их заданными постулатами. Цель булевой алгебры — описание поведения и структуры логических схем.

Булево выражение — это булевы константы и переменные, связанные логическими операциями И, ИЛИ и НЕ в единую формулу.

При вычислении логического выражения учитывается следующее старшинство логических операций:

1) инверсия (), not

2) конъюнкция (•), &, and

3) дизъюнкция (v), +, or

Для изменения порядка используются скобки.

Примеры.

1. F(X1,Х2,Хз) = (XI v X2) • (X1 v Хз) v X2 • Хз

2. F(X1,Х2,Хз) = (XI • X2 V Х2 • not ХЗ) • Xi V ХЗ

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

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

Другой класс схем — последовательностные схемы. Это схемы с внутренней памятью. В них значения выходных переменных определяются не только значениями входных переменных в текущий момент времени, но и их значениями в предыдущие моменты времени

Будем рассматривать только комбинационные схемы.

Построение таблицы истинности по булеву выражению

Построим таблицу истинности для следующей функции:

F(Xl,X2,XЗ) = (X1 V Х2) • (X1 v not ХЗ) v not (X2 • ХЗ)

Так как n=3, то всего может быть 8 различных комбинаций значений аргументов. (Для записи комбинаций следует пользоваться двоичной системой счисления.)

X1 X2 X3 F

X1	X2	X3	F

Вычислим значение F для каждого набора (х1,x2,х3).

F(0,0,0) = (0 or not 0) • (0 or 0) or not (0 • 0) = (0 v 1) •0 or not (0) = 0 •1 or 1=1

F(0,0,1) = (0 or not 0) • (0 or 1) or not (o •1) = (0 or 1) •1 or 1 = 1 и так далее.

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

Получение булевых выражений по таблицам истинности

Правила построения булева выражения:

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

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

Пример. Дана таблица истинности [2]:

X1	X2	X3	F

Построим булево выражение для F. Найдем строки, в которых F=1.Это вторая, третья и шестая.

Для второй строки X1=0, Х2=0, X3=1. Эту строку описывает минтерм not x1•not x2•X3

Для третьей строки X1=0, Х2=1, X3=0. Эту строку описывает минтерм not x1•X2•not x3

Для шестой строки X1=1, X2=0, X3=1. Эту строку описывает минтерм X1•not x2•X3

Объединяя термы, получим булево выражение для
F: =not x1•not x2•X3 or not x1•X2•not x3 or X1•not x2•X3

В это выражение вошли термы-произведения для строк с единичным значением функции F, а вся сумма соответствует совокупности из трех строк. Для остальных пяти наборов значений входных переменных это выражение равно нулю.

Дата добавления: 2014-01-06