Стрелка Пирса - NiNa.Az

Стре́лка Пи́рса (функция Вебба, отрицание дизъюнкции) — бинарная логическая операция, булева функция над двумя переменными. Введена в рассмотрение Чарльзом Пирсом в 1880—1881 годах.

Стрелка Пирса
ИЛИ-НЕ, NOR
Диаграмма Венна
Определение	${\displaystyle {\overline {x+y}}}$
Таблица истинности	${\displaystyle (1000)}$
Логический вентиль
Нормальные формы
Дизъюнктивная	${\displaystyle {\overline {x}}\cdot {\overline {y}}}$
Конъюнктивная	${\displaystyle {\overline {x}}\cdot {\overline {y}}}$
Полином Жегалкина	${\displaystyle 1\oplus x\oplus y\oplus xy}$
Принадлежность предполным классам
Сохраняет 0	Нет
Сохраняет 1	Нет
Монотонна	Нет
Линейна	Нет
Самодвойственна	Нет

Стрелка Пирса, обычно обозначаемая ↓, эквивалентна операции ИЛИ-НЕ (дополнение объединения множества) и задаётся в виде двумерной (двухаргументной, двухкоординатной) диаграммы (двумерного массива) истинности из четырёх ячеек:

x↓y = x NOR y = NOT(x OR y) = !(x||y) y 0 0 1 0 x 

на которой сразу видно, что функция симметрична относительно главной диагонали, или в виде таблицы истинности из трёх колонок (двенадцать ячеек):

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle a\downarrow b}$
0	0	1
0	1	0
1	0	0
1	1	0

Таким образом, высказывание «X ↓ Y» означает «(не X) и (не Y)», или, что то же самое, «не (X или Y)». Операция NOR коммутативна: от перемены мест операндов результат операции не изменяется.

УГО 2ИЛИ-НЕ по стандартам IEC и ANSI

Стрелка Пирса, как и штрих Шеффера, образует функционально-полный логический базис для пространства булевых функций от двух переменных. Это означает, что, используя только стрелку Пирса, можно построить все остальные логические операции, например:

${\displaystyle X\downarrow X\equiv \neg X}$ — отрицание;

${\displaystyle \left({X\downarrow X}\right)\downarrow \left({Y\downarrow Y}\right)\equiv {X\wedge Y}}$ — конъюнкция;

${\displaystyle \left({X\downarrow Y}\right)\downarrow \left({X\downarrow Y}\right)\equiv X\vee Y}$ — дизъюнкция;

${\displaystyle \left(\left({X\downarrow X}\right)\downarrow Y\right)\downarrow \left(\left({X\downarrow X}\right)\downarrow Y\right)\equiv X\rightarrow Y}$ — импликация.

В электронике это означает, что для реализации всего многообразия схем преобразования сигналов, представляющих логические значения, достаточно одного типового элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NOR). С другой стороны, такой подход увеличивает сложность реализующих выражения схем и тем самым снижает их надёжность, а также увеличивает время прохождения сигнала и снижает быстродействие устройства.

Функциональная операция, выполняемая при ${\displaystyle n}$ входах, определяется следующим выражением:

${\displaystyle F={\overline {x_{1}+x_{2}+x_{3}+x_{4}+...x_{n}}}.}$

Схемы

Реализация вентиля 2ИЛИ-НЕ с помощью диодно-транзисторной логики

Реализация вентиля 2ИЛИ-НЕ с помощью МОП

Говоря простым языком, вентиль 2ИЛИ-НЕ — это 2ИЛИ с подключённым к нему инвертором. Для наглядности — ниже приведён пример логической схемы 2ИЛИ-НЕ с выключателями. Как известно, логика 2ИЛИ близка к выражению «или A, или B, или то и другое». Чтобы получить операцию 2ИЛИ-НЕ, результат 2ИЛИ необходимо инвертировать, чтобы получить «не (A или B)». На схеме ниже это выглядит следующим образом: серым отмечены выключатели в состоянии «выключено», синим — в состоянии «включено». На верхней левой схеме оба выключателя находятся в положении «выключено». Таким образом, следуя выражению на выходе, получаем логический 0. Инвертированный результат будет равен 1 и тем самым будет логически удовлетворять выражению «не А, не B». Следующие схемы демонстрируют соответственно «ИЛИ А», «ИЛИ B», «И А, И B» с последующей инверсией результата.

Наглядные схемы 2ИЛИ-НЕ на выключателях

Слева представлены варианты реализации вентиля 2ИЛИ-НЕ с помощью диодно-транзисторной логики и с помощью МОП соответственно.

Представленная схема на МОП выполнена на однотипных МОП-транзисторах, однако существуют вариант схемы 2ИЛИ-НЕ на комплементарных (дополняющих) МОП-транзисторах. Такую схему получают путём последовательного соединения однотипных транзисторов и параллельного соединения группы транзисторов другого типа.

Программная реализация

На TurboBasic'e:^{[значимость факта?]}

'2-in NOR, (Peirce, Quine, Webb) CLS COLOR 10 DATA 1,0,0,0 '2-in NOR DEFINT I,J,P,Q,F DIM F1[1,1] FOR I=0 TO 1  FOR J=0 TO 1  READ F1[J,I]  'PRINT USING "#";F1[J,I];  NEXT J NEXT I PRINT "F1(P,Q) = {"; FOR Q=1 TO 0 STEP -1  FOR P=1 TO 0 STEP -1  F1 = F1[P,Q] 'PROGRAMM TABLE ALU  PRINT USING "#";F1;  NEXT P NEXT Q PRINT "} TABLE" PRINT "F1(P,Q) = {"; FOR Q=-1 TO 0  FOR P=-1 TO 0  F1 = -NOT(P OR Q) 'ELECTRONIC LOGIC ALU  PRINT USING "#";F1;  NEXT P NEXT Q PRINT "} LOGIC" END 

На C:^{[значимость факта?]}

// Программная реализация функции "стрелка Пирса"  //в виде двумерного массива (табличная) и //в виде логического уравнения (логическая) #include <stdio.h> //printf();getchar(); int main() {   int f1[2][2] = {1,0,0,0}; /*задание функции в виде двумерного массива (табличное, аппаратное АЛУ не требуется)*/  int p,q,f;   printf("f1(p,q)={");  for(p=1;p>=0;p--)  {  for(q=1;q>=0;q--)  {  f = f1[p][q]; /*программное табличное вычисление функции (аппаратное АЛУ не требуется)*/  printf("%i", f);  }  }  printf("} table\n");  printf("f1(p,q)={");  for(p=1;p>=0;p--)  {  for(q=1;q>=0;q--)  {  f = !(p||q); /*задание функции в виде логического уравнения (логическое, требуется аппаратное АЛУ)*/  printf("%i", f);  }  }  printf("} logic\n");  getchar();  return 0; } 

На заре электронной вычислительной техники Джон фон Нейман определил, что для логических вычислений процессор должен содержать аппаратное АЛУ. Такая архитектура процессора называется архитектура фон Неймана.^{[источник не указан 460 дней][значимость факта?]}

При программном же табличном вычислении логических функций аппаратное АЛУ в процессоре не требуется, что удешевляет процессор и, из-за уменьшения электроники, повышает надёжность процессора (дешевле и надёжнее).^{[источник не указан 460 дней][значимость факта?]}

В процессорах же с аппаратными АЛУ программное табличное вычисление логических функций может быть полезным дополнением, повышающим надёжность процессора, так как в случае неисправности аппаратного АЛУ можно переключиться на программное табличное вычисление логических функций^{[значимость факта?][источник не указан 460 дней]}.

См. также

• Идентичность
• Отрицание
• Конъюнкция
• Дизъюнкция
• Эквиваленция
• Исключающее или
• Импликация
• Обратная импликация
• Штрих Шеффера
• Условная дизъюнкция
• Таблица истинности
• Закон тождества

Примечания

1. Коваль В. Н. СТРЕЛКА ПИРСА // Энциклопедия кибернетики. Том 2. Киев, 1974. С. 162 Архивная копия от 19 октября 2018 на Wayback Machine
2. В Юникоде для операции ИЛИ-НЕ предусмотрен символ ⊽ U+22BD (NOR)

Литература

• Математический энциклопедический словарь. — М.: «Советская энциклопедия», 1988. — С. 457—457.
• Белоусов, Аркадий Алгебра логики и цифровые компьютеры
• Терещук Д. С. Логическое моделирование СБИС на переключательном уровне
• Ю. С. Забродин «Промышленная электроника» — С. 221.