У нашій онлайн базі вже 23511 рефератів!

Навігація
Перелік розділів
Найпопулярніше
Нові реферати
Пошук
Замовити реферат
Додати реферат
В вибране
Контакти
Російські реферати
Статьи
Об'яви

Новини
На сайті всього 23511 рефератів!
Ласкаво просимо на UA.TextReferat.com
Реферати, курсові і дипломні українською мовою, які можна скачати цілком або переглядати по сторінкам.

Усе доступно безкоштовно, тому ми не платимо винагороди за додавання. Авторські права на реферати належать їх авторам.

Бульові функції

Бульові функції

1. Алгебри бульових виразів і бульових функцій

7.1.1. Основні поняття

Множину {0, 1} позначимо літерою B. Множину всіх можливих послідовностей з 0 і 1 – Bn. Такі послідовності за традицією будемо називати наборами або векторами довжини n. Очевидно, Bn містить 2n елементів. Значення 0 і 1 називаються протилежними одне до одного.

Означення. Всюди визначена функція з Bn у B називається n-місною функцією алгебри логіки або n-місною бульовою функцією.

Послідовність змінних (x1, x2, …, xn) із значеннями у B позначимо . Бульова функція f() задається у вигляді таблиці, або графіка зі стандартним розташуванням наборів:

x1, x2, …, xn

f(x1, x2, …, xn)

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)

0, 1, …, 1, 1

f(0, 1, …, 1, 1)

1, 0, …, 0, 0

f(1, 0, …, 0, 0)

1, 1, …, 1, 0

f(1, 1, …, 1, 0)

1, 1, …, 1, 1

f(1, 1, …, 1, 1)

Зауважимо, що в стандартному розташуванні набори можна розглядати як двійкові записи послідовних чисел від 0 до 2n-1. Функцію, задану зі стандартним розташуванням наборів, можна ототожнити з набором довжини 2n. Наприклад, двомісну функцію, задану таблицею

x y

f(x, y)

0 0

1

0 1

0

1 0

1

1 1

1

можна ототожнити з вектором (1011).

Далі іноді будемо позначати n-місну функцію f() як f(n)(), підкреслюючи кількість змінних, від яких вона залежить.

Очевидно, що множина всіх можливих наборів довжини 2n, тобто множина n-місних бульових функцій, складається з 22n елементів. При n=0 це 2, при n=1 – 4, при n=2 – 16, при n=3 – 256 тощо.

Нуль-місними функціями є сталі 0 і 1.

Одномісні функції подано у наступній таблиці разом з виразами, якими ці функції позначаються:

x

0

1

x

Øx

0

0

1

0

1

1

0

1

1

0

Функції 0 і 1 називаються тотожними нулем і одиницею, функція x – тотожною, Øx – запереченням. Замість виразу Øx вживається ще вираз . Ці вирази читаються як "не x".

Подамо також деякі з 16 двомісних функцій разом із їх позначеннями:

x y

xÙy

xÚy

x®y

x«y

xÅy

x | y

x¯y

0 0

0

0

1

1

0

1

1

0 1

0

1

1

0

1

1

0

1 0

0

1

0

0

1

1

0

1 1

1

1

1

1

0

0

0

Функція, позначена виразом xÙy, називається кон'юнкцією і позначається ще як x&y, x×y або xy. Усі ці вирази читаються як "x і y".

Функція, позначена виразом xÚy, називається диз'юнкцією. Вираз читається як "x або y".

Функція, позначена виразом x®y, називається імплікацією і позначається ще як xÉy. Ці вирази читаються як "x імплікує y" або "з x випливає y".

Функція, позначена виразом x«y, називається еквівалентністю і позначається ще як x~y або xºy. Ці вирази читаються як "x еквівалентно y", що в даному випадку збігається з "x дорівнює y".

Функція, позначена виразом xÅy, називається додаванням за модулем 2 або "виключним або". Зауважимо, що її значення є протилежними до значень еквівалентності.

Функція, позначена виразом x|y, називається штрихом Шеффера і має значення, протилежні значенням кон'юнкції. Її вираз читається як "не x або не y".

Функція, позначена виразом x¯y, називається стрілкою Пірса і має значення, протилежні значенням диз'юнкції. Її вираз читається як "не x і не y".

Зауважимо, що інфіксні позначення наведених функцій вигляду x f y, де f – відповідний знак, склалися історично. Їх так само можна позначати й у вигляді f(x, y), наприклад, Ù(x, y).

З тримісних функцій наведемо лише так звану функцію голосування m(x, y, z), графік якої має такий вигляд:

x y z

m(x, y, z)

0 0 0

0

0 0 1

0

0 1 0

0

0 1 1

1

1 0 0

0

1 0 1

1

1 1 0

1

1 1 1

1

[1] 2 3 4

завантажити реферат завантажити реферат
Нове
Цікаві новини
Замовлення реферату
Замовлення реферату

Лічильники

Rambler's Top100

Усі права захищено. @ 2005-2017 textreferat.com