Vervulbaarheidsequivalentie
Van Wikipedia
In de klassieke logica zijn twee proposities vervulbaarheidsequivalent als er voor beiden wel of voor beiden niet een toekenning van waar of onwaar aan de atomaire formules bestaat waardoor de proposities waar zijn (dit wordt ook wel het vervullen van een formule of propositie genoemd). Anders geformuleerd houdt het in dat als de ene formule vervulbaar is (of niet) dan is de andere dat ook (niet) en andersom. Vervulbaarheidsequivalentie wordt soms genoteerd als ≡sat waarbij sat verwijst naar het Engelse woord voor vervulbaarheid: satisfiability.
Een verschil met logische equivalentie is dat het bij twee vervulbaarheidsequivalente formules wel mogelijk kan zijn om de ene formule te vervullen terwijl de andere met dezelfde toekenning niet vervuld wordt. Bij logische equivalentie geeft elke toekenning van waar of onwaar aan de atomaire formules dezelfde waarheidswaarde. Logische equivalentie is in dat opzicht stricter dan vervulbaarheidsequivalentie.
Een voorbeeld van vervulbaarheidsequivalentie:
Deze formules zijn niet logisch equivalent want bij A = waar en P = onwaar is A waar terwijl P ∧ (¬ P ∨ A) onwaar is. Dit is bijvoorbeeld te zien in de waarheidstabel (met T = true / waar en F = false / onwaar):
| P | A | ¬P | ¬P ∨ A | P ∧ (¬P ∨ A) |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | F |
| F | F | T | T | F |
De formules zijn wel vervulbaarheidsequivalent want er bestaat een toekenning die beiden formules waar maakt, namelijk A = waar en P = waar. Dit is te zien in de bovenste rij van de waarheidstabel.
