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

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

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

з дисципліни «інформатика».

на тему:

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

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

Множину {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) задається наступною таблицею:

x y z.

x (y.

y (z.

h1(x, y, z).

0 0 0.

0.

1.

0.

0 0 1.

0.

1.

0.

0 1 0.

1.

0.

0.

0 1 1.

1.

1.

1.

1 0 0.

1.

1.

1.

1 0 1.

1.

1.

1.

1 1 0.

1.

0.

0.

1 1 1.

1.

1.

1.

2. h2(x, y)=S ((, x (y, y (x) задається таблицею:

x y.

x (y.

y (x.

h2(x, y).

0 0.

0.

1.

0.

0 1.

1.

0.

0.

1 0.

1.

1.

1.

1 1.

1.

1.

1.

Нехай є множина бульових функцій F. Утворюючи з них та їх суперпозицій усі можливі суперпозиції, ми одержимо множину функцій, яку позначимо [F]. Отже, маємо алгебру ([F], S), породжену множиною функцій F. Інша множина функцій F1 буде породжувати, взагалі кажучи, іншу алгебру ([F1], S). Наприклад, алгебри (({(0111), (0001)}(, S) і (({(10), (0001)}(, S).

Розглянемо тепер поняття алгебри формул (термів, або виразів). Нехай є множина функцій F. Кожній n-місній функції з F поставимо у взаємно однозначну відповідність символ, що її позначає (функціональний символ) f (n). Нехай X — зліченна множина змінних (точніше, їх імен).

Означення.

1. Ім" я змінної є формулою.

2. Якщо f (n) — функціональний символ, а T1, T2, …, Tn є формулами, то f (n)(T1, T2, …, Tn) є формулою.

3. Інших формул немає.

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

Зв" язки між алгебрами функцій і алгебрами формул встановлюють наступні два означення.

Означення. Значенням формули T на наборі значень змінних з множини X є:

1) значення змінної x, якщо T є змінною x,.

2) f (n)((1, (2, …, (n), якщо T=f (n)(T1, T2, …, Tn), а формули T1, T2, …, Tn мають на цьому наборі значення відповідно (1, (2, …, (n.

Означення. n-місна бульова функція f (n) задається формулою T, якщо всі змінні у формулі T є змінними з множини X, і при будь-якому наборі значень ((1, (2, …, (n) цих змінних x1, x2, …, xn значення формули дорівнює значенню f (n)((1, (2, …, (n).

Звідси випливає інше означення суперпозиції функцій.

Означення. n-місна бульова функція f (n) є суперпозицією функцій f1, f2, …, fn, якщо її можна задати формулою, усі функціональні символи якої є серед символів функцій f1, f2, …, fn.

З наведених прикладів 1 і 2 видно, що функція h1(x, y, z) задається формулою ((((x, y), ((y, z)), або в інфіксному записі (x (y)((y (z). Аналогічно функція h2(x, y) задається формулою ((((x, y), ((y, x)), або (x (y)((y (x). Як бачимо, обидві функції задаються формулами з тими самими функціональними символами (, (, (, тобто є суперпозиціями цих функцій.

Наостанок наведемо узгодження, які склалися в математиці й дозволяють у формулах з функціональними символами (, (, (, (, (, (, |, (записувати не всі необхідні дужки. ****.

Суттєві та несуттєві змінні.

Розглянемо поняття суттєвої залежності функції від її змінних. Почнемо з прикладів: значення функції h2(x, y) з прикладу 2 на кожному з наборів збігаються зі значеннями x. Отже, зміна значення y не впливає на значення функції, тобто вона фактично не залежить від y. В той час як зміна значення x веде до зміни значення h2. Уточнимо ці міркування наступними означеннями.

Означення. Змінна xi функції f (n)(x1, x2, …, xi, …, xn) називається суттєвою, якщо існує хоча б одна пара наборів значень змінних.

((1, (2, …, (i-1, 0, (i+1, …, (n) і ((1, (2, …, (i-1, 1, (i+1, …, (n),.

така, що.

f (n)((1, (2, …, (i-1, 0, (i+1, …, (n) (f (n)((1, (2, …, (i-1, 1, (i+1, …, (n).

Змінна xi називається несуттєвою у противному разі, тобто коли за всіх можливих пар наборів значень.

((1, (2, …, (i-1, 0, (i+1, …, (n) і ((1, (2, …, (i-1, 1, (i+1, …, (n).

мають місце рівності:

f (n)((1, (2, …, (i-1, 0, (i+1, …, (n) = f (n)((1, (2, …, (i-1, 1, (i+1, …, (n).

Наприклад, неважко переконатися, що всі змінні функції h1 з прикладу 1 є суттєвими. Функція h2 має суттєву змінну x і несуттєву y. Функція двох змінних, задана як вектор (1111), не має суттєвих змінних.

Еквівалентні формули та закони.

Одна й та сама бульова функція задається, взагалі кажучи, багатьма різними формулами. Наприклад, неважко переконатися, що формули x (y і (x (y обидві задають функцію (1101). Таким чином, можна говорити про еквівалентність цих двох формул.

Означення. Нехай **** Формули (1 і (2 називаються еквівалентними, якщо.

Бульові функції та комбінаційні схеми.

І-елемент АБО-елемент (-елемент НЕ-елемент.

a a a.

b r b r b r a r.

r = a (b r = a (b r = a (b r = (a.

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

Входи перших трьох елементів вважаються симетричними згідно законів комутативності, яким задовольняють кон" юнкція, диз" юнкція та додавання за модулем 2.

З наведених логічних елементів будуються складніші схеми, які в загальному випадку мають n входів і m виходів і реалізують набір з m функцій від n аргументів:

a1 b1.

a2 b2.

.

.

.

an bm.

Тут bj=fj (a1, a2, …, an), j=1, 2, …, m.

Приклади.

1. Побудуємо схему з І-, АБОта НЕ-елементів, яка реалізує функцію (. Виразимо її за допомогою функцій набору {(, (, (}:

x (y = x ((y ((x (y.

x.

y.

Звідси відповідна схема має вигляд:

2. Побудуємо схему з Іта (-елементів, яка реалізує функцію (. Виразимо її за допомогою функцій набору {(, (, 1}:

x (y = x (y (x (y.

Звідси відповідна схема має вигляд:

x.

y.

3. Побудуємо схему з І-, АБОта НЕ-елементів, яка реалізує так званий «однорозрядний напівсуматор» [****] з двома симетричними входами x, y і двома виходами: s = x (y, d = x (y. З цих формул видно, що схема має реалізувати додавання двох однорозрядних чисел із переносом. Виразимо s за допомогою функцій набору {(, (, (}: s = x ((y ((x (y. Тоді схема має вигляд:

x s.

d.

y.

Список літератури.

Виленкин Н. Я. Популярная комбинаторика.-М.: Наука, 2000.

Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики.-М.: Наука, 1982.

Глушков В.М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки. Программирование.-К.: Наукова думка, 1988.

Ершов Ю.Л., Палютин Е. А., Математическая логика.-М.:Наука, 1979.

Карри Х. Б. Основания математической логики.-М.: Мир, 1969.

Клини С. К. Математическая логика.- М.: Мир, 1973.

Колмогоров А. Н. Фомин С.В. Элементы теории функций и функционального анализа.-М.: Наука, 1981.

Кузнецов О.П., Адельсон-Вельский Г. М. Дискретная математика для инженера.-М.:Энергоатомиздат, 1988.