Лекционный курс по основам информатики, страница 8

Формула (1) утверждает, что в алгебре логики рассматриваются только двоичные переменные.

Формулы (2)-(4) определяют операции дизъюнкции и конъюнкции.

Формула (5) определяет операцию отрицания.

4.4. Законы (теоремы и тождества) алгебры логики

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

Идемпотентные законы (6)

Коммутативные законы (7)

Ассоциативные законы (8)

Дистрибутивные законы (9)

Законы отрицания (10)

(11)

(12)

Законы двойственности (теоремы де Моргана)

(13)

Закон двойного отрицания (14)

Законы поглощения (15)

Операции склеивания (16)

(17)

Большинство теорем, а также аксиом записаны парами. При внимательном изучении пар можно вывести принцип двойственности – если в тождестве произвести взаимные замены операций дизъюнкции и конъюнкции, а также элементы 0 и 1, если они имеются, то получим тоже тождество. Такое свойство называется принципом двойственности.

f(v,0,l/+,&)=g(v,0,/+,&) где v=(x_n-1,...,x₀) то справедливо также тождество: f(v,l,0/&,+)=g(v,l,0/&,+)

Все теоремы могут быть доказаны аналитически или методом перебора.

Метод перебора – тождество (13)

Аналитический метод – тождество (17)

Порядок выполнения операций:

отрицание слагаемой или сомножителя;

конъюнкция сомножителей;

дизъюнкция слагаемых;

общее отрицание дизъюнкции или конъюнкции.

4.5. Логические функции

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

В соответствии с вышеприведенными аксиомами (1)-(5) функция может принимать в зависимости от значений переменных x_p только два значения 0 и 1.

Для функции n переменных x_n-1,…,x₀ будем использовать общее обозначение где v=(x_n-1,…,x₀) каждая переменная x_p (p=0,1,2,…,n) может принимать только два значения 0 и 1. Поэтому число всех возможных комбинаций значений x_n-1,…,x₀ конечно и равно 2ⁿ.

В общем виде конкретное значение переменной x_p (0 или 1) будем обозначать через e_p. Символами i, j и т.п. будем обозначать порядковые десятичные числа. e_n-1…e_p…e₀ – обобщающая запись двоичного числа, где e_p = 0 или 1, и являются элементами алгебры логики если они используются в качестве значений переменных, для этих элементов не существует соотношений больше или меньше.

4.6. Область определения логических функций

Областью определения функции n переменных x_n-1,…,x₀ является совокупность точек n-мерного пространства, причем каждая из точек задается определенной комбинацией значений этих переменных где e_p =0 или 1, (p=0,1,2,…,n-1).

Например, пусть есть некая функция 4х переменных n=4 то одна из точек определения этой функции V_i =(e_n-1…e_p…e₀) где i=e_n-1…e_p…e₀ (например, V_i=1100).

Из этих соотношений видно, что точки определения можно посчитать по порядку
от 0 до 2ⁿ как в двоичном счете, так и десятичном и в любом другом. Поэтому область определения функции f(v) n переменных имеет 2ⁿ точек т.е.

Для задания функции f(v) следует указать ее значения во всех точках области определения т.е. следует задать значения f(v_i)=0 или 1 где i=0,1,2,…,2ⁿ-1. В совокупности эти значения представляют некое двоичное число из 2ⁿ разрядов т.к. имеется всего различных 2ⁿ разрядных двоичных чисел, то и число различных функций n переменных равно .

Функции n переменных могут зависеть не от всех переменных x_n-1…x₀. Такие функции называются вырожденными.

Так же функция может быть задана как во всех точках определения, так и не во всех:

- функция n переменных f(v) называется полностью определенной, если ее значения f(v_i)=0 или 1 заданы во всех 2ⁿ точках V_i области определения;

- если же значение функции не задано хотя бы в одной точки V_i, то она называется не полностью определенной, это означает, что функция в этой точке может иметь значение 1 или 0 – и это не важно – такое значение будем называть коэффициентом с;

- если значения функции не заданы во всех точках V_i, то она называется полностью неопределенной.

4.6. Таблица истинности

Так как область определения любой функции n переменных конечна 2ⁿ точек она может быть задана таблицей значений f(v_i)=0 или 1 которые она принимает в точках v_i, где i=0,1,…,2^n-1. Такие таблицы называются таблицами истинности.

Например: функция двух переменных

4.7. Логические функции одной переменной

Разберем параметры таких функций:

n=1 – число переменных;

m=2 – число точек определения;

N=4 – число всех функций одной переменной.

Рассмотрим каждую функцию:

– нулевая функция.

– функция повторения.

– функция отрицания.

– единичная функция.

Таблица истинности функций одной переменной

4.8. Логические функции двух переменных

Рассмотрим параметры функций:

n=2 – число переменных;

m=4 – число точек определения;

N=16 – число всех функций двух переменных.

Таблица истинности всех функций двух переменных

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

Функция логического умножения (конъюнкция).

– логическое умножение, описывает работу логического элемента И.

Функция логического сложения (дизъюнкция)