Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика 2015

2.2. Логические основы работы ЭВМ

  • - А почему «операция Ы»?
  • - Чтобы никто не догадался.

Из фильма «Операция «Ы» и другие приключения Шурика».

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

Булева алгебра оперирует с логическими переменными, которые могут принимать только два значения: истина или ложь, обозначаемые соответственно 1 и 0.

Как ранее отмечалось, основной системой счисления ЭВМ является двоичная СС, в которой также используются только две цифры: 1 и 0. Таким образом, одни и те же цифровые устройства ЭВМ могут применяться для выполнения арифметических и логических операций. Это обуславливает универсальность (однотипность) схемной реализации процесса обработки информации в ЭВМ.

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

Совокупность значений логических переменных Xj, Х2,..., х„ называется набором переменных.

Логической функцией от набора логических переменных (аргументов) F(Xi, Х2, ..., х„ ) называется функция, которая может принимать только два значения: истина или ложь (1 или 0). Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются возможные наборы аргументов, а в правой части — соответствующие им значения функции. Логическую функцию норой называют функцией алгебры логики (ФАЛ).

Ниже приведена таблица истинности для логической функции «Равнозначность».

Аргументы

Функция

х2

Xj

F

0

0

1

0

1

0

1

0

0

1

1

1

В случае большого числа аргументов табличный способ задания функции алгебры логики становится громоздким, поэтому ФАЛ удобно выражать через другие, более простые ФАЛ.

Общее число ФАЛ л переменных определяется возведением числа 4 в степень л, т. е. 4П. Существуют четыре ФАЛ одной логической переменной.

Таблица 1

X

Fc/x)

F,(x)

F2(X)

Fj(x)

0

0

0

1

1

1

0

1

0

1

Функции F({x) = 0 и F;?x) = 1 являются константами (функции не изменяются при изменении аргумента). Функция Fi(x) = х повторяет значение аргумента х. Функция F^x) называется отрицанием переменной или инверсией и обозначается так:

Число ФАЛ двух переменных Xj и Хг равно 16: F/x) ... Fi~,(x). Шесть функций являются вырожденными: F(/x) =0, F{x) =Xj, F-(x) —X2, Fu{x) = X2, F12(x) = Xl,Fldx)= 1.

Из оставшихся десяти логических функций широкое распространение имеют функции F}(x) (конъюнкция, логическое умножение, логическая операция И) и F/x) (дизъюнкция, логическое сложение, логическая операция ИЛИ), которые совместно с функцией инверсии составляют функционально полную систему логических функций. С помощью этих трех функций можно представить (аналитически выразить) любую сколь угодно сложную логическую функцию. Очень важной для вычислительной техники и информатики является логическая функция Исключающее ИЛИ (неравнозначность, сложение по модулю два). Ниже приведены таблицы истинности для трех функций и их условные обозначения.

Инверсия

X

X

0

1

1

0

*2

X!

X2VX1

х2лх!

х2Фх1

дтъюнк.

коныонк.

неравноз.

0

0

0

0

0

0

1

1

0

1

1

0

1

0

1

1

1

1

1

0

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

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

Рассмотрим аксиомы, тождества и основные законы алгебры логики.

В алгебре логики рассматриваются переменные, которые могут принимать только два значения: 0 и 1. Базируется алгебра логики на отношении эквивалентности и трех упомянутых ранее операциях: дизъюнкции (синонимы — логическое сложение, операция ИЛИ), конъюнкции (логическое умножение, операция И) и отрицании (инверсия, операция НЕ).

Отношение эквивалентности обозначается знаком =.

Дизъюнкция обозначается знаком v, а иногда символом +.

Конъюнкция обозначается символом / либо точкой, которую можно опускать.

Отрицание обозначается чертой над переменной: X .

Алгебра логики определяется следующей системой аксиом:

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

С помощью аксиом можно получить ряд тождеств:

Перечислим законы алгебры логики:

• переместительный (или коммутативный)

От перестановки местами аргументов результат не изменяется.

• сочетательный (или ассоциативный)

Указанные операции можно выполнять в любом порядке.

• распределительный (или дистрибутивный)

• двойственности (или де Моргана)

Инверсия от дизъюнкции дает конъюнкцию инверсий.

Инверсия от конъюнкции дает дизъюнкцию инверсий.

• двойного отрицания

• поглощения

• склеивания

Рассмотрим пример преобразования логических выражений.

Пример.

Упростить логическое выражение:

Решение.

При проведении преобразований нужно использовать соотношение:

Этот результат получается из определения операции Исключающее ИЛИ: . При подстановке в это выражение у~ 1, получим

Используя закон де Моргана, получим:

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы