WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

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

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

формулами, то 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
Список літератури
1. Виленкин Н.Я. Популярная комбинаторика.-М.: Наука, 2000.
2. Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики.-М.: Наука, 1982
3. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование.-К.: Наукова думка, 1988.
4. Ершов Ю.Л., Палютин Е.А., Математическая логика.-М.:Наука, 1979.
5. Карри Х.Б. Основания математической логики.-М.: Мир, 1969.
6. Клини С.К. Математическая логика.- М.: Мир, 1973.
7. Колмогоров А.Н. Фомин С.В. Элементы теории функций и функционального анализа.-М.: Наука, 1981.
8. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.-М.:Энергоатомиздат, 1988.
Loading...

 
 

Цікаве