当前位置：文档之家 › 命题演算(5,6节)

命题演算(5,6节)

  • 格式：ppt
  • 大小：706.00 KB
  • 文档页数：59

下载文档原格式

  / 59

合集下载

逻辑代数(上)：命题演算 习题答案

逻辑代数(上)：命题演算 习题答案

练习6.11. 判断下列语句哪些是命题，若是命题其真值是什么？（1）a+b+c。

（2）x > 0 。

（3）请进！（4）离散数学是计算机科学与技术专业的基础课程。

（5）2009年7月我们去意大利的米兰旅游。

（6）啊！这里真漂亮。

（7）今天是星期四吗？（8）我明天或者后天去天津。

（9）如果买不到飞机票，我就去不了海南。

（10）除非你陪我，否则我不去。

（11）本命题是假的。

（12）如果雪是黑的，太阳从北边升起。

解：（1）不是命题。

（2）不是命题。

（3）不是命题。

（4）是命题。

真值是1。

（5）是命题。

真值是0。

（6）不是命题。

（7）不是命题。

（8）是命题。

真值是0。

（9）是命题。

真值是1。

（10）是命题。

真值是1。

（11）不是命题，是悖论。

（12）是命题。

真值是1。

2. 指出下列语句哪些是原子命题，哪些是复合命题？并将复合命题形式化。

（1）他去了教室，也去了机房。

（2）今晚我去书店或者去图书馆。

（3）我昨天没有去超市。

（4）我们不能既看电视又看电影。

（5）如果买不到飞机票，我就去不了海南。

（6）小王不是坐飞机去上海，就是坐高铁去上海。

（7）喜羊羊和懒羊羊是好朋友。

（8）除非小李生病，否则他每天都会练习书法。

（9）侈而惰者贫，而力而俭者富。

（韩非：《韩非子∙显学》）解：（1）P：他去了教室。

Q：他去了机房。

P∧Q（2）P：今晚我去书店。

Q：今晚我去图书馆。

P∨Q（3）P：我昨天去超市。

⌝P（4）P：我们看电视。

Q：我们看电影。

⌝(P∧Q)（5）P：我买到飞机票。

Q：我去海南。

⌝P→⌝Q（6）P：小王坐飞机去上海。

Q：小王坐高铁去上海。

（P∨Q）∧⌝(P∧Q) 或者⌝(P↔Q)（7）原子命题（8）P：小李生病。

Q：小李每天都会练习书法。

⌝P↔Q（9）P：侈。

Q：惰。

R：贫。

（(P∧Q)→R）∧（(⌝P∧⌝Q)→⌝R）3. 判定下列符号串是否为命题公式。

（1）P∧∨⌝Q（2）(P∨QR)→S（3）(P∨Q)→P（4）P→(P∨Q（5）P∧(P→Q)∧(P→⌝Q)（6）⌝ (P∨Q) ↔（⌝Q∧⌝P）（7）（P∧⌝R）∨（P→Q）解：（1）不是（2）不是（3）是（4）不是（5）是（6）是（7）是4. 请给出下列命题公式的真值表。

离散数学第1章 命题演算

离散数学第1章 命题演算

所以这句话没有办法判断真假，所以不是命题！
8
命题符号化

为了能用数学方法来研究命题之间的逻辑关系和推理， 需要将命题符号化。
一个任意的没有赋予具体内容的命题是一个命题变元。

定义：以“真” 、“假”为其变域的变元称为命题
变元。

常用大写的英文字母A，B，C，…P，Q，R，…等来表 示一个命题或命题变元。
定义 对于命题公式中各命题变元（分量）指派所有可能 的真值，以及由此而确定的命题公式的真值汇列成表，称 为真值表。


38
例1:命题公式P∧﹁ Q的真值表如下所示。
Ｐ F F T T
这组命题变 元的确定值 称为该公式 的一个指派
Ｑ F T F T
﹁Ｑ T F T F
P∧﹁ Q F F T F
整个表即为该公式 的真值表
34
§1-2
命题公式
将由命题变元和联结词组成的复杂的命题 变元称为命题公式。各个命题变元称为命题公 式的分量。
35
§1-2
命题公式
定义:命题逻辑公式(公式)可按如下法则生成: (1)命题是公式;
(2)如果P是公式,则(﹁ P)是公式;
(3)如果P,Q是公式,则(P ∧ Q),(P∨Q),(P→Q),
26
例如：



因为2<3，所以1+1=2。 在通常意义下2<3与1+1=2没有存在任 何联系，我们一般不会做如此推理。 但在数理逻辑下，设P:2<3; Q:1+1=2 这句话可以形式化为P→Q; 并且真值为T
27
联结词
5.双条件 定义 设P，Q是命题，P和Q的等价命题记
作 P Q ，读作“P当且仅当Q”，或 “P等 价 PQ Q”，当P和Q的真值都为T和F时， 的真 PQ

命题演算的推理理论

命题演算的推理理论

例 证明
((P→Q)∧P)→Q → ∧ →
((P→Q)∧P)∧¬ → ∧ ∧¬ ∧¬Q (¬P∨Q)∧P∧¬ ∧¬Q ¬ ∨ ∧ ∧¬ S ={¬P∨Q，P，¬Q} ¬ ∨ ， ，
Hale Waihona Puke 解：考察 合取范式为 子句集为 归结过程为 (1) ¬P∨Q ∨ (2) P (3) ¬Q (4) Q (5) □ 故原式为定理
(1)(2)归结 归结 (3)(4)归结 归结
∧¬Q)∧ ¬ ∨ ∧¬ ∧¬R→ 例 (p23) ¬(P∧¬ ∧(¬Q∨ R)∧¬ →¬P ∧¬
证明： ¬ ∧¬ ∧¬Q)∧ ¬ ∨ ∧¬ ∧¬ ∧¬R 证明： (¬(P∧¬ ∧(¬Q∨ R)∧¬ )∧¬ ¬P = (¬P ∨Q)∧ (¬Q∨ R)∧¬ ∧¬ ¬P ∧¬R ¬ ∧ ¬ ∨ ∧¬ 归结过程为 (1) ¬P ∨Q (2) ¬Q∨ R ∨ (3) ¬R (4) ¬ ¬P (5) ¬Q (6) ¬P (7) □ 故原式为定理
若干重要的归结规则
父辈子句 P和¬P∨Q 和 ∨ P∨Q和¬P∨Q ∨ 和 ∨ P∨Q和¬P∨¬ ∨ 和 ∨¬ ∨¬Q ¬P和P 和 P∨Q和¬Q∨¬ ∨ 和 ∨¬ ∨¬R 归结式 Q Q 说明 假设推理 子句合并成Q 子句合并成
¬P∨P或¬Q∨Q 两个可能的子句 ∨ 或 ∨ 均为重言式 □ P∨¬ ∨¬R ∨¬ 空子句， 空子句， 归结结束 三段论
例 (S ¬Q)∧(P Q)∧(R∨S)∧(R ¬Q) ¬P
证明： 证明： (S ¬Q)∧(P Q)∧(R∨S)∧(R ¬Q)∧¬¬ P ∧ ∧ ∨ ∧ ∧¬¬ =(¬S∨¬ ∧(¬P∨Q)∧(R∨S)∧(¬R∨¬ ∧¬¬ ∨¬Q)∧ ¬ ∨ ∧ ∨ ∧ ¬ ∨¬ ∧¬¬P ∨¬Q)∧¬¬ ¬ ∨¬ 建立子句集 {¬S∨¬ ¬P∨ Q, R∨S, ¬R∨¬Q, ¬¬ ∨¬Q, ¬¬P} ¬ ∨¬ ∨ ∨ ∨ 归结过程为: 归结过程为 (1) ¬S∨¬ ∨¬Q ∨¬ (2) ¬P∨ Q ∨ (3) R∨S ∨ (4) ¬R∨¬ ∨¬Q ∨¬ (5) ¬¬ ¬¬P (6) ¬P∨¬ ∨¬S (1)(2)归结 ∨¬ 归结 (7) ¬S (5)(6)归结 归结 (8) ¬P∨¬ ∨¬R (2)(4)归结 ∨¬ 归结 (9) ¬R (5)(8)归结 归结 (10) S (3)(9)归结 归结 (11)□ (7)(10)归结 □ 归结 故原式为定理。 故原式为定理。

第三章命题演算

第三章命题演算

要么选择鱼，要么选择熊掌。 ①(pq) (pq) ② (pq) (pq) ③ (p↔q)
4、假言命题 （蕴涵命题、条件命题）
（1）假言命题陈述某一命题 存在是另一命题存在的条件。 一般由蕴涵词联结支命题而 构成。
①如果甲是案犯，那么甲有作案时间。
②只要驳倒了对方的论证，就能胜诉。
不破不立，不塞不流，不止不行。 ( p→q)(r→s)(t→u)
但书练习
1、《刑法》第20条：正当防卫明显超过 必要限度造成重大损害的，应当负刑 事责任，但是应当减轻或免除处罚。
2、《律师法》第9条：受过刑事处罚的， 不予颁发律师执业证书，但过失犯罪 除外。
1、p→qr 2、pr→q
三、复合命题推理的基本有效式
p
q p→ q
+
+
+
+
+
+
_
+
5、等值命题
（1）等值命题就是陈述 两个支命题或者同真或者 同假。一般是用等值词联 结支命题而构成。
①一个数是偶数当且仅当能被2 整除。
②如果小明参加我也参加，否则 我也不参加。
（2）等值命题形式结构
p当且仅当q，p↔q， 称为等值式。 p称为前件， q称为后件。
命题联结词： 只有，才 仅当，才形式
只有水分充足，种子才会发芽
只有ｐ，才ｑ
如果没有充足的水分，种子就不会发芽
p→q
如果种子发芽了，那么一定有充足的水分
q→p
只有ｐ，才ｑ p→q q→p p←q
（3）必要条件假言命题 逻辑性质和真值表
三、复合命题推理的基本有效式
3、选言推理：根据析取词的逻辑 性质进行的演绎推理。
三、复合命题推理的基本有效式

命题演算

命题演算
7/28/2013 10:52 PM Deren Chen, Zhejiang Univ. 11
Table 4
Propositional Equivalences 命题演算
7/28/2013 10:52 PM
Deren Chen, Zhejiang Univ.
12
Propositional Equivalences 命题演算
The propositions p and q are called logically equivalent if p

q is a tautotogy. The notation p q
denotes that p and q are logically equivalent.
逻辑等值，或逻辑等价
p∨q
and p→q agree, these propositions are logically equivalent.
7/28/2013 10:52 PM
Deren Chen, Zhejiang Univ.
9
Table 3
Propositional Equivalences 命题演算
7/28/2013 10:52 PM
判断命题公式逻辑等价的方法：
1、真值表
2、命题公式的演算 基本等值定理；
公式的代入不变性；
等值关系的传递性。
7/28/2013 10:52 PM Deren Chen, Zhejiang Univ. 18
Propositional Equivalences 命题演算
命题公式逻辑等价关系的应用：
1、判定是否逻辑等价；
限定性命题公式： 最多仅含有否定、析取、合取 逻辑联结词的命题公式。 命题公式P的对偶公式（Dual）：将P中的 析取联结词换成合取联结词， 合取联结词换成析取联结词，

自考离散数学命题演算笔记

自考离散数学命题演算笔记

自考离散数学命题演算笔记一、命题演算的基本概念1. 命题：可以明确判断真假的陈述句称为命题。

2. 命题符号：用字母（如p、q、r等）表示的命题称为命题符号。

3. 命题演算：研究命题符号之间关系的数学分支。

二、命题演算的基本运算1. 否定（¬）：表示对命题的否定，如¬p表示对p的否定。

2. 合取（∧）：表示两个命题的合取，如p∧q表示p和q同时为真。

3. 析取（∨）：表示两个命题的析取，如p∨q表示p和q至少有一个为真。

4. 蕴含（→）：表示两个命题的蕴含关系，如p→q表示如果p为真，则q必为真。

5. 双条件（↔）：表示两个命题的双条件关系，如p↔q表示p和q同时为真或同时为假。

三、命题演算的基本法则1. 双重否定律：¬¬p = p2. 假言三段论：p→q, ¬q→¬p3. 假言换位：p→q ↔ ¬q→¬p4. 交换律：p∧q ↔ q∧p, p∨q ↔ q∨p5. 结合律：p∧(q∧r) ↔ (p∧q)∧r, p∨(q∨r) ↔ (p∨q)∨r6. 分配律：p∧(q∨r) ↔ (p∧q)∨(p∧r), p∨(q∧r) ↔(p∨q)∧(p∨r)7. 吸收律：p∧(p∨q) ↔ p, p∨(p∧q) ↔ p8. 德摩根律：¬(p∧q) ↔ ¬p∨¬q, ¬(p∨q) ↔ ¬p∧¬q9. 互补律：p∨¬p ↔ 1, p∧¬p ↔ 010. 等幂律：p∧p ↔ p, p∨p ↔ p自考离散数学命题演算笔记四、命题逻辑函数命题逻辑函数是指对命题进行运算的函数，它将命题作为输入，输出也是一个命题。

常见的命题逻辑函数包括：1. 常函数：常函数的输出是一个固定的命题，无论输入是什么。

例如，常真函数T的输出始终为真，常假函数F的输出始终为假。

2. 投影函数：投影函数的输出是其输入之一。

《命题演算》课件

《命题演算》课件

详细描述
概率命题演算在传统命题演算的基础上，引 入概率函数来量化命题的不确定性。通过概 率算子和概率分布，描述了命题在各种情况 下的可能性，从而更准确地表达现实世界中
的不确定性。
感谢您的观看
THANKS
逆否命题
对原命题的条件和结论都进行否定， 然后互换它们的位置，例如“如果天 下雨，那么地面会湿”的逆否命题是 “如果地面不湿，那么天不下雨”。
复合命题的表示与转换
复合命题
由两个或多个简单命题通过逻辑运算符组合而成的命题，例如“如 果天不下雨并且地面不湿，那么没有人在家”。
复合命题的表示方法
使用逻辑运算符（如“∧”、“∨”、“→”等）将简单命题组合 起来。
总结词
时序命题演算是命题演算的一种扩展，它引 入了时间因素来描述命题在时间序列上的状 态和变化。
详细描述
时序命题演算考虑了时间因素对命题状态的 影响，通过引入时间算子和时间依赖关系来 扩展命题演算。它能够描述在特定时间点上 命题的真假状态，以及随着时间推移命题的 变化情况。
概率命题演算
总结词
概率命题演算是命题演算的一种扩展，它引 入概率概念来描述命题的不确定性。
复合命题的真假判定
根据真值表或逻辑运算规则判断复合命题的真假值。
03 命题逻辑推理
推理规则
1 2 3
推理规则
推理规则是逻辑推理的基本准则，包括前提和结 论两部分。前提是推理的依据，结论是根据前提 得出的结果。
推理形式
推理形式是指推理的逻辑结构，包括前提和结论 的逻辑表达式。根据不同的逻辑表达式，可以得 出不同的推理形式。
模态命题演算
总结词
模态命题演算是命题演算的一种扩展，它引入了模态算子来描述命题之间的可能性、必 然性等关系。

第六讲命题演算的规则

第六讲命题演算的规则

（2）当结论是蕴涵时，把结论的前件当作附加前提引入，最后把 ）当结论是蕴涵时，把结论的前件当作附加前提引入， 此附加前提消去，返回到结论，仍作前件。 此附加前提消去，返回到结论，仍作前件。 ◆ 只有结论是蕴涵关系时才能使用CP规律，析取式可转化为蕴 只有结论是蕴涵关系时才能使用 规律， 规律 涵式； 涵式； 消去前提时只能消去引进的前提； ◆ 消去前提时只能消去引进的前提； 一次只能消一个前提； ◆ 一次只能消一个前提；
第六讲命题演算的两个主要准则命题解释以及命题演算的推导规则第六讲命题演算的两个主要准则命题解释以及命题演算的推导规则一命题演算的两个主要准则二命题解释三命题演算的推导规则1什么是命题演算1什么是命题演算2命题演算的两个准则2命题演算的两个准则凡是推导都必须有规则而准则是对规则的要求
命题演算的两个主要准则、 第六讲 命题演算的两个主要准则、命 题解释以及命题演算的推导规则
一、命题演算的两个准则
2、命题演算的两个准则
凡是推导都必须有规则，而准则是对规则的要求。 ◆ 凡是推导都必须有规则，而准则是对规则的要求。 ◆准则与规则的关系如同逻辑规律与具体规则的关系 。
一、命题演算的两个准则
2、命题演算的两个准则
（1）一致性准则：要求推理规则是正确的。 ）一致性准则：要求推理规则是正确的。
三、命题演算的推导规则
命题演算的基本定理： 命题演算的基本定理：
p∧q→q （10）简化律： p ∧ q → p ）简化律： （11）并合律： p ∧ q ↔ p ∧ q ）并合律： （12）并前律： （p → （q → r））↔（p ∧ q） → r ）并前律： ）） ） （13）归谬律： p → （q ∧ ﹁ q ） → ﹁p ）归谬律： （14）附加律： p →（p ∨ q） ↔ q → （p ∨ q） ）附加律： ） ） （15）换位律： （p → q） ↔ （﹁q → ﹁p） ）换位律： ） ） 摩根律： （16）德.摩根律： ﹁ （p ∧ q） ↔ ﹁ p ∨ ﹁ q ） 摩根律 ） ﹁ （p ∨ q） ↔ ﹁ p ∧ ﹁ q ） （17）蕴析律： （p → q） ↔ ﹁ p ∨ q ）蕴析律： ） （18）等值律： （p q） （p → q） ∧ （ q → p ） ）等值律： ） ） ↔ ↔ （p q） （p ∧ q） ∨ （ ﹁ p ∧ ﹁ q ） ） ）

命题逻辑等值演算

命题逻辑等值演算
mi(Mi)称为极小项(极大项)的名称。且有mi Mi ,
Mi mi。
例 2 由p, q两个命题变项形成的极小项与极大项
例 3 p, q, r三个命题变项形成的极小项与极大项
三、主范式
1、主析取范式：由极小项构成的析取范式。
2、主合取范式：由极大项构成的合取范式。
3、主范式：主析取范式与主合取范式统称为主范式。
值。
方法三 用等值演算先化简两个公式，再观察.
例3用等值演算法判断下列公式的类型
(1) q(pq)
解： q(pq)
q(pq) （蕴涵等值式）
q(pq)
（德摩根律）
p(qq)
（交换律，结合律）
p0
（矛盾律）
0
（零律）
由最后一步可知，该式为矛盾式.
(pq)r
（否定号内移——德摩根律）
这一步已为析取范式（两个简单合取式构成）
继续： (pq)r
(pr)(qr) （对分配律）
得到合取范式（由两个简单析取式构成）。
二、极小项与极大项
1、定义 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项（或它的
否定式）均以文字的形式出现且仅出现一次，称这样的简单合取式(简单析取式)为极
离散数学
第二章 命题逻辑等值演算
|
第二章 命题逻辑等值演算
一、等值式
1、等值式：设A，B是命题公式，且AB为重言式,则称A与B是等值的，记作AB。
说明 ：1）符号不是联结符，只是一种记法。
2）若A与B的真值表相同（真值表法），则AB；否则A
B。
3）判断公式等值的方法——利用已知的等值式通过代换得到新的等值式。
五、主范式的应用

命题逻辑及命题演算

命题逻辑及命题演算
时序逻辑的应用
时序逻辑主要用于描述和分析具有时间依赖性的系统，如计算机系 统和控制系统等。
时序逻辑的运算规则
时序逻辑的运算规则包括时间变量的定义、时间运算符的定义和运算 规则等，这些规则用于处理具有时间因素的复合命题和推理。
05 命题逻辑与计算机科学
计算机中的逻辑电路
逻辑门
计算机中的逻辑电路由基本 的逻辑门组成，如与门、或 门和非门。这些逻辑门实现 了基本的逻辑运算，如AND
可编程逻辑电路
通过编程实现特定功能的电路，如 FPGA、CPLD等。
04 命题逻辑的扩展
量词逻辑
量词
量词用来表示命题的数量或 者范围。在量词逻辑中，常 用的量词有全称量词（∀） 和存在量词（∃）。
全称量词
表示对某一集合中所有元素 都适用的命题。例如，∀x P(x)表示对于所有x，P(x)都 成立。
专家系统
专家系统是一种基于知识的系统，它利用逻辑推理来模拟专家的决策过程。 专家系统中的推理机使用命题逻辑来处理知识库中的事实和规则。
自然语言处理
自然语言处理中的语义分析部分涉及到逻辑推理。通过将 自然语言转换为逻辑形式，可以进行推理和问答等任务。
软件工程中的逻辑应用
01
软件测试
在软件工程中，逻辑用于设计和执行软件测试。测试用例通常基于命题
公理五
A ∧ B → A，A ∧ B → B （合取消去规 则）
02 命题演算的基本规则
推理规则
01
分离规则（Modus Ponens）： 如果P导致Q，并且P是真的，那 么可以得出Q也是真的。
02
假言推理规则（Modus Tollens）：如果P导致Q，并且 Q是假的，那么可以得出P也是 假的。

命题演算(推理理论)

命题演算(推理理论)
附加前提证明法
#2022
*
例3 构造下面推理的证明 2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明 (1) 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 (2) 推理的形式结构 前提：pq, pr, rs 结论：sq
*
(2) 写出证明的形式结构 前提：(pq)r, rs, s 结论：pq (3) 证明（证明过程三列式） 序号 当前得到的结论 当前得到结论的理由 ① rs P( 前提引入) ② s P ③ r T ①②I (拒取式) ④ (pq)r P ⑤ (pq) T ③④E (拒取式) ⑥ pq T⑤E 德摩根率
附加前提证明法实例
#2022
*
归谬法 (反证法) 欲证 前提：A1, A2, … , Ak 结论：B 做法 在前提中加入B，推出矛盾. 理由 A1A2…AkB (A1A2…Ak)B (A1A2…AkB) (A1A2…AkB)0 A1A2…AkB0
归谬法实例
*
11 p
⑥ (pq) T④⑤I(析取三段论) ⑦ pq T⑥E 德摩根率 ⑧ p T①⑦I(析取三段论) ⑨ p P pp (矛盾） T⑧⑨I（合取引入） 反证法
A B ∴AB
(11) 破坏性二难推理规则
推理规则
*
判断有效结论的过程就是论证过程。 基本方法： （1）真值表法 （2）直接证明法 （3）间接证明法（反证法） 具体：等值演算、 主析取范式、构造证明法等
三、逻辑证明方法
#2022
*
真值表法
例：判断下列推理是否正确。 今天杨尚树或去网吧或去教室。他没去教室，所以他去网吧了。 设 p：杨尚树去网吧。q：杨尚树去教室。则， 前提：p ∨ q , ¬ q 结论：p 推理的形式结构： ((p ∨ q) ∧¬ q) p

第六讲 命题演算系统

第六讲 命题演算系统



演绎定理：如果Γ ∪{A}├ B，则Γ ├ A→B。 演绎定理的证明需要数学归纳法，数学归纳法是证 明无穷个命题成立的方法，它由两部分组成，分别 是归纳基础和归纳步骤。归纳法可以分为两类： 第一类归纳法：有一批编了号码的命题 （1）我们能证明第1号命题是正确的； （2）如果我们还能证明，在第n号命题正确的时候， 第n+1号命题也正确，那么这一批命题就都是正确 的。
命题演算系统Lp

形式化的公理系统又称为形式系统。一个形 式系统主要由形式语言、初始公式、变形规 则以及由它们得到的公式四部分组成。下面 具体介绍命题演算系统。

命题演算系统Lp



初始符号 1、命题变元：p，q，r，……； 2、命题联接词： ∧，∨，→，，﹁； 3、辅助符号：（，）。 形成规则 1、任何命题变元是合式公式； 2、如果A是合式公式，则（﹁A）是合式公式； 3、如果A、B是合式公式，则（A ∧ B）、（A ∨ B）、 （A → B）、（A B）是合式公式； 4、只有按照1、2、3的规定形成的符号串才是合式公式。
命题演算形式系统Lp
命题演算形式系统Lp； 命题演算系统的可靠性； 命题演算系统的完全性。
命题演算系统Lp

命题演算系统通常记为：P，分为公理演算系统和 自然演绎推理系统，它们都是用形式语言构造出来 的。所谓公理演算系统，指的是由一些基本命题 （即公理）和推导规则以及由此推出的一些命题 （即定理）而形成的演绎系统。所谓自然演绎系统， 指的是没有公理只依赖推导规则推出一些命题（即 定理）而形成的演绎系统。


情况4：B是由出现在演绎序列中在前的两个 公式，通过分离规则得到的，此时前面必定 有两个这样的公式：一个是C，一个是C → B。 两者中的任一必然在LP中由Γ 和A为前提推 出，把这些公式序列数目分别设为：k和m， k和m都小于n。根据归纳假设可得：

2 命题演算

2 命题演算

• 重言式 • 可满足公式 • 矛盾式 • （一）真值表法 • 构造真值表和判定的方法如下： • 1．列出命题变项各种可能的真假组合情
况。 • 2．将被判定的公式分解为各个组成部分， 按照从左至右、由简到繁的顺序排列出来， 而被判定的公式列在最后。
• 3．根据五个基本真值表，依次给出表中所
有公式的真值。 • 4．根据表中最右边一列的值来判定。如果 这一列的值均为真，则该公式是重言式， 否则就不是重言式。
三、范式和优范式
• “范式”，就是仅由命题变元及其否定使用 范式”
合取和析取所构成的公式。 • 范式有两种，一种是合取范式，一种是析 取范式 。 • 合取范式是一合取式，其支命题都是简单 析取。 • 简单析取是其支命题是一个命题变项或 者一个命题变项的否定的析取式。
• 一简单析取式是否为重言式可以用非常简
导出规则
2．4 命题演算的一致性和完全性
• （一）命题演算的一致性 • 1．一致性的语义定义：命题演算是语义一
致的，其系统内的定理都是重言式。 • 2．一致性的语法定义：命题演算是语法一 致的，并非任一公式在其中可证。 • 3．一致性的古典定义：命题演算是古典意 义下一致的，不存在任何公式A 义下一致的，不存在任何公式A，A与非A皆 与非A 可证。
B和¬ B。那么原来的前提可推出¬ A。 。那么原来的前提可推出¬ （12）否定消除规则（ ¬−） 12）否定消除规则（ • 从¬ ¬ A可推出A。 可推出A • （三）定理的证明
2．3 命题逻辑公理系统P 命题逻辑公理系统P
• • • • • • •
（一）初始符号 1．p，q，r，s，p1，q1，…… 2．¬，∨。 3．（，）。 （二）形成规则 1．一个表示命题变项的初始符号π是合式公式。 ．一个表示命题变项的初始符号π 2．如果符号序列A是合式公式，那么¬ A是合 ．如果符号序列A是合式公式，那么¬ 式公式。

离散数学-命题演算

离散数学-命题演算

P Q
于是得到: (P Q) (P Q)
Lu Chaojun, SJTU
21
还有别的联结词吗?
• 除,,,,外还可定义其他联结词.如:
异或: P Q = (P Q) (P Q) 与非(NAND): P | Q = (P Q) Sheffer stroke 或非(NOR): P Q = (P Q) Peirce arrow
Lu Chaojun, SJTU
19
方法一
• 从每个使为真的解释写出一个各命题变
元的合取式;然后写出各合取式的析取式.
例:有三个成真解释.
P
Q
由(P,Q)=(F,F)可写出合取式: F
F
T
P Q
F
T
T
T
F
F
由(P,Q)=(F,T)可写出合取式: T
T
T
P Q
由(P,Q)=(T,T)可写出合取式:P Q
• 将 中所有肯定形式出现的变元Pi换成Pi, 所
有否定形式出现的变元Pi换成Pi, 所得公式记
为－. • 注意:求*时不能有,;求－时无此限制.
Lu Chaojun, SJTU
29
*和－的性质
• 定理
(*)* = (－)－=
• 定理
(*) = ()* (－) = ()－
• 定理
= *－ (De Morgan律的一般形式)
命题逻辑的等值演算 和推理演算
主要内容
• 公式间的等值关系与等值演算 • 利用真值表列写公式 • 联结词的完备集 • 对偶定理 • 范式和主范式 • 公式间的重言蕴涵关系与推理演算
Lu Chaojun, SJTU
2
公式间的等值关系

【精选资料】第1章 逻辑代数上命题演算

【精选资料】第1章 逻辑代数上命题演算

第1章逻辑代数（上）：命题演算1.1 逻辑联结词与命题公式1.1.1 逻辑联结词否定词(negation)“并非”(not)，用符号⌝（或~）表示。

设p表示一命题，那么⌝p表示命题p的否定。

当p真时⌝p假，而当p假时⌝p真。

⌝p读作“并非p”或“非p”。

用类似表1.1的真值表(truth table)规定联结词的意义。

表1.1p ⌝p1 1 0合取词(c onjunction)“并且”(and)，用符号∧表示。

设p，q表示两命题，那么p∧q 表示合取p和q所得的命题，即当p和q同时为真时p∧q真，否则p∧q为假。

p∧q读作“p并且q”或“p且q”。

合取词∧的意义和命题p∧q的真值状况可由表1.2来刻划。

表1.2p q p∧q0 0 1 1 0111析取词(disjunction)“或”(or)用符号∨表示。

设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有一为真时，p∨q为真，只有当p和q均假时p∨q为假。

p∨q 读作“p或者q”，“p或q”。

析取词∨的意义及复合命题p∨q的真值状况由表1.3描述。

表1.3p q p∨q0 0 1 1 011111蕴涵词(implication)“如果……，那么……”(if…then…)，用符号→表示。

设p，q 表示两命题，那么p→q表示命题“如果p，那么q”，它常被称作条件命题。

当p真而q假时，命题p→q为假，否则均认为p→q为真。

p→q中的p称为蕴涵前件，q称为蕴涵后件。

p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p 的必要条件”，“q当p”，“p仅当q”等等。

数学中还常把q→p，⌝p→⌝q，⌝q→⌝p分别叫做p→q的逆命题，否命题，逆否命题。

蕴涵词→的意义及复合命题p→q的真值状况规定见表1.4。

表1.4p q p→q0 0 1 1 011111双向蕴涵词(two-way implication)“当且仅当”（if and only if），用符号↔表示之。

命题演算

命题演算

1/6/2019 2:29 PM
Hongzhi Qiao, Xidian Univ.
25
第一章 --- 数理逻辑
Propositional Equiva lences 命题演算
联结的
1/6/2019 2:29 PM
Hongzhi Qiao, Xidian Univ.
8
第一章 --- 数理逻辑
举例：证明P→(Q→(P∧Q))是重言式
Propositional Equiva lences 命题演算
证明：构造它的真值表，用来看是否在它的任一解释I下其真
值都为真。
P Q (P∧Q) (Q→(P∧Q)) P→(Q→(P∧Q))
第一章 --- 数理逻辑
Propositional Equiva lences 命题演算
1/6/2019 2:29 PM
Hongzhi Qiao, Xidian Univ.
12
第一章 --- 数理逻辑
Show that the propositions p→q and
Propositional Equiva lences 命题演算
题变项代换同一公式。
（重言式之值不依赖于变元的值。）
常元（T 、F） 变元（A、B、C、。。。。。。）
1/6/2019 2:29 PM
Hongzhi Qiao, Xidian Univ.
18
第一章 --- 数理逻辑
举例：使用代入规则证明重言式。
Propositional Equiva lences 命题演算
第一章 --- 数理逻辑
logical expression?
Propositional Equiva lences 命题演算
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
注. ↑在《数字逻辑》与《数字电路》中称为“与非门(NAND) ” 。
3
§5.联结词归约 范式(NF) 5.联结词归约 范式(
(3)“或非 或非(not-or) ” 或非 表示“或非”的符号是: ↓ 符号↓ 称为谢孚竖(Sheffer stroke)。 谢孚竖 谢孚 对于两个命题p和q, p和q的或非命题“p或q不成立”表 示为：p↓q 。 p↓q称为p和q的或非式。 或非式 或非 p q p↓q p↓q为真⇔p且q为假。 t t f “或非”的真值表见表3: t f f p↓q q ¬(p∨q) ¬p∧¬q ； (p∨ ∧¬q f t f ¬p p p; p↓p; f f t p∧q (p p)↓(q q) ; (p↓p) (q↓q) 表3 p∨q (p q)↓(p q) 。 (p↓q) (p↓q)
1
§5.联结词归约 范式 联结词归约 范式(NF)
“异或”的真值表见表1: 常见的析取词还有: 不是,就是;可能,可能; 或者, 或者；…。 p ∨ q ¬(p↔q) (p↔ (p∨q)∧ (p∨q)∧(¬p∨¬q) ∨¬q) (p∧¬q)∨ (p∧¬q)∨(¬p∧q) p ∨ q ⊨p∨q , 反之不成立。 ∨
6
§5.联结词归约 范式 联结词归约 范式(NF)
证. 对于任一真值函项f(p1, p2, …, pn)(n≥1),设f所有的证实赋值 构成的集合为 {v|f(v)=t}={v1, v2, …, vm} (m≤2n) 其中:vi= (p1vi , p2vi, …, pnvi) (1≤ i≤ m) 。 对于每一个vi ,构造如下的合取式: αi= q1i ∧ q2i ∧ … ∧ qni (1≤ i≤ m) 其中: vi
p q r t t t t t f t f t t f f f t t f t f f f t f f f 表4
5
w(p,q, r) f f f t √ f f f t √
例1.表4给出了一个三元真值函项w: 给出了一个三元真值函项w 于是w(p,q, r) (p∧¬q∧¬r)∨(¬p∧¬q∧¬r) 于是 ¬q∧¬r ¬(q∨r) ; ¬p w(q,p, p) ; (q任意) ( ) p∧q ¬ ¬p∧¬ ¬q w(r, ¬p, ¬q) w(r, w(r′,p, p) , w(r′′,q, q) ) (r, r′, r′′任意) )
10
§5.联结词归约 范式 联结词归约 范式(NF)
定理4.范式存在性定理 定理 对于任何公式α,都存在DNF β,和CNF γ,使得 α β , α γ。 证.给出一个将公式α化为析取范式 (DNF)和合取范式(CNF)的算法: 1°联结词归约 联结词归约:将公式α中的联结词→,↔用联结词归约律化归 联结词归约 为仅含联结词¬,∧,∨的公式; 2°否定词深入 否定词深入:将公式中的否定词¬ 用否定深入定理,de 否定词深入 Morgan律(替换定理)直接移到每个原子(命题变项)之前; 3° ∧与∨调整 调整:利用分配律,结合律,交换律将公式化归成析取范 式 (DFN)和合取范式(CNF); 4°化简 化简:利用化简律,幂等律,吸收律消去一些多余的支(项)。 化简
12
Hale Waihona Puke §5.联结词归约 范式(NF) 5.联结词归约 范式(
例3.求公式α=(p→q)↔p∧r的DNF和CNF 。 解.1CNF α (¬(¬p∨q)∨(p∧r))∧(¬(p∧r)∨(¬p∨q)) (联结词归约律 替换) ((p∧¬q)∨(p∧r))∧((¬p∨¬r)∨(¬p∨q)) (de Morgan律,反身律) p∧(¬q∨r)∧(¬p∨q∨¬r) (分配律,结合律,交换律,幂等律) 2DNF α p∧(¬q∨r)∧(¬p∨q∨¬r) (利用1) ((p∧¬q)∨(p∧r))∧(¬p∨q∨¬r) (分配律) ((p∧¬q)∧(¬p∨q∨¬r))∨((p∧r)∧(¬p∨q∨¬r)) (分配律) (p∧¬q∧¬p)∨(p∧¬q∧q)∨(p∧¬q∧¬r)∨(p∧r∧¬p) ∨(p∧r∧q)∨(p∧r∧¬r) (分配律, 结合律) (p∧q∧r)∨(p∧¬q∧¬r) (化简律, 交换律)
8
§5.联结词归约 范式 联结词归约 范式(NF)
注. 这正是《数字逻辑》与《数字电路》中选择‘与非门’或者‘或非门’ 作为基本逻辑门及基本电路元件的原因。 但是‘与非↑’及‘或非↓’作为逻辑运算符,却不满足结合律。即 (p↑q )↑r p↑(q↑r) p q r p↑q (p↑q )↑r q↑r p↑(q↑r) (p↓q )↓r p↓(q↓r) t t t f t f t 第 一式如表5: t t f f t t f 令:α= (p↑q )↑r t f t t f t f β= p↑(q↑r) t f f t t t f 则观察表5可知: f t t t f f t α之列≠ β 之列, f t f t t t t 故 α β。 f f t 由于‘与非↑’及‘或非↓’不满足结 合律,所以在电路的逻辑设计初期 f f f 并不用它们,因为不方便。 t t f t 表5
~ 这里: p j (1≤ j≤n)是对应pj的一对文字之一。
2
§5.联结词归约 范式 联结词归约 范式(NF)
(2)“与非 与非(not-and) ” 与非 表示“与非”的符号是: ↑ (或) 符号↑ (或) 称为谢孚竖(Sheffer stroke)。 谢孚竖 谢孚 对于两个命题p和q, p和q的与非命题“p且q不成立”表 示为：p↑q 。 p↑q称为p和q的与非式。 与非式 与非 p q p↑q p↑q为真⇔p或q为假。 t t f “异或”的真值表见表2: t f t p↑q q ¬(p∧q) ¬p∨¬q ; (p∧ ∨¬q f t t ¬p p p; p↑p; f f t p∧q (p q)↑(p q) ; (p↑q) (p↑q) 表2 p∨q (p p)↑(q q) 。 (p↑p) (q↑q)
§5.联结词归约 范式(NF) 联结词归约 范式 (7).极小全功能集 极小全功能集 若全功能集A中每一个联结词,都不能用其余联结词来表达, 则称A是一个极小全功能集,或极小功能完备集。 定理2.联结词集{¬ ,∧} {¬ ,∨} {¬ ,→}都是极小全功能集 极小全功能集。 定理 定理3.联结词集{↑}, {↓} 都是极小全功能集 极小全功能集。 定理 全功能集 证. 1{↑}是全功能集 只须证全功能集{¬ 只须证全功能集 ,∧}中的每个联结词都可用联结词↑ 来表达既可。而这点已在本节1(2)中介绍过了。 2 {↑}是极小的 极小的 {↑}只有一个 只有一个联结词,当然是极小的 极小的。
注. p t t f f q t f t f 表1 p ∨q f t t f
∨ 在《数字逻辑》与《数字电路》中称为“异或门(EX) ”。
通常一个析取命题是形式化成“可兼或”或“不可兼或”，要根据实际
情况来定 。一般情况，先形式化成“可兼或”，若信息不够(比如在推理 ( 中) ，再形式化成“不可兼或”。
9
t t
t t
§5.联结词归约 范式 联结词归约 范式(NF)
2.范式 范式(NF—normal form) 范式 范式(NF—normal form) (1)范式 范式 范式是公式的规范形式。只含联结词¬,∧,∨ 。 , (2)析取范式 析取范式(DNF—disjunctive normal form) 析取范式
(3)合取范式 合取范式(CNF—conjunctive normal form) 合取范式
公式α是合取范式 ⇔ α是一合取式,即α= α1∧α2∧ … ∧αm 。 其中: 每个合取项αi (1≤ i≤m)都是文字的一个析取式。 例如公式α= ¬p ∧(p∨q∨¬r)∧(q∨¬r)是合取范式 (CNF)。
13
§5.联结词归约 范式 联结词归约 范式(NF)
(4)主范式 主范式(MNF—main normal form) 主范式 主范式是一范式，但相对于某一命题变项组(p1, p2, …, pn) 是全的。或者说是唯一的。 (5)主析取范式 主析取范式(MDNF—main disjunctive normal form) 主析取范式 公式α是主析取范式 ⇔ α是一析取范式,即 α= α1∨α2∨ …∨αm 。 其中: 每个析取项αi (1≤ i≤m)相对于命题变项组(p1, p2, …, pn)为 α i = ~1 ∧ ~ 2 ∧ ⋯ ∧ ~ n p p p
注. ↓在《数字逻辑》与《数字电路》中称为“或非门(NOR)”。
4
§5.联结词归约 范式 联结词归约 范式(NF)
(4).真值函项 真值函项(truth function) 真值函项 n元函数 f:{t,f}n→{t,f}称为n元真值函项(算子)。 一元真值函项：¬ ； 二元真值函项：∧,∨,→,↔,↑,↓, ∨ 等。
§5.联结词归约 范式 联结词归约 范式(NF)
p∨q
¬ ¬(p∨q) ∨ ¬w(r′, p, q)
w(r, w(r′,p, q) , w(r′′,p, q) ) (r, r′, r′′任意) 。 ) (5).联结词集 联结词集: 联结词集 真值函项集的任一子集A,都称为是一个联结词集。 例如{¬},{∧},{∨},{→},{↔} ,{↑},{↓},{¬,∧}, {¬,∨},{¬,→},{∧,∨} {¬ ,∧,∨},{ ∨ }…都是联结词集。 (6).全功能集 全功能集 一个联结词A,若对任一真值函项f,都可由A中的联结词来 表达,则称A是一个全功能集,或功能完备集。 定理1.联结词集{¬ ,∧,∨}是一个全功能集 全功能集。 定理
§5.联结词归约 范式(NF) 5.联结词归约 范式( 1.联结词归约
(1)“异或 异或(exclusive or) ” 异或
“异或”就是§2(3) 曾经提到过的“不可兼或” 。也 称其为“不可兼析取(exclusive disjunction) ” 。 表示“异或”的符号是: (或⊕)， ∨ 符号 ∨ 称为异或词, 简称异或 异或词 异或。 异或 异或 对于两个命题p和q, p和q的异或命题“要么p要么q”表 示为: ∨ q 。 p p ∨ q称为p和q的不可兼析取式。p、q称为该不可兼析 不可兼析取 不可兼析取式 取式的析取项。 析取项 析取 p ∨ q为真⇔p、q之一为真(不能同时为真) 。