Основные законы булевой алгебры

Связки имеют следующий приоритет: ~. Приоритет операций, представленных логическими связками можно изменить с помощью скобок.

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

1. закон двойного отрицания: А = А

2. закон коммутативности (от перестановки аргументов результат не меняется): А В = ВА АВ = ВА

3. закон ассоциативности (порядка вычислений): А (ВС) = (АВ)С А(ВС) = (АВ)С

4. закон дистрибутивности (раскрытия скобок): А (ВС) = (АВ)(АС) А(ВС) = (АВ)(АС)

5. правила де Моргана: (АВ) =АВ(АВ) =АВ

6. правила операций с константами 0 и 1: 0 = 1,1 = 0, А0 = А, А1 = 1, А1 = А, А0 = 0

7. правила операций с переменной и её инверсией: А А = 1 АА = 0

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

1. закон поглощения: А (АВ) = А А(АВ) = А

2. закон идемпотентности (повторное применение не даёт ничего нового): А А...А = А АА...А = А

3. на основании закона дистрибутивности, а также 7-го и 6-го законов: А (АВ) = АВ

4. Законы склеивания

АВВ=В

АВВ=В

Логические основы эвм

Для описания того, как функционируют аппаратные средства компьютера очень удобен математический аппарат алгебры логики, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры «1» и «0».

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

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

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

Логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-НЕ». С помощью этих схем можно реализовать любую логическую формулу, описывающую работу устройств компьютера.

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

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

Рис. 2.1.2. Схема «И»

На выходе схемы «И» значение «1» будет тогда и только тогда, когда на всех входах будут «1». Когда хотя бы на одном входе будет «0», на выходе также будет «0».

Операция конъюнкции на функциональных схемах обозначается знаком «&» (читается как «амперсэнд»), являющимся сокращенной записью английского слова and.

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

Рис. 2.1.3. Схема «ИЛИ»

На выходе схемы «ИЛИ» значение «0» будет тогда и только тогда, когда на всех входах будут «0». Когда хотя бы на одном входе будет «1», на выходе также будет «1».

Операция дизъюнкции на функциональных схемах обозначается знаком «1».

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

Рис. 2.1.4. Схема «НЕ»

Если на входе схемы – «0», то на выходе будет «1». Когда на входе – «1», на выходе будет «0».

Схема «И-НЕ»состоит из элемента «И» и инвертора и осуществляет отрицание результата схемы «И». Условное обозначение схемы «И-НЕ» представлено на рисунке 2.1.5.

Рис. 2.1.5. Схема «И-НЕ»

На выходе схемы «И-НЕ» значение «0» будет тогда и только тогда, когда на всех входах будут «1».

Схема «ИЛИ-НЕ»состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата схемы «ИЛИ». Условное обозначение схемы «ИЛИ-НЕ» представлено на рис. 2.1.6.

Рис. 2.1.6. Схема «ИЛИ-НЕ»

На выходе схемы «ИЛИ-НЕ» значение «1» будет тогда и только тогда, когда на всех входах будут «0».