Equivalences are Interderivable/Proof 2
Jump to navigation
Jump to search
Theorem
If two propositional formulas are interderivable, they are equivalent:
- $\paren {p \dashv \vdash q} \dashv \vdash \paren {p \iff q}$
Proof
Let $v$ be an arbitrary interpretation.
Then by definition of interderivable:
- $\map v {p \iff q}$ if and only if $\map v p = \map v q$
Since $v$ is arbitrary, $\map v p = \map v q$ holds in all interpretations.
That is:
- $p \dashv \vdash q$
$\blacksquare$
Sources
- 1993: M. Ben-Ari: Mathematical Logic for Computer Science ... (previous) ... (next): Chapter $2$: Propositional Calculus: $\S 2.4$: Logical equivalence and substitution: Theorem $2.4.4$