Udar Sheffera - Sheffer stroke

Udar Sheffera
NAND
Diagram Venna udaru Sheffera
Definicja
Tabela prawdy
Bramka logiczna NAND ANSI.svg
Normalne formy
Dysjunktywny
Łączący
Wielomian Żegalkina
Kraty posta
0-zachowanie nie
1-konserwujący nie
Monotonia nie
Affine nie

W funkcji logicznych i rachunku zdań The skoku Sheffer oznacza funkcję logiczną , która jest równoważna z negacji w powiązaniu działania, wyrażony w języku potocznym jako „nie jednocześnie.” Jest również nazywany nand ("nie i") lub alternatywnym zaprzeczeniem , ponieważ w efekcie mówi, że przynajmniej jeden z jego argumentów jest fałszywy. W elektronice cyfrowej odpowiada bramce NAND . Został nazwany na cześć Henry'ego M. Sheffera i zapisany jako ↑ lub jako | (ale nie jako ||, często używane do reprezentowania alternatywy ). W notacji Bocheńskiego można ją zapisać jako D pq .

Jego podwójnym jest operator NOR (znany również jako strzałka Peirce'a lub sztylet Quine'a ). Podobnie jak jego dual, NAND może być używany samodzielnie, bez żadnego innego operatora logicznego, do utworzenia logicznego systemu formalnego (co sprawia, że ​​NAND jest funkcjonalnie kompletny ). Ta właściwość sprawia, że bramka NAND jest kluczowa dla nowoczesnej elektroniki cyfrowej , w tym jej zastosowanie w projektowaniu procesorów komputerowych .

Definicja

Operacja NAND jest operacją logiczną na dwóch wartościach logicznych . Daje wartość prawdy, jeśli — i tylko wtedy — co najmniej jedno ze zdań jest fałszywe.

Tabela prawdy

Tabela prawdy o (również pisane jako lub D pq ) przedstawia się następująco

T
T
F
T
F
T
F
T
T
F
F
T

Równoważności logiczne

Skok Sheffera i jest zaprzeczeniem ich koniunkcji

    
Venn1110.svg      Venn0001.svg

Zgodnie z Prawami De Morgana jest to również równoznaczne z rozłączeniem negacji i

    
Venn1110.svg      Venn1010.svg Venn1100.svg

Historia

Udar został nazwany na cześć Henry'ego M. Sheffera , który w 1913 roku opublikował artykuł w Transactions of the American Mathematical Society, przedstawiający aksjomatyzację algebr Boole'a za pomocą udaru, i udowodnił jego równoważność ze standardowym sformułowaniem tego autorstwa Huntingtona, wykorzystując znane operatory logika zdań ( i , lub , not ). Z powodu samodwoistości algebr Boole'a, aksjomaty Sheffera są równie ważne dla obu operacji NAND lub NOR zamiast udaru. Sheffer zinterpretował to uderzenie jako znak braku połączenia ( NOR ) w swoim artykule, wspominając o braku połączenia tylko w przypisie i bez specjalnego znaku dla niego. To Jean Nicod jako pierwszy użył udaru jako znaku braku koniunkcji (NAND) w artykule z 1917 roku i od tego czasu stał się on powszechną praktyką. Russell i Whitehead użyli udaru Sheffera w drugim wydaniu Principia Mathematica z 1927 roku i zasugerowali go jako zamiennik dla operacji „lub” i „nie” z pierwszego wydania.

Charles Sanders Peirce (1880) odkrył funkcjonalną kompletność NAND lub NOR ponad 30 lat wcześniej, używając terminu ampheck (dla „cięcia w obie strony”), ale nigdy nie opublikował swojego odkrycia.

Nieruchomości

NAND nie posiada żadnej z następujących pięciu właściwości, z których każda musi być nieobecna, a brak wszystkich jest wystarczający dla co najmniej jednego członka zbioru funkcjonalnie kompletnych operatorów: zachowanie prawdy, fałsz zachowanie, liniowość , monotoniczność , samodwoistość . (Operator jest prawdą (fałszem) zachowując, czy jego wartość jest prawdą (fałszem), gdy wszystkie jego argumenty są prawdą (fałszem).) Zatem {NAND} jest kompletem funkcjonalnie pełnym.

Można to również zrealizować w następujący sposób: Wszystkie trzy elementy funkcjonalnie kompletnego zbioru {AND, OR, NOT} można skonstruować tylko przy użyciu NAND . Zatem zbiór {NAND} musi być również funkcjonalnie kompletny.

Inne operacje logiczne związane z udarem Sheffera

Wyrażone za pomocą NAND , zwykłe operatory logiki zdań to:

        
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

System formalny oparty na stylu Sheffera

Poniżej znajduje się przykład systemu formalnego opartego całkowicie na kreski Sheffera, ale posiadającego funkcjonalną ekspresję logiki zdań :

Symbolika

p n dla liczb naturalnych n :

( | )

Udar Sheffera dojeżdża, ale nie łączy się (np. (T | T) | F = T , ale T | (T | F) = F ). Dlatego każdy formalny system zawierający kreskę Sheffera jako symbol infiksowy musi również zawierać środki wskazujące na grupowanie (grupowanie jest automatyczne, jeśli kreska jest używana jako przedrostek, a więc: || TTF = T i | T | TF = F ). W tym celu użyjemy '(' i ')'.

Piszemy również p , q , r , … zamiast p 0 , p 1 , p 2 .

Składnia

Zasada konstrukcji I: Dla każdej liczby naturalnej n symbol p n jest dobrze sformułowaną formułą (wff), nazywaną atomem.

Zasada Konstrukcji II: Jeśli X i Y są wffs, to ( X  |  Y ) jest wff.

Reguła zamknięcia: Wszelkie formuły, których nie można skonstruować za pomocą dwóch pierwszych reguł konstrukcyjnych, nie są wffs.

Litery U , V , W , X i Y to metazmienne oznaczające wffs.

Procedura decyzyjna określająca, czy formuła jest poprawnie sformułowana, wygląda następująco: „zdekonstruuj” formułę, stosując reguły konstrukcji wstecz, dzieląc w ten sposób formułę na mniejsze podformuły. Następnie powtórz ten rekurencyjny proces dekonstrukcji dla każdej z podformuł. Ostatecznie formuła powinna zostać zredukowana do atomów, ale jeśli jakiś podformuł nie może być tak zredukowany, to formuła nie jest wff.

Rachunek różniczkowy

Wszystkie wffs formy

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

są aksjomaty. Przypadki

są regułami wnioskowania.

Uproszczenie

Ponieważ jedynym spójnikiem tej logiki jest |, symbol | można całkowicie odrzucić, pozostawiając tylko nawiasy do grupowania liter. Para nawiasów musi zawsze zawierać parę wff s. Przykładami twierdzeń w tym uproszczonym zapisie są

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

Notację można jeszcze bardziej uprościć, pozwalając

( U ) := ( UU )

dla każdego U . To uproszczenie powoduje konieczność zmiany niektórych zasad:

  1. W nawiasach dozwolone są więcej niż dwie litery.
  2. Litery lub wffs w nawiasach mogą dojeżdżać.
  3. Można wyeliminować powtarzające się litery lub wffs w tym samym zestawie nawiasów.

Rezultatem jest nawiasowa wersja grafów egzystencjalnych Peirce'a .

Innym sposobem na uproszczenie notacji jest wyeliminowanie nawiasów przy użyciu notacji polskiej . Na przykład wcześniejsze przykłady z samymi nawiasami można przepisać za pomocą samych pociągnięć w następujący sposób

( p ( p ( q ( q (( pq )( pq )))))) staje się
| p | p | q | q || pq | pq , i
( p ( p (( qq )( pp )))) staje się,
| p | p || qq | str . .

Jest to zgodne z tymi samymi zasadami, co wersja z nawiasem, z nawiasem otwierającym zastąpionym kreską Sheffera i usuniętym (zbędnym) nawiasem zamykającym.

Lub (w przypadku niektórych formuł) można pominąć zarówno nawiasy, jak i kreski i zezwolić, aby kolejność argumentów określała kolejność działania funkcji, tak aby np. zastosować funkcję od prawej do lewej (odwrotna notacja polska – dowolna inna jednoznaczna konwencja oparta na zamawianie zrobi)

Zobacz też

Uwagi

Bibliografia

  • Bocheński, Józef Maria (1960), Precis of Mathematical Logic , ks. Albert Menne, red. i przekład z wydania francuskiego i niemieckiego: Otto Bird, Dordrecht , South Holland : D. Reidel .
  • Kościół, Alonzo (1956). Wprowadzenie do logiki matematycznej. Tom 1 . Wydawnictwo Uniwersytetu Princeton .
  • Nicod, Jean GP (1917). „Redukcja liczby prymitywnych propozycji logiki”. Materiały Towarzystwa Filozoficznego w Cambridge . 19 : 32–41.
  • Charles Sanders Peirce , 1880, "Boolian [sic] Algebra z jedną stałą", w Hartshorne, C. i Weiss, P. , red., (1931-35) Zebrane dokumenty Charlesa Sandersa Peirce'a , tom. 4 : 12–20, Cambridge : Wydawnictwo Uniwersytetu Harvarda .
  • Sheffer, HM (1913), "Zestaw pięciu niezależnych postulatów dla algebr Boole'a, z zastosowaniem do stałych logicznych", Transactions of the American Mathematical Society , 14 : 481-488, doi : 10.2307/1988701 , JSTOR  1988701

Zewnętrzne linki