首页 > 代码库 > Notes on Logic-lecture 1
Notes on Logic-lecture 1
Lecture 1-03.01.2017
1.1 Universal algebra
Defination: An algebrical vocabulary $\Omega$ consists of :
- A denumberable none-empty set $V=\{...,x,y,z\}$(variables).
- A set for $F_{n}$ for each $n\ge 1$.
- A set $F_{0}$.
Defination: An $\Omega- structure$consists of
- A nonempty set $A$
- $\forall \omega \in A ,\omega_{A}:A^{n}\rightarrow A$(n-ary map).
Example: A group $G$:
$|F_{0}|=1$: uinte:$e$
$|F_{1}|=1$: $ ()^{-1}:G\rightarrow G $
$|F_{2}|=1$: $ \times :G\times G \rightarrow G $
$|F_{n}|=0 , n\ge 3$
Defination: A homomorphism $f:\left( A, \left(\omega_{A}\right)_{\omega}\right) \longrightarrow \left( B, \left(\omega_{B}\right)_{\omega}\right) $ is a map
$f:A\longrightarrow B$ such that $\forall \omega $, the below gragh communicate:
$$\begin{array}[c]{ccc}
A^{n}&\stackrel{\omega_{A}}{\longrightarrow}&A\\
\Big\downarrow\scriptstyle{f^{n}}&&\Big\downarrow\scriptstyle{f}\\
B^{n}&\stackrel{\omega_{B}}{\longrightarrow}&B
\end{array}$$
Example: Free $\Omega-structure$ generated by $V$,denote by $\mathcal{L}(V)$.
elements of $\mathcal{L}(V)$:$terms$.
- each variable is a term
- if $\omega \in F_{n}$, and if $t_{1},\cdots ,t_{n}$ are terms,then $\omega( t_{1},\cdots ,t_{n})$ is a term.
$$\begin{array}[c]{ccccc}
V &\xrightarrow{i}&\mathcal{L}(V)\\
&\searrow{f}&\Big\downarrow\\
&&(A,(\omega{A})_{\omega})
\end{array}$$
In most time, we take$\left( A, \left(\omega_{A}\right)_{\omega}\right) =\mathbb{2}=\{0,1\}$
1.2 The language of Sentential(Proposition)Logic
symbols | berbos name |
( | left parenthesis |
) | right parenthesis |
$\neg$ | negation symbol |
$\vee$ | conjunction symbol |
$\wedge$ | disjunction symbol |
$\rightarrow$ |
condition symbol |
$\leftrightarrow$ |
bicondition symbol |
$\alpha$ |
sentence symbol |
$\beta$ |
sentence symbol |
$\dots$ |
$\dots$ |
Example: $\Omega-structure$ : $A=\{0,1\}$(true:$1$,false:$0$)
$\neg 0=1,\neg 1=0$,
$0\vee 0=0,0\vee 1=1\vee 0=1\vee 1=1$,
$0\wedge 0=1\wedge 0=0\wedge 1=0,1\wedge 1=1$
,$0\rightarrow 0=0\rightarrow 1=1\rightarrow 1=1,1\rightarrow 0=0$.
Let $X$ be the set of some sentence symbol and denote the set of all sentences generated by $X$ and these five function $\neg,\vee,\wedge,\rightarrow,\leftrightarrow$ by $P(X)$.
Defination:(Trueth Assignments) A truth assignment on $P(X)$ is a homomorphism $\bar{v}:\ P(X)\longrightarrow 2$ which is extended by $v:\ X\longrightarrow 2$.
$$\begin{array}[c]{ccccc}
X &\xrightarrow{i}&P(X)\\
&\searrow{v}&\Big\downarrow\\
&&2
\end{array}$$
\end{array}$$
Defination:
- A truth assignment $\bar{v}:\ P(X)\longrightarrow 2$ satisfies $\tau \in P(X)$ if $\bar{v}(\tau)=1$,then $\bar{v}(\neg \tau)=0$.
- $\Sigma \subseteq P(X)$ sententially implies $\tau \in P(X)$ if for any truth assignments $v:\ X\longrightarrow 2$ if $\bar{v}(\alpha)=1$ for all $\alpha \in \Sigma$, then $\bar{v}(\tau)=1$.Denote by $\Sigma \models \tau$.
- $\emptyset \models \tau$(i.e. $\forall v: \ X\longrightarrow 2,\ \bar{v}(\tau)=1$).
Tautology: $\tau$ is said to be a tautology if and only if $\models \tau$.
Hilbert definded these three types tautology which is now said to be axiom:
- $\mathscr{A}_{1}:\ \alpha \rightarrow (\beta \rightarrow \alpha)$.
- $\mathscr{A}_{2}:\ (\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow (\alpha \rightarrow \beta)\rightarrow (\alpha \rightarrow \gamma)$.
- $\mathscr{A}_{3}:\ \neg \neg \alpha \rightarrow \alpha$.
Let $\Omega\ =\{\perp,\rightarrow\}$ where $\perp$ is consistant and $\rightarrow$ is a binary operation. Then $2=\{0,1\}$ is a $\Omega-structure$.
Notes on Logic-lecture 1