和“˄”的公式。 （2）由P→Q¬P˅Q，故可把包含→的公式等价变换为包含“¬”和“˅”的
公式。 （3）由P˄Q¬(¬P˅¬Q)，P˅Q¬(¬P˄¬Q)说明“˄”与“˅”可以相互交换。 故由“¬”“˄”“˅”“→”“↔”这5个联结词中若干个组成的命题公式，
1.3 命题公式与真值表
1.3 命题公式与真值表
等价式 定义1.3.4 给定两个命题公式A和B，设P1 , P2, P3,...Pn为所有出现于A和B中的
原子变元，若给P1 , P2, P3,...Pn任一组真值指派，A和B的真值都相同，称A和B 是等价的，记作AB。
从上述真值表的例子中，可以知道： ¬ P ˅ Q P→Q
设P: 我有就学机会； Q:我必用功读书。
所以本例可描述为： P→Q
1.2 复合命题与联结词
常用的联结词 （4）条件 P→Q的真值
当且仅当P的真值为T，Q的真值为F时，P→Q 为F.其余情况，P∨Q为T
PQ TT TF FT FF
P→Q T F T T
1.2 复合命题与联结词
常用的联结词 （5）双条件 定义1.2.6 给定两个命题P, Q，其复合命题P↔Q称作双条件命题，读作P当
离散数学期末复习
1.1 命题概念
命题：具有唯一真值的陈述句
1.1 命题概念
练习：
1.下列句子为命题的是（ D ）
A.全体起立！
B. X=0
C. 我在说谎
D.张三生于1886年的春天
2.下列句子不是命题的是（ D ）
A.中华人民共和国的首都是北京 B.张三是学生
C.雪是黑色的
D.太好了！
1.2 复合命题与联结词
(P˄Q) ˅(¬ P˄¬ Q)P↔Q 上述二式以后经常作为等值公式直接应用。
1.3 命题公式与真值表
定义1.3.5 设A为一命题公式，若A在它的各种指派情况下，其取值均为真, 则 称公式A为重言式或永真式。
定义1.3.6 设A为一命题公式，若A在它的各种指派情况下，其取值均为假, 则 称公式A为矛盾式或永假式。
常用的联结词 （1）否定
定义1.2.1 设P为一命题，P的否定是一个新的命题，记作¬P。 “¬”表示命题的否定.
¬ P的真值： 若P为T，¬ P为F；若P为F，¬ P为T
P
¬P
F
T
T
F
1.2 复合命题与联结词
常用的联结词 （2）合取 定义1.2.2 两个命题P和Q的合取是一个复合命题，记作P∧Q。 ∧称作合取联结词， 在自然语言中的“并且”、“和”、“既...又...”、“不
P↔Q T F F T
1.2 复合命题与联结词
1.2 复合命题与联结词
1.3 命题公式与真值表
真值表
定义1.3.3 设P为一命题公式，P1 , P2, P3,...Pn 为出现在P中的所有命题变元， 对 P1 , P2, P3,...Pn 指定一组真值称为对P的一种指派。若指定的一种指派，使P 的值为真，则称这组值为成真指派；若指定的一种指派，使P的值为假，则称 这组值为成假指派。
仅....而且....”、“虽然...但是...”等都可以符号化为∧ 例1 2是素数和偶数 设P：2是素数，Q:2是偶数，故上述命题可表述为P∧Q 例2 王乙工作努力且身体好。 设P:王乙工作努力，Q:王乙身体好，故上述命题可表述为P∧Q
1.2 复合命题与联结词
常用的联结词
（2）合取
P∧Q的真值
且仅当Q。 例 两个三角形全等，当且仅当它们的三组对应边相等。
设P: 两个三角形全等； Q:它们的三组对应边相等。
所以本例可描述为： P↔Q
1.2 复合命题与联结词
常用的联结词 （5）双条件 P↔Q 的真值
当P与Q的真值为相同时，P↔Q 为T.其余情况，P↔Q 为F
PQ TT TF FT FF
定义1.3.7 设A为一命题公式，若A在它的各种真值指派下至少存在一组成真指 派，则称A是可满足式。
1.3 命题公式与真值表
对合律 PP 幂等律 PPP,
PPP 结合律 (PQ)RP(QR),
(PQ)RP(QR) 交换律 PQQP,
PQQP 分配律 P(QR)(PQ)(PR),
P(QR)(PQ)(PR)
1.3 命题公式与真值表
吸收律 P(PQ)P,
P(PQ)P
德摩根律 (PQ)PQ,
(PQ)PQ
同一律
PFP ,
PTP
零律
PTT,
PFF
否定律
P ˅PT,
PPF
两个等值公式： ¬ P ˅ Q P→Q (P˄Q) ˅(¬ P˄¬ Q)P↔Q
1.4 等价变换与蕴含式
等价变换
定理1.4.1 设 X 是合式公式 A 的子公式，若有Y也是一个合式公式，且XY， 如果将A中的X用Y置换， 得到公式B,则 AB。
常用的联结词 （3）析取 定义1.2.3 两个命题P, Q的析取是个复合命题，记作P∨Q。 ∨称作析取联结词， 与自然语言中的“或”有些相似 例4 王强是这次校运动会的跳高或100米短跑的冠军。
设P: 王强是这次校运动会的跳高冠军； Q:王强是这次校运动会的100米短跑的冠军。
所以本例可描述为： P∨Q
例：证明Q→(P˅(P˄Q))Q→P 证：设A：Q→(P˅(P˄Q))，
因为P˅(P˄Q)P（吸收律） 故B:Q→P，即AB
1.4 等价变换与蕴含式
等价变换 判断命题公式是重言式或矛盾式
真值表 等价变换
1.4 等价变换与蕴含式
1.5 最小联结词组与范式
最小联结词组 （1）由P↔Q(P→Q)˄(Q→P)，故可把包含↔的公式等价变换为包含“→”
Hale Waihona Puke 当且仅当P与Q同时为T时，P∧Q为T.其余情况，P∧Q为F
PQ TT TF FT FF
P∧Q T F F F
1.2 复合命题与联结词
常用的联结词 （2）合取 注意:
命题联结词“合取”可将两个互为否定的命题联结在一起：P∧¬P 此时其真值永为F
P ¬P TF FT
P∧¬P F F
1.2 复合命题与联结词
1.2 复合命题与联结词
常用的联结词
（3）析取
P∨Q的真值
当且仅当P与Q同时为F时，P∨Q为F.否则，P∨Q为T
PQ TT TF FT FF
P∨Q T T T F
1.2 复合命题与联结词
常用的联结词 （4）条件 定义1.2.4 给定两个命题P, Q，其条件命题是一个复合命题，记作P→Q。 其中P为前件，Q为后件。P→Q读作“如果P那么Q”，“若P则Q” 例6 如果我有就学机会，那么我必用功读书。