Доведення

Запишемо таблицю істинності для функції стрілки Пірса:

З таблиці видно, що функція не зберігає 0 (на нульовому кортежі функція дорівнює 1) і не зберігає 1 (на одиничному кортежі функція дорівнює 0), тобто функція, " стрілка Пірса", не належить класам функцій які зберігають 0 та 1.

Також з таблиці видно, що функція не монотонна. Це пов'язано з тим, що на кортежах і , які знаходяться у відношенні передування, не виконується рівність . Тобто функція не належить класу монотонних функцій.

Для визначення належності до класу самодвоїстих функцій побудуємо таблицю істинності для двоїстої функції до стрілки Пірса.

Через те, що значення функції " стрілка Пірса" та двоїстої до неї не співпадають на однакових кортежах, то ця функція не належить класу самодвоїстих функцій.

Для перевірки лінійності функції побудуємо її канонічний поліном Жегалкіна із використанням властивостей: та .

Отриманий канонічний поліном містить нелінійні члени ( ). Отже, функція стрілка Пірса не є лінійною.

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

Введення еквівалентності

Стрілка Пірса має цікаву особливість, а саме - всі інші логічні функції можуть бути виражені через її суперпозиції. Таку ж властивість має і штрих Шефера.

Стрілка Пірса є заперечення диз'юнкції:

Вираження через стрілку Пірса інших логічних функцій:

Мінімізація функцій в базисі стрілки Пірса

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

Узагальнюючи для n змінних, будемо мати:

Дані співвідношення дозволяють звести задачу мінімізації логічних функцій в вищезгаданих базисах до задачі мінімізації ДНФ та КНФ. Дійсно, для випадку функції " стрілка Пірса" можна показати, що справедливе таке твердження.

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

Отже, КНФ функції можна подати в такому вигляді:

де — елементарні диз'юнкції:

Використовуючи наведені співвідношення будемо мати:

Твердження доведено. Таким чином, мінімізацію функції можна відтворити в базисі І, АБО, НЕ, а потім перейти до стрілки Пірса. Операція заперечення реалізується за допомогою стрілки Пірса:

Оскільки функція стрілка Пірса не підпорядковується закону асоціативності, то це треба враховувати при переході від багатомісних операцій до двомісних. Такий перехід можна зробити за допомогою таких співвідношень:

спрсправедливість яких легко перевіряється.

Приклад [ред. • ред. код]

Розглянемо функцію, яка має таку мінімальну КНФ (одна з можливих):

Переходимо до операції «стрілка Пірса»:

Перехід до двомісних операцій дає можливість обрати кінцевий вираз:

Схеми

Говорячи простою мовою, вентиль NOR, це АБО з підключеним до нього інвертором. Для наочності, нижче наведений приклад логіки NOR з вимикачами. Як відомо логіка АБО близька до виразу " Або A, Або B, Або те й інше", щоб отримати логіку NOR, результат АБО необхідно інвертувати, щоб отримати " Не A, і не B". На схемі нижче це виглядає наступним чином: Сірим відзначені вимикачі в стані " вимкнено", синім в стані " ввімкнено". На першій зліва схемі, обидва вимикачі знаходяться в положенні " вимкнено", таким чином, слідуючи вислову на виході отримуємо логічний 0. Інвертований результат буде дорівнює 1, і тим самим логічно задовольняти висловом " Не А, Не B". Наступні схеми демонструють відповідно " АБО А", " АБО B", " І А, І B" з наступною інверсією результату.

Наглядныесхемы ИЛИ-НЕ на выключателях(нажмите для просмотра)

Нижче представлені варіанти реалізації вентиля NOR за допомогою діод-транзисторної логіки, і за допомогою МОН відповідно.

Схеми

Представлена схема на МОП виконана на однотипних МОП-транзисторах однак існує варіант схеми NOR на доповнюючихМОП-тразісторах. Таку схему отримують шляхом послідовного з'єднання однотипних транзисторів і паралельного з'єднання групи транзисторів іншого типу.

⇐ Предыдущая 1 2 34