![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Булевы функции от n переменных
Булевы функции 1 названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два значения (если мощность множества значений функции равна 1, то это тривиальная функция - константа! ). С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики. Обозначим через B двухэлементное множество {0, 1}. Тогда это множество всех двоичных последовательностей (наборов, векторов) длины n. Булевой функцией от n переменных (аргументов) называется любая функция f(x1, xn): Bn -> B. Каждый из ее аргументов xi, 1 < = i < = n, может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из Bn также может быть 0 или 1. Обозначим через Теорема 3.1. Доказательство. Действительно, по теореме 1.1 число функций из k -элементного множества A в m -элементное множество Bравно mk. В нашем случае B={0, 1}, а A = Bn. Тогда m=2 и k= |Bn| = 2n. Отсюда следует утверждение теоремы. Имеется несколько различных способов представления и интерпретации булевых функций. В этом разделе мы рассмотрим геометрическое и табличное представления, а также представление с помощью логических формул. В " Эквивалентность формул и нормальные формы" будет показано, как булевы функции можно представлять с помощью формул специального вида - дизъюнктивных и конъюнктивных нормальных форм и многочленов Жегалкина. Кроме того, в лекциях " Предварительные сведения" и " Индукция и комбинаторика" (курс " Введение в схемы, автоматы и алгоритмы" ) будет рассмотрено еще два способа представления булевых функций: логические схемы и упорядоченные бинарные диаграммы решений. Геометрическое представление Bn можно рассматривать как единичный n-мерный куб. Каждый набор из нулей и единиц длины n задает вершину этого куба. На рис. 3.1 представлены единичные кубы Bn при n=3, 4.
При этом существует естественное взаимно однозначное соответствие между подмножествами вершин n-мерных единичных кубов и булевыми функциями от n переменных: подмножеству Например, верхней грани куба B3 (ее вершины выделены на рисунке) соответствует функция f: f(0, 0, 1)=f(0, 1, 1)=f(1, 0, 1)=f(1, 1, 1) =1 и f(0, 0, 0)=f(0, 1, 0)=f(1, 0, 0)=f(1, 1, 0) =0. Очевидно, что указанное соответствие действительно взаимнооднозначное: каждая булевая функция f от n переменных задает подмножество Af={(x1, ..., xn)|f(x1, ..., xn)=1} вершин Bn. Например, функция, тождественно равная 0, задает пустое множество Табличное представление Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции f(x1, ..., xn)имеет n+1 столбец. В первых n столбцах указываются значения аргументов x1, ..., xn, а в (n+1) -ом столбце значение функции на этих аргументах - f(x1, ..., xn).
Наборы аргументов в строках обычно располагаются в лексикографическом порядке:
Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, При больших n табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблицас 1024 строками. Но для малых n оно достаточно наглядно. Формулы Как мы видели, геометрическое и табличное представления булевых функций подходят лишь для функций с небольшим числом аргументов. Формулы позволяют удобно представлять многие функции от большего числа аргументов и оперировать различными представлениями одной и той же функции. Пусть Определение 3.2. 1. Базис индукции. Каждая переменная 2. Шаг индукции. Пусть Каждой формуле Базис индукции. Пусть Шаг индукции. Пусть Далее мы будем рассматривать формулы над множеством элементарных функций Определение 3.3. · Базис индукции. 0, 1 и каждая переменная · Шаг индукции. Пусть Тогда выражения В соответствии с этим определением выражения Для определения функции, задаваемой формулой, удобно использовать таблицу, строки которой сответствуют наборам значений переменных, а в столбце под знаком каждой логической связки стоят значения функции, задаваемой соответствующейподформулой. Популярное:
|
Последнее изменение этой страницы: 2017-03-08; Просмотров: 2471; Нарушение авторского права страницы