Syntaxis en semantiek

Alfabet

Geeft aan welke symbolen gebruikt mogen worden om uitdrukkingen in de taal te maken.

Een alfabet van de propositielogica bestaat uit:

1. Een verzameling propositieletters.
2. Logische symbolen: ¬, ∧,∨ ,→ ,↔
3. Hulpsymbolen: ) en ( .

Syntaxis

De grammatica van een taal. De set van regels die aangeeft op welke manier uidrukkingen van de taal gevormd mogen worden.

Semantiek

De betekenis van uitdrukkingen.

Propositie

Een bewering of uitspraak, uitgedrukt in een zin.

Logische Symbolen

Synoniemen: logische voegwoorden, connectieven

Verbinden proposities en kunnen samengestelde uitdrukkingen vormen.

• ¬ , niet
• ∧ , en
• ∨ , of
• → , als ... dan ...
• ↔ , dan en slechts dan als
• NOR, noch ...noch ...

Formule

De formules van de propositielogica worden als volgt gedefinieerd:

1. Elke propositieletter is een formule;
2. Als φ en ψ formules zijn, dan zijn ¬ φ, ( φ ∧ ψ ), ( φ ∨ ψ ), ( φ → ψ ) en ( φ ↔ ψ ) ook formules.
3. Niets anders is een formule.

Dit is inductief bewijs.

Inductieve definitie

Een inductieve definitie heeft drie kenmerkende onderdelen:

1. Een basisstap waarin bepaalde dingen meteen tot objecten van de gewenste soort verklaard worden.
2. Eén of meer opbouwstappen die verdere constructieprincipes geven om objecte te maken.
3. Een afsluitende stap die bepaalt dat alles wat niet in eindig veel stappen met behulp van 1 en 2 gevormd kan worden, geen toegestaan object is.

Substitutie

Notatie: substitutie van ψ voor p in φ ↔ [ ψ / p ] φ.

Hiermee bedoelen we de formule die onstaat als alle ψ in φ worden vervangen met p.

Constructieboom

Notatie:

Het opbouwen van een formule uit een aantal atomen met behulp van connectieven, weergegeven in een boomstructuur.

Waarheidstabel

Notatie:

Een tabel met daarin alle combinaties van de waarheidswaarden van bv. p en q.
Elke rij in deze waarheidstable correspondeert met een bepaalde situatie waarvoor de waarheidswaarden vastliggen.

Waardering

Synoniemen: situatie, valuation.
Notatie: V( )

De functie van alle propositie letters naar een waardering.

Model

Notatie: verzameling modellen van een formule: MOD(φ) = { V | V(φ) = 1 }

De waardering V heet een model van een formule φ als geldt: V(φ) = 1.

Model van een formuleverzameling

Een waardering V heet een model van een formuleverzameling ∑ als zij model is van elke φ ∈ ∑.

Tautologie

Als elke waardering van een formule φ ook meteen een model is van φ. bv.: ( φ ∨ ¬ φ ).
Ofwel als voor elke waardering V geldt: V(φ) = 1.

Logisch equivalent

Twee formules φ en ψ heten logisch equivalent als de formule ( φ ↔ ψ ) een tautologie is.

Functioneel volledig

C is een verzameling van connectieven. {¬, ∨}
C heet functioneel volledig als elke formule φ logisch equivalent is met een formule ψ die slechts connectieven uit C bevat.

Waarheidsfunctie

Een functie van {0, 1}^k naar {0, 1} heet een k-plaatsige waarheidsfunctie.

Disjunctieve normaalvorm

Notatie: ( φ₁ ∧ ... ∧ φ_n1 ) ∨ ... ∨ ( ϰ₁ ∧ ... ∧ ϰ_nk)
Waarbij φ₁, ... , ϰ_nk atomen of negaties van atomen zijn.

Als φ een formule is, dan bestaat er een formule φ* in disjunctieve normaalvorm, zodat φ en φ* logisch equivalent zijn.
Normaalvormen zijn speciale syntactische vormen waarmee meer algemene vormen equivalent kunnen zijn.