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

Алгебра логики, выстроенная в 19 веке долго существовала как абстрактная наука. Но в середине 20 века оказалось, что она имеет конкретное и очень важное применение в современной жизни. Булева алгебра в настоящее время служит основой для описания логики работы аппаратных и программных средств ЭВМ. Дело в том, что алгебра логики использует логические переменные, которые принимают лишь два значения 0 и 1. Аналогично ЭВМ, используя лишь сигналы 0 и 1, воспринимает их как двоичные числа или логические переменные.

Обозначим через E = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной математике. Часто они интерпретируются как “ложь” (л ={0}) и как “истина” (и ={1}). Декартово произведение E* Е* Е* …* E=Eⁿ является множеством упорядоченных наборов, состоящих из п чисел (нулей и единиц).

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

При этом каждому варианту кортежа должен быть поставлен в соотвествие единственный элемент из В – значение булевой функции, например f(0110)=0.

Например, при п = 3 множество Е³может быть упорядочено следующим образом.

Такое упорядочение еще называют “скользящей единицей”.

Логической ( булевой) функцией (или просто функцией) n переменных y = f(x₁, x₂, …, x_n) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

Способы задания функций

1. Табличный

γзначение функции от данных аргументов.

Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.

2. Векторный

F = (γ₁ γ₂ γ ₃ γ _n)

3. В виде формулы.

Рассмотрим функцию двух аргументов

Функции двух переменных z = f(x,y).

Число этих функций равно 2⁴ = 16. Перенумеруем и расположим их тоже в естественном порядке.

Рассмотрим более подробно эти функции. Две из них f₀ = 0 и f₁₅ = 1 являются константами. Функции

являются по существу функциями одной переменной.

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

Перечислим 7 важнейших функций:

1) конъюнкция (функция И)

Заметим, что конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают x&y или x˄ y;

2) дизъюнкция (функция или)

3) импликация (следование)

(читается “из x следует y”).

Это очень важная функция, особенно в логике. Ее можно рассматривать следующим образом: если х = 0 (т. е. х “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если у = 1 (т. е. у “истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным. Заметим, что любая теорема всегда фактически содержит эту логическую функцию;

4) сложение по модулю 2 (здесь и далее, если не оговорено противное, знаком “+” мы будем обозначать такое сложение):

5) эквивалентность или подобие

Эта f₉ = 1 тогда и только тогда, когда х = у. Заметим, что будем применять оба обозначения: х^у (в основном при изучении функций) и х~ у (когда речь будет идти о логических операциях);

6) штрих Шеффера

Иногда эту функцию называют “не и” (так как она равна отрицанию конъюнкции);

7) стрелка Пирса (иногда эту функцию называют штрих Лукасевича)

Эта функция является отрицанием дизъюнкции и поэтому иногда ее называют “не или”.

Заметим, что свойства последних двух функций (как будет видно далее) похожи между собой и, может быть, поэтому в литературе их часто путают (т. е. называют f₈штрихом Шеффера, а f₁₄– стрелкой Пирса).

Три оставшиеся функции, (f₂, f₄и f₁₁) особого значения в дискретной математике не имеют.

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