LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
sav08:substitution_theorems_for_propositional_logic [2008/03/11 14:57]
vkuncak 		sav08:substitution_theorems_for_propositional_logic [2008/03/11 16:11]
vkuncak
Line 4: Line 4:
  
 Called metatheorems,​ because they are not formulas //within// the logic, but formulas //about// the logic. Called metatheorems,​ because they are not formulas //within// the logic, but formulas //about// the logic.
 +
 +From semantics we can prove the following lemma by induction.
 +
 +Lemma: if $I_1(p) = I_2(p)$ for every $p \in FV(F)$, then $e(F)(I_1)=e(F)(I_2)$.
  
 ===== Substitutions ===== ===== Substitutions =====
Line 38: Line 42:
 ++++ ++++
  
-Corrollary: if $I_1(p) = I_2(p)$ for every $p \in FV(F)$, then $e(F)(I_1)=e(F)(I_2)$.+**Corollary (tautology instances):** if $\models ​F$, then $\models ​(subst(\sigma)(F))$ for every variable substitution $\sigma$.
  
-Corollary: ​if $\models F$, then $\models (subst(\sigma)(F))$ for every variable substitution $\sigma$.+We say that two formulas are equivalent ​if $\models ​(F \leftrightarrow G)$.
  
-Corollary: if $\models (F \leftrightarrow G)$ and $\sigma$ is a variable substitution,​ then +**Lemma:** If $\models (F \leftrightarrow G)$ then for every interpretation ​$I$ we have $e(F)(I) = e(G)(I)$.
-\[ +
-    \models (subst(\sigma)(F) \leftrightarrow subst(\sigma)(G) +
-\]+
  
-++Does ​the theorem hold if $\sigma$ is not variable substitution?​|No.++ +From the tautology instances Corrolary we obtain.
- +
-We say that two formulas are equivalent if $\models (F \leftrightarrow G)$.+
  
-**Lemma**: If $\models (F \leftrightarrow G)$ then for every interpretation ​$I$ we have $e(F)(I) = e(G)(I)$.+**Corollary:** if $\models (F \leftrightarrow G)$ and $\sigma$ is a variable substitution,​ then $\models (subst(\sigma)(F) \leftrightarrow subst(\sigma)(G))$.
  
 +Does the theorem hold if $\sigma$ is ++not a variable substitution?​|No,​ because a general substitution could produce an arbitrary formula.++
  
 This theorem was about transforming formulas from the outside, ignoring the structure of certain subformulas. This theorem was about transforming formulas from the outside, ignoring the structure of certain subformulas.
Line 61: Line 61:
  
 **Theorem on Substituting Equivalent Subformulas**:​ if $\sigma$ is equivalence-preserving,​ then for every formula $F$ we have $\models (F \leftrightarrow (subst(\sigma)(F))$. **Theorem on Substituting Equivalent Subformulas**:​ if $\sigma$ is equivalence-preserving,​ then for every formula $F$ we have $\models (F \leftrightarrow (subst(\sigma)(F))$.
-