离散数学-命题逻辑课件.ppt

1、Proposition LogicProposition Logic2022-12-241Concept 本章主要讨论：本章主要讨论：命题的表示、命题的演算命题的表示、命题的演算命题演算中的公式及其应用命题演算中的公式及其应用命题逻辑推理命题逻辑推理第一章第一章 命题逻辑Proposition LogicProposition Logic2022-12-242Concept 本节主要讨论三个问题：本节主要讨论三个问题：命题的概念命题的概念 命题的真值及命题的表示命题的真值及命题的表示 原子命题与复合命题原子命题与复合命题1.1 命题与命题的表示Proposition LogicProposit

2、ion Logic2022-12-243一、命题的概念一、命题的概念 命题命题是是一个能确定是真的或是假的一个能确定是真的或是假的判断。判断。（判断都是用（判断都是用陈述句陈述句表示）表示）All the following statements are propositions.1.Washington,D.C.,is the capital of the United States of America.2.Toronto is the capital of Canada.3.1+1=2.4.2+2=3.Propositions 1 and 3 are true,whereas 2 and

3、 4 are false.ConceptProposition LogicProposition Logic2022-12-244ExampleConsider the following sentences.1.What time is it?2.Read this carefully.3.x+1=2.4.x+y=z.Sentences 1 and 2 are not propositions because they are not statements.Sentences 3 and 4 are not propositions because they are neither ture

4、 nor false,since the variables in these sentences have not been assigned values.Proposition LogicProposition Logic2022-12-245Concept陈述句的分类陈述句的分类一般命题一般命题模糊命题模糊命题模态命题模态命题悖论悖论 地球绕太阳旋转。地球绕太阳旋转。100100是个大数。是个大数。下个月要下雨。下个月要下雨。我在说假话。我在说假话。Proposition LogicProposition Logic2022-12-246Concept命题的语句形式命题的语句形式:陈述

5、句陈述句非命题语句：非命题语句：疑问句疑问句 命令句命令句 感叹句感叹句 非命题陈述句：悖论语句非命题陈述句：悖论语句Proposition LogicProposition Logic几个经典的悖论几个经典的悖论:1 1、哲学家、哲学家EpimenidesEpimenides（埃庇米尼得斯，克里特哲（埃庇米尼得斯，克里特哲学家、预言家）学家、预言家）:“所有克利特人都在说谎，他所有克利特人都在说谎，他们中的一个诗人这么说。们中的一个诗人这么说。”2 2、理发师悖论、理发师悖论:“本人的理发技艺十分高超，誉满本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，全城。我将为本城

6、所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢我也只给这些人刮脸。我对各位表示热诚欢迎！迎！”3 3、苏格拉底悖论：、苏格拉底悖论：“我只知道一件事，那就是什我只知道一件事，那就是什么都不知道。么都不知道。”2022-12-247ConceptProposition LogicProposition Logic2022-12-248二、命题的真值及命题的表示二、命题的真值及命题的表示命题真值（命题真值（Truth Values）的表示：）的表示：真：真：T、1；假：假：F、0命题的符号表示：命题的符号表示：大写英文字母：大写英文字母：P、Q、R、带下标的大写字母：带下标的大写

7、字母：A1、A2、A3、数字：数字：1、2、3、ConceptProposition LogicProposition Logic2022-12-249命题语句真值确定的几点说明：命题语句真值确定的几点说明：1 1、时间性、时间性 2 2、区域性、区域性 3 3、标准性、标准性命题真值间的关系表示：命题真值间的关系表示：真值表（真值表（Truth Table)Truth Table)ConceptProposition LogicProposition Logic2022-12-2410Concept三、原子命题与复合命题三、原子命题与复合命题 简单命题简单命题 (原子命题原子命题)：由最简单

8、的陈述句由最简单的陈述句构成的命题构成的命题 (该句再不能分解成更简单的该句再不能分解成更简单的句子了句子了)。通常用大写英文字母表示。通常用大写英文字母表示。例例:2:2是个素数是个素数。复合命题复合命题 (分子命题分子命题)：由若干个原子命题由若干个原子命题构成的命题。构成的命题。例例:ab:ab、bcbc、ac,ac,是由三个原子命题是由三个原子命题构成的复合命题。构成的复合命题。Proposition LogicProposition Logic2022-12-2411conjuntion1.2 联结词 复合命题的构成：是用复合命题的构成：是用“联结词联结词”将原将原子命题联结起来构成

9、的。子命题联结起来构成的。归纳自然语言中的联结词，定义了六个归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：逻辑联结词，分别是：Proposition LogicProposition Logic2022-12-2412conjunction 表示：表示：“不成立不成立”，“不不”。用于：对一个命题用于：对一个命题P P的否定，写成的否定，写成 P P，并并读成读成“非非P P”。P P的真值：与的真值：与P P真值相反。真值相反。一.否定“”P P：今天是星期五：今天是星期五。P P：今天不是星期五今天不是星期五。P PT FF TProposition LogicPropositio

10、n Logic2022-12-2413 表示：表示：“并且并且”，“与与”,它仅表示逻辑上它仅表示逻辑上的的“与与”,与日常语言中的与日常语言中的“与与”不同。不同。conjunction二.合取“”P Q PQF F FF T FT F FT T T P：小王能唱歌。Q：小王能跳舞。PQ：小王能歌善舞。PQ的真值为真,当且仅当P和Q的真值均为真。Proposition LogicProposition Logic2022-12-2414 表示表示“或者或者”，是可兼取的。，是可兼取的。conjunction三.析取“”v 灯泡灯泡或者或者线路有故障。线路有故障。v第一节课上数学第一节课上数学

11、或者或者上上英语。英语。v汽车提前十五汽车提前十五或或二十分二十分钟到达。钟到达。可兼或或者排斥或表示近似数Proposition LogicProposition Logic2022-12-2415conjunction 析取“”的真值表P Q PQF F FF T TT F TT T TPQ的真值为F，当 且仅当P和Q均为FP:P:李明在教室。李明在教室。Q:Q:米卢是个好教练。米卢是个好教练。P P Q:Q:李明在教室或米卢李明在教室或米卢是个好教练。是个好教练。Proposition LogicProposition Logic2022-12-2416conjunctionP:P:米卢

12、在西安。米卢在西安。Q:Q:米卢在北京。米卢在北京。P P Q:Q:米卢在西安或者米卢米卢在西安或者米卢在北京。在北京。P Q的真值为F，当 且仅当P与Q的真值相同P Q P QF F FF T TT F TT T F四、异或“”Proposition LogicProposition Logic2022-12-2417 异或的另一种表示conjunctionv 异或异或是表示两个命题是表示两个命题不可能同时都成立。不可能同时都成立。v 命题命题“第一节课上数学第一节课上数学或者或者上英语。上英语。”可可以解释为：以解释为：“第一节课上数学而没有上英语第一节课上数学而没有上英语或者或者第一第一

13、节课上英语而没有上数学。节课上英语而没有上数学。”于是有于是有 P Q P Q 与与 (P(P Q)Q)(Q(Q P P)是一样的。是一样的。实际应用中必须注意实际应用中必须注意“或者或者”的二义性的二义性,注意注意区别可兼或和排斥或。这里不考虑近似或。区别可兼或和排斥或。这里不考虑近似或。Proposition LogicProposition Logic2022-12-2418五、蕴涵(条件)“”conjunction表示“如果P 则 Q”单条件,蕴涵P:前提、Q:结论P表示：缺少水分。Q表示：植物会死亡。PQ：如果缺少水分，植物就会死亡。P Q P QF F TF T TT F FT T

14、 T如果235，则今年是丰收年。Proposition LogicProposition Logic2022-12-2419 注意：“”既表示充分条件也表示必要条件，它决定了哪个作为它决定了哪个作为前件前件，哪个作为哪个作为后件后件。conjunction令：令：P P：天气好。：天气好。QQ：我去公园。：我去公园。1.1.如果天气好，我就去公园。如果天气好，我就去公园。（充分）（充分）2.2.只要天气好，我就去公园。只要天气好，我就去公园。（充分）（充分）3.3.仅当天气好，我才去公园。仅当天气好，我才去公园。（必要）（必要）4.4.只有天气好，我才去公园。只有天气好，我才去公园。（必要）（

15、必要）命题命题1 1、2 2 写成：写成：P PQ Q 命题命题3 3、4 4 写成：写成：Q QP PProposition LogicProposition Logic2022-12-2420conjunctionv Find the converse and the contrapositive of the implication If today is Thursday,then I have a test today.Solution:The converse is If I have a test today,then today is Thursday.And the cont

16、rapositive of this implication is If I do not have a test today,then today is not Thursday.Proposition LogicProposition Logic2022-12-2421conjunction六、等价(双条件）“”表示“P当且仅当Q”P：ABC是等边三角形。Q：ABC是等角三角形。PQ：ABC是等边三角形当且仅当它是等角三角形。P Q P QF F TF T FT F FT T TProposition LogicProposition Logic2022-12-2422Question练习

17、：填空已知PQ为T，则P为()，Q为()。已知PQ为F，则P为()，Q为()。已知P为F，则PQ为()。已知P为T，则PQ为()。已知PQ为T，且P为F，则Q为()。已知PQ为F，则P为()，Q为()。已知P为F，则PQ为()。已知Q为T，则PQ为()。已知 PQ为F，则P为()，Q为()。Proposition LogicProposition Logic2022-12-2423Question已知P为T，PQ为T，则Q为()。已知Q为T,PQ为T，则P为()。已知PQ为T，P为T,则Q为().已知PQ为F，P为T,则Q为().PP 的真值为().PP 的真值为()。Proposition

18、LogicProposition Logic2022-12-24241-3 命题公式及等价公式一一.命题变元命题变元 命题常量命题常量：即是我们前面所说的命题。例如：即是我们前面所说的命题。例如：“3 3是素数。是素数。”就是命题常量。就是命题常量。命题变元命题变元：用大写的英字母如：用大写的英字母如P P、QQ等表示任等表示任何命题。称这些字母为命题变元。何命题。称这些字母为命题变元。对命题变元作指派对命题变元作指派(给命题变元一个解释给命题变元一个解释)：将：将一个命题常量赋值给命题变元的过程，或者是一个命题常量赋值给命题变元的过程，或者是直接赋给命题变元真值直接赋给命题变元真值“T”T”

19、或或“F”F”的过程。的过程。注意注意：命题变元本身不是命题，只有给它一个：命题变元本身不是命题，只有给它一个指派，才变成命题。指派，才变成命题。FormulaProposition LogicProposition Logic2022-12-2425二.合式公式(wff)(well formed formulas)定义：1.命题变元是命题公式；2.设P是命题公式，则P也是命题公式；3.设P、Q是命题公式，则（P Q）、（P Q）、（P Q）、（P Q）也是命题公式；4.有限次地使用1、2、3所得到的也是命题公式。FormulaProposition LogicProposition Logi

20、c2022-12-2426 约定约定：为方便，最外层括号可以不写，合式公式可以写成：PQ，PR，(PQ)R 如果规定逻辑联接词的优先级：、则：P Q R也是合式公式FormulaProposition LogicProposition Logic2022-12-2427三.命题符号化Formula命题符号化的方法 1.首先要明确给定命题的含义。2.对于复合命题，找联结词，用联结词 断句，分解出各个原子命题。3.设原子命题符号，并用逻辑联结词联 结原子命题符号，构成给定命题的符 号表达式。Proposition LogicProposition Logic2022-12-2428vHow can

21、 the following English sentence be translated into a logical expression?You can access the Internet from campus only if you are a computer science major or you are not a freshmanFormulaSolution:a (c f ).Proposition LogicProposition Logic2022-12-2429v How can the following English sentence be transla

22、ted into a logical expression?You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.Solution:(r s)q.FormulaqrsProposition LogicProposition Logic2022-12-2430Formulav 说离散数学无用且枯燥无味是不对的。说离散数学无用且枯燥无味是不对的。P：离散数学是有用的。：离散数学是有用的。Q：离散数学是枯燥无味的。：离散数学是枯燥无味的。该命题可写成

23、：该命题可写成：(PQ)v 人不犯我，我不犯人；人若犯我，我必犯人不犯我，我不犯人；人若犯我，我必犯人。人。P：人犯我。：人犯我。Q：我犯人。：我犯人。该命题可写成：该命题可写成：(PQ)(PQ)或写成：或写成：PQP是是Q的必要条件的必要条件P是是Q的充分条件的充分条件P是是Q的充分且必要条件的充分且必要条件Proposition LogicProposition Logic2022-12-2431四、命题公式的真值表v所有公式中的命题变量用指定真值进行指所有公式中的命题变量用指定真值进行指派，即得到一个公式对应的真值。派，即得到一个公式对应的真值。P Q PPQ(PQ)Q T T F T

24、T T F F T T F T T T T F F T F FFormulaProposition LogicProposition Logic2022-12-2432 说明说明:设设P1P1，P2,P2,Pn,Pn为命题公式为命题公式P P中的命题变量，中的命题变量，对于命题变元每一种真值指派的可能组合，对于命题变元每一种真值指派的可能组合，都能唯一确定都能唯一确定P P的真值（即有的真值（即有2 2的的n n次幂种分次幂种分布）。布）。为了有序地列出公式的真值表，在对命题变为了有序地列出公式的真值表，在对命题变元做指派时，可以按照元做指派时，可以按照二进制数二进制数的次序列表的次序列表。F

25、ormulaProposition LogicProposition Logic2022-12-2433 二进制操作FormulaProposition LogicProposition Logic2022-12-2434为了为了有序地列出有序地列出A(PA(P1 1,P,P2 2,P,Pn n)的真值表，可以将的真值表，可以将F F看成看成0 0，将，将T T看成看成1 1，按照，按照二进制数二进制数00000,0,000001,0001,00010,010,11,1110,1110,111(1(即十进制的即十进制的0,1,2,0,1,2,.,2.,2n n-1)-1)的次序进行指派列真值表

26、。的次序进行指派列真值表。例如，例如，A(P,Q)A(P,Q)的真值表可按照如下次序指派：的真值表可按照如下次序指派：00(F,F)00(F,F)，01(F,T)01(F,T)，10(T,F)10(T,F)，11(T,T)11(T,T)例如，例如，A(P,Q,R)A(P,Q,R)的真值表可按照如下次序指派：的真值表可按照如下次序指派：000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T)100

27、(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T)FormulaProposition LogicProposition Logic2022-12-2435 例如列出例如列出P P(QQR)R)的真值表的真值表 P Q R Q RP(QR)000 F F F T T001 F F T T T010 F T F F T 011 F T T T T100 T F F T T101 T F T T T110 T T F F F111 T T T T TFormulaProposition LogicProposition Logic2022-12-2436 观察下面的真

28、值表Formula P Q P Q P Q（P Q）（P Q）P Q F F T T T T F T T T F F T F F F F F T T T T T T在上面的真实表中你是否发现什么问题？P Q P Q？（P Q）（P Q）P Q？Proposition LogicProposition Logic2022-12-2437 A AB B的定义的定义：A A、B B是含有命题变元是含有命题变元P P1 1,P,P2 2,P Pn n的命题公式，如不论对的命题公式，如不论对P P1 1,P,P2 2,P Pn n作任何指作任何指派，都使得派，都使得A A和和B B的真值相同，则称之为的

29、真值相同，则称之为A A与与B B等等价，记作价，记作A AB B。显然显然 P Q P Q （P Q）（P Q）P Q v 结论：结论：判断两个公式是否等价，更好的方判断两个公式是否等价，更好的方法是当变元数不多时，直接构造两个公式法是当变元数不多时，直接构造两个公式的真值表，看两个真值表是否相等即可。的真值表，看两个真值表是否相等即可。FormulaProposition LogicProposition Logic2022-12-2438 基本的等价公式基本的等价公式 对合律对合律 P PP P 幂等律幂等律 P PP PP PP PP PP P 结合律结合律 P P(QQR)R)(P

30、PQ)Q)R R P P(QQR)R)(P PQ)Q)R R 交换律交换律 P PQQQQP PP PQQQQP P 分配律分配律 P P(QQR)R)(P PQ)Q)(P PR)R)P P(QQR)R)(P PQ)Q)(P PR)R)吸收律吸收律 P P(P PQ)Q)P PP P(P PQ)Q)P P 德摩根定律德摩根定律 (P PQ)Q)P P Q Q (P PQ)Q)P P QQFormulaProposition LogicProposition Logic2022-12-2439 同一律同一律 P PF FP PP PT TP P 零律零律 P PT TT PT PF FF F 互

31、补律互补律 P P P PT T P P P PF F 附加：附加：P PQQP PQ Q P PQQQQP P P PQ Q(P PQ)Q)(Q(QP)P)P PQ Q(P PQ)Q)(P(P Q)Q)P PQ Q(P PQ)Q)(P P Q)Q)FormulaProposition LogicProposition Logic2022-12-2440 等价公式等价公式(前前1010个个)与集合论的公式比较与集合论的公式比较：对合律对合律 AAA AA A表示表示A A的绝对补集的绝对补集 幂等律幂等律 A AA AA AA AA AA A 结合律结合律 A A(B BC)C)(A AB)B

32、)C C；A A(B BC)C)(A AB)B)C C 交换律交换律 A AB BB BA AA AB BB BA A 分配律分配律 A A(B BC)C)(A AB)B)(A AC)C)A A(B BC)C)(A AB)B)(A AC)C)吸收律吸收律 A A(A AB)B)A AA A(A AB)B)A A FormulaProposition LogicProposition Logic2022-12-2441德摩根定律德摩根定律 (A AB)B)A AB B (A AB)B)A AB B 同一律同一律 A AA;AA;AE EA EA E表示全集表示全集 零律零律 A AE EE AE

33、 A 否定律否定律 A AA AE E A AA A下面通过例题应用等价公式下面通过例题应用等价公式FormulaProposition LogicProposition Logic2022-12-2442Example证明证明证明证明P P （Q Q R R）P P（Q Q R R）P P（Q Q R R）P P（Q Q R R）P P（Q Q R R）证明德摩根定律证明德摩根定律 P Q (P Q)P Q (P Q)P Q F F T T T T F T T T F F T F T T F F T T F F F F证明证明Proposition LogicProposition Logi

34、c2022-12-2443 (P(P (R (R Q)Q)(P(P Q Q R)R)P P (R(R Q)Q)(Q Q R)R)P P (R (R Q)Q)(Q Q R)R)P P T T P PExample证明证明(P (R Q)(P Q R)P结论结论 证明等价公式成立的常用方法：证明等价公式成立的常用方法：方法方法1 1：真值表。真值表。方法方法2 2：等价公式推导。等价公式推导。(用置换定律用置换定律)Proposition LogicProposition Logic2022-12-2444 置换定律置换定律:A是一个命题公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中

35、的X得到公式B，则AB。满足置换定律 的变换称为等价变换。Example例题例题1.1.求证吸收律求证吸收律 P(PQ)P(PQ)P P证明证明 P(PQ)P(PQ)(PF)(PQ)(PF)(PQ)(同一律同一律)P(FQ)P(FQ)(分配律分配律)PF PF (零律零律)P P (同一律同一律)Proposition LogicProposition Logic2022-12-2445Example.求证求证(PQ)(PQ)P 证明证明 (PQ)(PQ)(PQ)(PQ)(公式公式E11)(P Q)(PQ)(摩根定律摩根定律)(P Q)(PQ)(对合律对合律)P(QQ)(分配律分配律)PT (

36、互补律互补律)P (同一律同一律)公式公式E11：PQPQ Proposition LogicProposition Logic2022-12-2446化简化简(PQ)(P(PQ)解解 原公式原公式 (PQ)(P P)Q)(E11,结合结合)(PQ)(PQ)(对合律，幂等律对合律，幂等律)(PQ)(Q P)(交换律交换律)(PQ)Q)P (结合律结合律)Q P (吸收律吸收律)公式公式E11：PQPQ ExampleProposition LogicProposition Logic2022-12-24471-4 1-4 重言式与重言蕴涵式重言式与重言蕴涵式Formula观察下面真值表：PQ

37、(P Q)(P Q)P PFF F TFT F TTF F TTT F Tv可见不论可见不论P P、QQ取值如何，取值如何，P PPP 的真值总为的真值总为真，真，(P P Q)(Q)(P P Q)Q)的真值总为假。故的真值总为假。故称称 P PPP为为重言式重言式(永真式永真式)；称称 (P P Q)(Q)(P P Q)Q)为为矛盾式矛盾式(永假式永假式)。Proposition LogicProposition Logic2022-12-2448Definition永真永真(重言重言)式（式（TautologyTautology）公式中的命题变量元论公式中的命题变量元论怎样指派，公式对应的

38、真值恒为怎样指派，公式对应的真值恒为T T。永假（矛盾）式（永假（矛盾）式（Contradiction)Contradiction)公式中的命题变公式中的命题变量无论怎样代入，公式对应的真值恒为量无论怎样代入，公式对应的真值恒为F F。可满足公式（可满足公式（SatisfactionSatisfaction）公式中的命题变量无公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为论怎样代入，公式对应的真值总有一种情况为T T。一般命题公式（一般命题公式（ContingencyContingency）既不是永真公式也不既不是永真公式也不是永假公式。是永假公式。Proposition Logi

39、cProposition Logic2022-12-2449Formula 重言式的证明方法重言式的证明方法 方法方法1 1：列真值表。列真值表。方法方法2 2：公式的等价变换，化简成公式的等价变换，化简成“T”T”。方法方法3 3：用公式的主析取范式用公式的主析取范式(永真式的主析取范永真式的主析取范式包含所有的小项式包含所有的小项)。其中方法其中方法2 2 和方法和方法3 3 我们在以后讨论。我们在以后讨论。永真式的性质永真式的性质 如果如果A A是永真式，则是永真式，则 A A是永假式。是永假式。如果如果A A，B B是永真式，则是永真式，则(A(AB)B)、(A(AB)B)、(A(AB

40、)B)和和(A(AB)B)也都是永真式。也都是永真式。如果如果A A是永真式，则是永真式，则A A的置换的置换例例式也是永真式。式也是永真式。如果用公式X替换命题公式A中的某个变元,替换后得到的新公式B称为A的置换例式。Proposition LogicProposition Logic2022-12-2450v公式公式A A：P P(P P(P(PQ)Q)R)R)用用(D(DE)E)替换替换A A中中P P得到得到A A的置换例式的置换例式 B B：(D(DE)E)(D(DE)E)(D(DE)E)Q)Q)R)R)v如果如果A A是永真式，例如是永真式，例如A A为为 P PPP，用，用 (D

41、(DE)E)替换替换A A中中P P，得到，得到A A的置换例式的置换例式B B：(D(DE)E)(D(DE)E)，显然，显然B B也是永真式。也是永真式。v结论结论：如果可以断定给定公式是某个如果可以断定给定公式是某个永真永真式的置换例式的话，则这个公式也是永真式的置换例式的话，则这个公式也是永真式。式。（这为判定永真式提供了第（这为判定永真式提供了第4 4种思路）种思路）FormulaProposition LogicProposition Logic2022-12-2451 A AB B与与A AB B的关系的关系定理：定理：设A、B为两个命题公式，AB当且仅当AB为重言式证明证明若若A

42、 AB B，则无论进行怎样的指派，则无论进行怎样的指派，A A、B B的真值都相同，即的真值都相同，即A AB B为重言式。为重言式。若若A AB B为重言式，则无论进行怎样的为重言式，则无论进行怎样的指派，指派，A AB B的真值都为的真值都为T T，也就是说，也就是说A A和和B B的真值相同，即的真值相同，即A AB B。FormulaProposition LogicProposition Logic2022-12-2452 重言(永真)蕴涵式Formula1.定义定义：如果公式如果公式A AB B是重言式，则称是重言式，则称A A重重言言(永真永真)蕴涵蕴涵 B B，记作，记作A A

43、B B，读作，读作A A推出推出B B。如如(P P(P PQ)Q)Q Q 可记作可记作P P(P PQ)Q)QQ注意：注意：A AB B可以理解成由可以理解成由A A可推出可推出B B，即，即由由A A为真，为真，可以推出可以推出B B也为真也为真。2.重言(永真)蕴涵式证明方法方法方法列真值表。（略）列真值表。（略）方法方法假设前件为真，推出后件也为真。假设前件为真，推出后件也为真。方法方法假设后件为假，推出前件也为假。假设后件为假，推出前件也为假。Proposition LogicProposition Logic2022-12-2453例：例：求证求证 (AB)C)D(CD)A B证明

44、证明:设前件设前件(A(AB)B)C)C)D D(C CD)D)为为 真。则真。则(A(AB)B)C)C)、D D、(C CD)D)均真，均真，由由此此 可得可得 (A(AB)B)为为T T，即，即 A A B B为为T T。(A(AB)B)C)C)D D(C CD)D)A A B B D D为为T T，则，则D D为为F F C CD D为为T TC C为为F F(A(AB)B)C C为为T TABAB为为F FFormulaProposition LogicProposition Logic2022-12-2454例：例：求证求证 (AB)C)D(CD)A B证明证明:假设后件假设后件 A

45、 A B B为为F,F,则则A A与与B B均为均为T T。1.1.如如C C为为F F，则，则(A(AB)B)C C为为F F，所以前件，所以前件 (A(AB)B)C)C)D D(C CD)D)为为F F2.2.如如C C为为T T，则，则若若D D为为T T，则，则 D D为为F F，所以，所以 前件前件(A(AB)B)C)C)D D(C CD)D)为假为假 若若D D为为F F，则，则 C CD D为为F F，所以，所以前件前件(A(AB)B)C)C)D D(C CD)D)为假。为假。(A(AB)B)C)C)D D(C CD)D)A A B BFormulaProposition Log

46、icProposition Logic2022-12-24553.重要的重言蕴含式重要的重言蕴含式(如教材第如教材第43页所示页所示)I1.PQP,I2.PQQ I3.PPQ I4.QPQ I5.PPQ I6.QPQ I7.(PQ)P I8.(PQ)Q I9.P,Q PQ I10.P(PQ)Q I11.P(PQ)Q I12.Q(PQ)P I13.(PQ)(QR)PR I14.(PQ)(PR)(QR)R I15.AB(AC)(BC)I16.AB(AC)(BC)FormulaProposition LogicProposition Logic2022-12-2456 等价式与重言蕴含式的关系等价式

47、与重言蕴含式的关系Formula定理：定理：设P、Q为两个命题公式，PQ当且仅当PQ且QP证明证明必要性：必要性：若若P PQQ，则对于任何指派，则对于任何指派，P P、QQ都同真值，故都同真值，故P PQQ为为T T，QQP P为为T T，即，即P PQQ，QQP P充分性：充分性：若若P PQQ，QQP P，则说明，则说明P PQQ永真永真 ，QQP P永真。所以，永真。所以，（P PQQ ）（QQP P ）永真，即）永真，即 P P QQ为为T T，P P QQ为重言式，即为重言式，即P PQQProposition LogicProposition Logic2022-12-2457

48、蕴含的性质蕴含的性质A AB B且且A A为重言式，则为重言式，则B B必为重言式必为重言式若若A AB B且且B BC C，则，则A AC C(传递性传递性)若若A AB B且且A AC C，则，则A A(B B C C)若若A AB B且且C C B B，则，则(A AC C)B B证明见书证明见书P22P22FormulaProposition LogicProposition Logic2022-12-2458conjunction 15 其它连接词一、全功能真值表一、全功能真值表PQ C1 C2 C3 C4 C5 C6 C7 C8TTTFTTFFTFTFTFTFFTFTFTTFFTT

49、FFTFFTFFFTTFTPQ C9C10 C11 C12 C13 C14 C15 C16TTTFTFTFTFTFTFFTFTTFFTTFTFFTFTFFFTTFTFTFPQccQPProposition LogicProposition Logic2022-12-2459二、定义连接词二、定义连接词对第对第 8、10、12、14、16列的真值表进行定义如列的真值表进行定义如下：下：“与非与非”:(PQ)PQ “或非或非”:(P Q)PQ “异或异或”:(PQ)(P Q)P Q 逆条件命题逆条件命题 :(PQ)P Q conjunctioncc思考：对于任意公式A，是否可找到只包含其中一部分连

50、接词的公式与A等价？Proposition LogicProposition Logic2022-12-2460三、极小全功能联结词集合三、极小全功能联结词集合conjunction定义：定义：设设S S是一个联结词集合，如果是一个联结词集合，如果 任意一个命题公式任意一个命题公式A A都至少存在一个只包含都至少存在一个只包含S S中中联结词的公式与联结词的公式与A A等价，称等价，称S S为全功能集。显然，为全功能集。显然，,就是一个全功能集。就是一个全功能集。从从S S中任意去掉一个联结词后，得到一个联结词中任意去掉一个联结词后，得到一个联结词集合集合S S1 1,至少有一个公式至少有一个