数理逻辑学习笔记[0] 命题逻辑：语义

2024年4月22日 互联网

文章目录

  • 1 命题逻辑：语义
    • 1.1 命题和连接符
    • 1.2 真值函数和真值表
    • 1.3 操作和替换规则
    • 1.4 范式
    • 1.5 连接符的完备集
    • 1.6 推理及有效性
  • 勘误集
    • ml-1_1.pdf

1 命题逻辑：语义

1.1 命题和连接符

  1. Q: 数学语言，如“ x 0 x_0 x0​是集合 X X X的最大元”是符号语言嘛？如何把它转化为符号语言？
    A: 不是。数学语言是自然语言+记号。 x 0 ∈ X , ∀ x ∈ X , x ≤ x 0 x_0\in X,\forall x\in X,x\le x_0 x0​∈X,∀x∈X,x≤x0​. 注意 x 0 ∈ X x_0\in X x0​∈X不能遗漏！
  2. Q: 逻辑矛盾和悖论有何联系？悖论常常如何产生矛盾？
    A: 逻辑矛盾是同时断言一个陈述和它的否定。悖论是一种逻辑矛盾的形式（导致自相矛盾的陈述的一种）。
    实际上，悖论常常是自指语句，引起自相矛盾。当然也可以：“循环”地“指一圈”，导致自相矛盾。
    注：悖论不是命题。并且，存在既不是悖论也不是命题的陈述句（即不是悖论，但并不具有真假意义）。
  3. Q: 用多项式及其在某点的值类比，直观阐述简单命题、复合命题、命题变元、命题形式的关系。
    A: 简单命题相当于一个数字，如0. 复合命题相当于已知数组成的表达式，如 1 + 1 1+1 1+1. 命题变元相当于未知数，如 x x x. 命题形式相当于含未知数代数式，如 1 + x + y 1+x+y 1+x+y.
    复合命题的真值依赖于其中简单命题（原子）的真值及连接符。

1.2 真值函数和真值表

  1. Q: ( p ∨ q ) ∨ r (p\vee q)\vee r (p∨q)∨r对应的布尔函数（真值函数）定义域和值域分别是什么？将它表示成真值表为几行几列？一共有多少个与它相同定义域和值域的真值函数？
    A: f : { 1 , 0 } 3 → { 1 , 0 } f:\{1,0\}^3\to\{1,0\} f:{1,0}3→{1,0}.
    （如果表头4列分别为 p , q , r , ( p ∨ q ) ∨ r p,q,r,(p\vee q)\vee r p,q,r,(p∨q)∨r，不计表头所占的1行，则）4列，8行。
    2 2 3 2^{2^3} 223个。（当然，我们认为当定义域、值域和对应法则均相同的函数是相同的，而不重复计数。即使其对应命题形式可能不同）
  2. Q: “如果 1 = 2 1=2 1=2则 − 1 = − 2 -1=-2 −1=−2”是真命题吗？
    A: （按数字和符号通常的意义理解）是真命题。因为 1 = 2 1=2 1=2为假命题，故用 → \to →连接它和任何命题都得到真命题。（这是“空虚(vacuous)的真”）
  3. Q: 如何理解“命题形式可嵌套，可潜在无限长；给定一个命题形式，则为有限长”？
    A: 嵌套：命题形式由归纳（递归）定义，即首先任一变元是命题形式，其次变元间各种（一元或二元）运算也得到命题形式。
    “潜在”意为任给一个命题形式，都存在“比它更长”的，此过程可以“无限进行”下去。但是每一个确定的命题形式都是有限长的。
    注：线性代数中无限维线性空间中“线性表出”的定义也是如此。确定的某一种线性表出方式一定只含有限个向量。但并不存在一个整数是所有表出方式中向量个数的上界。
  4. Q: 如何理解“技术性符号如( ) ...都不是必要的”？请解释：没有省略号，怎么表示 p 1 ∧ p 2 ∧ ⋯ ∧ p n p_1\wedge p_2\wedge\cdots \wedge p_n p1​∧p2​∧⋯∧pn​呢？
    A: 比如中缀表达式转化为前缀表达式（ p ∨ q ∨ r p\vee q\vee r p∨q∨r转化为 ∨ ∨ p q r \vee\vee pqr ∨∨pqr）则无需括号。用省略号表达命题形式只是为了表达方便，完全可以不需要。
    “没有省略号，怎么表示 p 1 ∧ p 2 ∧ ⋯ ∧ p n p_1\wedge p_2\wedge\cdots \wedge p_n p1​∧
最新文章