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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

. (1)

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

… …

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

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