pathterminuspages/brkmnd.dk/aboutcontactabout me

Semantik

27-07-2017|Udsagnslogik

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

φψ_φ ∧ ψ
SSS
SFF
FSF
FFF

Disjunktion

φψ_φ ∨ ψ
SSS
SFS
FSS
FFF

Implikation

φψ_φ ⇒ ψ
SSS
SFF
FSS
FFS

Negation

φ_¬ φ
SF
FS

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).

pq_¬ qp ∧ ¬q¬(p ⇒ q)p ∧ ¬q ⇒ ¬(p ⇒ q)
SSFFFS
SFSSSS
FSFFFS
FFSFFS

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

φψ_φ ⇔ ψ
SSS
SFF
FSF
FFS

*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.

pq_p ∨ qp ∨ q ⇒ q
SSSS
SFSS
FSSS
FFFS

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