Формулы логики булевых функций

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

Булевы функции двух переменных

Функция отрицания

Представление булевой функции

Элементарные булевые функции

Аксиомы (постулаты) алгебры логики

1. Дизъюнкция двух переменных равна 1, если хотя бы одна из них равна 1 и равна 0, если обе переменные равны 0:

0+0=0;

0+1=1;

1+0=1;

1+1=1.

2. Конъюнкция двух переменных равна 0, если хотя бы одна пе­ременная равна 0 и равна 1, если обе переменные равны 1:

0∙0=0;

0∙1=0;

1∙0=0;

1∙1=1.

3.Инверсия одного значения переменной совпадает с ее другим значением:

1= 0;

0 = 1.

Булевой функцией f(x1, x2, ..., xn) называется функция, которая принимает два значения 0 или 1 в зависимости от переменных х1, каждая из которых может также принимать только два значения 0 или 1.

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

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

x1 x2 x3 f(х1,х2,х3)

Для формирования столбца значений переменных удобен лексико­графический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100=011+1.

Булевая функция п переменных может иметь 2n наборов. Поскольку функция принимает только два значения, общее число булевых функций и переменных равно 22n. Таким образом, функция одной переменной может иметь четыре значения: у = х; у = -x (отрицание х); у = 0 (константа 0); у = 1 (константа 1).

Из них выделим функцию "отрицание x" (обозначается -x). Эта функция представлена в таблице

x -x

Булевых функций двух переменных - 16. Те из них, которые имеют специальные названия, представлены в таблице.

x1 x2 x1 Ú x2 x1 & x2 x1 É x2 x1 ~ x2 x1 Å x2 x1 ¯ x2 x1 ½ x2
0 0
0 1
1 0
1 1

В таблице представлены следующие функции двух переменных:

x1 Ú x2– дизъюнкция;

x1 & x2– конъюнкция;

x1 É x2– импликация;

x1 ~ x2– эквивалентность;

x1 Å x2– сложение по модулю 2;

x1 ¯ x2– стрелка Пирса;

x1 ½ x2 – штрих Шеффера

Формула логики булевых функций определяется индуктивно следующим образом:

1. Любая переменная, а также константы 0 и 1 есть формула.

2. Если A и B - формулы, то A, AÚB, A&B, AÉB, A~B есть формулы.

3. Ничто, кроме указанного в пунктах 1-2, не есть формула.