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 16:09]
vkuncak
sav08:substitution_theorems_for_propositional_logic [2008/03/11 16:11]
vkuncak
Line 42: Line 42:
 ++++ ++++
  
-Corollary: if $\models F$, then $\models (subst(\sigma)(F))$ for every variable substitution $\sigma$.+**Corollary ​(tautology instances):** if $\models F$, then $\models (subst(\sigma)(F))$ for every variable substitution $\sigma$.
  
-Corollary: ​if $\models (F \leftrightarrow ​G)$ and $\sigma$ is a variable substitution,​ then $\models (subst(\sigma)(F) \leftrightarrow subst(\sigma)(G)$.+We say that two formulas are equivalent ​if $\models (F \leftrightarrow G)$.
  
-Does the theorem hold if $\sigmais ++not a variable substitution?​|No,​ because a general substitution could produce an arbitrary formula.+++**Lemma:** If $\models (F \leftrightarrow G)$ then for every interpretation $I$ we have $e(F)(I) = e(G)(I)$.
  
-We say that two formulas are equivalent ​if $\models (F \leftrightarrow G)$.+From the tautology instances Corrolary we obtain. 
 + 
 +**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.
  
 We next justify transforming formulas from inside. We next justify transforming formulas from inside.
- 
  
 We say that $\sigma = \{F_1 \mapsto G_1,​\ldots,​F_n \mapsto G_n\}$ is //​equivalence-preserving//​ iff for all $i$ where $1 \le i \le n$ we have $\models (F_i \leftrightarrow G_i)$. We say that $\sigma = \{F_1 \mapsto G_1,​\ldots,​F_n \mapsto G_n\}$ is //​equivalence-preserving//​ iff for all $i$ where $1 \le i \le n$ we have $\models (F_i \leftrightarrow G_i)$.
- 
-**Lemma**: If $\models (F \leftrightarrow G)$ then for every interpretation $I$ we have $e(F)(I) = e(G)(I)$. 
  
 **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))$.