Студопедия

КАТЕГОРИИ:


Архитектура-(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 наборов значений переменных, а в правой части – значения функции на этих наборах.

 

x1 x2 ... хn-1 xn f(x1, x2 ,... хn-1 , xn)
0 0... 0 0 0 0... 0 1 0 0... 1 0 ................ 1 1... 1 0 1 1... 1 1 f(0,0,...,0,0) f(0,0,...,0,1) f(0,0,...,1,0) ........ f(1,1,...,1,0) f(1,1,...,1,1)

 

При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2n . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2n, то есть , т.е. || = .

Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором значение функции равно 0 (1).

Пусть F={} – некоторое множество булевых функций. Его можно выбрать в качестве основного набора, называемого базисом. Формулой над базисом F (обозначается [F]) называется выражение вида [F]=, где F, а либо переменная, либо формула над F. Таким образом, всякая формула является суперпозицией базисных функций, для её представления обычно применяется форма записи с логическими операциями ~. Каждой формуле однозначно соответствует некоторая булева функция f, в этом случае говорят, что формула реализует функцию f (обозначается func F = f). Как будет показано ниже, такая реализация не единственна.

Приведем примеры логических функций одной и двух переменных и их реализаций в виде формул.

Логических функций одной переменной четыре: две нуль-местные (j0(х), j3(х)) – константы 0 и 1, значения которых не зависят от значения переменной, и две одноместные функции – тождественная и отрицание.

 

x j0 j1 j2 j3
         
         

Тождественная функция "повторяет" значение х: j1(х)=х. Функция отрицание возвращает значение, противоположное значению х: j2(х)=¬х.

Логических функций двух переменных шестнадцать:

х1 x2 j0 j1 j2 j3 j4 j5 j6 j7 j8 j9 j10 j11 j12 j13 j14 j15
                                   
                                   
                                   
                                   

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

* j012)0 и j15 12)1.

* j112) = х1 Ù х2 . Эта функция называется ещё логическим умножением и обозначается, также, х1х2.

* j212) = Ø (х1®х2).

* j312) = х1.

* j412) = Ø (х2®х1).

* j512) = х2.

* j612) = 12) называются неравнозначностью, разделительной дизъюнкцией или сложением по модулю 2 и обозначается еще как х1Å х2.

* j712) = х1Ú х2 .

* j812) = 1Úх2) – антидизъюнкция, которая называется, также, стрелка Пирса и обозначается х1¯х2.

* j912) = х12. Эту функцию называют еще равнозначностью и обозначают х1ºх2 .

* j1012) = .

* j1112) = х2®х1.

* j1212) = .

* j1312) = х1®х2.

* j1412) = 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; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.022 сек.