2015離散數(shù)學(xué)蘊含與推理

1、等價式(equivalences),蘊涵式(implication),定義1-5.3 當(dāng)且僅當(dāng)P ?Q是一個重言式時，我們稱“P蘊含Q”，并計作P ? Q,定義1-8.1 設(shè)A和C是兩個命題公式，當(dāng)且僅當(dāng)A?C為一重言式，即A?C ，稱C是A的有效結(jié)論?；駽可由A邏輯地推出。定義1-8.2 設(shè)H1，H2，…，Hm 和C為命題公式，若H1 ?H2 ? … ? Hm ? C，則稱C為一組前提H1，H2，…，Hm 的有效結(jié)論。,1.

2、p?q?p p?q?q 2. p，p ? q?q3. ? p，p?q?q 4. ?q，p ? q? ? p 5. p ? q，q ? r?p ? r 6. p?q , p ? q，q ? r? r,證明H1 ?H2 ? … ? Hm ? C的方法,真值表法： （1）假設(shè)A為T時，說明B也為T。 （2）假設(shè)B為F時，說明A也為F。例：證明? p ?(p ? q) ?q,證明H1

3、?H2 ? … ? Hm ? C的方法,1. p?q?p p?q?q 2. p，p ? q?q3. ? p，p?q?q 4. ?q，p ? q? ? p 5. p ? q，q ? r?p ? r 6. p?q , p ? q，q ? r? r,直接證法： P 規(guī)則：前提在論證過程中隨時可以引用。 (premise) T規(guī)則：在推導(dǎo)中，如果有一個或多個公式蘊含著公式S，則公式S可以

4、引入推導(dǎo)之中。,證：(P?R)?(Q?R)?(P?Q) ?R證明：(1) P?R P (2) Q?R P (3) P?Q P (4) ?P?Q T(3) E (5

5、) ?P?R T(4),(2) I (6) (P?R)?(?P?R) T(1),(5) I (7) R T(6) E,證明：J ?(M?N), (H?G) ?J, H?G ? M?N證明：(1) J ?(M?N) P (2) (H?G) ?J

6、 P (3) (H?G) ?(M?N) T(1),(2) I (4) H?G P (5) M?N T(3),(4) I,證明H1 ?H2 ? … ? Hm ? C的方法,間接證法：,要證 H1 ? H2 ? …? Hm ? C 記A=H1 ? H2 ? …? Hm ， 即是要證 A ? C，A

7、 ?C是重言式， ?A ?C是重言式，A ? ?C是矛盾式， 即是要證H1 ? H2 ? …? Hm ? ?C是矛盾式 等于多了一個前提?C，用直接證明方法證得矛盾即可,（1）反證法,例：證：S??Q, S?R, ?R, ?P Q ? P證明: (1) ?P P(附加前提) (2) S?R

8、 P (3) ?R P (4) S T(2),(3) I (5) S??Q P (6) ?Q T(4),(5) I (7) ?P

9、 Q P (8) (?P?Q)?(Q??P) T(7) E (9) ?P?Q T(8) I (10) Q T(9) I (11) Q??Q(永假） T(6),(10) I,證明H1 ?H2 ? … ?

10、Hm ? C的方法,間接證法：,若要證H1 ? H2 ? …? Hm ? R ? C記A=H1 ? H2 ? …? Hm ，即是要證 A ? R ? C，A ? (R ? C)是重言式， ?A ? (?R ? C)是重言式，? (A ?R) ? C是重言式， (A ?R) ? C是重言式， (A ?R) ? C即要證H1 ? H2 ? …? Hm ? R ? CR作為附加前提，用直接證法得到C即可,（2）CP規(guī)則,例：證：A

11、?B?C?D, D?E?F?A?F證明:利用CP規(guī)則 (1) A P(附加前提) (2) A?B T(1) I3 (3) A?B?C?D P (4) C?D T(2),(3) I11 (5) D T

12、(4) I2 (6) D?E T(5) I3 (7) D?E?F P (8) F T(6),(7) I11 (9) A?F CP規(guī)則,1.如果小霞是理科生，她一定學(xué)微積分，如果她不是文科生，她一定是理科生，她沒學(xué)微積分,所以她是文科生。2.所有

13、的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。,Logic Puzzles,There is an island that has two kinds of inhabitants, knights, who always tell the truth, and their opposites, knaves. Who always lie. You encounter two people A and B

14、if A says “ B is a knight” and B says “The two of us are opposite types.” 一個島上居住著兩類人—騎士和流氓。騎士說的都是實話，而流氓只會說謊。你碰到兩個人A和B，如果A說“B是騎士”，B說“我們不是一類人”。請判斷A、B兩人到底是流氓還是騎士。 其它情況： A說：“我們之間至少有一個是流氓”，B什么都沒說。 A說：“我們是

15、流氓或者B是騎士”，B什么都沒說。 A說：“我們都是流氓”，B什么都沒說。,2024/3/20,Muddy children puzzle,2. A father tells his two children, a boy and a girl, to play in their backyard without getting dirty. However, while playing ,both children

16、get mud on their foreheads. When the children stop playing, the father says“At least one of you has a muddy forehead.” and then asks the children to answer “ Yes” or “ No” to the question:“Do you know whether you have

17、a muddy forehead?” The father asks this question twice. What will the children answer each time this question is asked, assuming that a child can see whether his or her sibling has a muddy forehead, but cannot see his

18、or her own forehead? Assume that both children are honest and that the children answer each question simultaneously.,2024/3/20,Muddy children puzzle,2. 父親讓兩個孩子（一個男孩，一個女孩）在后院玩耍，并讓他們不要把身上搞臟。然而，在玩的過程中，兩個孩子都在額頭上沾了泥。當(dāng)孩子們回來后

19、，父親說“你們當(dāng)中至少有一個人額頭是有泥”，然后他問每兩個孩子“你知道你額頭上有泥嗎？”，要求他們回答“yes” 或者“no”,同樣的問題問了兩遍。假設(shè)每個孩子都可以看到對方的額頭上是否有泥，但不能看見自己的額頭，孩子們每次的回答是什么樣的呢？假設(shè)兩個孩子都很誠實并且都同時回答每一次提問。,2024/3/20,蘊含式(implication),定理1-5.4：設(shè)P、Q為任意兩個命題公式，P?Q的充分必要條件是P?Q且Q?P 。證明：由

20、定理 1-5.3 ，P ?Q，則P Q為重言式，因為由表1-4.7 P Q ?(P?Q)?(Q?P)，故(P?Q)為T且 (Q ?P)為T，即P?Q且Q?P 成立。 反之，若P?Q且Q?P 成立，則(P?Q)為T且 (Q?P)為T，因此P Q為T， P Q為重言式，即P?Q。這個定理也可作為兩個公式等價的定義。,蘊含的性質(zhì),*（1）設(shè)A、B、C是合式公式，若A ? B且A是重言式，則B必是重言式。*（2