A Mathematical Introduction to Logic -- Section 2.1

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

\(\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 2, Section 2.1, 介绍一阶逻辑的基本概念

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

前缀关键字的含义:

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

Chapter Two. First-Order Logic 一阶逻辑

Section 2.1 First-Order Language 一阶语言

\(\DEF\) Symbol 符号

A. Logical symbols 逻辑符号

  1. Parentheses 括号: \((\),\()\).
  2. Sentential connective symbols 命题链接符号: \(\rightarrow\), \(\lnot\).
  3. Variables 变量(one for each positive integer \(n\)); \[v_1, v_2, \ldots.\]
  4. Equality symbol 等于符号(optional): \(=\).

B. Parameters 参数

  1. Quantifier symbol 量词符号: \(\forall\).
  2. Predicate symbols 谓词符号: For each positive integer \(n\), some set(posibly empty) of symbols, called \(n\)-place predicate symbols.
  3. Constant symbols 常量符号: some set(possibly empty) of symbols.
  4. Function symbols 函数符号: For each positive integer \(n\), some set(possibly empty) of symbols, called n-place function symbols.

等于符号是特殊的二元谓词符号, 分类到逻辑符号里而不是参数里是因为这会影响到它在自然语言中的翻译的方式.

常量符号也可以叫0元函数符号.

\(n\)元谓词符号 可以翻译成自然语言的一个谓词, 可以映射为\(n\)元关系

具体到一种一阶语言, 一定要指明两点:

  1. 等于符号是否出现.
  2. 参数有哪些.

一阶语言的例子:

  1. 纯谓词(pure predicate)语言:
  • Equality: No.
  • \(n\)-place predicate symbols: \(A^n_1, A^n_2,\ldots.\)
  • Constant symbols: \(a_1, a_2, \ldots.\)
  • \(n\)-place function symbols: None.
  1. 集合论(set theory)语言:
  • Equality: Yes(usually).
  • Predicate parameterts: One 2-place predicate symbol \(\in\)
  • function symbols: None(or occasionally a constant symbol \(\varnothing\)).
  1. 初等数论(elementary number theory)语言:
  • Equality: Yes.
  • Predicate parameterts: One 2-place predicate symbol \(<\)
  • function symbols: The symbol \(0\).
  • 1-place function symbols: \(S\) (for successor).
  • 2-place function symbols: \(+\) (for addition), \(\cdot\)(for multiplication), and \(E\) (for exponentiation)

一个被广泛认同的观点是数学可以嵌入到集合论中, 也就是说:

  1. 数学中的陈述可以被集合论语言表述.
  2. 数学的定理, 可以从集合论的公理按照逻辑推导出来.

Two patterns:

  1. An English sentence which asserts that everything in a certain category has some property is translated: \[\forall v(\_\rightarrow\_)\]
  2. A sentence which asserts that there is some object or objects in the category and having the property is translated \[\exists v(\_\land\_)\]

\(\DEF\) Expression 表达式

An expression is any finite sequence of symbols.

\(\DEF\) Term 项

If we define for each \(n\)-place function symbol \(f\), an \(n\)-place term-building operation \(\cal{F}_f\) on expressions: \[\cal{F}_f(\varepsilon_1,\ldots,\varepsilon_n)=f\varepsilon_1\cdots\varepsilon_n\] The set of terms is the set of expressions that can be built up from the constant symbols and variables by applying(zero or more times) the \(\cal{F}_f\) operations.

The terms are the expression that are transformlated as names of objects(noun phrases), in contrast to the wffs which are translated as assertions about the objects. (项翻译成名词性短语来描述某个对象, 合式公式翻译成关于该对象的断言)

\(\MYNOTE\) 变量符号, 常量符号本身就是项. 项代表论域里的一个元素. 可以由常量或变量代表. 或由常量或变量经过一定运算得到.

\(\DEF\) Atomic Formulas 原子公式

An atomic formula is an expression of the form \[Pt_1\ldots t_n,\] where \(P\) is an \(n\)-place predicate symbol and \(t_1,\ldots,t_n\) are terms.

原子公式在一阶逻辑语言里的作用相当于命题逻辑中的命题符号

\(\MYNOTE\) 原子公式可以翻译成一个陈述句, 名词部分(主语, 宾语)由项表示, 谓语由谓词符号表示.

\(\DEF\) Well-Formed Formulas, (wffs, or just formulas) 合式公式

The set of well-formed formulas (wffs, or just formulas) is the set of expressions that can be built up from the atomic formulas by applying (zero or more times) the operations \(\cal{E}_\lnot\), \(\cal{E}_\rightarrow\) and \(\cal{Q}_i(i=1,2,\ldots).\) where \[ \matrix{ \cal{E}_\lnot(\gamma) = (\lnot\gamma),\cr \cal{E}_\rightarrow(\gamma,\delta) = (\gamma\rightarrow\delta),\cr \cal{Q}_i(\gamma) = \forall v_i\gamma\cr } \]

\(\MYNOTE\) 通过量词符号对变量进行限定, 以及通过逻辑符号表示陈述句之间的逻辑关系, 来对演绎思维进行数学建模.

\(\DEF\) occur free in the wff 自由出现

Consider any variable \(x\). We define, for each wff \(\alpha\), what it means for x to occur free in \(\alpha\) by recursion:

  1. For atomic \(\alpha\), \(x\) occurs free in \(\alpha\) iff \(x\) occurs in (i.e., is a symbol of) \(\alpha\).
  2. \(x\) occurs free in (\(\lnot\alpha\)) iff \(x\) occurs free in \(\alpha\).
  3. \(x\) occurs free in (\(\alpha\rightarrow\beta\)) iff x occurs free in \(\alpha\) or in \(\beta\).
  4. \(x\) occurs free in \(\forall v_i\alpha\) iff \(x\) occurs free in \(\alpha\) and \(x\neq v_i\).

\(x\) is a free variable of \(\alpha\).

\(\MYNOTE\) 自由变量是没有量词符号限定的变量.

\(\DEF\) Sentence 命题

If no variable occurs free in the wff \(\alpha\), then \(\alpha\) is a sentence.

\(\MYNOTE\) 没有自由变量的合式公式是命题.

On Notation

We naturally want methos of specifying wffs in more indirect but more readable ways.

  • \((\alpha\lor\beta)\) abbreviates \(((\lnot\alpha)\rightarrow\beta)\)
  • \((\alpha\land\beta)\) abbreviates \(((\lnot(\alpha\rightarrow(\lnot\beta)))\)
  • \((\alpha\leftrightarrow\beta)\) abbreviates \(((\alpha\rightarrow\beta)\land(\beta\rightarrow\alpha))\)
  • \(\exists x\alpha\) abbreviates \((\lnot\forall x(\lnot\alpha))\)
  • \(u=t\) abbreviates \(=ut\). A similar abbreviation applies to some other 2-predicate and function symbols.
  • \(u\neq t\) abbreviates \((\lnot=ut)\)

For parentheses, we omit mention of just as many as we possibly can.

  1. outermost parentheses may be dropped.
  2. \(\lnot\), \(\forall\), and \(\exists\) apply to as little as possible.
  3. \(\land\), \(\lor\) apply to as little as possible, subject to item 2(2比3优先级高). For example, \[ \lnot\alpha\land\beta\rightarrow\gamma\quad\text{is}\quad((\lnot\alpha)\land\beta)\rightarrow\gamma \]
  4. When one connective is used repeatedly, the expression is grouped to the right. For example, \[\alpha\rightarrow\beta\rightarrow\gamma\quad\text{is}\quad\alpha\rightarrow(\beta\rightarrow\gamma)\]

Exercises 2.1

Problem 1

Assume that we have a language with the following parameters: \(\forall\), intended to mean "for all things"; \(N\), intended to mean "is a number"; \(I\) , intended to mean "is interesting";<, intended to mean "is less than"; and \(0\), a constant symbol intended to denote zero. Translate into this language the English sentences listed below. If the English sentence is ambiguous, you will need more than one translation.

  1. Zero is less than any number.
  2. If any number is interesting, then zero is interesting.
  3. No number is less than zero.
  4. Any uninteresting number with the property that all smaller numbers are interesting certainly is interesting.
  5. There is no number such that all numbers are less than it.
  6. There is no number such that no number is less than it.

解:

  1. \(\forall v(Nv\rightarrow (0<v))\)
  2. any number如果意思是有的数是有趣的: \(\exists v(Nv\land Iv)\rightarrow I0\). 如果意思是任意的数都是有趣的: \(\forall v(Nv\rightarrow Iv)\rightarrow I0\)
  3. \(\forall v(Nv\rightarrow\lnot(v<0))\)
  4. \(\forall v(Nv\land\lnot Iv\land\forall u(Nu\land u<v\rightarrow Iu)\rightarrow Iv)\)
  5. \(\lnot\exists v(Nv\land \forall u(Nu\rightarrow u<v))\)
  6. \(\lnot\exists v(Nv\land \lnot\exists u(Nu\land u<v))\)
Problem 2

With the same language as in the preceding exercise, translate back into good English the wff \[ \forall x(Nx\rightarrow Ix\rightarrow\lnot\forall y(Ny\rightarrow Iy\rightarrow \lnot x<y)). \]

解: 对任意的有趣的数, 都能找到比它大的有趣的数. 即不存在最大的有趣的数.

这里有个推到有必要记住 \(\forall x(Nx\rightarrow Ix\rightarrow\alpha) = \forall x(Nx \land Ix\rightarrow\alpha)\)

Problem 3

Neither \(a\) nor \(b\) is a member of every set. (\(\forall\), for all sets; \(\in\), is a member of; \(a\), \(a\); \(b\), \(b\).)

解: \[ \lnot\forall xa\in x \land \lnot\forall x b\in x \]