Лекция 3. Алгебра логики

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

Алгебра логики оперирует с высказываниями. Под высказыванием понимают повествовательное предложение, относительно которого можно утверждать, истинно оно или ложно. Например, выражение «Расстояние от Москвы до Томска больше, чем от Москвы до Новороссийска» истинно, а выражение «5<2» - ложно.

Высказывания принято обозначать буквами латинского алфавита: A, B, C, …, X, Y и т.д. Если высказывание С истинно, то пишут С = 1, а если оно ложно, то С= 0.

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

Из всего набора логических операций в ЭВМ применяются только четыре:

1 Конъюнкция.

2 Дизъюнкция

3 Инверсия

4 Сумма по модулю два.

Рассмотрим логические операции и соот­ветствующие им элементы логических схем.

Конъюнкция. Соединение двух (или нескольких) высказы­ваний в одно с помощью союза И (AND) называется операцией логи­ческого умножения, или конъюнкцией. В логических выражениях эту операцию принято обо­значать знаком «^» или знаком умножения «*», а на электронных схемах –знаком «&». Сложное выска­зывание А & В истинно только в том случае, когда истинны оба входящих в него высказывания. Истинность такого высказывания задается табл.

А	В	А ^ В

Логическая схема И реализует конъюнкцию двух или более логи­ческих значений. Условное обозначение схемы И с двумя входами представлено на рис.

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет нуль, на выходе также будет нуль.Связь между выходом zэтой схемы и входами х и у описывается соотношением: z = x& у (читается как «х И у»).

Дизъюнкция. Объединение двух (или нескольких) высказы­ваний с помощью союза ИЛИ (OR) называется операцией логиче­ского сложения, или дизъюнкцией. В логических выражениях эту операцию принято обо­значать знаком «v» или знаком сложения «+»,а на электронных схемах – знаком «1». Сложное высказывание AvВ истинно, если истинно хотя бы одно из входящих в него высказыва­ний. Истинность такого высказывания задается табл.

А	В	А v В

Схема ИЛИ реализует дизъюнкцию двух или более логических значений. Условное обозначение схемы ИЛИ с дву­мя входами представлено на рис.

Когда хотя бы на одном входе схемы ИЛИ будет единица, на ее выходе также будет единица. Связь между выходом zэтой схемы и входами х и у описывается соотношением: z = xv у (читается как «х ИЛИ у»).

Инверсия. Присоединение частицы НЕ (NOT) к некоторому высказыванию называется операцией отрицания (инверсии) и обо­значается .Если высказывание А истинно, то ложно, и наоборот. Таблица истинности имеет вид:

А

Схема НЕ (инвертор) реализует операцию отрицания. Услов­ное обозначение схемы инвертора имеет вид:

Если на входе схемы «0», то на выходе «1», и наоборот. Связь ме­жду входом х этой схемы и выходом zможно записать соотношени­ем z= , где читается как «НЕ х» или «ИНВЕРСИЯ х».

Сумма по модулю два (иначе называется ИСКЛЮЧАЮЩЕЕ ИЛИ). Результатом выполнения операции сложения по модулю два является только остаток от сложения, т.е. перенос в старший разряд отбрасывается. В логических выражениях эту операцию принято обо­значать знаком « »,а на электронных схемах – знаком «=1». Сложное высказывание A В истинно, если истинно только одно из входящих в него высказыва­ний. Истинность такого высказывания задается табл.

А	В	А В

Схема ИСКЛЮЧАЮЩЕЕ ИЛИ соответствует сло­жению по модулю два двух логических значений. Условное обозначение схемы ИСКЛЮЧАЮЩЕЕ ИЛИ представлено на рис.

Когда только на одном входе схемы ИСКЛЮЧАЮЩЕЕ ИЛИ будет единица, на ее выходе также будет единица. Связь между выходом zэтой схемы и входами х и у описывается соотношением: z = x у (читается как «х плюс у по модулю 2»).

Кроме схемных элементов, соответствующих перечис­ленным логическим операторам, в состав логических схем входят комбинированные связки, именуемые вентилями, например сле­дующие.

Схема И—НЕ состоит из элемента И и инвертора и осуществля­ет отрицание результата схемы И. Таблица истинности схемы И—НЕ имеет вид:

x	y

Связь между выходом zи входами х и у схемы записывают как z = (читается как «ИНВЕРСИЯ х И у»).Условное обозначение схемы И—НЕ с двумя входами имеет вид:

Схема ИЛИ—НЕ состоит из элемента ИЛИ и инвертора и осу­ществляет отрицание результата схемы ИЛИ. Таблица истинности схемы ИЛИ—НЕ имеет вид:

x	y

Связь ме­жду выходом zи входами х и у схемы записывают как z = (читается как «ИНВЕРСИЯ х ИЛИ у»). Условное обозначение схемы ИЛИ—НЕ с двумя входами имеет вид функционирования КС определен, если задано со­ответствие между ее входными и выходными словами, на­пример, в виде таблицы истинности.

Это соответствие может быть задано и в аналитической форме с использованием булевых функций.

:

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

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

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

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

Закон функционирования КС определен, если задано со­ответствие между ее входными и выходными словами, на­пример, в виде таблицы истинности.

Это соответствие может быть задано и в аналитической форме с использованием булевых функций.