Лекции.Орг
 

Категории:


Как ухаживать за кактусами в домашних условиях, цветение: Для кого-то, это странное «колючее» растение, к тому же плохо растет в домашних условиях...


Универсальный восьмиосный полувагона: Передний упор отлит в одно целое с ударной розеткой. Концевая балка 2 сварная, коробчатого сечения. Она состоит из...


Архитектурное бюро: Доминантами формообразования служат здесь в равной мере как контекст...

L - клас усіх лінійних перемикальних функцій



Передповними називають класи перемикальних функцiй Р0, Р1, S, M, L, якi зберігають константи 0 і 1, є самодвоїстими, монотонними та лінійними.

Iснують функції, які належать кожному із п’яти класів, наприклад: f(x)=x.

Теорема про функціональну повноту: для того, щоб система пере-микальних функцій була повною, необхідно та достатньо, щоб вона цілком не мiстилася в жодному з п'яти класів T0,T1, S, L, M .

У задачах, де потрібно з'ясувати, чи є повною система перемикальних функцій, складають таблиці Поста, в кожну клітинку яких заносять символ плюс або мінус, залежно від того, чи входить перемикальна функція, що стоїть у вiдповiдному рядку, до класу, що знаходиться у вiдповiдному стовпцi.

Виходячи з теореми про повноту, одержуємо наступне правило: для повноти системи перемикальних функцій, необхідно та достатньо, щоб у кожному стовпці таблицi Поста знаходився хоча б один мінус.

Теорема про подання перемикальних функцiй через диз’юнкцію, кон’юнкцію та заперечення:будь-яка перемикальна функцiя може бути пред-ставлена у вигляді суперпозиції перемикальних функцій із множини {Ú, &, ¯}, де знак “¯” ставиться лише безпосередньо над деякими зi змінних і не ставиться над внутрішніми функціями.

Теорема про функціональну повноту деяких поширених систем перемикальних функцiй: функціонально повними є системи перемикальних функцiй { Ú, &, ¯ }, { Å, &, ¯ }, { Ú, ¯ }, { &, ¯ }, { Þ, ¯ }, { | }; { }.

Теорема про власність і замкненість класів Р0, Р1, S, M і L:класи P0, P1, S, M, L є власними та замкненими класами перемикальних функцiй.

Теорема Поста про функціональну повноту:. система перемикальних функцiй F={f1, f2, …, fk,…} є функціонально повною тоді і тільки тоді, коли в ній існує:

1) хоча б одна функція, що не зберігає константу 0;

2) хоча б одна функція, що не зберігає константу 1;

3) хоча б одна не самодвоїста функцiя;

4) хоча б одна не лінійна функцiя;

5) хоча б одна немонотонна функція.

Наслідок 1 теореми Поста про функціональну повноту: у результаті суперпозиції немонотонної перемикальної функції f(x1,…,xn) iз константами 0 і 1, може бути отримана функція заперечення`xi одного з її аргументів.

Система перемикальних функцiй називається ослаблено функціонально повною, якщо дана система містить у собі константи 0 і 1.

Наслідок 2 теореми Поста про ослаблену функціональну повноту: для того, щоб система перемикальних функцiй була ослаблено функціонально повною, необхідно та достатньо, щоб вона містила хоча б одну нелінійну та одну немонотонну функцію.

Функціонально повну систему перемикальних функцiй називають нескоротною, якщо будь-яка її частина не є функціонально повною.

Будь-яку функціонально повну систему перемикальних функцiй можна привести до нескоротного виду, видаляючи з неї зайві функції.

Наслідок 3 теореми Поста про ослаблену функціональну повноту: максимально можливе число перемикальних функцiй у нескоротній функціонально повній системі перемикальних функцiй дорівнює чотирьом.

Наслідок 4 теореми Поста про функціональну повноту: на практиці, для знаходження функцiонально повних систем перемикальних функцiй, зручно користуватися таблицями, подібними наведеній нижче.

 

Критерієм функціональної повноти буде наявність символу «+» у п’ятьох стовпчиках категорiї «Групи елементів» указаної таблиці.

 

 

Тип елементу Функція Групи елементів
Немоно-тонні Нелінійні Несамо- двоїсті Не збері-гають 0 Не збері-гають 1
Тривіальний x - - - - -
Нулевий 0 - - - - +
Одиничний 1 - - - + -
Інвертор + - - + +
Кон’юнкція хÙy - + + - -
Диз’юнкція хÚy - + + - -
Співпадання з забороною `хÙy º º + + + - +
Розділення з забороною (імплікація) `хÚy º º x®y + + + + -
Співпадiння з подвійною забороною (стрілка Пірса) `хÙ`y º º x¯y + + + + +
Розділення з подвійною забороною (штрих Шефера) `хÚ`y º º x½y + + + + +
Елемент рівнознач-ності хуÚ`х`у º х«у + - + + -
Елемент нерівнознач-ності хÅу + - + - +

 

КОНТРОЛЬНІ ПИТАННЯ

1. Що розуміють під елементарною перемикальною функцією ?

2. Сформулювати поняття логічного елементу.

3. Що являє собою комбінаційна схема ?

4. Чим вирізняється поняття цифрового автомату ?

5. За якою технологією здійснюється побудова тих комбінаційних схем, які реалізують перемикальні функції, задані аналітичними виразами ?

6. Охарактеризувати метод побудови комбінаційних схем, які реалізують перемикальні функції, задані таблицями істинності.

7. Чим вирiзняються функцiонально повнi системи перемикальних функцій ?

8. Яку роль вiдiграє теорема про подання перемикальних функцiй через диз`юнкцiю, кон`юнкцiю та заперечення ?

9. Сформулювати теорему про функцiональну повноту деяких поширених систем перемикальних функцiй

10. Охарактеризувати перемикальнi функцiї, що зберiгають константу 0 (клас P0) i константу 1 (клас P1), самодвоїстi (клас S), монотоннi (клас M) i лiнiйнi (клас L) перемикальнi функції.

11. Пояснити поняття власних i замкнених класiв перемикальних функцiй (класiв Поста).

12. Сформулювати теорему про власнiсть i замкненiсть класiв перемикальних функцiй P0, P1, S, M, i L.

13. Охарактеризувати роль теореми Поста про функiональну повноту та її наслiдкiв.

 





Дата добавления: 2016-11-24; просмотров: 6441 | Нарушение авторских прав


Рекомендуемый контект:


Похожая информация:

  1. Блоки функцій Мінфіну України
  2. Важкість праці: Динамічні, статичні навантаження. Напруженість праці. Увага, напруженість аналізаторних функцій, емоційна та інтелектуальна напруженість, монотонність праці.
  3. Визначення і властивості виробничих функцій
  4. Визначення товщини ізоляційного шару трубопровода у разі нормування лінійних питомих втрат – qL.
  5. Відповідно до методичних рекомендацій у 2016-2017 н.р. Англійська мова: 4 клас, І сем, 2 год.тиж , 16 роб.тиж № / дата Тема уроку Мовленнєві функції Експоненти функцій
  6. Дайте визначення правової системи та її функцій, запропонуйте класифікацію правових систем світу.
  7. Динамічний взаємозв’язок конкретних і загальних функцій
  8. Дослідження систем лінійних рівнянь алгебри
  9. Завдання до виконання практичної роботи. 1. Створіть електронну книгу «Аналіз даних за допомогою функцій» та збережіть її у папці Excel, що знаходиться у вашому каталозі
  10. Знайдіть значення тригонометричних функцій кута ,якщо 1) , .
  11. Класифікація функцій держави


Поиск на сайте:


© 2015-2019 lektsii.org - Контакты - Последнее добавление

Ген: 0.003 с.