ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

аранов Виктор Павлович. Дискретная математика.

Раздел 4. Функциональные системы с операциями. Алгебра логики. Лекция 19. Функции алгебры логики

Лекция 19. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

План лекции:

1. Функциональные системы и их роль в дискретной математике.

2. Определение булевой функции.

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

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

1. Функциональные системы и их роль в дискретной математике

Теория функциональных систем занимается изучением функций, описывающих работу дискретных преобразователей. К важнейшим классам функций относятся булевы функции, функции -значной логики, автоматные и вычислимые функции. С каждым из этих классов связываются операции, позволяющие из одних функций данного класса строить другие функции этого же класса. Такими операциями являются операция суперпозиции, операция обратной связи, операция примитивной рекурсии и -операция. В результате имеем функциональные системы с операциями – некоторые классы алгебр.

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

1. Определение булевой функции

Булевы функции составляют один из классов функциональных систем, на основе которых описывают работу дискретных преобразователей. К другим классам функциональных систем относятся функции -значной логики, автоматные функции и вычисляемые функции. С каждым из этих классов связывают операции, позволяющие из одних функций данного класса строить другие функции этого же класса. Такими операциями являются: операция суперпозиции, операция обратной связи, операция примитивной рекурсии и -операция. В результате получаем функциональные системы с операциями, то есть некоторые классы алгебр. Роль теории функциональных систем в дискретной математике можно сравнить с ролью математического анализа в непрерывной математике.

Булевой функцией переменных называют функцию , у которой все переменные и сама функция принимают только два значения. Эти функции называют также логическими функциями, функциями алгебры логики или переключательными функциями. Два возможных значения функции и ее аргументов обозначают по-разному: И (истина), Л (ложь); 0, 1; да, нет. В дальнейшем будем использовать 0 и 1.

Математическая логика, как самостоятельная область науки, сформировалась в середине XIX века, прежде всего благодаря работам ирландского математикам из г. Корке Джорджа Буля (отца писательницы Э.Л. Войнич, автора известного романа «Овод»). Первая работа Буля по логике – «Математический анализ логики» вышла в 1847 г. В 1854 г. вышел основной труд Буля – «Исследование законов мысли». Первые применения алгебры логики связаны с решением следующей задачи: выяснить, истинно или ложно сложное высказывание, если известна истинность или ложность составляющих высказываний.

Сложные высказывания образуются из исходных простых при помощи ограниченного набора логических операций (связок).

Будем обозначать простые высказывания буквами . Из них можно составить новые высказывания, например:

« и », обозначается ;

« или», обозначается ;

«не », обозначается ;

«если , то , обозначается .

Пусть буквами обозначены такие высказывания:

– «числовой ряд сходится»;

– «все члены ряда положительны»;

– «общий член ряда стремится к нулю».

Образуем некоторые составные высказывания:

– «если числовой ряд сходится, то его общий член стремится к нулю»;

– «члены ряда положительны и общий член ряда стремится к нулю;

– «если общий член ряда не стремится к нулю, то ряд расходится».

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

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

. (1)

В 30-х годах XX века булеву алгебру стали использовать для анализа структуры релейных схем (советский ученый В.И. Шестаков и американский математик и инженер Клод Шеннон). С развитием вычислительной техники булеву алгебру стали применять в качестве математического аппарата для описания работы дискретных устройств переработки информации. Такое устройство можно представить в виде «черного ящика» с входами и выходами (рис. 1).

… …

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

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

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

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

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

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

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

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

000	0
001	1
010	1
011	0
100	1
101	0
110	0
111	1

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

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

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

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

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

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

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

0	0	0	1	1
1	0	1	0	1

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

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

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

0 0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0 1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1 0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1 1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

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

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

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

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

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

или, или.

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

, .

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

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

, .

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

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

.

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

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

, .

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

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

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

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

.

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

.

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

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

, , .

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

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

.

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

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

.

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

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

.

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

.

Баранов Виктор Павлович. Дискретная математика.

Раздел 4. Функциональные системы с операциями. Алгебра логики

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ