A Mathematical Introduction to Logic -- Section 1.1/1.2

发表于 更新于 分类于 ， 阅读次数：

\(\def\tauequ{\mathbin{\vDash\style{display: inline-block; transform: scaleX(-1)}{\vDash}}}\) \(\def\Dashv{\mathbin{\style{display: inline-block; transform: scaleX(-1)}{\vDash}}}\) \(\def\DEF{\sf{D\scriptsize EF}.\quad}\) \(\def\DEFi{\sf{D\scriptsize EF}^*.\quad}\) \(\def\DEFn{\sf{D\scriptsize EF}_*.\quad}\) \(\def\DEFin{\sf{D\scriptsize EF}^*_*.\quad}\) \(\def\llbracket{\unicode{x27E6}}\) \(\def\rrbracket{\unicode{x27E7}}\) \(\def\PROOF{\sf{P\scriptsize ROOF}.\quad}\) \(\def\MYNOTE{\sf{M\scriptsize{Y}}\sf{N\scriptsize{OTE}}.\quad}\) \(\def\EXAMPLE{\bf\sf{E\scriptsize{XAMPLES}}\quad}\) 这是一个关于数理逻辑的读书笔记和学习总结, 书名是A Mathematical Introduction to Logic (以下简称AMIL), 作者Herbert B. Enderton, University of California

点击这里进入AMIL的目录

本文是Chapter 1, Section 1.1,和 1.2, 介绍命题逻辑的基本概念.

由于中文版错误太多, 大部分章节读的是英文第二版, 所以笔记也是中英文夹杂着写的. 英文一般是关键原文. 中文有的是原文的翻译, 有的是我自己的理解, 还有的是 为了做练习写的证明和计算过程.

前缀关键字的含义:

  • \(\DEF\) : 表明后面是概念定义.
  • \(^*\) : 表明后面内容并不是数学上的精确表达.
  • \(_*\) : 表明后面的内容并不来自于这本书.
  • \(\MYNOTE\) : 后面的内容是我用自己的话做的总结,或心得体会

Chapter One. Sentential Logic 命题逻辑

Section 1.1 The language of Sentential Logic 命题逻辑的语言

\(\DEF\) Symbol

An pre-defined infinite sequence of distinct objects, and no one of these symbols is a finite sequence of other symbols.

Symbol Verbose name Remarks
\((\) left parenthesis punctuation
\()\) right parenthesis punctuation
\(\lnot\) negation symbol 非 English: not
\(\land\) conjunction symbol 合取 English: and
\(\lor\) disjunction symbol 析取 English: or
\(\to\) conditional symbol 蕴涵 English: if __, then __
\(\leftrightarrow\) biconditoinal symbol 等价 English: if and only if
\(A_1\) first sentence symbol
\(A_2\) second sentence symbol
...
\(A_n\) nth sentence symbol
...

sentential connective symbols : \(\lnot,\land,\lor,\to,\leftrightarrow\), 命题链接符号

logical symbols : The sentential connective symbols, together with the parenthese. 逻辑符号

sentence symbols : parameters (or nonlogical symbols), 命题符号, 参数, 或非逻辑符号.

\(\DEF\) Expression 表达式

An expression is a finite sequence of symbols.

\(\DEF\) Well-formed Formulas 合式公式

A well-formed formula (or simply formula or wff) is an expression that can be built up from the sentence symbols by applying some finite number of times the formula-building operations (on expression) defined by the equations \[ \matrix{ \mathcal{E}_\lnot(\alpha) = (\lnot\alpha)\cr \mathcal{E}_\land(\alpha,\beta) = (\alpha\land\beta)\cr \mathcal{E}_\lor(\alpha,\beta) = (\alpha\lor\beta)\cr \mathcal{E}_\rightarrow(\alpha,\beta) = (\alpha\rightarrow\beta)\cr \mathcal{E}_\leftrightarrow(\alpha,\beta) = (\alpha\leftrightarrow\beta) } \]

Section 1.2 Truth Assignments

\(\DEF\) Truth Values 真值

A set of truth values consisting of two distinct points: \[ \begin{array}{l} F,\quad\text{called falsity}, \cr T,\quad\text{called truth}, \end{array} \]

\(\DEF\) Truth Assignment 真值分配

A truth assignement \(v\) for a set \(S\) of sentence symbols is a function \[ v:S \rightarrow \{F, T\} \] assigning either \(T\) or \(F\) to each symbol in \(S\).

Theorem 12A

Let \(S\) be a set of sentence symbols, \(\overline{S}\) be the set of wffs that can be built up from \(S\) by the five formula-building operations.

For any truth assignment \(v\) for a set \(S\) there is a unique function \(\cssId{overlinev}{\overline{v}}:\overline{S}\to\{F,T\}\) meeting the below conditions 0-5.

  1. For any \(A\in S, \overline{v}(A)=v(A)\). (Thus \(\overline{v}\) is an extension of \(v\).)

For any \(\alpha,\beta\) in \(\overline{S}\):

  1. \(\overline{v}\left(\boldsymbol(\lnot\alpha\boldsymbol)\right)=\left\{ \begin{array}{l} T\quad\text{if}\quad\overline{v}(\alpha)=F,\cr F\quad\text{otherwise}. \end{array} \right.\)

  2. \(\overline{v}\left(\boldsymbol(\alpha\land\beta\boldsymbol)\right)=\left\{ \begin{array}{l} T\quad\text{if}\quad\overline{v}(\alpha)=T\quad\text{and}\quad\overline{v}(\beta)=T,\cr F\quad\text{otherwise}. \end{array} \right.\)

  3. \(\overline{v}\left(\boldsymbol(\alpha\lor\beta\boldsymbol)\right)=\left\{ \begin{array}{l} T\quad\text{if}\quad\overline{v}(\alpha)=T\quad\text{or}\quad\overline{v}(\beta)=T\quad(\text{or both}),\cr F\quad\text{otherwise}. \end{array} \right.\)

  4. \(\overline{v}\left(\boldsymbol(\alpha\to\beta\boldsymbol)\right)=\left\{ \begin{array}{l} T\quad\text{if}\quad\overline{v}(\alpha)=T\quad\text{and}\quad\overline{v}(\beta)=F,\cr F\quad\text{otherwise}. \end{array} \right.\)

  5. \(\overline{v}\left(\boldsymbol(\alpha\leftrightarrow\beta\boldsymbol)\right)=\left\{ \begin{array}{l} T\quad\text{if}\quad\overline{v}(\alpha)=\overline{v}(\beta),\cr F\quad\text{otherwise}. \end{array} \right.\)

\(\DEF\) Satisfy 满足

We say that a truth assignment \(v\) satisfies \(\phi\) iff \(\overline{v}(\phi)=T\).

\(\DEF\) Tautologically imply 重言蕴涵

\(\Sigma\) Tautologically implies \(\tau\) (written \(\Sigma\vDash\tau)\) iff every truth assignment for the sentence symbols in \(\Sigma\) and \(\tau\) that satisfies every member of \(\Sigma\) also satisfies \(\tau\).

\(\DEF\) Tautology 重言式

We say that \(\tau\) is a tautology (written \(\vDash\tau\)) iff every truth assignment (for the sentence symbols in \(\tau\)) satisfies \(\tau\) (\(\varnothing\vDash\tau\)).

\(\DEF\) Tautologically Equivalent 重言等价

If \(\Sigma\) is singleton \(\{\sigma\}\), then we write "\(\sigma\vDash\tau\)" in place of "\(\{\sigma\}\vDash\tau\)." If both \(\sigma\vDash\tau\) and \(\tau\vDash\sigma\), then \(\sigma\) and \(\tau\) are said to be tautologically equivalent (written \(\sigma\tauequ\tau\))

\(\DEF\) A List of Tautologies 常用重言式列表

  1. Associative and commutative laws for \(\land, \lor, \leftrightarrow\) "析取,合取,和等价"的结合律和交换律

  2. Distributive laws 分配率: \[ \begin{array}{l} ((A\land(B\lor C))\leftrightarrow((A\land B)\lor(A\land C))).\cr ((A\lor(B\land C))\leftrightarrow((A\lor B)\land(A\lor C))). \end{array} \]

  3. Negation 否定: \[ \begin{array}{l} ((\lnot(\lnot A))\leftrightarrow A).\cr ((\lnot(A\to B))\leftrightarrow (A\land(\lnot B))).\cr ((\lnot(A\leftrightarrow B))\leftrightarrow ((A\land(\lnot B))\lor((\lnot A)\land B))). \end{array} \]

De Morgan's laws 摩尔定律: \[ \begin{array}{l} ((\lnot(A\land B))\leftrightarrow ((\lnot A)\lor(\lnot B))).\cr ((\lnot(A\lor B))\leftrightarrow ((\lnot A)\land(\lnot B))). \end{array} \]

  1. Other
  • Excluded middle 排中律: \((A\lor(\lnot A))\)
  • Contradiction 矛盾律: \((\lnot(A\land(\lnot A)))\)
  • Contraposition 逆否律: \(((A\to B)\leftrightarrow((\lnot B)\to(\lnot A)))\)
  • Exportation 输出律: \((((A\land B)\to C)\leftrightarrow(A\to(B\to C)))\)

点击这里进入AMIL目录