Инсульт Шеффера

Инсульт Шеффера

NAND
Определение	${\ Displaystyle {\ overline {х \ cdot y}}}$
Таблица истинности	${\ displaystyle (1110)}$
Логический вентиль
Нормальные формы
Дизъюнктивный	${\ displaystyle {\ overline {x}} + {\ overline {y}}}$
Конъюнктивный	${\ displaystyle {\ overline {x}} + {\ overline {y}}}$
Полином Жегалкина	${\ displaystyle 1 \ oplus xy}$
Решетки столба
0-сохраняющий	нет
1-консервирующий	нет
Монотонный	нет
Аффинный	нет
v т е

В булевых функций и исчислении высказываний , то штрих Шеффера обозначает логическую операцию , которая эквивалентна отрицанию в конъюнкции операции, выраженной в обычном языке , как «не оба». Его также называют nand («не и») или альтернативным отрицанием , поскольку он фактически говорит, что по крайней мере один из его операндов ложен. В цифровой электронике он соответствует логическому элементу NAND . Он назван в честь Генри М. Шеффера и написан как ↑ или как | (но не как ||, часто используется для обозначения дизъюнкции ). ВВ обозначениях Бохенского его можно записать как D pq .

Его двойным является оператор ИЛИ-ИЛИ (также известный как стрела Пирса или кинжал Куайна ). Как и его двойственная, NAND может использоваться сама по себе, без какого-либо другого логического оператора, для создания логической формальной системы (делая NAND функционально законченной ). Это свойство делает логический элемент NAND критически важным для современной цифровой электроники , включая его использование в разработке процессоров компьютеров .

Определение [ править ]

Операция NAND - это логическая операция над двумя логическими значениями . Он дает значение истина, если - и только если - хотя бы одно из предложений ложно.

Таблица истинности [ править ]

Таблица истинности из (также записывается в виде , или D рд ) следующим образом${\ displaystyle P \ uparrow Q}$${\ Displaystyle P \ mathop {|} Q}$

${\ displaystyle P}$	${\ displaystyle Q}$	${\ displaystyle P \ uparrow Q}$
Т	Т	F
Т	F	Т
F	Т	Т
F	F	Т

Логические эквивалентности [ править ]

Ход Шеффера и есть отрицание их соединения${\ displaystyle P}$${\ displaystyle Q}$

${\ displaystyle P \ uparrow Q}$	${\ displaystyle \ Leftrightarrow}$	${\ Displaystyle \ neg (П \ земля Q)}$
	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle \ neg}$

По законам Де Моргана это также эквивалентно разделению отрицания и${\ displaystyle P}$${\ displaystyle Q}$

${\ displaystyle P \ uparrow Q}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle \ neg P}$	${\ displaystyle \ lor}$	${\ displaystyle \ neg Q}$
	${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ lor}$

История [ править ]

Инсульт назван в честь Генри М. Шеффера , который в 1913 году опубликовал статью в Трудах Американского математического общества (Шеффера 1913) , обеспечивающая аксиоматизацию булевых алгебр , используя удар, и доказал его эквивалентность стандартной формулировки их с помощью Хантингтона , использующего знакомые операторы логики высказываний ( и , или , не ). Из-за самодуальности булевых алгебр аксиомы Шеффера одинаково справедливы как для операций И-НЕ, так и для операций ИЛИ-ИЛИ вместо штриха. Шеффер интерпретировал инсульт как знак нерасхождения ( НИ) в своей статье, упомянув несоединение только в сноске и без специального знака для этого. Это был Жан Никод, который первым использовал штрих как знак отсутствия соединения (NAND) в статье 1917 года, и с тех пор это стало современной практикой. ^[1] Рассел и Уайтхед использовали штрих Шеффера во втором издании Principia Mathematica 1927 года и предложили его как замену операциям «или» и «не» в первом издании.

Чарльз Сандерс Пирс (1880 г.) открыл функциональную полноту NAND или NOR более 30 лет назад, используя термин ampheck (для «разрезания в обе стороны»), но он так и не опубликовал свое открытие.

Свойства [ править ]

И-НЕ не обладает ни одним из следующих пяти свойств, каждое из которых должно отсутствовать, и отсутствие всех из которых достаточно, по крайней мере, для одного члена набора функционально полных операторов: сохранение истинности, ложность- сохранение, линейность , монотонность , самодуальность . (Оператор сохраняет истину (ложность), если его значение является истиной (ложью), когда все его аргументы являются истиной (ложностью).) Следовательно, {И-НЕ} является функционально полным набором.

Это также можно реализовать следующим образом: все три элемента функционально полного набора {И, ИЛИ, НЕ} могут быть построены с использованием только И-НЕ . Таким образом, набор {И-НЕ} также должен быть функционально полным.

Другие логические операции с точки зрения обводки Шеффера [ править ]

Выражаясь в терминах И-НЕ , обычные операторы логики высказываний:${\ displaystyle \ uparrow}$

${\ displaystyle \ neg P}$     ${\ displaystyle \ Leftrightarrow}$     ${\ displaystyle P}$ ${\ displaystyle \ uparrow}$ ${\ displaystyle P}$     ${\ displaystyle \ Leftrightarrow}$     ${\ displaystyle \ uparrow}$		${\displaystyle P\rightarrow Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle ~P}$ ${\displaystyle \uparrow }$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle ~P}$ ${\displaystyle \uparrow }$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\leftrightarrow Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle \uparrow }$ ${\displaystyle ((P\uparrow P)\uparrow (Q\uparrow Q))}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$
${\displaystyle P\land Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle \uparrow }$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\lor Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow P)}$ ${\displaystyle \uparrow }$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$

Формальная система, основанная на мазке Шеффера [ править ]

Ниже приводится пример формальной системы, полностью основанной на мазке Шеффера, но обладающей функциональной выразительностью логики высказываний :

Символы [ править ]

p _n для натуральных чисел n
(|)

Штрих Шеффера коммутирует, но не связывает (например, (T | T) | F = T, но T | (T | F) = F). Следовательно, любая формальная система, включающая штрих Шеффера в качестве инфиксного символа, также должна включать средства указания группировки (группировка выполняется автоматически, если штрих используется в качестве префикса, таким образом: || TTF = T и | T | TF = F). Для этого мы будем использовать «(» и «)».

Мы также пишем p , q , r ,… вместо p ₀ , p ₁ , p ₂ .

Синтаксис [ править ]

Правило построения I. Для каждого натурального числа n символ p _n представляет собой правильно построенную формулу (wff), называемую атомом.

Правило построения II: если X и Y - wff, то ( X  |  Y ) - wff.

Правило закрытия: любые формулы, которые не могут быть построены с помощью первых двух правил построения, не являются wffs.

Буквы U , V , W , X и Y - это метапеременные, обозначающие wffs.

Процедура принятия решения для определения того, является ли формула правильно сформированной, выглядит следующим образом: «деконструируйте» формулу, применяя Правила построения в обратном порядке, тем самым разбивая формулу на более мелкие подформулы. Затем повторите этот рекурсивный процесс деконструкции для каждой подформулы. В конце концов, формула должна быть сокращена до ее атомов, но если некоторая подформула не может быть сокращена таким образом, то формула не является wff.

Исчисление [ править ]

Все wffs формы

(( U  | ( V  |  W )) | (( Y  | ( Y  |  Y )) | (( X  |  V ) | (( U  |  X ) | ( U  |  X )))))

аксиомы. Экземпляры

( U  | ( V  |  W )), U W${\displaystyle \vdash }$

правила вывода.

Упрощение [ править ]

Поскольку единственной связкой этой логики является |, символ | можно вообще отбросить, оставив только круглые скобки для группировки букв. Пара круглых скобок всегда должна заключать пару wff s. Примеры теорем в этих упрощенных обозначениях:

( p ( p ( q ( q (( pq ) ( pq )))))),

( p ( p (( qq ) ( pp )))).

Обозначения можно упростить, если

( U ): = ( UU )

(( U )) U${\displaystyle \equiv }$

для любого U . Это упрощение вызывает необходимость изменения некоторых правил:

1. В скобках можно использовать более двух букв.
2. Буквы или wff в скобках разрешены для коммутации.
3. Повторяющиеся буквы или wff в одном и том же наборе скобок можно исключить.

Результатом является версия экзистенциальных графов Пирса в скобках .

Другой способ упростить нотацию - убрать скобки с помощью польской нотации . Например, предыдущие примеры, содержащие только круглые скобки, можно переписать, используя только штрихи, как показано ниже.

( p ( p ( q ( q (( pq ) ( pq )))))) становится

| p  | p  | q  | q  || pq  | pq и

( p ( p (( qq ) ( pp )))) становится,

| p  | p  || qq  | стр .

Это следует тем же правилам, что и версия с круглыми скобками, с заменой открывающей круглой скобки чертой Шеффера и удалением (лишней) закрывающей скобки.

Или можно опустить круглые скобки и штрихи и позволить порядку аргументов определять порядок применения функции , например, применяя функцию справа налево (обратная польская нотация - подойдет любое другое недвусмысленное соглашение, основанное на порядке)

${\displaystyle {\begin{aligned}&pqr\equiv (p\mid (q\mid r)),{\text{ whereas}}\\&rqp\equiv (r\mid (q\mid p)).\end{aligned}}}$

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

• Бохенский, Юзеф Мария (1960), Precis of Mathematical Logic , rev., Альберт Менне, отредактированный и переведенный с французского и немецкого изданий Отто Бердом, Дордрехт , Южная Голландия : D. Reidel .
• Черч, Алонзо , (1956) Введение в математическую логику , Vol. 1, Принстон : Издательство Принстонского университета .
• Никод, Жан GP (1917). «Уменьшение количества примитивных предложений логики». Труды Кембриджского философского общества . 19 : 32–41.
• Чарльз Сандерс Пирс , 1880 г., «Булевская [sic] алгебра с одной константой», в Hartshorne, C. и Weiss, P. , eds. (1931–35), Сборник статей Чарльза Сандерса Пирса , Vol. 4 : 12–20, Кембридж : Издательство Гарвардского университета .
• Шеффер, HM (1913), «Набор из пяти независимых постулатов для булевых алгебр, с приложением к логическим константам», Труды Американского математического общества , 14 : 481-488, DOI : 10,2307 / 1988701 , JSTOR  1988701

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме инсульта Шеффера .

• Статья Шеффера Инсульта в Интернет-энциклопедии философии
• http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
• реализация логических элементов NAND с 2 и 4 входами
• Доказательства некоторых аксиом с помощью функции Stroke от Ясуо Сэто @ Project Euclid