Понятие булевой функции

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

2015-08-11

10.8 KB

2 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


Понятие булевой функции

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

Определение 1 (Булева функция). Булевой функцией от n аргументов называется функция f из n-ой степени множества { 0, 1 } в множество { 0, 1 }.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B.

Булеву функцию от n аргументов можно рассматривать как n-местную алгебраическую операцию на множестве B. При этом алгебра <B;W>, где W – множество всевозможных булевых функций, называется алгеброй логики.

Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2n наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:

x1

x2

...

xn-1

xn

f

0

0

...

0

0

f(0,0,...,0,0)

0

0

...

0

1

f(0,0,...,0,1)

0

0

...

1

0

f(0,0,...,1,0)

0

0

...

1

1

f(0,0,...,1,1)

...

...

...

...

...

...

1

1

...

0

0

f(1,1,...,0,0)

1

1

...

0

1

f(1,1,...,0,1)

1

1

...

1

0

f(1,1,...,1,0)

1

1

...

1

1

f(1,1,...,1,1)

Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значения f(0,0,...,0,0), f(0,0,...,0,1), f(0,0,...,1,0), f(0,0,...,1,1),...,f(1,1,...,0,0), f(1,1,...,0,1), f(1,1,...,1,0), f(1,1,...,1,1). Этот набор называют вектором значений функции.

Таким образом, различных функций n переменных столько, сколько различных двоичных наборов длины 2n*. А их 2 в степени 2n.

Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1.

Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция, т.е. функция, значение которой совпадает с аргументом и так называемая функция ``отрицание''. Отрицание будем обозначать символом ¬ как унарную операцию. Приведём таблицы этих четырёх функций:

x

0

x

¬ x

1

0

0

0

1

1

1

0

1

0

1

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

Определение 2 (Фиктивные и существенные переменные). Переменная xi называется фиктивной (несущественной) переменной функции f(x1,···,xn), если

f(x1,···,xi-1,0,xi+1,···,xn) = f(x1,···,xi-1,1,xi+1,···,xn)

для любых значений x1,···,xi-1,xi+1,···,xn. Иначе переменная xi называется существенной.

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

x1

x2

x1 & x2

x1 Ъ x2

x1 Йx2

x1 Е x2

x1 є x2

x1 | x2

0

0

0

0

1

0

1

0

0

1

0

1

1

1

0

1

1

0

0

1

0

1

0

1

1

1

1

1

1

0

1

1

Эти функции записываются как бинарные операции в инфиксной нотации. x1 & x2 называется конъюнкциейx1 Ъ x2 – дизъюнкциейx1 Й x2 – импликациейx1 є x2 – эквивалентностьюx x2 – суммой по модулю 2x1 | x2 – штрихом Шеффера.

Значения 0 и 1 часто интерпретируют как ``ложь'' и ``истину''. Тогда понятным становится название функции ``отрицание'' – она меняет ``ложь'' на ``истину'', а ``истину'' на ``ложь''. Отрицание читается как ``не''. Конъюнкция читается обычно как ``и'' – действительно, конъюнкция равна 1 тогда и только тогда, когда равны 1 и первая и вторая переменная.* Кроме x1& x2 часто используют обозначение x1 Щ x2 или x1 · x2 или x1x2 или min(x1,x2). Дизъюнкция читается ``или'' – дизъюнкция равна 1 тогда и только тогда, когда равны 1 первая или вторая переменная.* Импликация выражает факт, что из x1 следует x2.* Импликацию часто также обозначают x1 ® x2.



 

Другие похожие работы, которые могут вас заинтересовать.
15898. Юридическая ответственность: понятие, цели, функции и принципы 38 KB
  Понятие юридической ответственности сложно и многогранно, оно позволит раскрыть природу и назначение юридической ответственности как правового института, который имеет присущие специфические признаки, функции, основания и виды.
7478. Введение в делопроизводство. Понятие делопроизводства, основные функции и процессы 12.68 KB
  Цель дисциплины основы делопроизводство: получение необходимых знаний и навыков для правильного составления и оформления документов возникающих в процессе принятия и реализации управленческих решений; освоение общепринятых в мире предпринимательства лексики и стиля деловой и коммерческой корреспонденции для свободного общения с деловыми партнером. Основные задачи дисциплины: ознакомить с общими принципами документационного обеспечения деятельности предприятия с порядком документирования информации; научить систематизировать...
19970. Понятие рынка. Основные условия его функционирования. Функции маркетинга и их характеристика 25.38 KB
  Рынок – одна из самых распространенных категорий в экономической теории и хозяйственной практике. Данная категория имеет множество различных толкований и у нас, и за рубежом. В это понятие включают и договор купли-продажи; и совокупность деловых операций, осуществляемых в определенной сфере экономики или в определенном месте, и состояние и развитие спроса и предложения в конкретной сфере экономики (например говорят о снижении цен на рынке металла или о дефиците на рынке труда)
3067. Деньги и их функции. Денежные агрегаты. Понятие и типы денежных систем 4.49 KB
  Первоначально в качестве денег обращались товарные деньги раковины какаобобы пушнина ювелирные украшения золото и серебро. Позднее в обращении появились символические деньги затраты на производство которых значительно уступали их покупательной способности в качестве денег бумажные деньги разменные монеты. В дальнейшем возникли кредитные деньги представлявшие собой обязательства вначале физических лиц фирм а затем и банков. Первые бумажные деньги появились в Китае еще в XII в.
14810. Криминологическая наука. Понятие, предмет , задачи и функции криминологии. История криминологической науки 8.47 KB
  Понятие предмет задачи и функции криминологии. Общая характеристика криминологии. Цели задачи функции криминологии и их реализация. Место криминологии в системе научного знания.
13362. Основные направления деятельности (функции) прокуратуры. Понятие и виды (отрасли) прокурорского надзора 4.73 KB
  В этом принципиальное отличие прокурорского надзора от иных видов осуществляемого государственными органами надзора и контроля административного экологического санитарного и т. Вовторых несмотря на то что прокуратура осуществляет надзор за соблюдением Конституции РФ и законов подавляющим большинством должностных лиц и государственных органов при определенных обстоятельствах руководителями и органами управления коммерческих и некоммерческих организаций а также гражданами она не уполномочена надзирать за высшими органами законодательной...
6690. Понятие и функции лизинга. Преимущества лизинга 122.98 KB
  Относительно экономической сущности лизинга пока еще нет единого мнения экономистов. Одни рассматривают лизинг как своеобразный способ кредитования предпринимательской деятельности, другие полностью отождествляют его с долгосрочной арендой
10899. Понятие и предмет гражданского права. Метод гражданско-правового регулирования. Принципы и функции гражданского права 28.68 KB
  Принципы и функции гражданского права. Понятие частного права. Гражданское право как отрасль права как наука как учебная дисциплина.
5751. Дезертирство. Понятие самовольного оставления части или места службы военнослужащих, проходящих военную службу. Понятие и состав статьи 338 Уголовного Кодекса «Дезертирство» 59.8 KB
  Понятие воинской обязанности и социально-экономические мотивы уклонения от воинской службы Понятие и состав уклонение от исполнения обязанностей военной службы путем симуляции болезни или иными способами. Понятие самовольного оставления части или места службы военнослужащих проходящих военную службу...
7295. ПОНЯТИЕ, ЗАДАЧИ И СИСТЕМА КРИМИНОЛОГИИ. ПОНЯТИЕ, ПРИЗНАКИ И ПРИЧИНЫ ПРЕСТУПНОСТИ. ПРЕДУПРЕЖДЕНИЕ ПРЕСТУПНОСТИ 18.67 KB
  Основные вопросы криминологической науки Современные научные направления в криминологии семейная криминология; экономическая криминология; пенитенциарная криминология; политическая криминология. Криминология и социальная профилактика...
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.