01-离散命题逻辑-1.1~1.3

第一部分

数理逻辑

2013年8月22日星期四

有一逻辑学家误入某部落，被拘于牢

狱，酋长欲放行，他对逻辑学家说： 逻辑学家手指一门问身旁一名战士说： 这扇门是死 今有两门，一为自由，一为死亡， 你可任意开启一门。为协助你脱逃， 今加派两名战士负责解答你所提的任 何问题。惟可虑者，此两战士中一名 天性诚实，一名说谎成性，今后生死 由你自己选择。 逻辑学家沉思片刻，

亡门，他(指另一名战士)将回答‘是’,对吗？

即向一战士发问，然后开门从容离去。

2013年8月22日星期四

P:被问战士是诚实人。 Q:被问战士的回答是 是 R:另一战士回答的是 是 S:这扇门是死亡门。

P T T F

Q T F F

R T F T

S F T F T

F T F 当被问人回答 是 时，此门是生门

当被问人回答 否 时，此门是死门

S (P∧ Q) ∨( P∧ Q)

(P∨ P) ∧ Q Q (S的真值总与Q的真值相反)

逻辑科学，它分为：

2013年8月22日星期四

逻辑，是研究思维形式及思维规律的科学,也把它称为研究推理的 概念是思维的基本单位 由一个或几个判断推出 通过概念对事物是否具有

辨证逻辑——是研究人的思维中的辩证法。

另一判断的思维形式， 某种属性进行肯定或否定 就是推理 的回答，这就是判断

例如： 用全面的和发展的观点观察事物； 具体问题具体分析； 实践是检查事物正误的唯一标准；等等。 形式逻辑——是研究人的思维的形式和一般规律。

在本学科，我们只关心形式逻辑。思维的形式结构包括了概念，判断和推理之间的结构和联系。形式逻辑主要研究推理。 推理，就是由若干个已知的判断(前提),推出新的判断(结论)的 思维过程。

推理推理分为以下几种： 类比推理：由个别事实推出个别结论。 如： 地球上有空气、水，地球上有生物。

2013年8月22日星期四

火星上有空气、水。 火星上有生物。

归纳推理：由若干个别事实推出一般结论。如：铜能导电。铁能导电。锡能导电。铅能导电。…… 一切金属都导电。 演绎推理：由一般规律推出个别事实。 形式逻辑主要是研究演绎推理的。

演绎推理

不能仅停留在文字表面，否则无法与机器沟通。

2013年8月22日星期四

若停留在文字表面，如：下雨换成下雪；铜换成 演绎推理举例： 铁；机器该如何处理 ？ 例1: 如果天下雨，则路上有水。 天下雨了。 (一般规律) (个别事实)

推出结论：路上有水。例2: (大前提):所有金属都导电。 (小前提):铜是金属。 推出结论：铜能导电。

(个别结论)

(一般规律) (个别事实) (个别结论)

数理逻辑数理逻辑是用数学的方法研究形式

逻辑。

2013年8月22日星期四

所谓数学方法，主要是指引进一套符号体系的方法，因此数 理逻辑又称为符号逻辑 现代数理逻辑有四大分支： 证明论、模型论、递归论、公理化集合论 它们共同的基础——

命题逻辑(Ls,命题演算)谓词逻辑(Lp,谓词演算)

命题逻辑命题逻辑示例： 如果天下雨，则路上有水。 (一般规律) 天下雨了。 推出结论：路上有水。 (个别事实) (个别结论)

2013年8月22日星期四

设 P表示：天下雨。设Q表示：路上有水。 设 表示：如果…则… 以上的推理过程表示为： 前提1:P Q 前提2:P 结 论：Q (如果天下雨，则路上有水。) (天下雨了。) (路上有水。)

谓词逻辑谓词逻辑示例： (大前提):所有金属都导电。

2013年8月22日星期四

(一般规律)

(小前提):铜是金属。推出结论：铜能导电。 设M(x): x是金属； 设 x 表示: 所有的x ; 以上的推理过程表示为： 大前提：( x)(M(x) C(x)) 小前提：M(a)

(个别事实)(个别结论) 设C(x): x能导电。 设 a: 表示铜.

(所有金属都导电。) (铜是金属。)

结 论： C(a)

(铜能导电。)

命题逻辑的应用

2013年8月22日星期四

给后继课程：编译原理、人工智能、

数字逻辑等提供必要的数学基础。P P Q P

P∧ Q

P Q

P∨ Q P Q

P∨ Q

P Q

P Q

Q P

P Q

P Q

P Q

P Q

P Q

P Q

P Q

第一章 命题逻辑

命题逻辑命题逻辑

2013年8月22日星期四

研究由命题为基础单位构成的前提和结论之间的可推导关系 它是谓词逻辑的基础 本章的主要内容：

命题、联结词、命题公式等价式、蕴涵式

范式、主范式推理理论

第一节 命题与联结词第一节 命题与联结词 一、命题的概念

2013年8月22日星期四

所谓命题(Proposition):是指具有非真必假的陈述句。

疑问句、感叹句、祈使句都不能判断其真假，故而都不是命题。 命题仅有两种可能的真值(truth value): 真(true)(用T或1表示) 假(false)(用F或0表示) 因此，命题逻辑也称为 二值逻辑 陈述句 二值逻辑

命题

2013年8月22日星期四

命题的真假是具有客观性质的，而不是由人的主观决定的。 命题是一个真或假的语句，但是不能既真又假。 若一个命题的真值为真，称该命题为真命题；

(用T或1表示)若一个命题的真值为假，称该命题为假命题； (用F或0表示)

命题注意：

2013年8月22日星期四

命题有真假，并不意味着现在就能确定其为真还是为假， 而是指它具有能够唯一确定的真假值这一性质。 例如：地球外的星球上存在生物

命题例1.1: 判断下面的语句是否为命题？ 如果是命题，是真命题还是假命题？ 今天下雪。 假命题 不是命题

2013年8月22日星期四

明天会刮风吗？ x+y > 4

不是命题 真命题

2是偶数，而3是奇数。

陈胜起义那天，杭州下雨了。 是命题，未知真假 这真是太好了！ 不是命题

命题你去哪里？ 不是命题

2013年8月22日星期四

给我一只笔。 不是命题 我正在说谎。 悖论，不是命题

1+1=10

是命题，在二进制条件下是真命题， 其他进制条件下是假命题

金星的表面温度是800oC。 465oC~485oC本命题是假的。 悖论，不是命题

假命题

悖论

2013年8月22日星期四

悖论 (paradox)其字面意思为 荒谬的理论或自相矛 盾的话 。 从逻辑上看，悖论性的语句具有这样的特征： 如果假定这个语句为真，那么会推出这个语句为假； 反之，如果假定这个语句为假，又会推出这个语句为真。

说它对也不是，不对也不是，真是左右为难。

悖论

2013年8月22日星期四

悖论古已有之。一般认为，最早的悖论是古希腊的 说谎者 悖论 。《新约全书·提多书》是这样记述的： 克里特岛上的一个本地先知伊壁孟尼德(Epimenides) 说： 克里特人总是撒谎，乃是恶兽，又馋又懒。 这个 见证是真的。 后来欧布里德(Eubulides)将他的话改进为： 我正在说谎。

悖论

2013年8月22日星期四

后来又发现了好几种 说谎者悖论 的变种，例如所谓 说 谎者循环 : A说： 下面是句谎话。 B说： 上面是句真话。 说谎者悖论 和 说谎者循环 是与自然语言的表达方

式密切相关的悖论，涉及真假、定义、名称、意义等语义方面的概念，这类悖论被称为 语义学悖论 。

悖论

2013年8月22日星期四

本文来源：https://www.bwwdw.com/article/3mnm.html