Sheffer inme - Sheffer stroke
NAND | |
---|---|
Tanım | |
Doğruluk şeması | |
mantık kapısı | |
Normal formlar | |
ayırıcı | |
bağlaç | |
Zhegalkin polinomu | |
Posta kafesleri | |
0-korumak | numara |
1-korumak | numara |
Monoton | numara |
afin | numara |
Gelen Boole fonksiyonları ve önermeler mantığı , Sheffer inme bir belirtmektedir mantıksal işlem eşdeğerdir reddi ve birlikte "olup, her iki" sıradan dilde ifade işlemi,. Aynı zamanda nand ("değil ve") veya alternatif inkar olarak da adlandırılır , çünkü fiilen işlenenlerinden en az birinin yanlış olduğunu söyler. In dijital elektronik , bu karşılık gelen NAND kapısı . Adını Henry M. Sheffer'dan alır ve ↑ veya | (ancak || olarak değil, genellikle ayrılmayı temsil etmek için kullanılır ). In Bochenski notasyonu o Ge olarak yazılabilir pq .
Onun ikili olduğunu NOR operatörü (olarak da bilinir Peirce ok veya Quine hançer). NAND, ikilisi gibi, mantıksal bir biçimsel sistem oluşturmak için (NAND'ı işlevsel olarak eksiksiz hale getirir ) başka herhangi bir mantıksal işleç olmadan kendi başına kullanılabilir . Bu özellik, NAND geçidini bilgisayar işlemci tasarımında kullanımı da dahil olmak üzere modern dijital elektronik için çok önemli kılar .
Tanım
NAND işlemi a, mantıksal işlem iki ilgili mantıksal değerler . Önermelerden en az biri yanlışsa - ve yalnızca - doğru değerini üretir .
Doğruluk şeması
Doğruluk tablosu içinde (aynı zamanda yazılı ya da D -q ) aşağıdaki gibi olduğu
T |
T |
F
|
T |
F |
T
|
F |
T |
T
|
F |
F |
T
|
mantıksal denklikler
Sheffer vuruşu ve onların birleşiminin olumsuzlanmasıdır
By De Morgan Kanunları , bu da bir inkarın disjunction eşdeğerdir ve
Tarih
Vuruş, 1913'te Amerikan Matematik Derneği'nin İşlemlerinde strok kullanılarak Boole cebirlerinin aksiyomlaştırılmasını sağlayan bir makale yayınlayan ve bilinen operatörleri kullanan Huntington tarafından standart bir formülasyona eşdeğerliğini kanıtlayan Henry M. Sheffer'ın adını almıştır . önerme mantığı ( ve , veya , değil ). Boolean cebirlerinin öz dualitesi nedeniyle , Sheffer'ın aksiyomları, vuruş yerine NAND veya NOR işlemlerinden biri için eşit derecede geçerlidir. Sheffer makalesinde felci bir ayrılmama işareti ( NOR ) olarak yorumlamış, bağlaçsızlıktan sadece bir dipnotta ve bunun için özel bir işaret koymadan bahsetmiştir. Bu oldu Jean NICOD ilk 1917 bir kağıt olmayan bağlantılı bir işareti (NAND) olarak felç kullanılır ve o zamandan beri mevcut uygulama haline gelmiştir. Russell ve Whitehead, Principia Mathematica'nın 1927 ikinci baskısında Sheffer vuruşunu kullandılar ve ilk baskının "veya" ve "değil" işlemlerinin yerine geçmesini önerdiler.
Charles Sanders Peirce (1880) , NAND veya NOR'un işlevsel bütünlüğünü 30 yıldan daha uzun bir süre önce ampheck ("her iki yolu kesmek" için) terimini kullanarak keşfetmişti , ancak bulgusunu hiç yayınlamadı.
Özellikler
NAND, her birinin olmaması gereken ve işlevsel olarak eksiksiz bir operatörler kümesinin en az bir üyesi için yeterli olan aşağıdaki beş özelliğin hiçbirine sahip değildir : doğruluk-koruma, yanlışlık- koruma, doğrusallık , monotonluk , öz-dualite . (Bir operatör, tüm argümanları doğru (yanlışlık) olduğunda, değerinin doğruluk (yanlışlık) olup olmadığını korur.) Bu nedenle {NAND} işlevsel olarak tam bir kümedir.
Bu aynı zamanda şu şekilde de gerçekleştirilebilir: İşlevsel olarak tamamlanmış {AND, OR, NOT} kümesinin üç öğesi de yalnızca NAND kullanılarak oluşturulabilir . Bu nedenle {NAND} kümesi de işlevsel olarak eksiksiz olmalıdır.
Sheffer vuruşu açısından diğer Boole işlemleri
NAND cinsinden ifade edildiğinde , önerme mantığının olağan operatörleri şunlardır:
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
Sheffer vuruşuna dayalı resmi sistem
Aşağıdaki, tamamen Sheffer vuruşuna dayanan, ancak önerme mantığının işlevsel ifadesine sahip olan bir biçimsel sistem örneğidir :
Semboller
p n doğal sayılar için n :
- ( | )
Sheffer stroku gidip gelir ancak ilişkilendirilmez (örneğin, (T | T) | F = T , ancak T | (T | F) = F ). Bu nedenle, bir ek sembolü olarak Sheffer vuruşunu içeren herhangi bir resmi sistem aynı zamanda gruplandırmayı belirtmek için bir araç içermelidir (kontur bir önek olarak kullanılıyorsa gruplama otomatiktir, bu nedenle: || TTF = T ve | T | TF = F ). Bu amaçla '(' ve ')' kullanacağız.
Ayrıca p 0 , p 1 , p 2 yerine p , q , r , … yazarız .
Sözdizimi
Yapı Kural I: Her bir doğal sayı için , n , sembol , p , n bir olduğunu iyi oluşan formül bir atom adı (wff).
İnşaat Kural II: Eğer X ve Y wffs, o zaman ( X | Y ) bir wff olduğunu.
Kapanış Kuralı: İlk iki Yapı Kuralı ile oluşturulamayan formüller wff değildir.
Harfler , U , V , W , X, ve Y'nin wffs bekletildikten metavariables vardır.
Bir formülün iyi biçimlendirilmiş olup olmadığını belirlemeye yönelik bir karar prosedürü aşağıdaki gibidir: Yapı Kurallarını geriye doğru uygulayarak formülü "yapıbozuma uğratın", böylece formülü daha küçük alt formüllere bölün. Daha sonra bu özyinelemeli yapıbozum işlemini alt formüllerin her biri için tekrarlayın. Sonunda formül atomlarına indirgenmelidir, ancak bazı alt formüller bu kadar indirgenemezse, formül bir wff değildir.
kalkülüs
formun tüm wff'leri
- (( U | ( V | W )) | (( Y | ( Y | Y )) | (( X | V ) | (( U | X ) | ( U | X )))))
aksiyomlardır. Örnekleri
çıkarım kurallarıdır.
sadeleştirme
Bu mantığın tek bağlacı | olduğundan, | Harfleri gruplamak için yalnızca parantezler bırakılarak tamamen atılabilir. Bir çift parantez her zaman bir çift wff s içermelidir . Bu basitleştirilmiş gösterimdeki teorem örnekleri şunlardır:
- ( p ( p ( q ( q (( pq )( pq ))))))
- ( p ( p (( qq )( pp )))).
Notasyon, izin verilerek daha da basitleştirilebilir.
- ( U ) := ( UU )
herhangi U . Bu sadeleştirme, bazı kuralları değiştirme ihtiyacına neden olur:
- Parantez içinde ikiden fazla harfe izin verilir.
- Parantez içindeki harfler veya wff'lerin yer değiştirmesine izin verilir.
- Aynı parantez içinde tekrarlanan harfler veya wff'ler elimine edilebilir.
Sonuç, Peirce varoluşsal grafiklerinin parantez içindeki bir versiyonudur .
Gösterimi basitleştirmenin başka bir yolu, Polonyalı Gösterim kullanarak parantezleri ortadan kaldırmaktır . Örneğin, yalnızca parantezli önceki örnekler, yalnızca konturlar kullanılarak aşağıdaki gibi yeniden yazılabilir.
- ( p ( p ( q ( q (( pq )( pq )))))) olur
- | p | p | q | q || pq | pq , ve
- ( p ( p (( qq )( pp )))) olur,
- | p | p || qq | s .
Bu, açılış parantezinin bir Sheffer vuruşuyla değiştirildiği ve (gereksiz) kapanış parantezinin kaldırıldığı parantez versiyonuyla aynı kuralları takip eder.
Ya da (bazı formüller için), bir iki parantez ihmal olabilir ve vuruş ve sırasını belirlemek için bağımsız değişken sırasını izin işlevi uygulama , örneğin, sol (ters Polonya gösterime sağdan fonksiyonun uygulanması, böylece - başka herhangi bir kesin kuralı göre sipariş olur)
Ayrıca bakınız
Notlar
Referanslar
- Bocheński, Józef Maria (1960), Precis of Mathematical Logic , rev., Albert Menne, Otto Bird, Dordrecht , Güney Hollanda tarafından düzenlenmiş ve Fransızca ve Almanca baskılardan çevrilmiştir : D. Reidel .
- Kilise, Alonzo (1956). Matematiksel mantığa giriş. Cilt 1 . Princeton Üniversitesi Yayınları .
- Nicod, Jean GP (1917). "Mantığın İlkel Önermelerinin Sayısında Bir Azalma". Cambridge Felsefe Derneği Tutanakları . 19 : 32-41.
- Charles Sanders Peirce , 1880, Hartshorne, C. ve Weiss, P. , eds., (1931–35) içinde "Bir Sabitli Boolian [sic] Cebir", Charles Sanders Peirce , Cilt. 4 : 12–20, Cambridge : Harvard University Press .
- Sheffer, HM (1913), "Mantıksal sabitlere uygulama ile Boole cebirleri için beş bağımsız postüla seti", Transactions of the American Mathematical Society , 14 : 481–488, doi : 10.2307/1988701 , JSTOR 1988701