Сделай Сам Свою Работу на 5

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





Булевы векторы и единичный n-мерный куб

Множество называется единичным n-мерным кубом. Упорядоченная последовательность (кортеж) длины n называется вершиной единичного n-мерного куба. Мощность множества вершин единичного n-мерного куба равна .

На множестве вершин единичного n-мерного куба задаются следующие характеристики:

· Вес вектора, равный ;

· Номер вектора, равный десятичному числу, записанному в двоичной системе счисления: если разряды двоичного вектора нумеруются справа налево, начиная с 0, т.е. .

· Расстояние Хемминга между двумя булевыми векторами, равное числу разрядов, в которых эти векторы различаются, определяемое как . Два вектора называются соседними, если расстояние Хемминга между ними равно 1, и противоположными, если расстояние Хемминга между ними равно n.

· На множестве булевых векторов длины n определено отношение предшествования: . Нетрудно доказать, что отношение предшествования является отношением частичного порядка на множестве вершин единичного n-мерного куба.

Функции алгебры логики (булевы функции)

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



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

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



Двойственные функции

Функция , определенная как отрицание функции от отрицания ее аргументов называется двойственной функции : . Согласно определению таблица двойственной функции получается инвертированием столбца функции и последующим переворачиванием ее. Например,

.

Соответствующие таблицы представлены ниже.

x1 x2 x1®x2

Примеры элементарных двойственных функций:

f Двойственна
x x
& Ú
Ú &

Очевидно выполнение тождественного равенства

.

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

Элементарными булевыми функциями называются функции с арностью 0, 1 и 2. При этом нужно заметить, что множество функций двух переменных включают в себя все 0-местные и 1-местные функции, в описании которых присутствует две или одна фиктивная переменная соответственно. Множество всех элементарных булевых функций может быть представлено в виде таблицы, содержащей 4 строки и 16 столбцов. Каждый столбец определяет одну из элементарных булевых функций. Наиболее употребимыми являются двуместные функции: {&,Ú,®,«,Å,ê,¯}, одноместные функции f(x)=x и f(x)=`x, и две 0-местные функции: константа 0 и константа 1, не имеющие ни одной существенной переменной (других таких функций в множестве элементарных булевых функций нет).



Элементарные булевы функции используются для аналитического задания булевых функций произвольной местности формулами. При этом используется принцип суперпозиции функций. Согласно этому принципу формула определяется индуктивно:

· Пропозициональная переменная есть формула.

· Если А и В формулы, то любое слово А·В – формула, если ·Î{&,Ú,®,«,Å,ê,¯}. Слово `А также является формулой.

· Других формул нет.

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

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

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.