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

Контрольна робота з дисципліни “інформатика” на тему: Основи двійкової арифметики. Порозрядні логічні операції (Булівські операції) Основні поняття
Множину {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
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
1
x
x
1
1
1
1
1
Функції і 1називаються тотожними нулемі одиницею, функція x – тотожною, x – запереченням. Замість виразу x вживається ще вираз />. Ці вирази читаються як «не x».
Подамо також деякі з 16 двомісних функцій разом із їх позначеннями:
x y
xy
xy
xy
xy
xy
x | y
xy
0 0
1
1
1
1
0 1
1
1
1
1
1 0
1
1
1
1 1–PAGE_BREAK—-PAGE_BREAK–
1
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
1
0 1
1
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).    продолжение
–PAGE_BREAK–
Змінна 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 аргументів:

/>

a/>/>1b1
a/>/>2b2
.
.
.
a/>/>nbm

Тут 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.