Totuusfunktio

Totuusfunktio on matemaattisen logiikan termi, joka tarkoittaa totuusarvon (tavallisesti tosi tai epätosi) antamista väitelauseelle (propositio).^[1] Totuusfunktion tulee täyttää seuraavat aksioomat:

• se antaa kullekin väitelauseelle totuusarvoksi joko toden tai epätoden (law of excluded middle)
• samalle väitelauseelle voidaan antaa vain yksi totuusarvo: joko tosi tai epätosi (law of contradiction)
• kaikki totuusfunktiot antavat loogisilla operaattoreilla (konnektiivi) muodostetuille yhdistetyille väitelauseille totuusarvon samalla tavalla niiden osien totuusarvojen perusteella.

Tavallisessa Tosi/Epätosi-kaksiarvologiikassa totuusarvoa Tosi ilmaistaan usein bitillä ${\displaystyle 1_{\mathbf {} }}$ ja totuusarvoa Epätosi bitillä ${\displaystyle 0_{\mathbf {} }}$. Tällöin totuusfunktio on mikä tahansa funktio ${\displaystyle f_{\mathbf {} }}$, jonka pituus on ${\displaystyle 0_{\mathbf {} }}$:aa suurempi kokonaisluku ${\displaystyle n_{\mathbf {} }}$ ja joka saa arvon ${\displaystyle 0_{\mathbf {} }}$ tai ${\displaystyle 1_{\mathbf {} }}$ jokaista ${\displaystyle n_{\mathbf {} }}$-pituista bittijonoa kohti. Esimerkiksi totuustaulussa

${\displaystyle x_{1}x_{2}x_{3}\mathbf {} }$	${\displaystyle f(x_{1}x_{2}x_{3})_{\mathbf {} }}$
${\displaystyle 000_{\mathbf {} }}$	${\displaystyle 1_{\mathbf {} }}$
${\displaystyle 001_{\mathbf {} }}$	${\displaystyle 1_{\mathbf {} }}$
${\displaystyle 010_{\mathbf {} }}$	${\displaystyle 1_{\mathbf {} }}$
${\displaystyle 011_{\mathbf {} }}$	${\displaystyle 1_{\mathbf {} }}$
${\displaystyle 100_{\mathbf {} }}$	${\displaystyle 0_{\mathbf {} }}$
${\displaystyle 101_{\mathbf {} }}$	${\displaystyle 1_{\mathbf {} }}$
${\displaystyle 110_{\mathbf {} }}$	${\displaystyle 0_{\mathbf {} }}$
${\displaystyle 111_{\mathbf {} }}$	${\displaystyle 0_{\mathbf {} }}$

on kuvattu eräs ${\displaystyle 3_{\mathbf {} }}$-pituisista totuusfunktioista, jossa siis funktio ${\displaystyle f_{\mathbf {} }}$ saa arvon ${\displaystyle 1_{\mathbf {} }}$ muun muassa silloin, kun ${\displaystyle x_{1}x_{2}x_{3}\mathbf {} }$-bittijonona on ${\displaystyle 101_{\mathbf {} }}$. Yleisesti tunnettu esimerkki ${\displaystyle 2_{\mathbf {} }}$-pituisista totuusfunktioista on propositiologiikan JA-konnektiivi, jossa ${\displaystyle f_{\mathbf {} }}$-funktiomerkinnän tilalla on yleensä ${\displaystyle \land }$-merkki, joka lisäksi - niin kuin ${\displaystyle 2_{\mathbf {} }}$-paikkaisissa funktioissa useinkin - merkitään väliin edessä olemisen sijaan. Näillä merkinöillä JA-totuusfunktio on siis tällainen: ${\displaystyle 0\land 0=0,0\land 1=0,1\land 0=0}$ ja ${\displaystyle 1\land 1=1}$.

Eri totuusfunktioita voi myös yhdistellä, jolloin saadaan edelleen jokin totuusfunktio. Yhdistämisessä bittimuuttujien tilalle saa mielivaltaisesti sijoittaa jonkin käytettävän bittimuuttujan (Bittimuuttujien määrä riippuu yhdistämisessä saatavan totuusfunktion halutusta pituudesta. Jos ${\displaystyle n_{\mathbf {} }}$ on esimerkiksi ${\displaystyle 5_{\mathbf {} }}$, käytettävissä ovat bittimuuttujat ${\displaystyle x_{1},x_{2},x_{3},x_{4}\mathbf {} }$ ja ${\displaystyle x_{5}\mathbf {} }$.) tai totuusfunktiosta tulevan bittiarvon. Esimerkiksi jos ${\displaystyle f(00)=0,f(01)=1,f(10)=1_{\mathbf {} }}$ ja ${\displaystyle f(11)=1_{\mathbf {} }}$ sekä ${\displaystyle g(00)=0,g(01)=1,g(10)=1_{\mathbf {} }}$ ja ${\displaystyle g(11)=0_{\mathbf {} }}$ ovat annetut totuusfunktiot, niin niistä voidaan yhdistellä muun muassa ${\displaystyle 5_{\mathbf {} }}$-paikkainen totuusfunktio ${\displaystyle y_{\mathbf {} }}$ säännöllä ${\displaystyle y(x_{1}x_{2}x_{3}x_{4}x_{5})=g(f(x_{3}g(x_{5}x_{5}))f(x_{4}x_{2}))_{\mathbf {} }}$, jolloin esimerkiksi ${\displaystyle y(10101)=g(f(1g(11))f(00))=g(f(10)0)=g(10)=1_{\mathbf {} }}$. Kaikkien bittimuuttujien tai käytettävissä olevien totuusfunktioiden ei tarvitse esiintyä yhdistelmässä, mutta toisaalta sama bittimuuttuja tai totuusfunktio saa esiintyä useamminkin kuin kerran. (Esimerkki-yhdistelmässä ${\displaystyle x_{1}\mathbf {} }$-bittimuuttuja ei esiintynyt lainkaan, mutta ${\displaystyle x_{5}\mathbf {} }$-bittimuuttuja ja molemmat käytettävissä olleet totuusfunktiot esiintyivät kahdesti.)

Jonkin kiinteän totuusfunktio-joukon (mahdollisesti äärettömän) kohdalla tärkeä kysymys on, onko tämä totuusfunktio-joukko täydellinen. Totuusfunktioiden joukon täydellisyydellä tarkoitetaan sitä, että joukon totuusfunktioita käyttäen voidaan ylläkuvatussa mielessä yhdistellä mikä tahansa haluttu totuusfunktio. Yleinen esimerkki täydellisestä totuusfunktio-joukosta on propositiologiikasta tutut JA- TAI- ja EI-konnektiivit (merkitään ${\displaystyle \land ,\lor }$ ja ${\displaystyle \lnot }$), sillä niitä käyttäen mikä tahansa totuusfunktio voidaan esittää disjunktiivisessa normaalimuodossa. Tässä tapauksessa täydellinen totuusfunktio-joukko sisältää kaksi 2-paikkaisia totuusfunktioita (JA ja TAI) sekä yhden 1-paikkaisen totuusfunktion (EI), mutta yleisessä tapauksessa annetut totuusfunktiot voivat olla pitempiä. Emil Post:n esittämän menetelmän avulla on mahdollista selvittää mistä tahansa totuusfunktio-joukosta, onko se täydellinen vai ei. Tämä menetelmä perustuu seuraavaksi esitettäviin totuusfunktio-luokkiin.

0P:

Tähän luokkaan kuuluvat 0:n säilyttävät totuusfunktiot. Tässä 0:n säilyttäminen tarkoittaa sitä, että totuusfunktion arvona on 0 silloin, kun syötteessä kaikkien bittimuuttujien arvona on 0. Esimerkiksi ${\displaystyle h(0000)=0}$ on 0:n säilyttävä totuusfunktio täysin riippumatta siitä mitä arvoja se muilla syötteillä saa. Artikkelin alussa totuustaululla esitetty ${\displaystyle f}$ ei ole 0:n säilyttävä totuusfunktio.

1P:

Tähän luokkaan kuuluvat 1:n säilyttävät totuusfunktiot. Tässä 1:n säilyttäminen määritellään aivan vastaavasti 0:n säilyttämiseen nähden. Esimerkiksi ${\displaystyle g(11)=1}$ on 1:n säilyttävä totuusfunktio.

Iso:

Tähän luokkaan kuuluvat isotoniset totuusfunktiot. Isotonisuuden määrittely perustuu järjestykseen, joka määritellään toisaalta yksittäisten totuusarvojen ja tätä kautta myös useista totuusarvoista (totuusarvo kutakin bittimuuttujaa kohti) koostuvien syötteiden välillä. Totuusarvojen välinen järjestys määritellään niin, että 0 on pienempi kuin 1 ("Tosi on suurempi kuin epätosi."), mikä merkitään ${\displaystyle 0<1}$, mistä merkintää laajennetaan tavalliseen tapaan ottamaan huomioon myös yhtäsuuruus, jolloin esimerkiksi ${\displaystyle 0\leq 1}$ ja ${\displaystyle 1\leq 1}$, mutta ${\displaystyle 1\leq 0}$ ei ole voimassa. Nyt järjestys laajennetaan useammasta totuusarvosta koostuvalle syötteelle niin, että syöte ${\displaystyle s}$ on pienempi tai yhtäsuuri kuin syöte ${\displaystyle t}$, jos tämä on voimassa erikseen kullakin syötteen totuusarvolla yllä määritellyn totuusarvojen välisen järjestyksen suhteen. Esimerkiksi ${\displaystyle s=100\leq 110=t}$, mutta ${\displaystyle 10101\leq 10010}$ ei ole voimassa, koska vasemmanpuoleisessa syötteessä kolmas ja viides bittimuuttuja on arvoltaan aidosti suurempi (siis ${\displaystyle 1>0}$-tilanne) kuin vastaava kohta oikeanpuoleisessa syötteessä. Tässä tapauksessa kuitenkaan myöskään ${\displaystyle 10010\leq 10101}$ ei ole voimassa (Nyt vasemmanpuoleisessa neljäs bittimuuttujan arvo on aidosti suurempi kuin oikeanpuoleisessa.), mikä tarkoittaa sitä, että nämä kaksi syötettä eivät ole vertailtavissa, eli on olemassa syötteitä, joita ei voi asettaa keskinäiseen järjestykseen, mikä tarkoittaa sitä, että annettu järjestys ei ole täydellinen. (Täydellisessä järjestyksessä kaikilla syötteillä ${\displaystyle s}$ ja ${\displaystyle t}$ olisi voimassa se, että joko ${\displaystyle s\leq t}$ tai ${\displaystyle t\leq s}$.)

Nyt voidaan määritellä totuusfunktion isotonisuus.

Totuusfunktio ${\displaystyle f}$ on isotoninen, jos sen kaikilla vertailtavissaolevilla syötteillä ${\displaystyle s\leq t}$ on voimassa ${\displaystyle f(s)\leq f(t)}$, eli funktio antaa aidosti pienemmälle syötteelle pienemmän tai yhtäsuuren arvon kuin suuremmalle syötteelle. (Jos syötteet ovat samat, silloin tietysti funktion antama totuusarvokin on sama.) Artikkelin alussa totuustaulussa esitetty totuusfunktio ${\displaystyle f}$ ei ole isotoninen, sillä mm. ${\displaystyle 000\leq 100}$, mutta ${\displaystyle f(000)=1\leq 0=f(100)}$ ei ole voimassa. Sen sijaan (${\displaystyle g(00)=0,g(01)=1,g(10)=0,g(11)=1}$)-totuusfunktio on isotoninen, sillä siinä järjestysvertailtavissa olevat ei-samat syötteet ovat ${\displaystyle 00\leq 10,00\leq 01,00\leq 11,01\leq 11}$ ja ${\displaystyle 10\leq 11}$ ja jokaisen kohdalla ${\displaystyle g}$ antaa vasemmanpuoleiselle pienemmälle syötteelle pienemmän tai yhtäsuuren totuusarvon kuin suuremmalle oikeanpuoleiselle.

Totuusfunktion osoittaminen ei-isotoniseksi totuustaulusta katsomalla onnistunee helpoiten löytämällä kaksi syötettä, jotka eroavat toisistaan vain yhden bittimuuttujan arvon suhteen ja joista funktion arvo on ${\displaystyle 1}$ siinä missä kyseisen bittimuuttujan arvo on ${\displaystyle 0}$ ja päinvastoin. (Esimerkiksi artikkelin alun totuustaulun ${\displaystyle f}$-totuusfunktiolla on tällaiset syötteet, kun syötteiksi valitaan ${\displaystyle f(000)=1>0=f(100)}$, joissa arvoltaan eroava syötteen bittimuuttuja on siis tässä tapauksessa ensimmäinen kolmesta.) On helposti osoitettavissa, että funktio on isotoninen tarkalleen silloin, kun tällaista syöteparia ei ole.

SD:

Tähän luokkaan kuuluvat itseduaaliset totuusfunktiot. Funktion itseduaalisuus perustuu sen "käyttäytymiseen" suhteessa EI-konnektiiviin (${\displaystyle \lnot 0=1,\lnot 1=0}$), jonka käyttö voidaan laajentaa myös useammasta bittimuuttujasta koostuvaan syötteeseen soveltamalla EI-konnektiivia kuhunkin bittimuuttujaan erikseen.

(esimerkiksi ${\displaystyle \lnot (10100)=\lnot 1\lnot 0\lnot 1\lnot 0\lnot 0=01011}$) Totuusfunktion ${\displaystyle f}$ koon ollessa ${\displaystyle n}$ se on itseduaalinen, jos sen kaikilla syötteillä ${\displaystyle x_{1}x_{2}\dots x_{n}}$

${\displaystyle f(\lnot x_{1}\lnot x_{2}\dots \lnot x_{n})=\lnot f(x_{1}x_{2}\dots x_{n})}$ on voimassa. Toisin sanoen tämä tarkoittaa sitä, että funktion arvo muuttuu aina vastakkaiseksi, jos syötteessä kaikkien bittimuuttujien arvot muutetaan vastakkaisiksi. Esimerkiksi ${\displaystyle (g(000)=0,g(001)=1,g(010)=0,g(011)=0,g(100)=1,g(101)=1,g(110)=0,g(111)=1)}$-totuusfunktio on itseduaalinen, ja tätä vaatimusta toteuttaa osaltaan se, että siinä mm. ${\displaystyle g(\lnot 0\lnot 0\lnot 1)=g(110)=0=\lnot 1=\lnot g(001)}$.

Tämä artikkeli tai osio on keskeneräinen. Voit auttaa Wikipediaa laajentamalla sivua. Lisää tietoa saattaa olla keskustelusivulla. Merkinnän syy: Yksi luokka on vielä esittämättä kuin myös se, että miten näiden luokkien perusteella päätellään totuusfunktio-joukon täydellisyys.

Katso myös

• Tautologia
• Totuustaulu
• Ekvivalenssi
• Implikaatio
• Totuusarvo

Lähteet