1. Propositielogica Flashcards
Theoretische vragen bij propositielogica
Waaruit bestaat het alfabet van de propositielogica?
- propositieletters
- logische connectieven
- hulpsymbolen
Wat is een instantie van een formule?
Het invullen van een abstracte formule (formule met Griekse letters) met concrete formules uit de propositielogica
(φ ↔ ┐ψ) wordt bijvoorbeeld (p ↔ ┐q)
Wat is een waardering in de propositielogica?
Een waardering geeft aan elke propositieletter de waarde 0 of 1.
Wat is een model van een formule?
Een waardering V is een model van een formule als diegene de formule waarmaakt (= 1).
Hoe we erachter komen of een bepaalde waardering een model is, is door het gebruik van modeleliminatie
Wat is een tautologie in de propositielogica?
We krijgen een tautologie als elke waardering V een model is voor een formule ϕ
Wat is een contradictie in de propositielogica?
Geen enkele waardering is een model voor een formule, wat betekent dat er geen enkele waardering is waardoor V(φ) = 1
Wanneer zijn 2 formules logisch equivalent in de propositielogica?
Twee formules zijn logisch equivalent als φ, ψ en hun implactie (φ → ψ) een tautologie is.
Elke waardering zal een model zijn voor de implicatie.
Wat is de functionele volledigheid van connectieven in de propositielogica?
Een verzameling connectieven C is functioneel volledig als elke formule φ logisch equivalent is met een formule ψ, enkel bestaande uit connectieven uit C.
Voor elke formule φ is er een logische equivalent die opgebouwd is uit een verzameling connectieven C.
Wanneer staat een formule in disjuncte normaalvorm?
Een formule is in disjunctieve normaalvorm wanneer deze als een disjunctie van conjuncties is geformuleerd bestaande uit atomen of negaties van atomen
Disjunctie normaalvorm: (φ1 ∧…∧ φn1) ∨ … ∨ (X1 ∧…∧ Xnk)
Wanneer is een formule geldig gevolg van een andere?
Een formule ψ is een geldig gevolg van een formuleverzameling Σ als elke model van Σ ook model is van ψ.
Notatie: Σ ⊨ ψ
We krijgen een speciaal geval wanneer de formuleverzameling leeg is, dit zou betekenen dat ψ een geldig gevolg is zonder dat er wordt gespecifieerd van wat dus, “van alles”, ψ is een geldig gevolg van alles (= tautologie)
Wat is een tegenvoorbeeld in de propositielogica?
Een model voor de formuleverzameling Σ dat geen model is voor de formule ψ.
Wanneer is een formuleverzameling semantisch consistent bij semantische tableaus?
Een formuleverzameling Σ is semantisch consistent als deze een model heeft zodat alle waarderingen links van het sequent waar zijn en rechts onwaar.
Wat is de adequaatheidsstelling voor semantische tableaus?
De adequaatheidsstelling zegt dat semantische tableaus een correcte methode is om geldig gevolg te bewijzen. Omdat Ψ enkel geldig gevolg is van de formuleverzameling Σ als er een gesloten tableau is voor het sequent φ1,…φn o ψ en als alle semantische tableaus voor het sequent gesloten zijn.
Wanneer is een formule afleidbaar in de propositielogica?
Een formule φ is afleidbaar uit een verzameling aannames Σ als er een afleiding van φ bestaat op basis van de gegeven afleidingsregels waarin aan het eind alleen nog aannames uit Σ van kracht zijn.
Notatie: Σ ⊢ φ
Wat is een stelling in de propositielogica?
Wanneer φ afleidbaar is zonder aannames (= op het zicht), dan is deze een stelling met een lege verzameling.
