Predikatlogik handlar om predikat, som är propositioner, består av variabler.

Predikatlogik - Definition

Ett predikat är ett uttryck för en eller flera variabler som bestäms på någon specifik domän. Ett predikat med variabler kan göras till en proposition genom att antingen auktorisera ett värde till variabeln eller genom att kvantifiera variabeln.

• Tänk på att E(x, y) betecknar 'x = y'
• Tänk på att X(a, b, c) betecknar 'a + b + c = 0'
• Tänk på att M(x, y) betecknar 'x är gift med y'.

Kvantifierare:

Variabeln av predikat kvantifieras av kvantifierare. Det finns två typer av kvantifierare i predikatlogik - Existentiell kvantifierare och Universalkvantifierare.

Existentiell kvantifierare:

Om p(x) är en proposition över universum U. Då betecknas den som ∃x p(x) och läses som 'Det finns minst ett värde i universum för variabel x så att p(x) är sant. Kvantifieraren ∃ kallas den existentiella kvantifieraren.

Det finns flera sätt att skriva en proposition, med en existentiell kvantifierare, dvs.

icke deterministiska finita automater

(∃x∈A)p(x) eller ∃x∈A så att p (x) eller (∃x)p(x) eller p(x) är sant för vissa x ∈A.

Universell kvantifierare:

Om p(x) är en proposition över universum U. Då betecknas den som ∀x,p(x) och läses som 'För varje x∈U, är p(x) sant.' Kvantifieraren ∀ kallas Universal Quantifier.

Det finns flera sätt att skriva en proposition, med en universell kvantifierare.

∀x∈A,p(x) eller p(x), ∀x ∈A Eller ∀x,p(x) eller p(x) är sant för alla x ∈A.

klass vs objekt java

Negation av kvantifierade förslag:

När vi förnekar en kvantifierad proposition, det vill säga när en universellt kvantifierad proposition förnekas, får vi en existentiellt kvantifierad proposition, och när en existentiellt kvantifierad proposition förnekas, får vi en universellt kvantifierad proposition.

De två reglerna för negation av kvantifierad proposition är följande. Dessa kallas också DeMorgans lag.

Exempel: Negera vart och ett av följande förslag:

1.∀x p(x)∧ ∃ y q(y)

Sol: ~.∀x p(x)∧ ∃ y q(y))
≅~∀ x p(x)∨∼∃yq (y) (∴∼(p∧q)=∼p∨∼q)
≅ ∃ x ~p(x)∨∀y∼q(y)

2. (∃x∈U) (x+6=25)

Sol: ~( ∃ x∈U) (x+6=25)
≅∀ x∈U~ (x+6)=25
≅(∀ x∈U) (x+6)≠25

3. ~( ∃ x p(x)∨∀ y q(y)

Sol: ~( ∃ x p(x)∨∀ y q(y))
≅~∃ x p(x)∧~∀ y q(y) (∴~(p∨q)= ∼p∧∼q)
≅ ∀ x ∼ p(x)∧∃y~q(y))

Propositioner med flera kvantifierare:

Propositionen som har mer än en variabel kan kvantifieras med flera kvantifierare. De multipla universella kvantifierarna kan ordnas i valfri ordning utan att ändra innebörden av den resulterande propositionen. Dessutom kan de multipla existentiella kvantifierarna ordnas i valfri ordning utan att ändra innebörden av propositionen.

Propositionen som innehåller både universella och existentiella kvantifierare, ordningen på dessa kvantifierare kan inte bytas ut utan att ändra innebörden av propositionen, t.ex. propositionen ∃x ∀ y p(x,y) betyder 'Det finns något x så att p (x, y) är sant för varje y.'

Exempel: Skriv negationen för vart och ett av följande. Bestäm om det resulterande påståendet är sant eller falskt. Antag att U = R.

1.∀ x ∃ m(x²

Sol: Negation av ∀ x ∃ m(x²2≧m). Betydelsen av ∃ x ∀ m (x²≧m) är att det finns för några x så att x²≧m, för varje m. Påståendet är sant eftersom det finns något större x så att x²≧m, för varje m.

2. ∃ m∀ x(x²

Sol: Negation av ∃ m ∀ x (x²2≧m). Betydelsen av ∀ m∃x (x²≧m) är att för varje m finns det för några x så att x²≧m. Påståendet är sant som för varje m, det finns för något större x så att x²≧m.

instans av java