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

Стрі́лка Пі́рса також відома як оператор 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}$

Таблиця істинності

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

${\displaystyle ~A}$	${\displaystyle ~B}$	${\displaystyle ~A\downarrow B}$
0	0	1
0	1	0
1	0	0
1	1	0

Властивості

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

${\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)}$

Функціональна повнота

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

Доведення

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

${\displaystyle ~A}$	${\displaystyle ~B}$	${\displaystyle ~A\downarrow B}$
0	0	1
0	1	0
1	0	0
1	1	0

З таблиці видно, що функція не зберігає 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 ~A}$	${\displaystyle ~B}$	${\displaystyle ~A\downarrow B}$	${\displaystyle ~\lnot (\lnot (A)\downarrow \lnot (B))}$
0	0	1	1
0	1	0	1
1	0	0	1
1	1	0	0

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

Для перевірки лінійності функції побудуємо її канонічний поліном Жегалкіна із використанням властивостей: ${\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 P\downarrow Q}$	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg (P\lor Q)}$
	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg }$

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

${\displaystyle \neg P}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle P\downarrow P}$ ${\displaystyle \neg }$     ${\displaystyle \Leftrightarrow }$		${\displaystyle P\rightarrow Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle {\Big (}(P\downarrow P)\downarrow Q{\Big )}}$ ${\displaystyle \downarrow }$ ${\displaystyle {\Big (}(P\downarrow P)\downarrow Q{\Big )}}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \downarrow }$
${\displaystyle P\land Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\downarrow P)}$ ${\displaystyle \downarrow }$ ${\displaystyle (Q\downarrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \downarrow }$		${\displaystyle P\lor Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\downarrow Q)}$ ${\displaystyle \downarrow }$ ${\displaystyle (P\downarrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \downarrow }$

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

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

${\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 на доповнюючих МОП-тразісторах. Таку схему отримують шляхом послідовного з'єднання однотипних транзисторів і паралельного з'єднання групи транзисторів іншого типу.

Див. також

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