Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Астрономия->Реферат
Людина завжди прагнула відшукати причину всіх явищ, що при­вертали до себе її увагу. Головним серед них була смерть. У тих випадках, коли причина смер...полностью>>
Астрономия->Реферат
Наділена від народження відповідними біологічними якостями (тобто нормальним людським організмом, включаючи мозок, що здатний до подальшого розвитку),...полностью>>
Астрономия->Реферат
Український письменник і композитор, музично-культурний діяч і православний священик на Буковині, педагог і редактор часописів Буковини, художник – та...полностью>>
Астрономия->Реферат
Важливою складовою частиною поведінки людини є рольова поведінка. Соціалізована особистість завжди є носієм певного арсеналу психологічних ролей: проф...полностью>>

Главная > Реферат >Астрономия

Сохрани ссылку в одной из сетей:

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

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

на тему:

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

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

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

xy

xy

xy

xy

xy

x | y

xy

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. H2(x, y, z)=S(; xy, yz) задається наступною таблицею:

x y z

xy

yz

H2(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. H3(x, y)=S(; xy, yx) задається таблицею:

x y

xy

yx

H3(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 видно, що функція H2(x, y, z) задається формулою ((x, y), (y, z)), або в інфіксному записі (xy)(yz). Аналогічно функція H3(x, y) задається формулою ((x, y), (y, x)), або (xy)(yx). Як бачимо, обидві функції задаються формулами з тими самими функціональними символами , , , тобто є суперпозиціями цих функцій.

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

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

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

Означення. Змінна 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).

Наприклад, неважко переконатися, що всі змінні функції H2 з прикладу 1 є суттєвими. Функція H3 має суттєву змінну 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



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

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

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

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

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

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

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

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

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


Загрузить файл

Похожие страницы:

  1. Основи інформатики. Теорії інформаційних систем та обчислювальної техніки

    Конспект >> Информатика, программирование
    ... у двійковій - 60, у трійковій - 57. Але трійкова система ... натуральних чисел записаних в десятковій, двійковій, вісімковій та шістнадцятков ... числення з основою p в систему числення з основою q, використовуючи арифметику нової системи числення з основою q, ...
  2. Теоретичні основи інформатики та комп ютерної техніки

    Реферат >> Информатика
    ... із системи числення з основою p в систему числення з основою q, використовуючи арифметику нової системи числення з основою q, потрібно ... що її арифметика для нас звичніша. Приклади переведення чисел у двійкову, вісімкову та ...
  3. Перетворення кодів з однієї системи числення в іншу

    Реферат >> Коммуникации и связь
    ... Алфавіт Множина цифр алфавіту Основа двійковий вісімковий десятковий шістнадцятковий * * – символи, як ... десяткова арифметика. Нижче проілюстрований порядок перекодування чисел з десяткової системи числення в двійкову ...
  4. Системи числення (2)

    Курсовая работа >> Информатика, программирование
    ... з десяткової системи числення в двійкову, основа якої дорівнює 2, ... – основа двійкової системи числення, дорівнює 2). 3. Виконати розрахунок за правилами десяткової арифметики. ... Приклад, нехай нам потрібно перевести число 1000111.001 з двійково ...
  5. Реалізація ідеї арифметичного кодування

    Реферат >> Астрономия
    ... отримання інформації. 4.2 Бажане використання цілочисленої арифметики. 4.3 Ефективна реалізація моделі. 5. ... . (Тут застосовуємо логариф з основою 10, бо вищенаведене кодування виконувалося ... ми працюємо з двійковою арифметикою, передаємо двійкові числа та вимі ...

Хочу больше похожих работ...

Generated in 0.0030801296234131