Forside/Blogaden
Tekster
UfNet
Musik
Nørderier
Linktree
FB
Om
Nu når vi har defineret hvad velformede formler er, kan vi tilskrive mening til ditto formler. Lad sand og falsk være givet ved \( \top \) hhv. \( \bot \), lad \( t \) være en sandhedsfunktion defineret som: $$ t : \mathcal{F} \rightarrow \{\top,\bot\} $$ hvor \( \mathcal{F} \) er mængden af velformede formler. Alternativt lad φ, ψ være velformede formler, og vi kan tilskrive mening ved hjælp af sandhedstabeller. Altså (vi skriver bare ud hvad \( t(\phi), \phi \in \mathcal{F} \) giver):
| φ | ψ | _ | φ ∧ ψ |
| ⊤ | ⊤ | ⊤ | |
| ⊤ | ⊥ | ⊥ | |
| ⊥ | ⊤ | ⊥ | |
| ⊥ | ⊥ | ⊥ |
| φ | ψ | _ | φ ∨ ψ |
| ⊤ | ⊤ | ⊤ | |
| ⊤ | ⊥ | ⊤ | |
| ⊥ | ⊤ | ⊤ | |
| ⊥ | ⊥ | ⊥ |
| φ | ψ | _ | φ → ψ |
| ⊤ | ⊤ | ⊤ | |
| ⊤ | ⊥ | ⊥ | |
| ⊥ | ⊤ | ⊤ | |
| ⊥ | ⊥ | ⊤ |
| φ | _ | ¬ φ |
| ⊤ | ⊥ | |
| ⊥ | ⊤ |
Så vi har altså at en konjunktion er sand kun i det tilfælde at begge operander er sande. Disjunktion er næsten omvendt. Den er er falsk kun i den situation hvor begge operander er falske. Det er den slags disjunktion der normalt bruges i logik. Den kaldes inklusiv da tilfældet \( \top \lor \top \) er sandt. En alternativ disjunktion er den ekslusive hvor \( \top \lor \top \) er falsk. Den ekslusive virker måske mere intuitiv, feks. kan det være virke underligt at "jeg har en hund eller jeg har en kat" er sandt i det tilfælde hvor "jeg" har begge dele. Endnu mærkeligere er det måske at "jeg gav dig 100kr eller jeg gav dig 200kr" er sandt i det tilfælde hvor jeg gave dig 300kr. Men nok om det. Implikation er lidt speciel. Den er falsk alene i det tilfælde at noget sandt medfører noget falsk. Feks. er det noget sludder at sige: "hvis jeg har 100kr, så har du en milliard" (jeg antager at du ikke har en milliard). På den anden side er det fint at sige noget a la: "hvis jeg har en milliard, har du en milliard". Jeg ved ikke hvad der er lettest: at prøve at opbygge en intuition om de her ting eller bare at acceptere at det er sådan det er defineret. Lige med den logik vi er igang med her, er der ikke så meget sandhed at holde styr på. Så her er det måske ok bare at acceptere sandhedstabellerne.
En sandhedstabel der kun har ⊤ i sidste kolonne, kaldes en tautologi. En sandhedstabel der kun har ⊥ i sidste kolonne, kaldes en kontradiktion, eller bare for absurd eller en modstrid. En sandhedstabel med en blanding kaldes for kontingent.
Vi kalder en mængde af konnektiver der kan beskrive alle andre konnektiver, for en adækvat mængde konnektiver. Ideen er at vi med nogle konnektiver kan danne andre konnektiver. Vi har at to velformede formler er logisk ækvivalente hvis de er ens i sidste kolonne. Vi angiver ditto ækvivalens med tegnet \( \equiv \). Feks. har vi: $$ \phi \land \psi \equiv \neg (\neg \phi \lor \neg \psi) $$ Det kan vi vise med en sandhedstabel:
| φ | ψ | φ ∧ ψ | ¬ (¬ φ ∨ ¬ ψ) |
| ⊤ | ⊤ | ⊤ | ⊤ |
| ⊤ | ⊥ | ⊥ | ⊥ |
| ⊥ | ⊤ | ⊥ | ⊥ |
| ⊥ | ⊥ | ⊥ | ⊥ |
Som det kan ses er de to sidste kolonner helt identiske, og de to udtryk er altså logisk ækvivalente. Vi kan blive yderligere formelle her. En implikation der vender begge veje, kaldes en biimplikation. Denne har konnektivet ↔. En biimplikation har følgende sandhedstabel:
| φ | ψ | _ | φ ↔ ψ |
| ⊤ | ⊤ | ⊤ | |
| ⊤ | ⊥ | ⊥ | |
| ⊥ | ⊤ | ⊥ | |
| ⊥ | ⊥ | ⊤ |
OK. Vi har at hvis \( \phi \leftrightarrow \psi \) er en tautologi for to formler \( \phi,\psi \), så er \( \phi \equiv \psi \).
Hvis mængden af konnektiver kun var ∧,∨,¬, har vi lige vist at vi kan sløjfe ∧ da vi kan skrive dette med brug af ∨ samt ¬. Her er disse to altså en adækvat mængde.
Lad en mængde af formler være givet som \( \Phi = \phi_1, \phi_2, \dots \). Vi siger at en eller anden formel, \( \psi \), følger af denne mængde når følgende er opfyldt: hvis alle formler i \( \Phi \) er sande, så er \( \psi \) det også. Vi kalder formler i \( \Phi \) for præmisser, og vi kalder \( \psi \) for konklusion. Formelt skriver vi: $$ \phi_1, \phi_2, \dots \vDash \psi $$ Ingen af symbolerne \( \equiv, \vDash \) er en del af vores logik. Derfor kalder vi dem metasymboler. Et eksempel på en følgeslutning er reglen modus ponens - en deduktiv måde at argumentere på. I ord skriver vi
Hvis jeg ved at fra p medfølger q. Og hvis jeg ved at p er sand Så ved jeg at q er sand
Formelt skriver vi det som: $$ p \rightarrow q, p \vDash q $$
Følgeslutninger kan koges ned til at følgende implikation er en tautologi: $$ ((p \rightarrow q) \land p) \rightarrow q $$ Vi kan tjekke efter med en sandhedstabel:
| p | q | (p → q) ∧ p | ((p → q) ∧ p) → q |
| ⊤ | ⊤ | ⊤ | ⊤ |
| ⊤ | ⊥ | ⊥ | ⊤ |
| ⊥ | ⊤ | ⊥ | ⊤ |
| ⊥ | ⊥ | ⊥ | ⊤ |
Tjek sidste række: bingo!
At konstruere sandhedstabeller er en udmattende og ydmygende opgave. Ved små formler som de viste er det ok. Men bliver formlerne mere komplicerede, bliver det hurtigt et helvede at holde styr på alle rækkerne og kolonnerne i tabellen. Hver variabel har en af to værdier - den er binær. Så der er \( 2^{k} \) kolonner for \( k \) forskellige variable. I næste afsnit ser vi på et (noget mere simpelt og elegant) bevissystem kaldet naturlig deduktion. Det er nemlig sådan at vi kan skifte som vi har lyst til mellem at bevise formler i naturlig deduktion og at vise at de følger med sandhedstabeller.
Index
Del
Terminus