Инсульт Шеффера - Sheffer stroke
NAND | |
---|---|
Определение | |
Таблица истинности | |
Логический вентиль | |
Нормальные формы | |
Дизъюнктивный | |
Конъюнктивный | |
Полином Жегалкина | |
Решетки столба | |
0-сохраняющий | нет |
1-консервирующий | нет |
Монотонный | нет |
Аффинный | нет |
В булевых функций и исчислении высказываний , то штрих Шеффера обозначает логическую операцию , которая эквивалентна отрицанию в конъюнкции операции, выраженной в обычном языке , как «не оба». Его также называют nand («не и») или альтернативным отрицанием , поскольку он фактически говорит, что по крайней мере один из его операндов ложен. В цифровой электронике он соответствует логическому элементу NAND . Он назван в честь Генри М. Шеффера и написан как ↑ или как | (но не как ||, часто используется для обозначения дизъюнкции ). В обозначениях Бохенского это можно записать как D pq .
Его двойным является оператор ИЛИ-ИЛИ (также известный как стрела Пирса или кинжал Куайна ). Как и его двойственная, NAND может использоваться сама по себе, без какого-либо другого логического оператора, для создания логической формальной системы (делая NAND функционально законченной ). Это свойство делает логический элемент NAND критически важным для современной цифровой электроники , включая его использование в разработке процессоров компьютеров .
Определение
Операция NAND - это логическая операция над двумя логическими значениями . Он дает значение истина, если - и только если - хотя бы одно из предложений ложно.
Таблица истинности
Таблица истинности из (также записывается в виде , или D рд ) следующим образом
Т |
Т |
F
|
Т |
F |
Т
|
F |
Т |
Т
|
F |
F |
Т
|
Логические эквивалентности
Ход Шеффера и есть отрицание их соединения
По законам Де Моргана это также эквивалентно разделению отрицания и
История
Штрих назван в честь Генри М. Шеффера , который в 1913 году опубликовал в журнале Transactions of the American Mathematical Society статью, в которой приводилась аксиоматизация булевых алгебр с использованием штриха, и доказал ее эквивалентность стандартной формулировке Хантингтона с использованием знакомых операторов пропозициональная логика ( и , или , не ). Из-за самодуальности булевых алгебр аксиомы Шеффера одинаково верны как для операций И-НЕ, так и для операций НЕ-ИЛИ вместо штриха. Шеффер интерпретировал штрих как знак нерасхождения ( NOR ) в своей статье, упомянув несоединение только в сноске и без специального знака для этого. Это был Жан Никод, который первым использовал штрих как знак отсутствия соединения (NAND) в статье 1917 года, и с тех пор это стало современной практикой. Рассел и Уайтхед использовали черту Шеффера во втором издании Principia Mathematica 1927 года и предложили его как замену операциям «или» и «не» в первом издании.
Чарльз Сандерс Пирс (1880 г.) открыл функциональную полноту NAND или NOR более 30 лет назад, используя термин ampheck (для «разрезания в обе стороны»), но он так и не опубликовал свое открытие.
Характеристики
И-НЕ не обладает ни одним из следующих пяти свойств, каждое из которых должно отсутствовать, и отсутствие всех из которых достаточно, по крайней мере, для одного члена набора функционально полных операторов: сохранение истинности, ложность- сохранение, линейность , монотонность , самодуальность . (Оператор сохраняет истину (ложность), если его значение является истиной (ложью), когда все его аргументы являются истиной (ложностью).) Следовательно, {И-НЕ} является функционально полным набором.
Это также можно реализовать следующим образом: все три элемента функционально полного набора {И, ИЛИ, НЕ} могут быть построены с использованием только И-НЕ . Таким образом, набор {И-НЕ} также должен быть функционально полным.
Другие логические операции в терминах штриха Шеффера
Выражаясь в терминах И-НЕ , обычные операторы логики высказываний:
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
Формальная система на основе мазка Шеффера
Ниже приводится пример формальной системы, полностью основанной на мазке Шеффера, но обладающей функциональной выразительностью логики высказываний :
Символы
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 . Это упрощение вызывает необходимость изменения некоторых правил:
- В скобках можно использовать более двух букв.
- Буквы или wff в скобках разрешены для коммутации.
- Повторяющиеся буквы или 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