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

Инсульт Шеффера
NAND
Диаграмма Венна инсульта Шеффера
Определение
Таблица истинности
Логический вентиль NAND ANSI.svg
Нормальные формы
Дизъюнктивный
Конъюнктивный
Полином Жегалкина
Решетки столба
0-сохраняющий нет
1-консервирующий нет
Монотонный нет
Аффинный нет

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

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

Определение

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

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

Таблица истинности из (также записывается в виде , или D рд ) следующим образом

Т
Т
F
Т
F
Т
F
Т
Т
F
F
Т

Логические эквивалентности

Ход Шеффера и есть отрицание их соединения

    
Venn1110.svg      Venn0001.svg

По законам Де Моргана это также эквивалентно разделению отрицания и

    
Venn1110.svg      Venn1010.svg Venn1100.svg

История

Штрих назван в честь Генри М. Шеффера , который в 1913 году опубликовал в журнале Transactions of the American Mathematical Society статью, в которой приводилась аксиоматизация булевых алгебр с использованием штриха, и доказал ее эквивалентность стандартной формулировке Хантингтона с использованием знакомых операторов пропозициональная логика ( и , или , не ). Из-за самодуальности булевых алгебр аксиомы Шеффера одинаково верны как для операций И-НЕ, так и для операций НЕ-ИЛИ вместо штриха. Шеффер интерпретировал штрих как знак нерасхождения ( NOR ) в своей статье, упомянув несоединение только в сноске и без специального знака для этого. Это был Жан Никод, который первым использовал штрих как знак отсутствия соединения (NAND) в статье 1917 года, и с тех пор это стало современной практикой. Рассел и Уайтхед использовали черту Шеффера во втором издании Principia Mathematica 1927 года и предложили его как замену операциям «или» и «не» в первом издании.

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

Характеристики

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

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

Другие логические операции в терминах штриха Шеффера

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

        
Venn10.svg          Venn01.svg Venn01.svg
   
                 
Venn1011.svg          Venn0101.svg Venn1100.svg          Venn0101.svg Venn1110.svg
   
        
Venn1001.svg          Venn1110.svg Venn0111.svg
 
        
Venn0001.svg          Venn1110.svg Venn1110.svg
   
        
Venn0111.svg          Venn1010.svg Venn1100.svg

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

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

Символы

p n для натуральных чисел n :

(|)

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

Мы также пишем p , q , r ,… вместо p 0 , p 1 , p 2 .

Синтаксис

Правило построения 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 )))))

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

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

Упрощение

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

( p ( p ( q ( q (( pq ) ( pq )))))),
( p ( p (( qq ) ( pp )))).

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

( U ): = ( UU )

для любого 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 | стр .

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

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

Смотрите также

Примечания

использованная литература

  • Бохенский, Юзеф Мария (1960), Precis of Mathematical Logic , rev., Альберт Менне, отредактированный и переведенный с французского и немецкого изданий Отто Бердом, Дордрехт , Южная Голландия : D. Reidel .
  • Церковь, Алонсо (1956). Введение в математическую логику. Том 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

внешние ссылки