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

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

ГоловнаМатематика, Геометрія, Статистика → Бульові функції - Реферат

Бульові функції - Реферат

прикладів: значення функції 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 називаються еквівалентними, якщо
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
3. Замкнені та повні набори функцій. Критерій Поста повноти набору функцій
У підрозділі 7.1 ми побачили, що будь-яку бульову функцію можна задати як суперпозицію функцій з набору { , , } або з набору { , , 1}.
Означення. Множина всіх функцій, що є суперпозиціями функцій деякого набору F, і лише їх, називається замиканням цього набору й позначається [F].
Таким чином, якщо P2 позначає множину всіх бульових функцій, то
{ , , } = [{ , , 1}] = P2.
Означення. Множина функцій F називається функціонально повною, якщо F =P2.
Отже, множини { , , } і { , , 1} є функціонально повними.
Природним є питання про те, які властивості повинні мати функціонально повні множини функцій.
Видатний математик Еміль Пост сформулював і обгрунтував критерій повноти множини функцій у загальному випадку алгебри функцій з операцією суперпозиції. У цьому критерії, тобто необхідній і достатній умові, використовується поняття передповного класу. Розглянемо його.
Нехай F позначає множину всіх можливих функцій деякої алгебри функцій A з операцією суперпозиції.
Означення. Множина функцій S називається передповним класом алгебри A, якщо S F і за будь-якої функції f з множини FS набір S {f} є повним: S {f} =F.
Критерій Поста. Нехай S1, S2, … - усі передповні класи алгебри функцій F. Множина функцій M є повною тоді й тільки тоді, коли для кожного передповного класу Si множина M містить f MSi.
Приймемо це твердження без доведення.
Пост також дослідив передповні класи алгебри бульових функцій. Їх виявилося лише 5. Це множини всіх функцій:
що зберігають сталу 0,
що зберігають сталу 1,
самодвоїстих,
лінійних,
монотонних.
Означимо вказані функції.
Означення. Функція f(n) зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)(0, 0, …, 0)=0.
Означення. Функція f(n) зберігає сталу 1, якщо на одиничному наборі має значення 1: f(n)(1, 1, …, 1)=1.
Наприклад, тотожна функція f(x)=x зберігає сталі 0 і 1, функція f(x)= x не зберігає жодної.
****Двоїста до …
Означення. Функція f(n) є самодвоїстою, якщо для всіх пар протилежних наборів вона приймає на них протилежні значення:
f(n)( 1, 2, …, n) = ****f(n)( 1, 2, …, n) зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)(0, 0, …, 0)=0.
Означення. Функція f(n) зберігає сталу 1, якщо на одиничному наборі має значення 1: f(n)(1, 1, …, 1)=1.
Неважко переконатися, що множини означених функцій, позначені відповідно T0, T1, S, L, M, є замкненими класами.
Список рекомендованої літератури
1. Виленкин Н.Я.Популярная комбинаторика.-М.: Наука, 1975.
2. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.-М.: Наука, 1973.
3. Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики.-М.: Наука, 1982
4. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование.-К.: Наукова думка, 1988.
5. Ершов Ю.Л., Палютин Е.А., Математическая логика.-М.:Наука, 1979.
6. Карри Х.Б. Основания математической логики.-М.: Мир, 1969.
7. Клини С.К. Математическая логика.- М.: Мир, 1973.
8. Колмогоров А.Н. Фомин С.В. Элементы теории функций и функционального анализа.-М.: Наука, 1981.
9. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.-М.:Энергоатомиздат, 1988.
10. Курош А.Г. Лекции по общей алгебре.-М.: Наука, 1973.
11. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.-М.: Наука, 1984.
12. Линдон Р. Заметки по логике.- М.: Мир, 1968.
13. Мендельсон Э. Введение в математическую логику.-М.: Наука, 1984.
14. Новиков П.С. Элементы математической логики.-М.: Наука, 1973.
15. Ставровський А.Б., Коваль Ю.В. Методичні рекомендації та вказівки до курсу "Дискретна математика" (розділ "Множини та відповідності").- К.:"Київський університет", 1994.
16. Трохимчук Р.М. Збірник задач з дискретної математики (розділ "Множини і відношення") для студентів факультету кібернетики.-К.:"Київський університет", 1997.
17. Трохимчук Р.М. Множини і відношення. Навчальний посібник для студентів факультету кібернетики.-К.:"Київський університет", 1993.
18. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.
19. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
Loading...

 
 

Цікаве