Totuusfunktio - Truth function

On logiikka , joka on totuusfunktio on funktio , joka hyväksyy totuusarvojen syötteenä ja tuottaa ainutlaatuisen totuusarvo lähtönä. Toisin sanoen: Totefunktion syöttö ja lähtö ovat kaikki totuusarvoja; totuusfunktio tuottaa aina täsmälleen yhden totuusarvon; ja samat totuusarvot syötetään aina samalla totuusarvolla. Tyypillinen esimerkki on ehdotuslogiikassa , jossa yhdistetty käsky rakennetaan käyttämällä yksittäisiä lauseita, jotka on yhdistetty loogisilla kytkentöillä ; Jos yhdistetyn lauseen totuusarvo määräytyy kokonaan osatekijän (lausekkeiden) totuusarvojen perusteella, yhdistettyä lausetta kutsutaan totuusfunktioksi , ja kaikkien käytettyjen loogisten kytkentöjen sanotaan olevan totuuden toiminnallisia .

Klassinen lauselogiikka on totuusfunktionaalinen logiikka, koska jokaisella lausunnolla on täsmälleen yksi totuusarvo, joka on joko tosi tai väärä, ja jokainen looginen liitos on totuuden toiminnallinen (vastaavan totuuden taulukon kanssa ), joten jokainen yhdistetty lausuma on totuusfunktio. Toisaalta modaalilogiikka ei ole totuudenmukaista.

Yleiskatsaus

Looginen sidekudoksen on totuus-toiminnallinen jos totuus-arvo yhdisteen lause on funktio totuus-arvo sen osa-lauseita. Kytkentäluokka on totuudenmukainen, jos kukin sen jäsenistä on. Esimerkiksi liitos " ja " on totuusfunktionaalinen, koska lause, kuten " Omenat ovat hedelmiä ja porkkanat ovat vihanneksia ", on totta , ja vain, jos jokainen sen ala lauseista " omenat ovat hedelmiä " ja " porkkanat ovat vihanneksia " on totta, ja se on väärä muuten. Jotkut luonnollisen kielen liitännät, kuten englanti, eivät ole totuudenmukaisia.

Muodon "x uskoo, että ..." liitännät ovat tyypillisiä esimerkkejä liitännöistä, jotka eivät ole totuudenmukaisia. Jos esimerkiksi Mary uskoo virheellisesti, että Al Gore oli Yhdysvaltain presidentti 20. huhtikuuta 2000, mutta hän ei usko, että kuu on valmistettu vihreästä juustosta, niin lause

" Mary uskoo, että Al Gore oli Yhdysvaltojen presidentti 20. huhtikuuta 2000 "

on totta kun

" Mary uskoo, että kuu on valmistettu vihreästä juustosta "

on väärä. Molemmissa tapauksissa jokainen komponenttilause (eli " Al Gore oli Yhdysvaltain presidentti 20. huhtikuuta 2000 " ja " kuu on valmistettu vihreästä juustosta ") on väärä, mutta jokainen yhdistetty lause, joka on muodostettu etuliitteellä " Mary uskoo, että "eroaa totuusarvosta. Eli totuus-arvo lauseen muotoa " Marian mielestä ... " ei määritellä pelkästään totuuden arvon komponentti- lauseen, ja siten (yksipaikkainen) yhdistäviä (tai yksinkertaisesti toimija , koska se on yksipaikkainen ) ei ole totuudenmukainen.

Kaavojen rakentamisessa käytetty klassisten logiikan liitoskohtien (esim. & , → ) luokka on totuusfunktionaalinen. Niiden arvot erilaisille totuusarvoille argumenttina annetaan yleensä totuustaulukoissa . Totuus-toiminnallinen proposition laskenta on muodollinen järjestelmä, jonka kaavat voidaan tulkita joko oikeiksi tai vääriksi.

Binaaristen totuusfunktioiden taulukko

Kaksi-arvo logiikka, on kuusitoista mahdollista totuusfunktio, jota kutsutaan myös Boolen toimintoja , on kaksi tuloa P ja Q . Mikä tahansa näistä funktioista vastaa klassisen logiikan tietyn loogisen liitoksen totuustaulukkoa, mukaan lukien useita rappeutuneita tapauksia, kuten funktio, joka ei riipu yhdestä tai molemmista sen argumenteista. Totuus ja valhe on merkitty vastaavasti 1 ja 0 seuraavissa totuustaulukoissa lyhyyden vuoksi.

Ristiriita / väärä Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio ${\ displaystyle \ bot}$ "pohja" P ∧ ¬ P O pq   Q 0 1 P 0    0   0  1    0   0	Tautologia / totta Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio ${\ displaystyle \ top}$ "alkuun" P ∨ ¬ P V pq   Q 0 1 P 0    1   1  1    1   1
Ehdotus P Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio P p I pq   Q 0 1 P 0    0   0  1    1   1	P: n kieltäminen Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio ¬ P ~ P N p F pq   Q 0 1 P 0    1   1  1    0   0
Ehdotus Q Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio Q q H pq   Q 0 1 P 0    0   1  1    0   1	Q: n kieltäminen Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio ¬ Q ~ Q N q G pq   Q 0 1 P 0    1   0  1    1   0
Yhdistelmä Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio P ∧ Q P & Q P   ·   Q P  JA  Q P ↛¬ Q ¬ P ↚ Q ¬ P ↓ ¬ Q K pq   Q 0 1 P 0    0   0  1    0   1	Vaihtoehtoinen kieltäminen Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio 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
Disjunktio Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio P ∨ Q P  TAI  Q P ← ¬ Q ¬ P → Q ¬ P ↑ ¬ Q ¬ (¬ P ∧ ¬ Q ) A pq   Q 0 1 P 0    0   1  1    1   1	Yhteinen kieltäminen Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio P ↓ Q P  NOR  Q P ↚ ¬ Q ¬ P ↛ Q ¬ P ∧ ¬ Q X pq   Q 0 1 P 0    1   0  1    0   0
Aineellinen yksinkertainen Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio 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	Aineellinen merkitys Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio 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
Käänteinen yksinkertaistaminen Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio 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	Käänteinen merkitys Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio 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
Yksinomainen disjunktio Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio 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	Kaksivaiheinen Merkintä Vastaavat kaavat Totuus taulukko Venn-kaavio 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

Toiminnallinen täydellisyys

Koska funktio voidaan ilmaista koostumuksena , totuusfunktionaalisella loogisella laskennalla ei tarvitse olla erillisiä symboleja, jotta kaikki yllä mainitut toiminnot olisivat toiminnallisesti täydellisiä . Tämä on ilmaistu propositiologiikka kuin looginen vastaavuus tietyn yhdisteen lausuntoja. Esimerkiksi klassisella logiikalla on ¬ P  ∨  Q, joka vastaa P  →  Q: ta . Ehdollinen operaattori "→" ei siis ole välttämätön klassiseen pohjaiseen loogiseen järjestelmään, jos "¬" (ei) ja "∨" (tai) ovat jo käytössä.

Minimaalinen joukko toimijoita, jotka voivat ilmaista jokaisen lausuman ilmaistavissa on propositiologiikka kutsutaan minimaalinen toiminnallisesti täydellinen . Pelkästään NAND {↑} ja NOR yksin {↓} saavuttavat minimaalisen täydellisen operaattorijoukon.

Seuraavat ovat toiminnallisesti täydelliset operaattorisarjat, joiden aromit eivät ylitä 2:

Yksi elementti

{↑}, {↓}.

Kaksi elementtiä

${\ displaystyle \ {\ vee, \ neg \}}$ , , , , , , , , , , , , , , , , , . ${\ displaystyle \ {\ wedge, \ neg \}}$${\ displaystyle \ {\ to, \ neg \}}$${\ displaystyle \ {\ saa, \ neg \}}$${\ displaystyle \ {\ to, \ bot \}}$${\ displaystyle \ {\ saa, \ bot \}}$${\ displaystyle \ {\ to, \ nleftrightarrow \}}$${\ displaystyle \ {\ gets, \ nleftrightarrow \}}$${\ displaystyle \ {\ to, \ noightarrow \}}$${\ displaystyle \ {\ to, \ nleftarrow \}}$${\ displaystyle \ {\ gets, \ nrightarrow \}}$${\ displaystyle \ {\ gets, \ nleftarrow \}}$${\ displaystyle \ {\ nrightarrow, \ neg \}}$${\ displaystyle \ {\ nleftarrow, \ neg \}}$${\ displaystyle \ {\ noightarrow, \ top \}}$${\ displaystyle \ {\ nleftarrow, \ alkuun \}}$${\ displaystyle \ {\ nrightarrow, \ leftrightarrow \}}$${\ displaystyle \ {\ nleftarrow, \ leftrightarrow \}}$

Kolme elementtiä

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

Algebralliset ominaisuudet

Joillakin totuusfunktioilla on ominaisuuksia, jotka voidaan ilmaista lauseissa, jotka sisältävät vastaavan sidoksen. Jotkut näistä ominaisuuksista, joita binäärinen totuusfunktio (tai vastaava looginen liitos) voi olla, ovat:

• assosiatiivisuus : Lausekkeessa, joka sisältää kaksi tai useampia samoja assosiatiivisia kytkentöjä peräkkäin, operaatioiden järjestyksellä ei ole merkitystä, kunhan operandien järjestystä ei muuteta.
• kommutatiivisuus : Kytkimen operandit voidaan vaihtaa vaikuttamatta lausekkeen totta-arvoon.
• jakautuvuus : Kytkentä, joka on merkitty · jakautuu toisen, +: llä merkityn liitännän yli, jos a · b ( c + c ) = ( a · b ) + ( a · c ) kaikille operandeille a , b , c .
• idempotenssi : Aina kun operaation operandit ovat samat, liitos antaa operandin tuloksena. Toisin sanoen operaatio on sekä totuuden että vääryyden säilyttäminen (katso alla).
• absorptio : Kytkentäpari täyttää absorptiolain, jos kaikille operandeille a , b . ${\ displaystyle \ maa, \ lor}$${\ displaystyle a \ land (a \ lor b) = a}$

Joukko totuusfunktioita on toiminnallisesti täydellinen vain ja vain, jos se sisältää jokaiselle seuraavista viidestä ominaisuudesta ainakin yhden jäsenen, josta puuttuu se:

• yksitoikkoinen : Jos f ( a ₁ , ..., a _n ) ≤ f ( b ₁ , ..., b _n ) kaikille a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0,1} siten, että a ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . Esim . ${\ displaystyle \ vee, \ wedge, \ top, \ bot}$
• affiini : Jokaisen muuttujan arvon muuttaminen joko aina tai ei koskaan muuta operaation tosi-arvoa, kaikkien muiden muuttujien kaikille kiinteille arvoille. Esim. , . ${\ displaystyle \ neg, \ leftrightarrow}$${\ displaystyle \ not \ leftrightarrow, \ top, \ bot}$
• itse kaksi : Lue totuus-arvojen osoituksia toiminnan ylhäältä alas sen totuustaulu on sama kuin ottaen täydentää sen lukeminen alhaalta ylöspäin; toisin sanoen f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). Esim . ${\ displaystyle \ neg}$
• totuuden säilyttäminen : Tulkinta, jossa kaikille muuttujille annetaan tosi-arvo "tosi", tuottaa näiden toimintojen tuloksena tosi-arvon "tosi". Esim . (katso voimassaolo ) ${\ displaystyle \ vee, \ wedge, \ top, \ rightarrow, \ leftrightarrow, \ subset}$
• vääryyden säilyttäminen : Tulkinta, jonka mukaan kaikille muuttujille annetaan tosi-arvo 'väärä', tuottaa näiden toimintojen tuloksena tosi-arvon 'väärä'. Esim . (katso voimassaolo ) ${\ displaystyle \ vee, \ wedge, \ nleftrightarrow, \ bot, \ not \ subset, \ not \ supset}$

Arity

Konkreettista toimintoa voidaan kutsua myös operaattoriksi . Kaksi-arvo logiikka on 2 nullary operaattorit (vakioita), 4 unaarioperaattorit , 16 binaarinen operaattorit , 256 ternäärinen operaattorit , ja n aarinen operaattoreille. Kolmessa-arvo logiikka on 3 nullary operaattorit (vakioita), 27 unaarioperaattorit , 19683 binaarinen operaattorit , 7625597484987 ternäärinen operaattorit , ja n aarinen operaattoreille. In k -arvoiset logiikka, on k nullary operaattoreita, unaarioperaattorit, binaarinen operaattorit, kolmen komponentin operaattorit, ja n aarinen operaattoreille. N aarisen operaattori k -arvoiset logiikka on funktion . Siksi tällaisten operaattoreiden lukumäärä on , miten edellä olevat luvut on johdettu. ${\ 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}}}$

Jotkut tietyn ariteetin operaattoreista ovat tosiasiallisesti rappeutuneita muotoja, jotka suorittavat matalamman aritin operaation joillekin tuloille ja jättävät huomiotta loput tulot. Edellä mainituista 256 kolmiarvoisesta loogisesta operaattorista heistä ovat tällaisia ​​rappeutuneita binääristen tai matalampien operaattoreiden muotoja, joissa käytetään sisällyttämisen ja poissulkemisen periaatetta . Kolmikertainen operaattori on yksi sellainen operaattori, joka on tosiasiallisesti unaarinen operaattori, jota sovelletaan yhteen tuloon, ja jättää huomiotta kaksi muuta tuloa. ${\ displaystyle {\ binom {3} {2}} \ cdot 16 - {\ binom {3} {1}} \ cdot 4 + {\ binom {3} {0}} \ cdot 2}$${\ displaystyle f (x, y, z) = \ ei x x}$

"Not" on unaarinen operaattori , sillä on yksi termi (¬ P ). Loput ovat binaarisia operaattoreita , jotka muodostavat yhdistetyn lauseen kahdella termillä ( P ∧ Q , P ∨ Q , P → Q , P ↔ Q ).

Loogisten operaattorien joukko Ω voidaan jakaa osajoukkoihin seuraavasti:

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

Tämän osion, on joukko operaattorin symbolien arity j . ${\ displaystyle \ Omega _ {j}}$

Tunnetummassa proposition laskennassa se jaetaan tyypillisesti seuraavasti: ${\ displaystyle \ Omega}$

tyhjät operaattorit: ${\ displaystyle \ Omega _ {0} = \ {\ bot, \ top \}}$

unaariset operaattorit: ${\ displaystyle \ Omega _ {1} = \ {\ ei \ \}}$

binäärioperaattorit: ${\ displaystyle \ Omega _ {2} \ subseteq \ {\ land, \ lor, \ rightarrow, \ leftrightarrow \}}$

Koostumusperiaate

Sen sijaan, että käytetään totuustaulujen , looginen sidekudoksen symbolit voidaan tulkita avulla tulkinta funktio ja toiminnallisesti täydellisen sarjan totuus-toimintoja (väriasteikko 1991), kuten on esitetty yksityiskohtaisesti, että periaate compositionality merkitys. Olkoon I olla tulkintaa funktio, anna Φ , Ψ olla kaksi lausetta ja anna totuusfunktio f _NAND määritellään seuraavasti:

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

Sitten, mukavuussyistä, f _ei , f _tai f _ja ja niin edelleen on määritelty avulla f _NAND :

• f _ei ( x ) = f _nand ( x , x )
• f _tai ( x , y ) = f _nand ( f _ei ( x ), f _ei ( y ))
• f _ja ( x , y ) = f _ei ( f _nand ( x , y ))

tai vaihtoehtoisesti f _ei , f _tai f _ja ja niin edelleen on määritelty suoraan:

• f _ei (T) = F; f _ei (F) = T;
• f _tai (T, T) = f _tai (T, F) = f _tai (F, T) = T; f _tai (F, F) = F
• f _ja (T, T) = T; f _ja (T, F) = f _ja (F, T) = f _ja (F, F) = F

Sitten

jne.

Joten jos S on lause, joka on merkkijono, joka koostuu loogisista symboleista v ₁ ... v _{n, jotka} edustavat loogisia kytkentöjä, ja ei-loogisista symboleista c ₁ ... c _n , niin ja vain, jos I ( v ₁ ) ... I ( v _n ) on järjestetty tulkita v ₁ ja v _n avulla f _NAND (tai mikä tahansa muu joukko toiminnallisia täydellinen totuus-toimintoja), niin totuus-arvo määritetään kokonaan totuus-arvot c ₁ ... c _n , ts. I ( c ₁ ) ... I ( c _n ) . Toisin sanoen, kuten odotetaan ja vaaditaan, S on tosi tai väärä vain kaikkien ei-loogisten symbolien tulkinnassa. ${\ displaystyle I (t)}$

Tietokone Tiede

Loogiset operaattorit on toteutettu logiikka portit on digitaalisia piirejä . Käytännössä kaikki digitaaliset piirit (suurin poikkeus on DRAM ) on rakennettu NAND- , NOR- , NOT- ja lähetysportista . NAND- ja NOR-portit, joissa on vähintään 3 tuloa tavallisten 2 tulon sijasta, ovat melko yleisiä, vaikka ne vastaavatkin loogisesti 2-tuloisten porttien kaskadia. Kaikki muut operaattorit toteutetaan hajottamalla ne loogisesti vastaavaksi yhdistelmäksi kahdesta tai useammasta yllä olevasta logiikkaportista.

"Pelkkä NAND", "NOR yksin" ja "EI ja JA" "looginen vastaavuus" on samanlainen kuin Turingin vastaavuus .

Apollo-ohjaustietokone osoittaa sen, että kaikki totuusfunktiot voidaan ilmaista pelkästään NOR: n avulla .

Katso myös

Huomautuksia

Viitteet

• Tämä artikkeli sisältää materiaalia TruthFunction päällä PlanetMath , joka on lisensoitu Creative Commons Nimeä / Share-Alike .

Lisälukemista

• Józef Maria Bocheński (1959), Matematiikan logiikan käännös, ranskan- ja saksankielisistä versioista, kääntäjä Otto Bird, Dordrecht, Etelä-Hollanti: D. Reidel.
• Alonzo Church (1944), Johdatus matemaattiseen logiikkaan , Princeton, NJ: Princeton University Press. Katso totuusfunktion käsitteen historia johdannosta.