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

Контрольна робота

з дисципліни “інформатика”

на тему:

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

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

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

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

) задається у вигляді таблиці, або графіка зі стандартним розташуванням наборів:

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

x y f(x, y)

0 0 1

0 1 0

1 0 1

1 1 1

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

), підкреслюючи кількість змінних, від яких вона залежить.

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

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

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

. Ці вирази читаються як "не 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".