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

Булевы функции.

Определение. Булевой функциейf(X₁, X₂, …, X_n) называется произвольная n – местная функция, аргументы и значения которой принадлежат множеству {0, 1}.

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

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

Ниже будет подробно рассматриваться двухэлементное множество и двоичные переменные, принимающие значения из этого множества. Его элементы часто обозначают 0 и 1, однако они, вообще говоря, не являются числами в обычном смысле (хотя и похожи на них по некоторым свойствам). Наиболее распространённая интерпретация двоичных переменных – логическая: “да” – “нет”, “истинно” – “ложно”. В контексте, содержащем одновременно двоичные и арифметические величины, а также функции, эта интерпретация обычно фиксируется явно. Например, в языках программирования (Pascal и др.) вводится специальный тип переменной – логическая переменная, значения которой обозначаются true и false. В данной лекции логическая интерпретация двоичных переменных не везде является обязательной, поэтому будем считать, что , рассматривая 0 и 1 как формальные символы, не имеющие арифметического смысла.

1. Функции алгебры логики.

Определение. Алгебра, образованная множеством вместе со всеми возможными операциями на нём, называется алгеброй логики.

Определение. Функцией алгебры логики (логической функцией) называется арная операция на множестве .

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

Определение. Алгебра, образованная элементным множеством вместе со всеми операциями на нём, называется алгеброй значной логики, а арная операция на элементном множестве называется значной логической функцией.

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

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

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