КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Булевы функции
Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B = {1, 0}. Функцией алгебры логики (логической функцией) или булевой функцией f(x1,x2,...,xn) называется отображение f: B n® B, определенное на множестве упорядоченных наборов элементов множества B и принимающее значения из этого множества. Обозначим через P n – множество булевых функций n переменных. Логическую функцию n переменных f(x1,x2,...,xn) можно задать таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части – значения функции на этих наборах.
При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2n . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2n, то есть , т.е. || = . Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором значение функции равно 0 (1). Пусть F={} – некоторое множество булевых функций. Его можно выбрать в качестве основного набора, называемого базисом. Формулой над базисом F (обозначается [F]) называется выражение вида [F]=, где F, а либо переменная, либо формула над F. Таким образом, всякая формула является суперпозицией базисных функций, для её представления обычно применяется форма записи с логическими операциями ~. Каждой формуле однозначно соответствует некоторая булева функция f, в этом случае говорят, что формула реализует функцию f (обозначается func F = f). Как будет показано ниже, такая реализация не единственна.
Приведем примеры логических функций одной и двух переменных и их реализаций в виде формул. Логических функций одной переменной четыре: две нуль-местные (j0(х), j3(х)) – константы 0 и 1, значения которых не зависят от значения переменной, и две одноместные функции – тождественная и отрицание.
Тождественная функция "повторяет" значение х: j1(х)=х. Функция отрицание возвращает значение, противоположное значению х: j2(х)=¬х. Логических функций двух переменных шестнадцать:
Рассмотрим подробнее все эти функции. * j0(х1,х2)0 и j15 (х1,х2)1. * j1(х1,х2) = х1 Ù х2 . Эта функция называется ещё логическим умножением и обозначается, также, х1х2. * j2(х1.х2) = Ø (х1®х2). * j3(х1,х2) = х1. * j4(х1.х2) = Ø (х2®х1). * j5(х1,х2) = х2. * j6(х1,х2) = (х1~х2) называются неравнозначностью, разделительной дизъюнкцией или сложением по модулю 2 и обозначается еще как х1Å х2. * j7(х1.х2) = х1Ú х2 . * j8(х1.х2) = (х1Úх2) – антидизъюнкция, которая называется, также, стрелка Пирса и обозначается х1¯х2. * j9(х1.х2) = х1~х2. Эту функцию называют еще равнозначностью и обозначают х1ºх2 . * j10(х1.х2) = . * j11(х1.х2) = х2®х1. * j12(х1.х2) = . * j13(х1.х2) = х1®х2. * j14(х1.х2) = (х1Ùх2) – антиконъюнкция, которая называется еще штрих Шеффера и обозначается х1 | х2. Формулы, реализующие одну и ту же функцию, называются равносильными. Отношение равносильности формул является отношением эквивалентности и обозначается º.
Фиктивной переменной (несущественной) функции f (x 1,..., x n) называется переменная хi, изменение значения которой не меняет значения функции, то есть f (x 1,..., х i-1, 1, x i+1,..., x n) = f (x 1,..., х i-1, 0, x i+1,..., x n). Например, в функциях j3 и j12 переменная х2 фиктивна, а в функциях j5 и j10 фиктивна переменная х 1. Функция f (x 1,..., x n), имеющая фиктивную переменную x i, по существу зависит от (n– 1)-й переменной, т.е. представляет собой функцию g (x 1,..., х i-1, x i+1,..., x n). В этом случае говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной, причём эти функции считаются равными. Пусть f (x 1, ¼, x n) Î P n – булева функция. Тогда функция f *(x 1, ¼, x n), определенная следующим образом f *(x 1, ¼, x n) = , называется двойственной к функции f. Теорема (Принцип двойственности). Пусть F={}. Тогда, если формула [F] реализует функцию f, то формула * над базисом F*={}, полученная из формулы заменой функций fi на двойственные им функции fi *, реализуют функцию f *.
Дата добавления: 2014-01-11; Просмотров: 329; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |