Matematik/Diskret matematik/Logik/Predikatlogik

Predikatlogik

Predikatlogiska begrepp

Predikatlogiska kvantifikatorer

I predikatlogiken tillkommer två predikatlogiska kvantifikatorer:

• ∀ - för alla x
• ∃ - det finns minst ett x

Med dessa kan man uttrycka mängdförhållanden, t.ex kan satsen Allt består av atomer skrivas:

• ∀x består av atomer(x)

och satsen Det finns något som består av flera sorters atomer kan skrivas:

• ∃x består av flera sorters atomer(x)

Individområden

Man låter x stå för ett individområde. Exempel individområde = alla fågelarter:

• ¬∀x kan flyga(x) - Inte alla fågelarter kan flyga
• ∃x ¬(kan flyga)(x) - Det finns minst en av alla fågelarter som inte kan flyga

Kvantifikatorn binder en individvariabel i hela den efterföljande satsen. Om alla variabler är bundna sägs satsen vara sluten annars är den öppen. Exempelvis:

• ∀xR(x)∧S(x) - Sista förekomsten av x är inte bunden då första satsen slutar vid ∧-tecknet
• ∀x[R(x)∧S(x)] - Båda förekomsterna av x är bundna.

Vi låter L(x,y) stå för "x och y har samma färg" och sätter individområdet till alla legobitar.
Studera dessa två satser:

1. ∀y∃x L(x,y)
2. ∃x∀y L(x,y)

Sats nr 1 betyder "för alla legobitar y så finns minst en legobit x som har samma färg"
Sats nr 2 betyder "det finns minst en legobit x som för alla legobitar y har samma färg" (alla bitar har samma färg)

Logisk sanning inom predikatlogiken

För att en predikatlogisk sats av typen ∀xA(x) ska vara sann måste alla måste a(t) vara sann för hela individområdet.
Satsen ∃xA(x) är sann om A(t) är sann för minst en individ i individområdet och falsk om A(t) är falsk för hela individområdet.