Краткие теоретические сведения

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

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

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

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

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

логический элемент «И» — логическое умножение – конъюнктор;

логический элемент «ИЛИ» — логическое сложение – дизъюнктор;

логический элемент «НЕ» — инверсию – инвертор.

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

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

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

Логический элемент “И”.

На входы А и В логического элемента подаются два сигнала (00, 01, 10 или 11). На выходе получается сигнал 0 или 1 соответствии с таблицей истинности операции логического умножения.

Логический элемент “ИЛИ”.

На входы А и В логического элемента подаются два сигнала (00, 01, 10 или 11). На выходе получается сигнал 0 или 1 в соответствии с таблицей истинности операции логического сложения.

Логический элемент “НЕ”.

На вход А логического элемента подается сигнал 0 или 1. На выходе получается сигнал 0 или 1 в соответствии с таблицей истинности инверсии.

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

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

В результате получилась 1, т.е. «истина».

Пример 2.Дано выражение: не (1 и(0 или 1) и1). Вычислить значение выражения с помощью логической схемы.

Учитывая скобки в выражении, строим логическую схему.

Результат вычисления: 0.

Также вы должны научиться записывать логическое выражение по логической схеме. Как это делается?

Для примера возьмем предыдущую схему.

Анализируем сколько переменных, сколько операций будет содержать выражение. Начинаем с конца схемы, т.е. с последней операции. Так как последний элемент – инверсия, значит отрицаться будет все выражение. Мы видим, что схема содержит конъюнкцию 1, 1 и дизъюнкции 0 и 1. Получается, что выражение выглядит так:

Задание:

1) Пусть а, b, с — логические величины, которые имеют следующие значения: а = истина, b = ложь, с = истина. Нарисуйте логические схемы для следующих логических выражений и вычислите их значения:

а и b;

а или b;

не а или b;

а и b или с;

а или b и с;

не а или b и с;

(а или b) и (с или b);

не (а или b) и (с или b);

не (а и b и с).

2) Построить логические схемы по логическому выражению:

х₁ и (не х₂ или х₃);

х₁ и х₂ или не х₁ и х₃;

х₄ и (х₁ и х₂ и х₃ или не х₂ и не х₃).

3) Выполните вычисления по логическим схемам. Запишите соответствующие логические выражения:

1) 2)

4) Дана логическая схема. Построить логическое выражение, со­ответствующее этой схеме. Вычислить значение выражения для

х₁ = 0, х₂ = 1;

х₁ = 1, х₂ = 0;

х₁ = 1, х₂ = 1;

х₁ = 0, х₂ = 0.

5) Упростить полученное в задаче 4 выражение и построить для него новую логическую схему.

6) Дана логическая схема. Построить соответствующее ей логическое выражение. Вычислить значение выражения для

х₁ = х₂ = 1, х₃ = х₄ = 0;

х₄ = 1 и любых х₁, х₂, х₃;

х₁ = 0, х₄ = 0 и любых значениях х₂, х₃.

7) Упростить полученное в задаче 6 логическое выражение и построить для него новую логическую схему.

8) Дана логическая схема. Построить соответствующее ей логическое выражение.

Вычислить значение выражения для

х₁ = х₂ = х₃ = 1;

х₁ = х₂ = х₃ = 0;

х₁ = 0, х₃ = 1 и любых значениях х₂

9) Упростить полученное в задаче 8 логическое выражение и построить для него новую логическую схему.