Стрелка Пирса

Материал из testwiki
Перейти к навигации Перейти к поиску

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

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

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

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

a b a↓b
0 0 1
0 1 0
1 0 0
1 1 0

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

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

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

X↓X≡¬X — отрицание;
(X↓X)↓(Y↓Y)≡X∧Y — конъюнкция;
(X↓Y)↓(X↓Y)≡X∨Y — дизъюнкция;
((X↓X)↓Y)↓((X↓X)↓Y)≡X→Y — импликация.

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

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

F=x1+x2+x3+x4+...xn‾.

Схемы

Реализация вентиля 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;
}

На заре электронной вычислительной техники Джон фон Нейман определил, что для логических вычислений процессор должен содержать аппаратное АЛУ. Такая архитектура процессора называется архитектура фон Неймана.Шаблон:Нет АИШаблон:Значимость факта?

При программном же табличном вычислении логических функций аппаратное АЛУ в процессоре не требуется, что удешевляет процессор и, из-за уменьшения электроники, повышает надёжность процессора (дешевле и надёжнее).Шаблон:Нет АИШаблон:Значимость факта?

В процессорах же с аппаратными АЛУ программное табличное вычисление логических функций может быть полезным дополнением, повышающим надёжность процессора, так как в случае неисправности аппаратного АЛУ можно переключиться на программное табличное вычисление логических функцийШаблон:Значимость факта?Шаблон:Нет АИ.

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Вс Шаблон:Булева алгебра

  1. ↑ Коваль В. Н. СТРЕЛКА ПИРСА // Энциклопедия кибернетики. Том 2. Киев, 1974. С. 162 Шаблон:Wayback
  2. ↑ В Юникоде для операции ИЛИ-НЕ предусмотрен символ ⊽ U+22BD (NOR)
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Стрелка_Пирса&oldid=3458