Matematik/Diskret matematik/Logik/Predikatlogik

Från Wikibooks
Diskret matematik

Introduktion | Kombinatorik | Mängder | Logik (Satslogik/Predikatlogik) | Talteori
Formelsamling/Matematik | Matematikportalen





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.

Predikatlogisk sanning

Predikatlogisk konsekvens

Predikatlogisk ekvivalens