Gerçek işlevi - Truth function

İçinde mantık , bir gerçek işlevi a, fonksiyon kabul gerçek değerlerinin girdi olarak alır ve çıktı olarak benzersiz bir gerçek değer üretir. Başka bir deyişle: Bir doğruluk işlevinin girdisi ve çıktısı, tüm doğruluk değerleridir; bir doğruluk işlevi her zaman tam olarak bir doğruluk değeri verir; ve aynı doğruluk değerlerinin girilmesi her zaman aynı doğruluk değerini verecektir. Tipik örnek, önermeler mantığındadır , burada bir bileşik ifade, mantıksal bağlantılarla birbirine bağlanan bireysel ifadeler kullanılarak oluşturulur ; Bileşik ifadenin doğruluk değeri tamamen kurucu ifadelerin doğruluk değer (ler) i tarafından belirlenirse, bileşik ifadeye doğruluk işlevi denir ve kullanılan mantıksal bağlaçların doğruluk işlevi olduğu söylenir .

Klasik önermesel mantık , her ifadenin doğru veya yanlış olan tam olarak tek bir doğruluk değerine sahip olması ve her mantıksal bağın doğruluk işlevli olması (karşılık gelen doğruluk tablosu ile ) olması nedeniyle, hakikat-işlevsel bir mantıktır , dolayısıyla her bileşik ifade bir doğruluk işlevidir. Öte yandan, modal mantık , gerçek-işlevsel değildir.

Genel Bakış

Bir bileşik cümlenin doğruluk-değeri, alt cümlelerinin doğruluk-değerinin bir fonksiyonuysa, mantıksal bir bağlantı , gerçek-işlevseldir. Bir bağlayıcı sınıfı, üyelerinden her biri öyleyse, gerçek işlevlidir. Örneğin, bağ " ve " gerçeği işlevsel "gibi bir cümle beri olduğu Elmalar meyveler ve havuç sebze olan " doğrudur , ancak ve ancak alt cümle "her elma meyveleri olan " ve " havuç sebze olan " dır true, aksi takdirde false. İngilizce gibi doğal bir dilin bazı bağlantıları gerçek işlevli değildir.

"X inanıyor ki ..." biçimindeki bağlaçlar, doğruluk işlevi olmayan tipik bağlayıcı örneklerdir. Örneğin Mary, yanlışlıkla Al Gore'un 20 Nisan 2000'de ABD Başkanı olduğuna inanıyor, ancak ayın yeşil peynirden yapıldığına inanmıyorsa, o zaman cümle

" Mary, Al Gore'un 20 Nisan 2000'de ABD Başkanı olduğuna inanıyor "

doğrudur

" Mary, ayın yeşil peynirden yapıldığına inanıyor "

yanlış. Her iki durumda da, her bir bileşen cümle (yani " Al Gore, 20 Nisan 2000'de ABD'nin başkanıydı " ve " ay yeşil peynirden yapılmıştır ") yanlıştır, ancak her bir bileşik cümle, " Mary, "doğruluk değeri farklıdır. Yani "biçiminde bir cümle gerçeği değeridir ... Meryem inanmaktadır " bileşen cümlenin gerçeği değeri tarafından yalnızca belirlenmez ve dolayısıyla (birli) bağ (ya da sadece operatör o birli olduğundan ) gerçek olmayan işlevseldir.

Formüllerin oluşturulmasında kullanılan klasik mantık bağlaçları sınıfı (örn. & , ) doğruluk-işlevseldir. Argüman olarak çeşitli doğruluk değerleri için değerleri genellikle doğruluk tablolarında verilir . Hakikat-işlevsel önerme hesabı , formülleri doğru veya yanlış olarak yorumlanabilen resmi bir sistemdir .

İkili doğruluk fonksiyonları tablosu

İki değerli mantıkta, iki P ve Q girişinin Boole fonksiyonları olarak da adlandırılan on altı olası doğruluk fonksiyonu vardır . Bu işlevlerden herhangi biri , klasik mantıkta belirli bir mantıksal bağlantının doğruluk tablosuna karşılık gelir; bu , argümanlarından birine veya her ikisine bağlı olmayan bir işlev gibi birkaç dejenere durum içerir. Aşağıdaki doğruluk tablolarında, kısalık uğruna doğru ve yanlış, sırasıyla 1 ve 0 olarak gösterilmektedir.

Çelişki / Yanlış
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması

"alt"
P ∧ ¬ P
O pq
  Q
0 1
P 0    0   0 
1    0   0 
Venn0000.svg


Totoloji / Doğru
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması

"üst"
P ∨ ¬ P
V pq
  Q
0 1
P 0    1   1 
1    1   1 
Venn1111.svg


Önerme P
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P p
I pq
  Q
0 1
P 0    0   0 
1    1   1 
Venn0101.svg


P'nin Olumsuzluğu
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
¬ P
~ P
N p
F pq
  Q
0 1
P 0    1   1 
1    0   0 
Venn1010.svg


Önerme Q
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
Q q
H pq
  Q
0 1
P 0    0   1 
1    0   1 
Venn0011.svg


Q'nun Olumsuzluğu
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
¬ Q
~ Q
N q
G pq
  Q
0 1
P 0    1   0 
1    1   0 
Venn1100.svg


Bağlaç
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P & Q
P   ·   Q
P  VE  Q
P ↛¬ Q
¬ P Q
¬ P ↓ ¬ Q
K pq
  Q
0 1
P 0    0   0 
1    0   1 
Venn0001.svg


Alternatif inkar
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P | Q
P  NAND  Q
P → ¬ Q
¬ P Q
¬ P ∨ ¬ Q
D pq
  Q
0 1
P 0    1   1 
1    1   0 
Venn1110.svg


Ayrılma
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P  VEYA  Q
P ← ¬ Q
¬ P Q
¬ P ↑ ¬ Q
¬ (¬ P ∧ ¬ Q )
A pq
  Q
0 1
P 0    0   1 
1    1   1 
Venn0111.svg


Ortak inkar
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P  NOR  Q
P ↚ ¬ Q
¬ P Q
¬ P ∧ ¬ Q
X pq
  Q
0 1
P 0    1   0 
1    0   0 
Venn1000.svg


Malzemenin uygulanmaması
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P Q P Q
P ∧ ¬ Q
¬ P Q
¬ P ↚ ¬ Q
L pq
  Q
0 1
P 0    0   0 
1    1   0 
Venn0100.svg


Maddi ima
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P Q
P Q
P ↑ ¬ Q
¬ P Q
¬ P ← ¬ Q
C pq
  Q
0 1
P 0    1   1 
1    0   1 
Venn1011.svg


Converse uygulama dışı
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P Q P Q
P ↓ ¬ Q
¬ P Q
¬ P ↛ ¬ Q
M pq
  Q
0 1
P 0    0   1 
1    0   0 
Venn0010.svg


Converse implication
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P Q
P Q
P ∨ ¬ Q
¬ P Q
¬ P → ¬ Q
B pq
  Q
0 1
P 0    1   0 
1    1   1 
Venn1101.svg


Münhasır ayrılma
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q
P Q
P Q
P  XOR  Q
P ¬ Q ¬ P Q ¬ P ↮ ¬ Q J pq


  Q
0 1
P 0    0   1 
1    1   0 
Venn0110.svg


Çift koşullu
Gösterim Eşdeğer
formüller
Doğruluk tablosu Venn şeması
P Q PQ P  XNOR  Q P  IFF  Q


P ↮ ¬ Q
¬ P Q
¬ P ¬ Q E pq
  Q
0 1
P 0    1   0 
1    0   1 
Venn1001.svg


İşlevsel bütünlük

Bir fonksiyon bir bileşim olarak ifade edilebildiğinden , bir doğruluk-fonksiyonel mantıksal analizin, yukarıda bahsedilen tüm fonksiyonların fonksiyonel olarak tamamlanması için adanmış sembollere sahip olması gerekmez . Bu, belirli bileşik ifadelerin mantıksal denkliği olarak bir önermesel hesapta ifade edilir . Örneğin, klasik mantık, P  →  Q'ya eşdeğer ¬ P  ∨  Q'ya sahiptir . Bu nedenle , "¬" (değil) ve "∨" (veya) halihazırda kullanılıyorsa , klasik tabanlı mantıksal sistem için koşullu operatör "→" gerekli değildir.

Bir minimal her deyim expressible ifade edebilen operatörlerin kümesi önermeler mantığı bir denir minimal fonksiyonel komple set . Minimal olarak eksiksiz bir işleç kümesi, yalnızca NAND {↑} ve yalnızca NOR {↓} ile elde edilir.

Aşağıdakiler, toparlanmaları 2'yi geçmeyen, işlevsel olarak eksiksiz minimal operatör kümeleridir:

Bir öğe
{↑}, {↓}.
İki unsur
, , , , , , , , , , , , , , , , , .
Üç unsur
, , , , , .

Cebirsel özellikler

Bazı doğruluk fonksiyonları, karşılık gelen bağlayıcıyı içeren teoremlerde ifade edilebilen özelliklere sahiptir. Bir ikili doğruluk işlevinin (veya karşılık gelen mantıksal bağlayıcının) sahip olabileceği özelliklerden bazıları şunlardır:

  • ilişkilendirilebilirlik : Bir satırda iki veya daha fazla aynı ilişkilendirici bağlantı içeren bir ifade içinde, işlenenlerin sırası değişmediği sürece işlemlerin sırası önemli değildir.
  • değişme : Bağlantının işlenenleri, ifadenin doğruluk değerini etkilemeden değiştirilebilir.
  • dağılım : · ile gösterilen bir bağ, tüm a , b , c işlenenleri için a · ( b + c ) = ( a · b ) + ( a · c ) ise, + ile gösterilen başka bir bağlayıcının üzerine dağıtır .
  • idempotence : İşlemin işlenenleri aynı olduğunda, bağlayıcı sonuç olarak işleneni verir. Diğer bir deyişle, operasyon hem gerçeği hem de yalanı koruyucudur (aşağıya bakınız).
  • soğurma : Tüm a , b işlenenleri için bir çift bağlayıcı soğurma yasasını karşılar .

Bir dizi doğruluk işlevi, ancak ve ancak aşağıdaki beş özelliğin her biri için eksik olan en az bir üye içeriyorsa işlevsel olarak tamamlanmıştır :

  • monoton : Eğer tüm a 1 , ..., bir n , b 1 , ..., b n ∈ için f ( a 1 , ..., a n ) ≤ f ( b 1 , ..., b n ) {0,1} öyle ki a 1 b 1 , a 2 b 2 , ..., a n b n . Örneğin ,.
  • affine : Her değişken için değerini değiştirmek, diğer tüm değişkenlerin tüm sabit değerleri için işlemin doğruluk değerini her zaman değiştirir veya hiçbir zaman değiştirmez. Örneğin ,, .
  • self dual : İşlem için doğruluk-değer atamalarını doğruluk tablosunda yukarıdan aşağıya okumak, onu aşağıdan yukarıya doğru okumanın tümleyicisini almakla aynıdır; başka bir deyişle, f bir 1 , ..., ¬ bir n ) = ¬ f ( bir 1 , ..., bir n ). Örneğin ,.
  • gerçeği koruma : Tüm değişkenlere "doğru" olan bir doğruluk değerinin atandığı yorum , bu işlemlerin bir sonucu olarak "doğru" olan bir doğruluk değeri üretir. Örneğin ,. ( geçerliliğe bakın )
  • yalanı koruma : Tüm değişkenlerin doğruluk değerinin 'yanlış' olarak atandığı yorum , bu işlemlerin bir sonucu olarak 'yanlış' bir doğruluk değeri üretir. Örneğin ,. ( geçerliliğe bakın )

Derece

Somut bir işlev, bir operatör olarak da adlandırılabilir . İki değerli mantıkta 2 sıfır operatör (sabit), 4 tekli operatör , 16 ikili operatör , 256 üçlü operatör ve n- değişken operatör vardır. Üç değerli mantıkta 3 nullary operatörleri (sabitler), 27 vardır tekli operatörler , 19683 ikili operatörler , 7625597484987 üçlü operatörler ve n -ary operatörler. Gelen k -valued mantık vardır k nullary operatörler, tekli operatörler, ikili operatörleri, üçlü operatörleri ve n -ary operatörleri. Bir n içinde -ary operatör k mantığı bir fonksiyonudur -valued . Bu nedenle, bu tür operatörlerin sayısı , yukarıdaki sayıların nasıl türetildiği budur.

Bununla birlikte, belirli bir aritenin bazı operatörleri aslında bazı girdiler üzerinde daha düşük bir operasyon gerçekleştiren ve geri kalan girdileri göz ardı eden dejenere formlardır. Yukarıda belirtilen 256 üçlü boole operatöründen , dahil etme-dışlama ilkesini kullanan ikili veya daha düşük düzeyli operatörlerin bu tür dejenere formlarıdır . Üçlü operatör , aslında bir girişe uygulanan ve diğer iki girişi yok sayan tekli operatör olan böyle bir operatördür.

"Değil" bir olan tekli operatör tek bir terim (¬ alır P ). Geri kalanı ikili operatörler bir bileşik açıklama yapmak (iki terim alarak P Q , P Q , P Q , P Q ).

Mantıksal operatörlerin grubu Ω edilebilir paylaştırıldı aşağıdaki gibi ayrık alt-grup halinde:

Bu bölümde, arity j'nin operatör sembolleri kümesidir .

Daha tanıdık önermesel taşta, tipik olarak aşağıdaki gibi bölümlenir:

boş operatörler:
tekli operatörler:
ikili operatörler:

Kompozisyon ilkesi

Doğruluk tablolarını kullanmak yerine mantıksal bağlantılı semboller , anlam bileşimi ilkesiyle detaylandırıldığı üzere, bir yorumlama fonksiyonu ve işlevsel olarak eksiksiz bir doğruluk fonksiyonları seti (Gamut 1991) aracılığıyla yorumlanabilir. Let Ben izin, bir yorumlama fonksiyonu Φ , Ψ herhangi iki cümle olabilir ve gerçeği fonksiyonu izin f NAND olarak tanımlanabilir:

  • f nand (T, T) = F; f nand (T, F) = f nand (F, T) = f nve (F, F) = T

Daha sonra, kolaylık sağlamak için, ön değil , f veya ön ve benzeri ve vasıtasıyla tanımlanmıştır f nand :

  • f değil ( x ) = f nand ( x , x )
  • f veya ( x , y ) = f nand ( f değil ( x ), f değil ( y ))
  • f ve ( x , y ) = f değil ( f nand ( x , y ))

ya da seçenek olarak f değil , f veya f ve ve böylece direkt olarak tanımlanmıştır:

  • f değil (T) F =; f değil (F) S =;
  • f veya (T, T) = f veya (T, F) = f veya (F, T) = T; f veya (F, F) = F
  • f ve (T, T) = T; f ve (T, F) = f ve (F, T) = f ve (F, F) = F

Sonra

  • I (~) = I ( ) = f değil
  • I (&) = I ( ) = f ve
  • I ( v ) = I ( ) = f veya
  • Ben (~ Φ ) = I ( Φ ) = I ( ) ( I ( Φ )) = f değil ( I ( Φ ))
  • Ben ( Φ Ψ ) = I ( ) ( I ( Φ ), I ( Ψ )) = f ve ( I ( Φ ), I ( Ψ ))

vb.

Bu nedenle S , mantıksal bağlantıları temsil eden mantıksal semboller v 1 ... v n ve mantıksal olmayan semboller c 1 ... c n'den oluşan bir sembol dizisinden oluşan bir cümle ise , o zaman ancak ve ancak I ( v 1 ) ... I ( v , n ) yorumlamak temin edilmiştir v 1 için v n vasıtasıyla f nand (veya fonksiyonel bir tam gerçek-işlevlerinin herhangi bir diğer setiyle) daha sonra gerçek-değere gerçeği-değerleri ile tamamen belirlenir c 1 ... c n , yani I ( c 1 ) ... I ( c n ) . Başka bir deyişle, beklendiği ve gerektiği gibi, S yalnızca mantıksal olmayan tüm sembollerinin yorumlanması altında doğru veya yanlıştır.

Bilgisayar Bilimi

Mantıksal operatörler olarak uygulanır mantık kapıları içinde dijital devrelerin . Pratik olarak tüm dijital devreler (en büyük istisna DRAM'dir ) NAND , NOR , NOT ve iletim kapılarından oluşturulur . Normal 2 giriş yerine 3 veya daha fazla girişli NAND ve NOR geçitleri oldukça yaygındır, ancak bunlar mantıksal olarak 2-girişli geçitlerin bir kademesine eşdeğerdir. Diğer tüm operatörler, yukarıdaki mantık kapılarının 2 veya daha fazlasının mantıksal olarak eşdeğer bir kombinasyonuna bölünerek gerçekleştirilir.

"Tek başına NAND", "yalnızca NOR" ve "NOT ve AND" nin "mantıksal eşdeğerliği" Turing eşdeğerliğine benzer .

Tüm doğruluk işlevlerinin yalnızca NOR ile ifade edilebileceği gerçeği Apollo rehberlik bilgisayarı tarafından gösterilmiştir .

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma

  • Józef Maria Bocheński (1959), A Précis of Mathematical Logic , Fransızca ve Almanca versiyonlarından Otto Bird, Dordrecht, Güney Hollanda tarafından çevrildi: D. Reidel.
  • Alonzo Kilisesi (1944), Matematiksel Mantığa Giriş , Princeton, NJ: Princeton University Press. Doğruluk işlevi kavramının geçmişi için Giriş bölümüne bakın.