Udsagnslogik : Semantik - Nørderier/Teori

OBS! Denne artikel får stadig besøg ind i mellem. Den er ikke blevet opdateret siden jeg skrev den. Der er en masse tegn i artiklen der ikke er korrekt formateret. Indholdet her er i stedet på vej over på min engelsksprogede del af siden: https://brkmnd.com/pages/logic/Default.aspx?id=4.

Semantikken for udsagnslogik er givet ved sandhedstabeller.

Definition 1

1. Der er to sandhedsværdier nemlig S og F der står for sandt hhv. falsk.
2. En evaluering af en formel, φ, er en tildeling af en sandhedsværdi til ethvert atom i formlen.

Sandhedstabeller

Konjunktion

φ	ψ	_	φ ∧ ψ
S	S		S
S	F		F
F	S		F
F	F		F

Disjunktion

φ	ψ	_	φ ∨ ψ
S	S		S
S	F		S
F	S		S
F	F		F

Implikation

φ	ψ	_	φ ⇒ ψ
S	S		S
S	F		F
F	S		S
F	F		S

Negation

φ	_	¬ φ
S		F
F		S

Tautologi

⊤

S

Modstrid

⊥

F

Med sandhedstabellerne kan vi danne sammensatte udsagn hvor vi for at bevise dem løser hele tabellen. Vi siger derfor at semantikken er kompositorisk. Dette kan være ok hvis vi kun har med 2 eller 3 atomiske udsagn at gøre. Problemet er at sandhedstabeller er udtømmende, for at lave en skal vi tjekke alle muligheder. Det vil sige, at har vi 2 atomer, er der 2^2 = 4 muligheder. Generelt er der n atomer = 2^n muligheder. For 3 er der altså 8, for 4 16 osv. Dette bliver hurtigt uoverskueligt.

Eksempel(1)

Vi vil gerne vise p .and \not q .drarrow .not(p .drarrow q).

p	q	_	¬ q	p ∧ ¬q	¬(p ⇒ q)	p ∧ ¬q ⇒ ¬(p ⇒ q)
S	S		F	F	F	S
S	F		S	S	S	S
F	S		F	F	F	S
F	F		S	F	F	S

Definition1

Som det ses står der kun S i sidste kolonne. Er dette tilfældet, kaldes følgen for en tautologi. Står der kun F i sidste kolonne, kaldes følgen for en modstrid.

Som det yderligere ses er .not(p .drarrow q) .drarrow p .and \not q også en tautologi. Det vil altså sige at p .and \not q .dlrarrow \not(p .drarrow q) er en tautolgi (tabellen for ⇔ står herunder). Gælder en tautologi for ⇔, siger vi at de to sider er logisk ækvivalente. Vi skriver p .and \not q .equiv .not(p .drarrow q). ≡ kaldes et metategn.

Biimplikation

φ	ψ	_	φ ⇔ ψ
S	S		S
S	F		F
F	S		F
F	F		S

*En biimpplikation er simpelthen en implikation der vender begge veje.

Hvor vi under bevisteori skriver %phi_1, %phi_2, ... , %phi_n .assert %psi når der gælder %phi_1 .and %phi_2 .and ... .and %phi_n .drarrow %psi, kan vi skrive %phi_1, %phi_2, ... , %phi_n .sassert %psi når sandhedstabellen for implikationen er en tautologi.

Derudover gælder:

Definition2

%phi_1, %phi_2, ... , %phi_n .assert %psi .equiv %phi_1, %phi_2, ... , %phi_n .sassert %psi

Praktisk set er forskellen på en semantisk følge og en bevisteoretisk følge den at for førstnænvte skal vi vise alle mulige situationer for at vise at følgen gælder. For sidstnænvte skal vi blot lave beviset. Omvendt, for at vise at en konklusion ikke følger semantisk, skal vi blot finde et tilfælde med F i sidste kolonne. Skal vi vise at en følge ikke gælder bevisteoretisk, skal vi lave et udtømmende bevis.

Eksempel(2)

Vi vil gerne vise at p .or q .sassert q.

p	q	_	p ∨ q	p ∨ q ⇒ q
S	S		S	S
S	F		S	S
F	S		S	S
F	F		F	S

Sandhedstabllen for ⇒ er en tautologi, og vi har vist at følgen gælder.