Лекция на тему: Логические (булевы) функции

Тема занятия: Логические (Булевы) функци

Основные логические функции

Обозначим через Е ={0,1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной математике. Часто они интерпретируются как «ложь» (л ={0}) и как «истина» (и ={1}).

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

Переменные, которые могут принимать только два значения
0 и 1называются логическими переменными.

Из определения логической функции следует, что функция п переменных – это отображение Е^п в Е, которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции. Например, функция трех переменных f( x, y, z ) может определяться следующей таблицей истинности.

Это означает что f(0,0,0) =1, f(0,0,1) =0, f(0,1,0) = 1 и т.д.

Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).

При таком задании наборы Е^п всегда упорядочены естественным образом, это позволяет определять функцию только последним столбцом. Например, в нашем примере f = (10110100).

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

Теперь можно описать основные функции дискретной математики.

Рассмотрим функции двух переменных. Функции двух переменных определены на множестве _ = {(0 0),(0 1),(1 0),(1 1)}, эти наборы переменных можно рассматривать как двоичные коды чисел 0, 1, 2, 3, именно такой порядок расположения наборов будем считать стандартным. Число функций двух переменных равно 2⁴ = 16, занумеруем их числами от нуля до 15.

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

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

f₁ (x, y) = xy =

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

1. Дизъюнкция (функция ИЛИ)

f₇ (x, y) =x у =

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

f₁₃(x, y) = _ =

Иногда импликацию обозначают х⊃у или _ (читается «из х следует у»).

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

1. Сложение по модулю 2

f₆ (x, y) = x⊕y =

1. Эквивалентность или подобие

f₉ = x∼y = x↔y

1. Штрих Шеффера

f₁₄(x, y) = x⎢y =

«не И» (так как она равна отрицанию конъюнкции);

1. Стрелка Пирса (иногда эту функцию называют штрих Люкасевича, функция Вебба, функция Даггера)

Эта функция является отрицанием дизъюнкции «не ИЛИ».

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

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

Две формулы называются равными или эквивалентными, если функции реализуемые ими равны.

Пример: Доказать эквивалентность формул:

(x₁ &(x₂ ⊕x₃)) ≡ (x₁ (x₂ →x₃)&( x₃ →x₂)).

Упрощение записи формул:

1. внешние скобки можно опустить;

2. приоритет применения связок возрастает в следующем порядке:
   ∼,→, , & ;

3. связка над одной переменной сильнее всех связок;

1. если связка стоит над формулой, то сначала выполняется формула, затем отрицание;

2. если нет скобок, то операции ∼ и → выполняются в последнюю очередь.

Некоторые свойства элементарных функций

1. Идемпотентность & и : x x = x, x&x = x;

2. Коммутативность &, ,⊕,⎥,∼,↓;

3. Ассоциативность &, , ⊕, ∼ поэтому в формулах вида xyz можно не ставить никаких скобок

4. Дистрибутивность

а) & по отношению к : x&(x y) = xy xz;

б) по отношению к & : x (y&z) = (x y)&(x z);

в) & по отношению к ⊕ : x(y⊕z) = xy⊕xz.

1. Инволюция (двойное отрицание) x = x;

2. Правила де Моргана x y = x & y и xy = x y.

1. Правило констант

X 0 = X X 1 = 1

X & 0 = 0 X & 1 = 1

X⊕1 = X X⊕0 = X.

1. Самодистрибутивность импликации

x→(y→z) = (x→y) → ( x→z)

9. Закон противоречия

x & x = 0

10. Закон исключенного третьего

x x = 1

Равенство всех этих формул доказывается по определению, т.е. по равенству функций которые он реализуют.

Следствия из свойств элементарных функций

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

xy xy = x(y y) = x∙1 = x (дистрибутивность & относительно );

(x y)&(x y) = x y y = x 0 = x (дистрибутивность относительно &).

2. Законы поглощения:

x xy = x(1 y) = x∙1 = x; x&(x y) = x xy = x.

Свойства элементарных функций и теорема о замене подформул на эквивалентные позволяют упрощать формулы.

Пример:

Упростим формулы:

1. x₂x₃ x₁x₂x₃ = x₃(x₂ x₁x₂) = x₃((x₂ x₁)&(x₂ x₂)) = (x₁ x₂)x₃.

2. x₁ x₁x₂ x₁x₂x₃ x₁x₂x₃x₄ = x₁ x₁(x₂ x₂x₃ x₂x₃x₄) =

= x₁ x₁(x₂ x₃ x₂ x₃x₄) = (x₁ x₁)( x₁ x₂ x₃ x₂ x₃ x₄) =

= x₁ (x₂ x₃) (x₂ x₃)x₄ = x₁ (x₂ x₃ (x₂ x₃))(x₂ x₃ x₄) = x₁ x₂ x₃ x₄

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