2. Predikaatlogica

Question 1

Waaruit bestaat het alfabet van de predikaatlogica?

Answer 1

• Propositieletters
• Logische connectieven en kwantoren
• Hulpsymbolen ) en (
• Een verzameling C van constanten
• Een verzameling P van predicaatletters
• Een verzameling F van functieletters
• Individuele variabelen

Question 2

Wat is een zin in de predikaatlogica?

Answer 2

Een formule zonder vrije variabelen

Voorbeeld: ∃xPx

Question 3

Waaruit bestaat een structuur D in de predikaatlogica?

Answer 3

Een domein D met daarin relaties R en operaties O

D mag nooit leeg zijn!

Question 4

Wat is de interpretatiefunctie I in de predikaatlogica?

Answer 4

Een functie die ons helpt formules te interpreteren en de toegang geeft tot de predicaatletters, functieletters, constanten en variabelen.

Question 5

Wat is een model M in de predikaatlogica?

Answer 5

De verzameling van een structuur D en haar interpretatiefunctie I ook genoteerd als (D, I)

Question 6

Wat is een model van een formule in de predikaatlogica?

Answer 6

Een paar M (D, I) waarbij geldt dat iedere bedeling b deze formule waar maakt

Question 7

Wat is een logische equivalentie in de predikaatlogica?

Answer 7

Twee formules ϕ en ψ zijn logisch equivalent als hun implicatie een geldig gevolg is die kan getrokken worden uit het niks onder elke model en elke bedeling

Question 8

Wanneer is een formule geldig gevolg van een formuleverzameling in de predikaatlogica?

Answer 8

Een formule ψ is een geldig gevolg van een formuleverzameling Σ als en slechts als voor elk model M en bedeling b geldt dat wanneer voor elke formule φ die deel uit maakt van de formuleverzameling Σ hun waardering waar is dat ook de waardering van ψ waar moet zijn.

Question 9

Wat is een tegenvoorbeeld in de predikaatlogica?

Answer 9

Een tegenvoorbeeld is een model samen met een bedeling die φ1,…,φn waar maakt en ψ onwaar

Question 10

Wanneer is een formule universeel geldig?

Answer 10

Een formule ψ is universeel geldig wanneer als deze een geldig gevolg is uit niets

Alle waarderingen maken de formule (=1) bij elke model en elke bedeling

Question 11

De algemene prenexvorm van een formule

Answer 11

Q1 x1 … Qn xn ψ

ψ is een formule waar geen kwantoren meer in voorkomen

Question 12

Geef de inductieve definiëring van een term

Answer 12

1. variabelen en constanten zijn termen
2. als f een k-plaatsige functieletter is en t1… tk zijn termen, dan ook f(t1,…,tk)
3. niets anders is een term

Question 13

Geef de inductieve definiëring voor formules binnen de predikaatlogica

Answer 13

1. Als P een k-plaatsige predikaatletter is en t1… tk zijn termen, dan is P(t1,…,tk) een formule
2. Als φ en ψ formules zijn dan, ook hun combinaties m.b.v. de logische connectieven als φ een formule is en x een variabele, dan ook ∀x φ en ∃x φ
3. niets anders is een formule

Question 14

Wanneer is een variabele x vrij in een formule φ

Answer 14

Een voorkomen van een variabele x heet vrij als het niet binnen het bereik van de kwantor ∀x of ∃x ligt

Question 15

Hoe heet een formule zonder vrije variabele in de predikaatlogica?

Answer 15

een zin

Question 16

Wat is een oplossing om te garanderen dat de substitutie (van x door t in t’) veilig gebeurd en waarom?

Answer 16

1. Het invoeren van een alfabetische variant
2. Gebonden variabele worden dan vervangen door een nieuwe variabele (= letter)

Question 17

Welke voorkomens van x substitueren we bij het uitvoeren van substitutie (van x door t in t’)? Kies uit vrij of gebonden.

Answer 17

Vrije voorkomens

Question 18

Wat is de waardering V M,b voor een constante in de predikaatlogica?

Answer 18

De waardering voor een term indien deze een constante is, is de interpretatie van die constante

V M,b (a) = I(a)

Question 19

Wat is de waardering V M,b voor een functie in de predikaatlogica?

Answer 19

De interpretatie van die functie en de oplossing van elke waardering waarop deze functie op wordt toegepast

V M,b(f (t1,…,tk)) = I(f) (V M,b (t1),…,V M,b (tk))

Question 20

Welke factoren bepalen de waarheidswaarde van een formule?

Answer 20

De structuur D, de interpretatiefunctie I en het effect van de bedeling op de vrije variabelen in die formule.

Question 21

Hoe bepalen we de waarheidswaarde voor een zin?

Answer 21

Dat gaat niet aangezien deze geen vrije variabelen heeft

We kunnen geen bedeling uitvoeren

Question 22

Zijn logische equivalente formules, universeel geldige formules? Zo ja, waarom?

Answer 22

Een formule ψ is universeel geldig wanneer deze een geldig gevolg is uit niets; een logisch equivalente formule is per definitie een geldige gevolgtrekking uit het niets