Стрілка Пірса

NOR
Визначення	${\displaystyle {\overline {a+b}}}$
Таблиця істинності	${\displaystyle (0001)}$
Логічний вентиль
Нормальні форми
Диз'юнктивна	${\displaystyle {\overline {a}}\cdot {\overline {b}}}$
Кон'юнктивна	${\displaystyle {\overline {a}}\cdot {\overline {b}}}$
Алгебрична	${\displaystyle 1\oplus a\oplus b\oplus ab}$
Ґратка Поста
${\displaystyle P_{0}}$ (зберігає 0)	✗
${\displaystyle P_{1}}$ (зберігає 1)	✗
${\displaystyle M}$ (монотонна)	✗
${\displaystyle L}$ (лінійна)	✗
${\displaystyle S}$ (самодвоїста)	✗

Стрі́лка Пі́рса також відома як оператор NOR (англ. logical nor, joint denial)  — була введена Чарлзом Сандерсом Пірсом (Charles Sanders Peirce) у 1880—1881 р.р.. Математики Ч. Пірс та Д. Вебб, які незалежно один від одного вивчали властивості цієї функції, створили алгебру, названу алгеброю Пірса-Вебба. Для її позначення використовують символ ${\displaystyle ~\downarrow }$. Це двомісна логічна операція, яка є запереченням диз'юнкції; тому значення «істинно» одержується тільки тоді, коли обидва операнди мають значення «хибно». За допомогою стрілки Пірса (операції NOR) можна виразити будь-яку двомісну логічну операцію. Таким чином «стрілка Пірса» може бути використана сама по собі, без будь-яких інших логічних функцій, в складі логічної формальної системи (що робить цю функцію функціонально повною).

Комп'ютер, який був використаний для космічного корабля Аполлон, котрий вперше доправив людину на Місяць, був побудований повністю за допомогою мікросхем, кожна з яких об'єднувала два трьохвхідних виключних або (NOR).

${\displaystyle A\downarrow B\equiv \lnot (A\lor B)\equiv {\overline {A\lor B}}\ }$

Стрілка Пірса — це двомісна логічна операція, яка є запереченням диз'юнкції; тому значення «істинно» одержується тільки тоді, коли обидва операнди мають значення «хибно». Іншими словами, функція приймає хибне значення, якщо хоча б один із аргументів істинний.

Таблиця істинності виглядає таким чином:

• комутативність

${\displaystyle ~a\downarrow b\equiv b\downarrow a}$

• тотожності:

${\displaystyle \bot \equiv (a\downarrow a)\downarrow a}$

${\displaystyle ~a\equiv (a\downarrow a)\downarrow (a\downarrow b)}$

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

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

Також з таблиці видно, що функція не монотонна. Це пов'язано з тим, що на кортежах ${\displaystyle \alpha =(0,0)}$ і ${\displaystyle \beta =(0,1)}$, які знаходяться у відношенні передування, не виконується рівність ${\displaystyle f(\alpha )\leq f(\beta )}$. Тобто функція не належить класу монотонних функцій.

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

${\displaystyle \lnot (\lnot (A)\downarrow \lnot (B))\equiv \lnot (\lnot (A)\lor \lnot (B))\equiv {\overline {{\overline {A}}\lor {\overline {B}}}}}$

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

Для перевірки лінійності функції побудуємо її канонічний поліном Жегалкіна із використанням властивостей: ${\displaystyle x\lor y\equiv x\wedge y\oplus x\oplus y}$ та ${\displaystyle \lnot x\equiv x\oplus 1}$.

${\displaystyle A\downarrow B\equiv \lnot (A\lor B)\equiv (A\lor B)\oplus 1\equiv A\wedge B\oplus A\oplus B\oplus 1}$

Отриманий канонічний поліном містить нелінійні члени (${\displaystyle A\wedge B}$). Отже, функція стрілка Пірса не є лінійною.

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

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

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

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

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

${\displaystyle x\downarrow y\equiv \lnot (x)\wedge \lnot (y)\equiv \lnot (x\lor y)}$.

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

${\displaystyle x_{1}\downarrow x_{2}\downarrow x_{3}\downarrow \ldots \downarrow x_{n}\equiv \lnot (x_{1})\wedge \lnot (x_{2})\wedge \lnot (x_{3})\wedge \ldots \wedge \lnot (x_{n})\equiv \lnot (x_{1}\lor x_{2}\lor x_{3}\lor \ldots \lor x_{n})}$

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

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

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

${\displaystyle f=t_{1}\wedge t_{2}\wedge t_{3}\wedge \ldots \wedge t_{n}\equiv \lnot (\lnot (t_{1}\wedge t_{2}\wedge t_{3}\wedge \ldots \wedge t_{n}))\equiv \lnot (\lnot (t_{1})\lor \lnot (t_{2})\lor \lnot (t_{3})\lor \ldots \lor \lnot (t_{n})),}$

де ${\displaystyle t_{i}}$— елементарні диз'юнкції:

${\displaystyle t_{i}={\widetilde {x_{1}}}\lor {\widetilde {x_{2}}}\lor {\widetilde {x_{3}}}\lor \ldots \lor {\widetilde {x_{s}}}}$

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

${\displaystyle \lnot (t_{i})=\lnot ({\widetilde {x_{1}}}\lor {\widetilde {x_{2}}}\lor {\widetilde {x_{3}}}\lor \ldots \lor {\widetilde {x_{s}}})}$

${\displaystyle f=\lnot (t_{1})\downarrow \lnot (t_{2})\downarrow \lnot (t_{3})\downarrow \ldots \downarrow \lnot (t_{n})}$

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

${\displaystyle \lnot (x)\equiv x\downarrow x}$.

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

${\displaystyle x_{1}\downarrow x_{2}\downarrow x_{3}\equiv x_{1}\downarrow \lnot (x_{2}\downarrow x_{3})\equiv \lnot (x_{1}\downarrow x_{2})\downarrow x_{3}\neq (x_{1}\downarrow x_{2})\downarrow x_{3}}$,

${\displaystyle x_{1}\downarrow x_{2}\downarrow x_{3}\downarrow x_{4}\equiv \lnot (x_{1}\downarrow x_{2})\downarrow \lnot (x_{3}\downarrow x_{4})}$

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

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

${\displaystyle f(x_{1},x_{2},x_{3},x_{4})=({\overline {x_{1}}}\lor {\overline {x_{2}}})\wedge ({\overline {x_{3}}}\lor {\overline {x_{4}}})\wedge (x_{1}\lor x_{2}\lor x_{3}\lor x_{4})}$.

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

${\displaystyle f(x_{1},x_{2},x_{3},x_{4})=({\overline {x_{1}}}\downarrow {\overline {x_{2}}})\downarrow ({\overline {x_{3}}}\downarrow {\overline {x_{4}}})\downarrow (x_{1}\downarrow x_{2}\downarrow x_{3}\downarrow x_{4})}$.

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

${\displaystyle f(x_{1},x_{2},x_{3},x_{4})={\overline {({\overline {x_{1}}}\downarrow {\overline {x_{2}}})\downarrow ({\overline {x_{3}}}\downarrow {\overline {x_{4}}})}}\downarrow ({\overline {x_{1}\downarrow x_{2}}}\downarrow {\overline {x_{3}\downarrow x_{4}}})}$.

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

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

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

• Штрих Шефера
• Булева множина
• Закони де Моргана

• Г. Цейтлін. Елементи теорії булевих функцій. — Київ : Техніка, 1967. — 76 с.(укр.)
• Вітенько І. В. Математична логіка: Курс лекцій. — Ужгород : УжДУ, 1971. — 224 с.(укр.)
• Хромой В. Я. Збірник вправ і задач з математичної логіки. — Київ : Вища школа, 1978. — 160 с.(укр.)
• Дрозд Ю. А. (2005). Основи математичної логіки (PDF). Київ: ВПЦ "Київський університет". с. 96. (укр.)
• Безущак О. О., Ганюшкін О. Г. Математична логіка: Навчальний посібник. — Київ : ВПЦ "Київський університет", 2023. — 143 с.(укр.)