【离散数学】谓词逻辑

目录

1. 谓词

2. 量词

3. 等价式

4. 蕴含式 

5. 前束范式 

6. 推理理论 

附：系列文章

---

1. 谓词

① 我们用大写字母表示谓词，小写字母表示客体名称，例如A表示"是个大学生"，c表示张三，e表示李四，则A(c)，A(e)分别表示“张三是个大学生”，“李四是个大学生”。

② 我们把A(b)称为一元谓词，B(a,b)称为二元谓词，L(a,b,c)称为三元谓词，依次类推 

2. 量词

存在量词：∃

全称量词：∀ 

3. 等价式

① ﹁(∀x)P(x)⇔(∃x)﹁P(x) 

证：设P(x)表示x今天来上课，则﹁P(x) 表示x今天没来上课

﹁(∀x)P(x)表示不是所有人今天来上课，(∃x)﹁P(x)表示存在有人今天没来上课，一个意思

② ﹁(∃x)P(x)⇔(∀x)﹁P(x)  

① (∀x)(A(x)∨B)⇔((∀x)A(x)∨B)

② (∀x)(A(x)∧B)⇔((∀x)A(x)∧B) 

③ (∃x)(A(x)∨B)⇔((∃x)A(x)∨B)

④ (∃x)(A(x)∧B)⇔((∃x)A(x)∧B)  

由于B中不存在约束变元x，所以这个公式成立

① ((∀x)A(x)→B)⇔(∃x)(A(x)→B)

② ((∃x)A(x)→B)⇔(∀x)(A(x)→B)

③ (B→(∀x)A(x))⇔(∀x)(B→A(x))

④ (B→(∃x)A(x))⇔(∃x)(B→A(x))

⑤ (∀x)(P(x)∨Q(y))⇔((∀x)P(x)∨Q(y))

① (∀x)(A(x)∧B(x))⇔(∀x)A(x)∧(∀x)B(x)

证：A(x)表示人会唱歌，B(x)表示人会跳舞

(∀x)(A(x)∧B(x))表示所有人都唱歌跳舞

(∀x)A(x)∧(∀x)B(x)表示所有人唱歌且所有人跳舞 

② (∃x)(A(x)∨B(x))⇔(∃x)A(x)∨(∃x)B(x)

证：A(x)表示人会唱歌，B(x)表示人会跳舞

(∃x)(A(x)∨B(x))表示存在有人唱歌或者有人跳舞

(∃x)A(x)∨(∃x)B(x)表示存在有人唱歌或者存在有人跳舞 

4. 蕴含式 

① (∀x)A(x)∨(∀x)B(x)⇒(∀x)(A(x)∨B(x))

证：A(x)表示学生聪明，B(x)表示学生努力

(∀x)A(x)∨(∀x)B(x)表示所有人聪明或者所有人都努力

(∀x)(A(x)∨B(x))表示所有人都聪明或者努力

② (∃x)A(x)∧(∃x)B(x)⇒(∃x)(A(x)∧B(x))

5. 前束范式 

简单来说，就是把量词都提到最前面就是前束范式（注意改名） 

6. 推理理论 

① 先ES（存在指定规则），再US（全称指定规则） 

② 证明方法同命题的推理理论

附：系列文章

概念

测试