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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Визначення[ред.ред. код]

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

Діаграма Венна для операції ~A \downarrow B

Таблиця істинності[ред.ред. код]

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

~A ~B ~A \downarrow B
0 0 1
0 1 0
1 0 0
1 1 0

Властивості[ред.ред. код]

~a \downarrow b \equiv b \downarrow a
  • тотожності:
 \bot \equiv (a \downarrow a) \downarrow a
~a \equiv (a \downarrow a) \downarrow (a \downarrow b)

Функціональна повнота[ред.ред. код]

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

Доведення[ред.ред. код]

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

~A ~B ~A \downarrow B
0 0 1
0 1 0
1 0 0
1 1 0

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

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

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

 \lnot ( \lnot( A ) \downarrow \lnot( B ) ) \equiv \lnot ( \lnot( A ) \lor \lnot( B ) ) \equiv \overline{ \overline{ A } \lor \overline{ B } }
~A ~B ~A \downarrow B ~\lnot(\lnot(A) \downarrow \lnot(B))
0 0 1 1
0 1 0 1
1 0 0 1
1 1 0 0

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

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

 A \downarrow B \equiv \lnot ( A \lor B ) \equiv ( A \lor B ) \oplus 1 \equiv A \wedge B \oplus A \oplus B \oplus 1

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

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

Введення еквівалентності[ред.ред. код]

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

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

P \downarrow Q     \Leftrightarrow     \neg (P \or Q)
Venn1000.svg     \Leftrightarrow     \neg Venn0111.svg

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

\neg P     \Leftrightarrow     P \downarrow P
\neg Venn01.svg     \Leftrightarrow     Venn10.svg
   
P \rightarrow Q     \Leftrightarrow     \Big( (P \downarrow P) \downarrow Q \Big) \downarrow \Big( (P \downarrow P) \downarrow Q \Big)
Venn1011.svg     \Leftrightarrow     Venn0100.svg \downarrow Venn0100.svg
 
P \and Q     \Leftrightarrow     (P \downarrow P) \downarrow (Q \downarrow Q)
Venn0001.svg     \Leftrightarrow     Venn1010.svg \downarrow Venn1100.svg
   
P \or Q     \Leftrightarrow     (P \downarrow Q) \downarrow (P \downarrow Q)
Venn0111.svg     \Leftrightarrow     Venn1000.svg \downarrow Venn1000.svg

Мінімізація функцій в базисі стрілки Пірса[ред.ред. код]

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

 x \downarrow y \equiv \lnot( x ) \wedge \lnot( y ) \equiv \lnot( x \lor y ) .

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

 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 )

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

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

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

 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 ) ),

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

 t_i = \widetilde{x_1} \lor \widetilde{x_2} \lor \widetilde{x_3} \lor \ldots \lor \widetilde{x_s}

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

 \lnot( t_i ) = \lnot( \widetilde{x_1} \lor \widetilde{x_2} \lor \widetilde{x_3} \lor \ldots \lor \widetilde{x_s} )
 f = \lnot( t_1 ) \downarrow \lnot( t_2 ) \downarrow \lnot( t_3 ) \downarrow \ldots  \downarrow \lnot( t_n )

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

 \lnot( x ) \equiv x \downarrow x.

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

 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 ,

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 )

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

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

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

 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) .

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

 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) .

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

 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 за допомогою діод-транзисторної логіки, і за допомогою МОН відповідно.

Схеми
Dtl
Mopnand.png


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

Див. також[ред.ред. код]