1 1 0 2. h2(x, y)=S(; xy, yx) задається таблицею: -
x y | xy | yx | 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)), або в інфіксному записі (xy)(yz). Аналогічно функція h2(x, y) задається формулою ((x, y), (y, x)), або (xy)(yx). Як бачимо, обидві функції задаються формулами з тими самими функціональними символами , , , тобто є суперпозиціями цих функцій. Наостанок наведемо узгодження, які склалися в математиці й дозволяють у формулах з функціональними символами , , , , , , |, записувати не всі необхідні дужки. **** Суттєві та несуттєві змінні Розглянемо поняття суттєвої залежності функції від її змінних. Почнемо з прикладів: значення функції 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), не має суттєвих змінних. Еквівалентні формули та закони Одна й та сама бульова функція задається, взагалі кажучи, багатьма різними формулами. Наприклад, неважко переконатися, що формули xy і xy обидві задають функцію (1101). Таким чином, можна говорити про еквівалентність цих двох формул. Означення. Нехай **** Формули 1 і 2 називаються еквівалентними, якщо Бульові функції та комбінаційні схеми І-елемент АБО-елемент -елемент НЕ-елемент a a a b r b r b r a r r = ab r = ab r = ab r = a Розглянемо реалізацію бульових функцій у вигляді комбінаційних схем. Найпростішими з них є логічні елементи, відповідні бульовим функціям: кон'юнкції , диз'юнкції , додавання за модулем 2 та заперечення . Вони позначаються й зображаються таким чином: Входи перших трьох елементів вважаються симетричними згідно законів комутативності, яким задовольняють кон'юнкція, диз'юнкція та додавання за модулем 2. З наведених логічних елементів будуються складніші схеми, які в загальному випадку мають n входів і m виходів і реалізують набір з m функцій від n аргументів: a1 b1 a2 b2 . . . an bm
Тут bj=fj(a1, a2, …, an), j=1, 2, …, m.. Приклади. 1. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує функцію . Виразимо її за допомогою функцій набору {, , }: xy = xyxy. x y Звідси відповідна схема має вигляд: 2. Побудуємо схему з І- та -елементів, яка реалізує функцію . Виразимо її за допомогою функцій набору {, , 1}: xy = xyxy. Звідси відповідна схема має вигляд: x y 3. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує так званий "однорозрядний напівсуматор"[****] з двома симетричними входами x, y і двома виходами: s = xy, d = xy. З цих формул видно, що схема має реалізувати додавання двох однорозрядних чисел із переносом. Виразимо s за допомогою функцій набору {, , }: s = xyxy. Тоді схема має вигляд: x s d y
Список літератури Виленкин Н.Я. Популярная комбинаторика.–М.: Наука, 2000. Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики.–М.: Наука, 1982 Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование.–К.: Наукова думка, 1988. Ершов Ю.Л., Палютин Е.А., Математическая логика.–М.:Наука, 1979. Карри Х.Б. Основания математической логики.–М.: Мир, 1969. Клини С.К. Математическая логика.– М.: Мир, 1973. Колмогоров А.Н. Фомин С.В. Элементы теории функций и функционального анализа.–М.: Наука, 1981. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.–М.:Энергоатомиздат, 1988.
Додати в блог або на сайт
Цей текст може містити помилки. Астрономія | Реферат 75.6кб. | скачати
Схожі роботи: Арифметично-логічні операції Логічні операції над поняттями Визначення і логічні операції над поняттями Поняття як логіко смислова форма мислення Логічні операції з поняттями Поняття як логіко-смислова форма мислення Логічні операції з поняттями Логічні основи ораторського мистецтва Логічні основи теорії аргументації Логічні основи редагування тексту на матеріалі сучасної р Логічні основи редагування тексту на матеріалі сучасної районної преси Удмуртії
|