Законы преобразования над переменными

Основы алгебры логики

Поскольку цифровые вычислительные машины оперируют только информацией, представленной в виде «0» и «1», то и действия, выполняемые над ней, отличаются от общепринятых. Основы алгебры логики, разработанные математиком Д. Булем, базируются на использовании только двух переменных — a и b.

1. Логическое сложение a и b — логическая «ИЛИ»-дизъюнкция:

а + b = у, 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1.

2. Логическое умножение а и b — логическая «И» -конъюнкция:

а * b = у, 0*0 = 0, 0*1=0, 1*0 = 0, 1*1 = 1

3. Инверсия (отрицание) а или b — логическое «НЕ», когда значение переменной изменяется на обратное (противоположное).

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

В алгебре логики используются разнообразные законы, позволяющие выполнять преобразования над переменными:

1. Переместительный — от изменения мест переменных значение функции не меняется:

x v y = yvx; x*y = y * x

2. Сочетательный — от изменения первоочередности вычислений значение функции не меняется:

х v (у v г) = (х v у) v z; (x*y)*z = x*(y*z)

3. Распределительный:

(x v y)*z = x*y v x*z; x v (y*z) = (x v y)*(x v z)

4. Правила де Моргана:

НЕ(х v у) = НЕ х * НЕ у; НЕ(х * у) = НЕ х v НЕ у.

5. Идемпотенции:

х v х = х; х * х = х

6. Поглощения:

xv(x*y) = x; x*(xvy) = x

7. Склеивания:

(x*y) v(НЕ x*y) = y (x v y)*(НЕ x v y) = y

8. Операция над переменной и ее инверсией:

x v НЕ х = 1; x * НЕ х = 0.

9. Операции с константами:

x v 0 = x, x v 1 = 1; x *l = x, x * 0 = 0

10. Двойное отрицание:

НЕ-НЕ х = х.

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

 

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