离散数学复习资料

1、离散数学习题与解答第一篇数理逻辑第一章命题逻辑1- 1(1)指出下列语句哪些是命题，哪些不是命题，如果是命题指出他的真值a)离散数学是计算机科学系的一门必修棵b) n >小吗c)明天我去看电影d) 请勿随地吐痰e)不存在最大质数f) 如果我掌握了英语，法语，那么学习其他欧洲的语言就容易多了g) 9+5<12h) x<3i) 月球上有水j) 我正在说假话解a)不是命题b)是命题，真值视具体情况而定c)不是命题d)是命题，真值为te)是命题，真值为tf)是命题，真值为fg)不是命题h)是命题，真值视具体情况而定i) 不是命题1-2(1)用P表示命题“天下雪”，(又表示命题“我将去

2、镇上 ：R表示命题“我有时间”.以符号形 式写出下列命题：(a)如果天不下雪和我有时间，那么我将去镇上.(b)我将去镇上，仅当我有时间.(c)天不下雪(d)天下雪，那么我不去镇上解a)(n PA R)一 Qb)QfRc)n Pd)P-n Q1-2(2)将下面这段陈述中所出现的原子命题符号化，并指出他们的真值，然后将这段陈述中的每一命题符号化 小是有理数是不对的.2是偶素数.2或4是素数.如果2是素数则3也是素 数.2是素数当且仅当3也是素数.解:陈述中出现5个原子命题，将他们符号化为：P:也是有理数其真彳1为FQ：2是素数其真彳1为TR:2是偶数其真彳1为TS:3是素数其真彳1为TU:4是素数

3、其真彳1为F陈述中各命题符号化为 :n P;QA R;QV U;QfS;Qv = > S1- 2(3)将下列命题符号化a) 如果3+3=6,则雪是白色的.b) 如果3+3 w 6,则雪是白色的c) 如果3+3=6,则雪不是白色的.d) 如果3+3 w 6,则雪不是白色的e) 王强身体很好，成绩也很好.f) 四边形ABCD是平行四边形，仅当其对边平行解:设P:3+3=6Q:雪是白色的R:王强成绩很好S:王强身体很好U:四边形ABCD是平行四边形V:四边形ABCD的对边是平行的于是 :a)可表不为:P-> Qb)可表本为：P Qc)可表示为：P>n Qd)可表示为：Pn Qe)

4、可表不'为：SA Rf) 可表不'为：Uv = > V1-3(1)判别下列公式中哪些是合式公式,那些不是合式公式a) (QfRA S)b) (Pv = >(R- S)c) (P-Q)-(Q-P)d) (RS T)e) (P (Q R) (P Q) (P R)解:a)不是合式公式(若规定运算符优先级后也可以作为合式公式)b)是合式公式c)不是合式公式(括号不配对)d)不是合式公式e)是合式公式1-3(2)对下列各式用指定的公式进行代换:a) (A-B)f B)f A),用(A-C)代换 A,用(BA C) - A 代换 B。b) (A-B)V(B-A),用 B 代换

5、A,A 代换 B.解:a)(A- CH (BA C)f A) - (BA C尸 A)- (A- C) b)(BfA)V (A- B)1- 3(3)用符号形式写出下列命题a) 假如上午不下雨,我去看电影;否则就在家里读书或看报.b) 我今天进城,除非下雨.c) 仅当你走 ,我将留下 .解a)设P:上午天下雨.Q:我去看电影R:我在家读书S我在家看报原命题可译为 七PQ)A(P-(RV S)b)设:P:我今天进城Q:天下雨原命题可译为Q-Pc)设:P:你走Q:我留下原命题可译为：Q一P1 3 (4)称P-n Q为条件命题P- Q的反换式Qf P为条件命题 AQ的逆换式n Q-n P为条件命题-Q的

6、逆反式试写出如下条件命题的反换式，逆换式，逆反式。(a)如果他有勇气，则他将得胜。(b)如果天下雨，我不去。解(a)设P：他有勇气，Q：他将得胜原条件命题可译为：P-Q反换式：P-n Q,表示：如果他没有勇气，则他将不能获胜。逆换式：Q-P,表示：如果他将得胜，则他有勇气。逆反式：IQ-n P,表示：如果他不获胜，则他没有勇气。(b)设P:天下雨，Q:我去原条件命题可译为：P-n Q反换式：IP-Q,表示：如果如果天不下雨，则我去。逆换式：Q-P,表示：如果我不去，则天下雨。逆反式：IQ一n P,表示：如果我去，则天不下雨。1- 4 (1 )试求下列各命题公式的真值表并解释其结果(a) (A

7、Q) A ( CK P);(b) (PA Q) - P;(c) Q-(PVQ);(d) AQ)< = > (n PV Q);(e) (n PV Q)A (n (n PAn Q);(f) n ( P-Q) A QAR o解(a)从真值表 1-1 中可看出：(P-Q) A ( Q-P) < = > ( P< = > Q)(b)从真值表1-2中可看出：(PA Q) 一 P是永真式(c)从真值表1-3中可看出：Q一( PVQ)是永真式(d)从真值表1-4中可看出：(P-Q)< = > (n PVQ)是永真式(e)从真值表1-5中可看出：(PV Q) A

8、(n (n PAn Q)< =>n PV Q< => P 一 Q< =>n (PA Q)(f)从真值表1-6中可看出：(P-Q) AQAR是永真式P QP 一 QQfP(-Q) A ( Q-P)T TTTTT FFTFF TTFFF FTTT表1-1P QPA Q(PA Q) 一 PT TTTT FFTF TFTF FFT表1-2PQPV QQf ( PVQ)TTTTTFTTFTTTFFFT表1-3P Qn PPfQn PV Q(P-Q)V = > (n PV Q)lT TFTTTT FFFFTF TTTTTF FTTTT表1-4P Qn Pn Qn

9、PV Qn (n PAq Q)(n PV Q) A (n (n PAn Q)T TFFTTTT FFTFFFF TTFTTTF FTTTTT表1-5PQR-Qn (P-Q)n AQ) AQn ( P- Q) A QA RTTTFFFFTTFFFFFTFTTTFFTFFTTFFFTTTFFFFTFTFFFFFTTFFFFFFTFFF表1-61- 4 (2)用真值表判断下列各组公式是否等价：(a) (Q 一 R)W (PA Q) 一 R(b) A Q) 一 R与(PA Q) 一 R解由表 1-7 可知 P一 (Q-R) < = > ( PA Q) 一 R 而(P Q) 一 Rvw &g

10、t; ( PA Q) 一 RP Q RP- (Q-R)(PA Q) 一 R(P-Q) 一 RT T TTTTT T FFFFTFTTTTT F FTTTF T TTTTF T FTTFF F TTTTF F FTTF表1-71-4 (3)试以真值表证明下列命题：(a)合取运算的结合律(b)德摩根定律解(a)如表 1-8, (PAQ) A R< = >(b)如表 1-9, ( PAQ)< = >n PVn Qn (PV Q)< = >n PA n QPQRPA Q(PA Q) A RQA RPA (QA R)TTTTTTTTTFTFFFTFTFFFFTFFFF

11、FFFTTFFTFFTFFFFFFFTFFFFFFFFFFF表1-8PQn Pn Qn PV n Qn (PAQ)n P An Qn (PVQ)TTFFFFFFTFFTTTFFFTTFTTFFFFTTTTTT表1-92- 4 (4)证明下列等价式：(a) A一( BA) v =Af ( A-n B);(b) (AV B) 一Cv = > ( A一C) A (B-C);(c) n ( Av = > B) v = >( AA n B)V (n A AB);(d) (AA B) A C) 一 D)A ( C一 (AV ( BV D)< = > ( CA( Av = &g

12、t; B)一D证(a) A( B-A)v = >n AV (n B V A)v = > (n B V A)V n Av = > (AVi B) Vn A< => AV (n BVn A)< => AV (n AV B)< => AV ( A-n B)< =>n A一( A一n B)(b) (A- C) A ( B-C)V = > (n AVC)A (n BV C) v = > Ai A A n B) V C< => n ( AV B) VC< => (AVB) C(c) ( A< = &

13、gt; B) < = >n ( (A-B) A ( B- A)< =>n ( (n AV B)A (n BVA) < =>n (n AV B)Vn (n BVA) < => (AAn B) V ( BAn A)(d) ( ( (AAB) AC) -D) A ( C- (AV (BVD)< = >(AABA C) V D)A (n CV (AV BVD) < => (nAVnBVnCV D) (n CVAVBVD)< => (nCV D)V ( AVn B) A (AVB)< => (nCVD)V (

14、AAn B) V ( BAn A)< => (nCV D)Vn( (n AV B)A (n BVA)< => (nCVn(nAVB)A (n BVA) VD< =>n ( C( (n AVB)A (n BVA) V D< =>n ( CA (A-B) A ( B-A) V D< =>n ( CA (Av = > B) V D< => (CA (Av = >B) -D1- 4 (5)判断下列命题公式的类型(永真；永假；非永真，也非永假) (a) ( ( FQ) A P) -Q;(b) ( P-(P VQ) A R

15、;(c) P A (P VQ) An P) -Q).解(a) ( ( PfQ) A P) -Qv = >(i PV Q) A P) - Q< = >n ( (n PV Q) A P) V Q< => (n (n PV Q) Vn P) V Q< => (PAn Q) Vn P) V Q< => (PVn P)A (n QVn P) V Q< => (n QVn P) V Q< => TVn P< => T( a)为永真式(b) n ( P (P VQ) A R< = >n (n PV P VQ

16、) AR< => (PAn P An Q) A R< => FA R< => F< .(b)为永假式(c) P A (P VQ) An P) -Q)v = > P A(i (P V Q) An P) VQ)< => P A(n (PAn P )V(Q A n P) V Q)< => P A(n (FV(Q Ai P) V Q)< => p A(n Q V P VQ)< => PA T< => P，(c)为非永真式，也非永假式1-4.(6)化简如下语句：“情况并非如此：若他不来，则我不去”

17、。解:首先符号化上述语句。设P:他来。Q:我去则原句：(P-n Q)然后化简上述命题公式n (n P-n Q)< =>n Qn q Q-n n P)< =>n ( Q-P)< =>n (n QV P)< => Q A P即：我去了，但他未来。14 (7) (a)如果 AVCv = > BVC,是否有 A< = > B如果A A Cv = > BA C,是否有A< = > B如果A< = >n B,是否有 A< = > B解(a)不能说必有 A< = > B,因为当AVC<

18、; = > BV C时，有可能某种指派使 C为T, 但A、B的值并不相同(b)不能说必有 A< = > B,因为当AA C< = > BA C时，有可能某种指派使C为F,彳1 A、B的值并不相同(c)结论正确。因为(AB)< = > (n B-n A),所以1B-n A为永真式 时，Af B也是永真式。即 B< >n A时，必有 A= > B。同理A< >n B时，B= > A。所 以B< = >n A 时，必有 Av = > B 1-5 (1)试证下列各式为永真式：(a) (P A ( PQ) -

19、 Q;(b) P ( PQ);(c) ( ( P-Q) A ( Qf R) - ( PR);(d) ( (PAQ) V (QAR) V (RA P) < = > ( (PV Q) A (QVR) A ( RV P) 解(a) (PA (P-Q) ) - Q< =>(P( (n PV Q) - Qv = >(PAi P) V (PA Q)-Qv = >(PAQ)-Q< => n ( PAQ) V Q< =>n PVn QVQ< =>n PV T< => T(b) P- ( PQ)< => PV (n

20、PVQ)< => PVn PV Q< => TVQ< => T(c) 当本条件命题的后件为 F时，必有P: T; R F考察条件的前件(PfQ) A (Qf R)。当Q: F时，因P-Q: F;当Q: T时，因QfR: F。所以前件必为 F。故(P Q) A ( Q-R) = > P- R因此(P-Q) A ( Q-R) - ( PR)是永真式(d) (PAQ) V (QA R) V (RA P)< => (qa ( PV R) V (RA P)< => (Q V ( RA P) A ( (PV R) V (RA P)<

21、=> (QV R) A (Q V P) A ( PVR)< => (PVQ) A (QV R) A ( RV P)，(PAQ) V (QAR)V (RA P)V = > (PV Q)A ( QVR)A (RV P)1- 5 (2)不构造真值表证明下列蕴涵式：(a) (P- Q) => P (PA Q);(b) A Q)-Q=>PV Q;(c) (Qf ( P Ai P) - ( » ( » ( P An P) => Rf Q证(a)解法1设P Q为T,则(1) P 为 T, Q为 T 因而 P (PA Q)为 T或(2) P为F 则

22、必有P ( PA Q)为T所以(a)成立。解法2设 A (PAQ)为 F则P为T, Q为F所以 P-Q为F所以(a)成立。解法3(P-Q) - ( P- (PAQ)< = >n (n PV Q)V (n PV ( PA Q)< = >n (n PV Q) V ( (n PV P)A (n PVQ)< = >n (n PV Q)V (n PV Q)< => T所以(a)成立。(b)设PVQ为F,则P为F, Q为F则PfQ为T,所以(P- Q) - Q为F所以(b)成立。(c) (Q- ( P An P) - ( » ( R- ( P An

23、 P)< = >n (n QVF)V (n RV (n RV F)< =>n (n QV V (n RVn R)< =>n (n Q) Vq R< => n Qn R< => FH'Q所以(Qf ( P AnP)-(R-(R-( PAnP)< = > RQ当然有("(P AnP)-(»(»( PAnP)=> RQ1- 5 (3)试证明P< = > Q, Q逻辑蕴含Po证本题要求证明：(P< = > Q) A Q = > P设(PV = > Q)

24、AQ为T,则Q为T且 (PV = >Q)为T 所以P必为T,因而蕴含式成立。1 - 5 (4)逻辑推证下列各式：(a) P = > (n P-C);(b) AABAC = >C;(c) C = >AVBVB;(d) n (AAB) = >n A Vn B;(e) -BVC) ,DVE, (DVE) A = >BVC;(f) (AAB) -C, n D, n C V D = >n A" B。证(a)若P为T,则IP为F,故IP-C必为T。所以(a)成立。(b)若C为F,则AAB AC必为F。故(b)成立。(c)因为AVBVi B< = &

25、gt;To 故C = >AVBVi B。(d)设AVi B为F,则A为T且B为T所以AAB为T, (A AB)为F。故( d)成立。(e)设1Af (BVC) ,DVE, (DVE)fi A均为T则因DVE为T及(DVE)A为T,而可得i A为T又因Af (BVC)为T故得BVC为T,故(e)成立。(f)设(AAB) -C, n D, n CVD均为T,则D为F,由CVD为T,可知C为F。再由(AAB) -C为T可得AAB为F,因而必有1(AAB)为T,也即AVi B为T,故(f)成立。1 - 6 ( 1 )把下列各式用只含V和I的等价式表达，并要尽可能简单：(a) (PAQ) An P

26、;(b) (P- (Q Vn R) ) A n PAQ;(c) n PAn QA (n R-P)。解(a) (PAQ) An P< => (PA n P) A Q< => F A Q< =>n (T Vq Q)(b) (P- (Q Vn R) ) A n PAQ< => (n PVQVn R) A (nPAQ)< => (n P An PAQ) V (QAn PAQ) V (n RAn PAQ)< => (n PAQ) V (n PAQ) V (n PAQAq R)< => (n PAQ) V (n PAQAq

27、 R)< => (n PAQ) A (T An R)< => (n PAQ) AT< =>n PA Q< =>n ( PVq Q)(c) n PAn QA (n R-P)< =>n PAn QA (RVP)< => (n PAn QAR) V (n PAn QAP)< => (n PA n Q A R) V F< =>n PA Q A R< = >n ( PVQ Vn R)1 - 6 (2)对下列各式仅用“或非”(J )表示：(a) n P;(b) PVQ;(c) PAQ;解:(a) n

28、 P< = >n ( P V P) < = > P JP(b) PVQ< = >n (n ( PVQ) ) < = >n ( PjQ)< => (PJ Q) J ( PJ Q)(c) PA Q< = >q (n PVq Q) < = >n PJi Q< => (P J P) J (Q J Q)1 - 6 (3)对下列各式仅用“与非”(T)表示：(a) n P;(b) PVQ;(c) PAQ;解:(a) n P< = >n ( P AP) < = > Pf P(b) PV Q&

29、lt; = >n (n PAq Q) < = >n P T n Q< => (PT P) T (Q T Q)(c) PAQ< = >n (n ( PAQ) ) < = >n ( PT Q)< => (PT Q) T (PT Q)1 6 ( 4 )把b FQ)分别表示成只含“ T ”和只含“ J ”的等价公式。 解4 (n P-Q) < = >n PV (PVQ) < = >T V Q< = >T< = >n PVP< = > (n P) T (PTP)< =>

30、; PT (PTP)。4 (n P-Q) < = >n PVP< => b PJ P) J (n PJ P)< => (PJ P) J P) J ( (PJ P) J P)。的等价1 6 ( 5 )把 PT Q表示成只含“ J ”的等价公式，把 PJ Q表示成只含“ T公式。解PT Q< = >nPAQ) < = >n PVn Q< = > ( P P) V (Q Q)< => C (P J P) J (Q J Q) J (P J P) Q< = >n ( PVQ) < = >n PAq

31、 Q< = > (< => C (PT P) T (QTQ) T ： (PT P)J (QjQ) °PT P) A (Q T Q)T (Q T Q) o1 6 ( 6 )证明 V , A 和不是最小联结词组。证(反证法)若V , A , f均是最小联结词组，则 否定(n )命题连接词可分别仅用V, A,f表示，即 n P< = > ( PV ,) n P< = > ( PA ,)n P< = > P> ( P» ( P-) 1)但当时所有命题变元均指派T时，各等价式的左端为F而右端却为T,故产生矛盾。故V,A

32、和f均不是最小联结词组。c16 ( 7)证明广，<,f是最小联结词组。证:因为，V是最小联结词组，且PVQv = >i P->Q。故, ->是功能完备的联结词组。又仆和f都不是功能完备的，所以，-是最小联结 词组。ccc又因为P->QV = >i(P->Q)故i , ->也是功能完备的联结词组。 但-4c不是功能完备的。因为若它是功能完备的，则否定()命题联结词必有仅用f表示，即： cc cn P< = > ( P > ( P > ( P >11)c但当对命题变元指派F时，上等价式的左端为T,但右端为F,矛盾。所以，

33、-也是 最小联结词组。1 7 ( 1 )求公式P A (P-Q)的析取范式和合取范式。解析取范式：PA (P-Q) < = >P A (n PVQ)< => (P An P) V (PAQ)合取范式：PA (P-Q) < = >P A (n PVQ)或PA (P-Q) < = >P A (n PVQ)< => (P V (QAn Q) ) A ( P VQ)< => (P VQ) A (PViQ) A (n P VQ)1 7 (2)把下列各式化为析取范式(每项两个变元)：(a) ( PAQ) -R；(b) P- ( (QA

34、R) - S);(c) (P-Q) -R;(d) n (PAQ) A (P VQ);解:(a) (n PAQ) fRv = >i (n PAQ) VR<=>PVQVR< = >PA (Q Vn Q) Vn QA (R" R) VRA (P Vn P)< => (PAQ) V (P An Q) V (n QAR) V (n Q An R) V (RAP)(RAnP)(b) P- ( (QAR) - S)< =>n PV (n (QAR) VS) V = >n P Vn Q Vn RV S< = >n PA (QVi

35、Q) Vn QA (R"R) "RA (S"S) VSA (PVn P) < => (n PAQ) V b P An Q) Vn (QAR) V (n QAn R) V (n RAS) V(n RA S) V (S P) V (S Ai P)(c) (P-Q) fRV = " (n P VQ) VR< = >(PAQ) VRV = >(PAQ) V (RA (P"P)< => (P An Q) V (RAP) V (RAP)(d) n (PAQ) A (P VQ)< => (n P Vn Q

36、) A (P VQ)< => (n PAP) V (n PAQ) V (P An Q) V (n QAQ)1 - 7 ( 3)把下列各式化为合取范式：(a) <V (n P AQAR);(b) n (P-Q) V (PVQ);(c) n (P-Q)；(d) (P-Q) -R;(e) (1 PAQ) V (P An Q)解:(a) PV (n PAQAR) < = > (P Vq P) A (PVQ) A (PVR)< => (P VQ) A (PVR)(b)n (P-Q) V (PVQ) < = >n (n PVQ) V (PVQ)<

37、 => (P An Q) V (P VQ)< => (PVPVQ) A (iQVPVQ)< => (P VQ) A (P VQ Vn Q)(c)n (P-Q) < = >n (n P VQ)< = >P An Q< = > (PV (n QAQ) )A b Q V (n PAP)< => (PVi Q) A (P VQ) A (n Q Vn P) A (n QVP)< => (P VQ) A (P Vn Q) A (n P Vn Q)(d) (P-Q) fRv = >i (n P VQ) VR<

38、; => (P An Q) V R< = > (PVR) A (n QVR)(e) b PAQ) V (P An Q)< => (n PAQ) VP) A ( (n PAQ) Vn Q)< => (n PVP) A (QVP) A (n P Vn Q) A (Q Vn Q)< => (PVQ) A (n P Vn Q)1 - 7 (4)求下列各式的主析取范式及主合取范式，并指出其中哪些是重言式：(a) (iPVQ)f(Pv = >iQ);(b)PV (1 P- (QV (n Q-R) );(c) (P- (QAR) ) A (1 P-

39、 (n QAn R);(d) P- (PA (Q-P);(e) (Q-P) A (n PAQ)。解:(a) (n P Vq Q) > (Pv = >i Q)< =>n (iPViQ) V (PV = >iQ)< => (PAQ) V (P An Q) V b PAQ)(主析取范式)< = >m 3,2, i < = >n o< = >pvq(主合取范式)(b) P V (1 P- (QV (n Q-R) )< = >P V (PV (QV (QVR) )< = >P VQVR< = &g

40、t;n o(主合取范式)< =1 , 2 , 3 , 4 , 5 , 6 , 7< => (n P An QAR) V (n P AQAn R) V (n PAQAR) V (PA)Q An R) V (P An QAR) V (P AQAq R) V (PAQAR)(主析取范式)(c) (P- (QAR) ) A (1 P- (n QAn R)< => (n PV (QAR) ) A (PV (n QAn R)< => (n PV (QAR) ) AP) V ( ( PV (QAR) ) A (n Q An R)< => (n PAP)

41、V (QARAP) V (n PA Q An R) V (QARA1QAn R)< => (PAQAR) V (n PAQAR) < = >m 7, o (主析取范式)< =>1,2, 3, 4, 5, 6< = >(PVQVR) A (PVQVR) A (PVQVR) A (n P V QVR) A ( PVQVi R) A (n P Vn QVR)(主合取范式)(d) P- (PA (QfP)< = >n PV (PA (iQVP) )< => (iPVP) A (iPViQVP) < = >T (永真式，

42、主合取范式为空) < =>22 0 , 1 , 2 , 3< => (n P An Q) V (n PAQ) V (P An Q) V (PAQ)(主析取范式)(e) (Q-P) A (n PAQ)< => (n QVP) A (n PAQ) < = > (n QAn PAQ) V (P An PAQ)< = >FVF< = >F(永假式，主析取范式为空)< =>n O , 1 o 2 , 3< => (PVQ) A (P Vn Q) A (n PVQ) A (n P Vn Q)1 - 7 (5)用

43、主析取范式判断下列各题中的两个命题公式是否等价。(a) (A-B) A (A-C)与Af (BAC) ;(b) (A-B) f (AAB)与(A-B) A (B - A) ;(c) P- (Qf R)与Qf (P-R) 。解:(a) (A-B) A (A-C) < = > (n AVB) A (n AVC)< =>Zj 0,1, 2, 3, 7Af (BAC) V=>Z20,1, 2, 3, 7这两个公式的主析取范式相同，所以它们等价。(b) (A-B) f (AAB) < = >n (n AVB) V (AAB)< => (A An B)

44、 V (AAB)(n AfB) A (B -A)< => (AV B) A (n B V A) < => (A An B) (B An B) V (AAA) V (BAA)< => (A An B) V (AAB) VA< => (A An B) V (AAB) V (AA (B Vq B) ) < => (A An B) V (AAB)可见这两个公式的主析取范式相同，所以它们等价。(c) P- (Qf R)< =>12 1 , 3 , 4 , 5 , 7Qf (P-R)< =>Z2 0 , 1 , 2 , 3

45、 , 4 , 5 , 7可见这两个公式的主析取范式不相同，所以它们不等价。1 7 (6)已知一命题公式A (P, Q, R)当且仅当其中的二个命题变元为真时，A为 真。试求A。解:根据题意写出A的真值表P Q RAT T T T T F TFT T F F F T T F T F F F T F F FF T T F T F F F表 1-10由真值表易得 AV = > (P AQAn R) V (P An QAR) V (n P AQAR)1 7 (7)由表1-11求出公式Ei,匕，&，E4。在表上有问号()的地方以F或T代入都可以, 只要求公式形式较简单。P Q RE1EE3

46、E4T T T T T F TFT T F F F T T F T F F F T F F FT T F F F F F FT F T T T F T TF F T T T T T TF F F F F F F T表 1-11解:根据真值表写出 E1的主析取范式：E1V = > (PAi QAR) V (n P An Q An R)根据真值表写出 E2的主合取范式：E2< = > (n P Vn QVR) A (P Vn QVR)对E3在问号()处代入 T,根据真值表写出 E3的主合取范式：曰< =>(1 PV Q Vq R) A (n P Vq QVR)对巳，在

47、问号()处代入 F,根据真值表写出 E4的主析取范式：曰< =>1 P An QA R1- 8 (1)用真值表方法分别判断：(a) (b)中的结论是否一组相关前提的有效结论 (a)前提：若a能被4整除，则a能被2整除。a能被4整除。结论：a能被2整除。(b)前提：若a能被4整除，则a能被2整除。a能被2整除。结论：a能被4整除。解:(a)设P: a能被4整除Q： a能被2整除于是前提为：(P - Q) AP结论：QP为假的情况。所以“ a能被4整原判断即为：（P - Q） AP = >Q是否成立 构造（P-Q） A P的真值表，见表1 12P QP 一 Q(P-Q) APQT

48、 TTTTT FFFFF TTFTF FTFF表 1-12从表中可见当（P-Q） A P为真时，Q也为真。所以结论是一组相关前提的有效结论。（b）类似于（a）,原判断即为：（P-Q） AQ = >P是否成立构造（P-Q） A Q的真值表，见表1 13P QP 一 Q(P-Q) AQPT TTTTT FFFTF TTTFF FTFF表 1-13从表中可见当（P-Q） A Q为真时，出现 除”不是给定的一组检体的有效结论。8 (2)用推理规则证明以下各式：(a)n ( P An Q) ,nQVR, n R=>n P ；(b)BA C, ( Bv = > C)f(HVG)=>

49、 GV H;(c)P-Q, (n Q VR)An R, n(n P AS)= >n S;(d)P VQ, Q - R, P-> S, S=>RA (P VQ)。证(a) (1 )R(2) n Q VR(3) R Vn Q(4) n Q(5)n (P An(6) n P VQ (7)QVn P (8) I P(b) (1) BA C(2) B(3) C(4) n CV B(5) n BVCCf B(7) B-C(8) B< = > C(9) (B< = >PPT (2), E3T(1)(2), I10Q)pT ,E8T(6), E3T(4)，IioPT(

50、1), IiT (D, 12T(2), 14T(3), I4T(4), E16 T (5), E16T (6)(7), E0C) 一( HVG)P1-（10） HVG（11） GV HT（ 8 ） （ 9） ，T（10） ， E311（c） （1）（1 QVR） An RP（2） n RT（1） ， I2（3） n QVRT（ 1） ， I1（4） R Vn QT（3） ， E3（5） n QT（ 2 ） （ 4） ，I10（6） P-QP（7） I PT（ 5） （ 6 ） ，I12（8）n （n PA S）P（9） PVn ST（ 8） ， E8（10） n ST（ 7） （ 9） ，I1

51、0（d） （1） P- SP（2） n SP（3） n PT（ 2） （ 1 ） ，I12（4） PVQP（5） QT（ 3） （ 4） ，I10（6） Q-RP（7） RT（ 5） （ 6） ，I11（8） RA （PVQ）T（ 7 ） （ 4） ，I91-8（3）仅用规则P和T推证以下公式：（a） n AVB, Cf n B=>Afn C;（b） Af （ B- C）, （CA D） - E, n Ff （ DAn E） = > Af （BfF）;（c） （AV B） （ CA D）, （DV E - F= > A F;（d） （A- B） A （ C- D）, （B-E

52、） A （ D-F）- （ EA F）, AC=> n A。证 ： （a） （1）（AC）P （附加前提）（2）AT（1） ， I7（3）CT（ 1） ， I8（4） -AV BP（ 5）BT（ 2） （4） ， I10（ 6）Cf n BP（7）BT（3） （6） ， I11（ 8）BAn B （矛盾）T（ 5） （ 7 ） ， I9（b） （1）Af（Bf F）P （附加前提）（ 2）AT（ 1 ） ， I7（3）BfF）T（ 1 ） ， I8（ 4）BT（ 3） ， I7（5）FT（3） ， I8（ 6）Af（ BfC）P（ 7）BfCT（ 2） （ 6） ， I11（ 8）CT（

53、 4） （ 7） ， I11（9）n Ff （DAn E）P（10） DA E（11） D（12） 12） CA D（13） （CA D） - E（14） 14） E（15） 1 E（16） EA n E （矛盾）（c） （1） n （ A-F）（2） 2） A（3） n F（4） AV B（5） （AV B） （ CA D）（6） 6 ） CA D（7） 7） D（8） DV E（9） （DV E f F（10） 10） F（11） FA n F （矛盾）（d） （1） （A- B） A （ 8D）（2） AfB（3） （B- E） A （ D-F）（4） BfE（5） AfE（6） n （

54、 EAF）（7） n EVn F（8） E-n F（9） A-n F（10） 10） C- D（11） 11） D-F（ 12 ） C- F（13） 13） A- C（14） 14） A- F（15） n F-n A（16） An A（17） n AVj A（18） 1 A1- 8（4）用CP规则证明上题中的（a） （b）证 ： （ a ） （ 1 ） A（2） n AV B（3） 3） BT（5） （ 9） ， I11T（ 10） ， I1T（ 8） （ 11 ） ， I9PT（ 12） （ 13） ， I11T（10） ， I2T（ 14） （ 15） ， I9P （附加前提）T（1） ，

55、 I7T（1） ， I8T（2）， I3PT（4） （ 5） ， I11T（ 6） ， I2T（7） ， I3PT（8） （9） ， I11T（ 10） （3） ， I9PT（1 ） ， I1PT（3） ， I1T（2） （4） ， I13PT（ 6） ， E8T（7） ， E 16T（5） （8） ， I13T（1） ， I2T（ 3） ， I2T（ 10） （ 11 ） ， I13PT（ 12） （ 13） ， I13T（ 14）， E18T（9） （ 15） ， I13T（16）， E 16T（17）， E 10c） 。P （附加前提）PT（2）, IioP（4） C n B（5） 1 C（6） A-n C3）（4）,CPIl 2CA D）b） （1） A（ 2） A-（ B-C）（ 3） B-C（ 4） B（ 5） C（ 6） （CA D） - E（ 7） C-（ D- E）（ 8） D- E（ 9） DV E（ 10） 1 （ DAn E）（ 11） n F-