Igazság funkció - Truth function

A logika szerint az igazságfüggvény olyan függvény, amely elfogadja az igazságértékeket bemenetként, és egyedi igazságértéket állít elő kimenetként. Más szavakkal: Az igazságfüggvény bemenete és kimenete mind igazságérték; egy igazságfüggvény mindig pontosan egy igazságértéket fog kiadni; és ugyanazon igazságérték (ek) megadása mindig ugyanazt az igazságértéket adja ki. A tipikus példa a propozíciós logika , ahol az összetett utasításokat logikai kapcsolatokkal összekapcsolt egyes utasítások felhasználásával állítják össze ; ha az összetett állítás igazságértékét teljes egészében az alkotó állítás (ok) igazságértéke (i) határozza meg, az összetett állítást igazságfüggvénynek nevezzük , és minden alkalmazott logikai összekötőt igazságfunkcionálisnak mondunk .

A klasszikus propozíciós logika igazság-funkcionális logika, mivel minden állításnak pontosan egy igazságértéke van, amely akár igaz, akár hamis, és minden logikai összekötő igazság funkcionális (egy megfelelő igazságtáblával ), így minden összetett állítás igazságfüggvény. Másrészt a modális logika nem igazság-funkcionális.

Áttekintés

A logikai kötődés akkor funkcionális, ha az összetett mondat igazságértéke a részmondatok igazságértékének függvénye. A kapcsolatok egy osztálya igazság-funkcionális, ha minden tagja az. Például a " és " kötőszó igazság-funkcionális, mivel az " Alma gyümölcs és sárgarépa zöldség " mondat igaz , és csak akkor, ha az " alma gyümölcs " és a " sárgarépa zöldség " almondatok mindegyike igaz, és egyébként hamis. A természetes nyelv egyes összekapcsolói, például az angol, nem működnek igazság szerint.

Az "x úgy véli, hogy ..." formájú kapcsolók tipikus példák a nem igazság-funkcionális kapcsolatokra. Ha pl. Mary tévesen úgy véli, hogy Al Gore 2000. április 20-án az USA elnöke volt, de nem hiszi, hogy a hold zöld sajtból áll, akkor a mondat

" Mary úgy véli, hogy Al Gore 2000. április 20-án az USA elnöke volt "

igaz míg

" Mary úgy véli, hogy a hold zöld sajtból készül "

hamis. Mindkét esetben minden egyes mondat (azaz " Al Gore az USA elnöke volt 2000. április 20-án " és " a hold zöld sajtból készült ") hamis, de minden egyes összetett mondat a " Mary úgy véli, hogy "igazság-értékben különbözik. Azaz, az igazság-értéke egy mondat a forma „ Mária úgy véli, hogy ... ” nem határozható meg kizárólagosan az igazság-értéke az azt alkotó mondat, és így a (egyváltozós) összekötő (vagy egyszerűen üzemben mivel unary ) nem igazság-funkcionális.

A képletek felépítésénél használt klasszikus logikai kapcsolatok (pl. & , → ) osztálya igazság-funkcionális. A különféle igazságértékekre vonatkozó érveket általában igazságtáblák adják meg . Az igazság-funkcionális propozíciós számítás olyan formális rendszer, amelynek képletei igaznak vagy hamisnak is értelmezhetők.

A bináris igazság függvényeinek táblázata

A két értékes logika, ahol tizenhat lehetséges igazságfüggvények, más néven Boole-függvények , két bemenet P és Q . Ezen funkciók bármelyike ​​megfelel a klasszikus logika bizonyos logikai összekötőinek igazságtáblázatának , beleértve számos degenerált esetet, például egy függvényt, amely nem függ egyik vagy mindkét argumentumától. Az igazságot és a hamisságot a rövidség kedvéért az alábbi igazságtáblákban 1-nek, illetve 0-nak jelöljük.

Ellentmondás / hamis Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram ${\ displaystyle \ bot}$ "alsó" P ∧ ¬ P O pq   Q 0 1 P 0    0   0  1    0   0	Tautológia / Igaz Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram ${\ displaystyle \ top}$ "top" P ∨ ¬ P V pq   Q 0 1 P 0    1   1  1    1   1
P tétel Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P p I pq   Q 0 1 P 0    0   0  1    1   1	P tagadása Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram ¬ P ~ P N p F pq   Q 0 1 P 0    1   1  1    0   0
Q tétel Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram Q q H pq   Q 0 1 P 0    0   1  1    0   1	Q tagadása Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram ¬ Q ~ Q N q G pq   Q 0 1 P 0    1   0  1    1   0
Konjunkció Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P ∧ Q P & Q P   ·   Q P  ÉS  Q P ↛¬ Q ¬ P ↚ Q ¬ P ↓ ¬ Q K pq   Q 0 1 P 0    0   0  1    0   1	Alternatív tagadás Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram 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
Disszjunkció Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P ∨ Q P  VAGY  Q P ← ¬ Q ¬ P → Q ¬ P ↑ ¬ Q ¬ (¬ P ∧ ¬ Q ) A pq   Q 0 1 P 0    0   1  1    1   1	Közös tagadás Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P ↓ Q P  NOR  Q P ↚ ¬ Q ¬ P ↛ Q ¬ P ∧ ¬ Q X pq   Q 0 1 P 0    1   0  1    0   0
Anyagi egyszerűség Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P ↛ Q P Q P Q${\ displaystyle \ not \ supset}$ ${\ displaystyle>}$ P ∧ ¬ Q ¬ P ↓ Q ¬ P ↚ ¬ Q L pq   Q 0 1 P 0    0   0  1    1   0	Anyagi vonzat Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P → Q P ⊃ Q P Q${\ displaystyle \ leq}$ P ↑ ¬ Q ¬ P ∨ Q ¬ P ← ¬ Q C pq   Q 0 1 P 0    1   1  1    0   1
Converse nonimplication Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P ↚ Q P Q P Q${\ displaystyle \ not \ subset}$ ${\ displaystyle <}$ P ↓ ¬ Q ¬ P ∧ Q ¬ P ↛ ¬ Q M pq   Q 0 1 P 0    0   1  1    0   0	Fordított implikáció Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P ← Q P ⊂ Q P Q${\ displaystyle \ geq}$ P ∨ ¬ Q ¬ P ↑ Q ¬ P → ¬ Q B pq   Q 0 1 P 0    1   0  1    1   1
Kizárólagos diszjunkció Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P ↮ Q P ≢ Q P ⨁ Q P  XOR  Q P ¬ Q ¬ P Q ¬ P ↮ ¬ Q J pq${\ displaystyle \ leftrightarrow}$ ${\ displaystyle \ leftrightarrow}$   Q 0 1 P 0    0   1  1    1   0	Kétfeltételes Jelölés Ekvivalens képletek Igazság táblázat Venn-diagram P Q P ≡ Q P  XNOR  Q P  IFF  Q${\ displaystyle \ leftrightarrow}$ P ↮ ¬ Q ¬ P ↮ Q ¬ P ¬ Q E pq${\ displaystyle \ leftrightarrow}$   Q 0 1 P 0    1   0  1    0   1

Funkcionális teljesség

Mivel egy függvény kifejezhető kompozícióként , az igazság-funkcionális logikai számításnak nem kell külön dedikált szimbólumokkal rendelkeznie ahhoz, hogy az összes fent említett függvény funkcionálisan teljes legyen . Ez fejeződik ki a ítéletlogika a logikai ekvivalencia bizonyos összetett utasításokat. Például a klasszikus logika ¬ P  ∨  Q egyenértékű P  →  Q-val . A "→" feltételes operátor ezért nem szükséges egy klasszikus alapú logikai rendszerhez, ha a "¬" (nem) és a "∨" (vagy) már használatban van.

Az operátorok minimális halmazát, amely képes kifejezni a propozíciós számításban minden kifejezést, funkcionálisan minimális halmaznak nevezzük . Az operátorok minimálisan teljes készletét egyedül a NAND {↑} és a NOR önmagában {↓} érheti el.

Az alábbiakban bemutatjuk a minimálisan funkcionálisan teljes operátorkészleteket, amelyek aritása nem haladja meg a 2-et:

Egy elem

{↑}, {↓}.

Két elem

${\ displaystyle \ {\ vee, \ neg \}}$ , , , , , , , , , , , , , , , , , . ${\ displaystyle \ {\ wedge, \ neg \}}$${\ displaystyle \ {\ to, \ neg \}}$${\ displaystyle \ {\ gets, \ neg \}}$${\ displaystyle \ {\ to, \ bot \}}$${\ displaystyle \ {\ gets, \ bot \}}$${\ displaystyle \ {\ to, \ nleftrightarrow \}}$${\ displaystyle \ {\ gets, \ nleftrightarrow \}}$${\ displaystyle \ {\ to, \ nrightarrow \}}$${\ displaystyle \ {\ to, \ nlearrow \}}$${\ displaystyle \ {\ gets, \ nrightarrow \}}$${\ displaystyle \ {\ gets, \ nlearrow \}}$${\ displaystyle \ {\ nregyenes, \ neg \}}$${\ displaystyle \ {\ nleftarrow, \ neg \}}$${\ displaystyle \ {\ nregyenes, \ top \}}$${\ displaystyle \ {\ nleftarrow, \ top \}}$${\ displaystyle \ {\ nrightarrow, \ leftrightarrow \}}$${\ displaystyle \ {\ nleftarrow, \ leftrightarrow \}}$

Három elem

${\ displaystyle \ {\ lor, \ leftrightarrow, \ bot \}}$ , , , , , . ${\ displaystyle \ {\ lor, \ leftrightarrow, \ nleftrightarrow \}}$${\ displaystyle \ {\ lor, \ nleftrightarrow, \ top \}}$${\ displaystyle \ {\ land, \ leftrightarrow, \ bot \}}$${\ displaystyle \ {\ land, \ leftrightarrow, \ nleftrightarrow \}}$${\ displaystyle \ {\ land, \ nleftrightarrow, \ top \}}$

Algebrai tulajdonságok

Néhány igazságfüggvény olyan tulajdonságokkal rendelkezik, amelyek kifejezhetők a megfelelő kötőszót tartalmazó tételekben. A bináris igazság függvényének (vagy egy megfelelő logikai összekötőnek) ezek a tulajdonságai lehetnek:

• asszociativitás : Egy kifejezésben két vagy több ugyanazt az asszociatív összekötőt tartalmazó kifejezésben a műveletek sorrendje nem számít, amíg az operandusok sorrendje nem változik.
• kommutativitás : A kötődés operandusai felcserélhetők anélkül, hogy befolyásolnák a kifejezés igazságértékét.
• disztributivitás : A · jelöléssel ellátott összekötő eloszlik egy másik, + -gal jelölt összekötő felett, ha a · b ( c + c ) = ( a · b ) + ( a · c ) minden a , b , c operandusra .
• idempotencia : Amikor a művelet operandusai megegyeznek, a kötõ az operandust adja eredményül. Más szavakkal, a művelet egyszerre őrzi az igazságot és a hamisságot is (lásd alább).
• abszorpció : Egy összekötő pár kielégíti az abszorpciós törvényt, ha minden a , b operandus esetében . ${\ displaystyle \ land, \ lor}$${\ displaystyle a \ land (a \ lor b) = a}$

Az igazságfüggvények akkor és csak akkor teljesek, ha a következő öt tulajdonság mindegyikéhez tartalmaz legalább egy olyan tagot, amelyből hiányzik:

• monoton : Ha f ( a ₁ , ..., a _n ) ≤ f ( b ₁ , ..., b _n ) mind a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0,1} oly módon, hogy a ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . Pl . ${\ displaystyle \ vee, \ wedge, \ top, \ bot}$
• affin : Minden változó értékének megváltoztatása vagy mindig, vagy soha nem változtatja meg a művelet igazságértékét, az összes többi változó összes rögzített értéke esetén. Pl. , . ${\ displaystyle \ neg, \ leftrightarrow}$${\ displaystyle \ not \ leftrightarrow, \ top, \ bot}$
• self kettős : olvasásához az igazság-érték megbízások az üzemeltetés felülről lefelé annak igazság táblázat ugyanaz, mint vevő a komplement az olvasás lentről felfelé; más szóval, f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). Pl . ${\ displaystyle \ neg}$
• igazság megőrzése : A értelmezés, amely szerint minden változót rendelünk igazság érték „igazi” termel egy igaz értéke „true” eredményeként ezeket a műveleteket. Pl . (lásd érvényesség ) ${\ displaystyle \ vee, \ wedge, \ top, \ rightarrow, \ leftrightarrow, \ subset}$
• hamisítás megőrzése : Az az értelmezés, amely szerint az összes változóhoz a „hamis” igazságértéket rendelik , e műveletek eredményeként a „hamis” igazságértékét eredményezi. Pl . (lásd érvényesség ) ${\ displaystyle \ vee, \ wedge, \ nleftrightarrow, \ bot, \ not \ subset, \ not \ supset}$

Arity

Konkrét funkciót operátornak is nevezhetünk . Két értékű logikai van 2 nullary operátorok (állandók), 4 unáris operátorok , 16 bináris operátorok , 256 terner üzemeltetők , és n -aril üzemeltetők. A háromértékű logikában 3 nulla operátor (konstans), 27 unáris operátor , 19683 bináris operátor , 7625597484987 terner operátor és n- operátor van. A k -értékű logikában k nulla operátor, unár operátor, bináris operátor, hármas operátor és n operátor. A n értékű operátor a k -értékű logikában egy függvény . Ezért az ilyen operátorok száma megvan , így származtatták a fenti számokat. ${\ displaystyle 2 ^ {2 ^ {n}}}$ ${\ displaystyle 3 ^ {3 ^ {n}}}$ ${\ displaystyle k ^ {k}}$${\ displaystyle k ^ {k ^ {2}}}$${\ displaystyle k ^ {k ^ {3}}}$${\ displaystyle k ^ {k ^ {n}}}$ ${\ displaystyle \ mathbb {Z} _ {k} ^ {n} \ to \ mathbb {Z} _ {k}}$${\ displaystyle | \ mathbb {Z} _ {k} | ^ {| \ mathbb {Z} _ {k} ^ {n} |} = k ^ {k ^ {n}}}$

Egy adott aritás operátorainak egy része azonban valójában degenerált forma, amely alacsonyabb aritású műveletet hajt végre néhány bemeneten, és figyelmen kívül hagyja a többi bemenetet. A fent idézett 256 ternáris logikai operátor közül közülük a bináris vagy alacsonyabb aritású operátorok ilyen degenerált formái, a befogadás – kizárás elvét alkalmazva . A hármas operátor egy olyan operátor, amely valójában egy univerzális operátor, amelyet egy bemenetre alkalmaznak, és figyelmen kívül hagyja a másik két bemenetet. ${\ displaystyle {\ binom {3} {2}} \ cdot 16 - {\ binom {3} {1}} \ cdot 4 + {\ binom {3} {0}} \ cdot 2}$${\ displaystyle f (x, y, z) = \ lnot x}$

„Nem” egy egyváltozós üzemeltető , tart egy egységes kifejezés (¬ P ). A többiek bináris operátorok , két kifejezést használva egy összetett utasítás elkészítéséhez ( P ∧ Q , P ∨ Q , P → Q , P ↔ Q ).

A beállított logikai operátorok Ω lehet megosztjuk diszjunkt részhalmazai az alábbiak szerint:

${\ displaystyle \ Omega = \ Omega _ {0} \ cup \ Omega _ {1} \ cup \ ldots \ cup \ Omega _ {j} \ cup \ ldots \ cup \ Omega _ {m} \ ,.}$

Ebben a partícióban a j aritás operátorszimbólumainak halmaza . ${\ displaystyle \ Omega _ {j}}$

Az ismertebb propozíciós számológépben általában az alábbiak szerint osztjuk fel : ${\ displaystyle \ Omega}$

nulla operátorok: ${\ displaystyle \ Omega _ {0} = \ {\ bot, \ top \}}$

unary operátorok: ${\ displaystyle \ Omega _ {1} = \ {\ lnot \}}$

bináris operátorok: ${\ displaystyle \ Omega _ {2} \ subseteq \ {\ land, \ lor, \ rightarrow, \ leftrightarrow \}}$

A kompozicionalitás elve

Az igazságtáblák helyett a logikai kötőszimbólumok értelmezési funkcióval és az igazság-funkciók funkcionálisan teljes halmazával értelmezhetők (Gamut 1991), amint azt a jelentés összetételének elve részletezi . Hadd én lesz értelmezési funkciót, legyen Φ , Ψ bármely két mondatot, és hagyja, hogy az igazság függvény f _NAND szerint kell meghatározni:

• f _nand (T, T) = F; f _nand (T, F) = f _nand (F, T) = f _nand (F, F) = T

Ezután, a kényelem kedvéért, f _nem , f _vagy f _és és így tovább definiálják: a F _NAND :

• f _nem ( x ) = f _nand ( x , x )
• f _vagy ( x , y ) = f _nand ( f _nem ( x ), f _nem ( y ))
• f _és ( x , y ) = f _nem ( f _n ( x , y ))

vagy, alternatív módon f _nem , f _vagy f _és és így tovább meghatározása közvetlenül:

• f _nem (T) = F; f _nem (F) = T;
• f _vagy (T, T) = f _vagy (T, F) = f _vagy (F, T) = T; f _vagy (F, F) = F
• f _és (T, T) = T; f _és (T, F) = f _és (F, T) = f _és (F, F) = F

Azután

stb.

Tehát, ha S olyan mondat, amely a logikai kapcsolókat képviselő v ₁ ... v _n logikai szimbólumokból és a c ₁ ... c _n nem logikus szimbólumokból álló szimbólumlánc , akkor és csak akkor, ha I ( v ₁ ) ... I ( V _n ) már előírt értelmezése v ₁ a v _n útján f _NAND (vagy bármely egyéb funkcionális teljes igazság-funkciók), majd az igazság-értékét határozzuk meg teljes egészében az igazság-értékei c ₁ ... c _n , azaz I ( c ₁ ) ... I ( c _n ) . Más szavakkal, ahogy elvártuk és megkívántuk, S csak az összes nem logikus szimbólumának értelmezése esetén igaz vagy hamis. ${\ displaystyle I (s)}$

Számítástechnika

A logikai operátorokat logikai kapuként valósítják meg a digitális áramkörökben . Gyakorlatilag az összes digitális áramkör (a fő kivétel a DRAM ) a NAND , NOR , NOT és az átviteli kapukból épül fel . A szokásos 2 bemenet helyett a 3 vagy több bemenettel rendelkező NAND és NOR kapuk meglehetősen gyakoriak, bár logikailag egyenértékűek a 2 bemenetes kapuk kaszkádjával. Az összes többi operátort úgy hajtják végre, hogy kettő vagy több fenti logikai kapu logikailag egyenértékű kombinációjára bontják őket.

A "egyedül NAND", "NOR egyedül" és a "NOT and AND" "logikai egyenértékűsége" hasonló a turingi ekvivalenciához .

Azt a tényt, hogy minden igazságfunkció kifejezhető önmagában a NOR segítségével, az Apollo útmutató számítógép bizonyítja .

Lásd még

Megjegyzések

Hivatkozások

• Ez árucikk anyag TruthFunction a PlanetMath , amely alatt licencelt Creative Commons Nevezd / Share-Alike License .

További irodalom

• Józef Maria Bocheński (1959), A matematikai logika précisje, francia és német változatból fordította Otto Bird, Dordrecht, Dél-Hollandia: D. Reidel.
• Alonzo Church (1944), Bevezetés a matematikai logikába , Princeton, NJ: Princeton University Press. Az igazságfüggvény történetének történetét lásd a Bevezetésben.