Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Основи двійкової арифметики. Порозрядні логічні операції (Булівські операції)

Основи двійкової арифметики. Порозрядні логічні операції (Булівські операції)

Назва:
Основи двійкової арифметики. Порозрядні логічні операції (Булівські операції)
Тип:
Реферат
Мова:
Українська
Розмiр:
20,58 KB
Завантажень:
33
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3 
Основні поняття

Множину {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

Її назва зумовлена тим, що її значення на кожному наборі збігається з більшістю значень змінних у цьому наборі.

Множину всіх n-місних функцій позначимо P(n), а множину всіх функцій, тобто об'єднання P(n) по всіх n – P2.

Перейдемо до означення таких понять, як алгебра бульових функцій і алгебра формул.

Алгебри бульових функцій, як і всі інші алгебри, визначаються своїми носіями та сигнатурами операцій. Носіями в алгебрах бульових функцій є множини функцій. Сигнатуру складає операція суперпозиції, або підстановки.

Означення. Нехай є n-місна функція f(n)( ) і n функцій g1(y1,1, y1,2, …, y1,m1), g2(y2,1, y2,2, …, y2,m2), …, gn(yn,1, yn,2, …, yn,mn), залежні від змінних з деякої їх множини Y={y1, y2, …, yk}. Суперпозицією, або підстановкою функцій g1, g2, …, gn у функцію f(n) називається функція h(m)(y1, y2, …, ym), кожне значення якої h(1, 2, …, m) визначається як

f(n)(g1(1,1, 1,2, …, 1,m1), g2(2,1, 2,2, …, 2,m2), …, gn(n,1, n,2, …, n,mn)).

Суперпозиція ще позначається як

S(f(n); g1(y1,1, y1,2, …, y1,m1), g2(y2,1, y2,2, …, y2,m2), …, gn(yn,1, yn,2, …, yn,mn)).

Приклади.

1. h1(x, y, z)=S(; xy, yz) задається наступною таблицею:

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3 



Реферат на тему: Основи двійкової арифметики. Порозрядні логічні операції (Булівські операції)

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок