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

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

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

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

Таблица 1. Таблица истинности булевой функции

00…00
00…01
00…10
…	…
11…10
11…11

В качестве примера в таблице 2 задана функция от трех переменных, которая равна 1, нечетное количество переменных равно 1, и 0 – в остальных случаях.

Таблица 2. Пример задания булевой функции

Отметим, что наборы значений аргументов в таблице записывают в естественной форме, то есть -ый по порядку набор представляет собой двоичную запись числа, =0, 1, 2, …,.

Обозначим через систему всех булевых функций от переменных. Число всех функций из равно числу перестановок с повторениями значений функции {0, 1} на выборке из входных наборов переменных, то есть.

Следует отметить, что числа с ростом быстро растут:

Следовательно, уже при сравнительно небольших значениях () перебор функций из данного множества становится практически невозможен даже с использованием вычислительной техники. Кроме того, с ростом числа аргументов таблица истинности сильно усложняется. Так, например, уже при не очень большом числе аргументов, скажем при =10, таблица становится громоздкой (имеет 1024 строки), а при =20 – практически необозримой. Поэтому используют другие способы задания функции, среди которых основным является аналитический способ, то есть при помощи формул. При этом способе некоторые функции выделяются и называются элементарными, а другие функции строят из элементарных с помощью суперпозиции. Такой способ задания функции хорошо известен в математическом анализе. Например, функция построена суперпозицией многочлена, квадратного корня, косинуса и функции.

Булевы функции одного аргумента представлены в таблице 3.

Таблица 3. Булевы функции одного аргумента

Среди этих функций и представляют собой константы,, а называется отрицанием (инверсией, логическое НЕ):

В таблице 4 приведены все 16 функций от двух аргументов.

Таблица 4. Булевы функции от двух аргументов

0 0
0 1
1 0
1 1

Рассмотрим более подробно эти функции.

Константы: – тождественная ложь,

– тождественная истина.

Унарные функции (функции одного аргумента).

Функции тождественности:

или, или.

Отрицание (инверсия, логическое НЕ):

,.

Бинарные функции (функции двух аргументов).

Конъюнкция (логическое умножение, логическое И):

,.

Читается “ и ”. Так как эта операция совпадает с операцией умножения в элементарной алгебре, то для конъюнкции используют также обозначение или. Конъюнкция двух высказываний истинна только в том случае, когда истинны оба высказывания.

Дизъюнкция (логическое сложение, логическое ИЛИ):

.

Читается “ или ”. Дизъюнкция двух высказываний ложна только в том случае, когда ложны оба высказывания.

Для конъюнкции и дизъюнкции можно записать

,.

Импликация (функция логического следования):

(импликация от к).

Читается “если, то ”, “ влечет ”, “из следует ”. – условие импликации, а – её заключение. Это важная функция, особенно в математической логике. Её можно рассматривать следующим образом. Из ложного условия можно вывести и истинное и ложное заключение (и это правильно). Если заключение истинно, то его можно вывести как из истинного так и из ложного условия (и это тоже правильно). Импликация ложна только в случае, когда условие истинно, а заключение ложно.

Аналогично имеем импликацию от к:

.

Функция неравнозначности (сумма по модулю 2, исключающее ИЛИ):

.

Читается “либо, либо ” или “ не эквивалентно ”.

Функция эквивалентности (равнозначности, подобия):

,,.

Читается “ в том и только том случае, если ”.

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

.

Эта функция является отрицанием дизъюнкции и поэтому ее называют также “НЕ ИЛИ”. Читается “не или ”.

Штрих Шеффера (антиконъюнкция):

.

Эта функция – отрицание конъюнкции и поэтому ее называют также “НЕ И”. Читается “не и ”.

Функция запрета (отрицание импликации):

.

Читается “, но не ”. Аналогично

.

Дата добавления: 2014-01-04