Totuusfunktio
Totuusfunktio on matemaattisen logiikan termi, joka tarkoittaa totuusarvon (tavallisesti "tosi" tai "epätosi") antamista väitelauseelle (propositio). Totuusfunktion tulee täyttää seuraavat aksioomat:
Tavallisessa Tosi/Epätosi-kaksiarvologiikassa totuusarvoa Tosi ilmaistaan usein bitillä formula_1 ja totuusarvoa Epätosi bitillä formula_2. Tällöin totuusfunktio on mikä tahansa funktio formula_3, jonka pituus on formula_2:aa suurempi kokonaisluku formula_5 ja joka saa arvon formula_2 tai formula_1 jokaista formula_5-pituista bittijonoa kohti. Esimerkiksi totuustaulussa
on kuvattu eräs formula_9-pituisista totuusfunktioista, jossa siis funktio formula_3 saa arvon formula_1 muun muassa silloin, kun formula_12-bittijonona on formula_13. Yleisesti tunnettu esimerkki formula_14-pituisista totuusfunktioista on propositiologiikan JA-konnektiivi, jossa formula_3-funktiomerkinnän tilalla on yleensä formula_16-merkki, joka lisäksi - niin kuin formula_14-paikkaisissa funktioissa useinkin - merkitään väliin edessä olemisen sijaan. Näillä merkinöillä JA-totuusfunktio on siis tällainen: formula_18 ja formula_19.
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 formula_20 on esimerkiksi formula_21, käytettävissä ovat bittimuuttujat formula_22 ja formula_23.) tai totuusfunktiosta tulevan bittiarvon. Esimerkiksi jos formula_24 ja formula_25 sekä formula_26 ja formula_27 ovat annetut totuusfunktiot, niin niistä voidaan yhdistellä muun muassa formula_21-paikkainen totuusfunktio formula_29 säännöllä formula_30, jolloin esimerkiksi formula_31. 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ä formula_32-bittimuuttuja ei esiintynyt lainkaan, mutta formula_23-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 formula_34 ja formula_35), 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 formula_36 on 0:n säilyttävä totuusfunktio täysin riippumatta siitä mitä arvoja se muilla syötteillä saa. Artikkelin alussa totuustaululla esitetty formula_37 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 formula_38 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 formula_39, mistä merkintää laajennetaan tavalliseen tapaan ottamaan huomioon myös yhtäsuuruus, jolloin esimerkiksi formula_40 ja formula_41, mutta formula_42 ei ole voimassa. Nyt järjestys laajennetaan useammasta totuusarvosta koostuvalle syötteelle niin, että syöte formula_43 on pienempi tai yhtäsuuri kuin syöte formula_44, jos tämä on voimassa erikseen kullakin syötteen totuusarvolla yllä määritellyn totuusarvojen välisen järjestyksen suhteen. Esimerkiksi formula_45, mutta formula_46 ei ole voimassa, koska vasemmanpuoleisessa syötteessä kolmas ja viides bittimuuttuja on arvoltaan aidosti suurempi (siis formula_47-tilanne) kuin vastaava kohta oikeanpuoleisessa syötteessä. Tässä tapauksessa kuitenkaan myöskään formula_48 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ä formula_43 ja formula_44 olisi voimassa se, että joko formula_51 tai formula_52.)
Nyt voidaan määritellä totuusfunktion isotonisuus.
Totuusfunktio formula_37 on isotoninen, jos sen kaikilla vertailtavissaolevilla syötteillä formula_51 on voimassa formula_55, 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 formula_37 ei ole isotoninen, sillä mm. formula_57, mutta formula_58 ei ole voimassa. Sen sijaan (formula_59)-totuusfunktio on isotoninen, sillä siinä järjestysvertailtavissa olevat ei-samat syötteet ovat formula_60 ja formula_61 ja jokaisen kohdalla formula_62 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 formula_63 siinä missä kyseisen bittimuuttujan arvo on formula_64 ja päinvastoin. (Esimerkiksi artikkelin alun totuustaulun formula_37-totuusfunktiolla on tällaiset syötteet, kun syötteiksi valitaan formula_66, 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 (formula_67), jonka käyttö voidaan laajentaa myös useammasta bittimuuttujasta koostuvaan syötteeseen soveltamalla EI-konnektiivia kuhunkin bittimuuttujaan erikseen.
(esimerkiksi formula_68) Totuusfunktion formula_37 koon ollessa formula_70 se on itseduaalinen, jos sen kaikilla syötteillä formula_71
formula_72 on voimassa. Toisin sanoen tämä tarkoittaa sitä, että funktion arvo muuttuu aina vastakkaiseksi, jos syötteessä kaikkien bittimuuttujien arvot muutetaan vastakkaisiksi. Esimerkiksi formula_73-totuusfunktio on itseduaalinen, ja tätä vaatimusta toteuttaa osaltaan se, että siinä mm. formula_74.