Propositional Logic(1)

Let me introduce some symbols which are used for propositional logic.

 

 

Sentential connectives : $\neg$, $\wedge$,$\vee$, $\rightarrow$, $\leftrightarrow$

 

and with parentheses, we call them logical symbols

 

nonlogical symbol : sentence symbols($A_1, A_2, \cdots$) whose interpratation is upon the natural language. thus meaning of nonlogical symbols is unfixed.

 

we define symbol is distinct from each other. that is, any symbol is not a finite sequence of others; $\rightarrow \neq \wedge$, $A_1 \neq A_2$, $A_1 \neq \wedge$

 

thus any sequence of symbols is unique. that is, if $<x_1, x_2, \cdots, x_n>= <y_1, y_2, \cdots, y_m>$, then $m=n$, $x_i = y_i$ for all $i$

 

for conveniene, we'll omit '<', '>', ',' for a sequence. one example of this is $<(, A_1, \rightarrow, A_2, )>$ $=$ $(A_1 \rightarrow A_2)$

 

define expression as a finite sequence of symbols. for some expressions, we'll call them well-formed formulas(wffs) when they meet below conditions.

 

1. any sentential symbol is wff.

2. If $\alpha$ and $\beta$ are wffs, then so are $(\neg \alpha), (\alpha \wedge \beta), (\alpha \vee \beta), (\alpha \rightarrow \beta), (\alpha \leftrightarrow \beta)$

3. no expression is a wff that is not made by process (1), (2).

 

 

 

define formula-building operations as below.

 

$\varepsilon _\neg (\alpha) = (\neg \alpha)$

$\varepsilon _\wedge(\alpha, \beta) = (\alpha \wedge \beta)$

$\varepsilon _\vee(\alpha, \beta) = (\alpha \vee \beta)$

$\varepsilon _\rightarrow(\alpha, \beta) = (\alpha \rightarrow \beta)$

$\varepsilon _\leftrightarrow(\alpha, \beta) = (\alpha \leftrightarrow \beta)$

 

define construction sequence as a finite sequence $<\epsilon_1, \epsilon_2, \cdots, \epsilon_n>$ of expressions where $\epsilon_i$ is a sentence symbol or $\epsilon_i = \varepsilon _\neg(\epsilon_j)$ where for some $j<i$, or $\epsilon_i = \varepsilon_x(\epsilon_j, \epsilon_k)$ for some $j<i, k<i$ where x is any sentential connective.

 

using above definitions, we can check any wff $\alpha$ corresponds with some construction sequence that ends with $\alpha$. then using strong mathematical induction, induction principle is established.

 

Induction principle : let $\mathbb{S}$ is a set of wffs which contains all sentence symbols and closed under five formula-building operations. then $\mathbb{S}$ is the set of all wffs.