首页 > 代码库 > 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: 

  1. 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$.
  2. $\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$.   
  3. $\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