习题1.1-1.2参考答案

习题参考答案第1章数理逻辑1.1命题1．解（a）(ⅰ)┐P∧R→Q(ⅱ)Q→R(ⅲ)┐P(ⅳ)P∧┐Q(b)(ⅰ)我去镇上当且仅当我有时间且天不下雪。(ⅱ)我有时间并且去镇上。(ⅲ)如果我去镇上，那么我有时间；如果我有时间，那么我去镇上（或：我去镇上当且仅当我有时间）。(ⅳ)说我有时间或我去镇上是不对的。2．解（a）上海并非处处清洁。（b）并非每一个自然数都是偶数。3．解（a）逆命题：如果我不去，那么天下雨。逆反命题：如果我去，那么天不下雨。（b）逆命题：如果你去，我将逗留。逆反命题：如果你不去，我将不逗留。（c）逆命题：如果方程nnnzyx无正整数解，那么n是大于2的正整数。逆反命题：如果方程nnnzyx有正整数解，那么n不是大于2的正整数。（d）逆命题：如果我不能完成这个任务，那么我没有获得更多帮助。逆反命题：如果我能完成这个任务，那么我获得了更多帮助。4．给P和Q指派真值T，给R和S指派真值F，求出下列命题的真值：（a）P∨Q∧R(b)P∨Q∧R∨┐((P∨Q)∧(R∨S))(c)(┐(P∧Q)∨┐R)∨(P┐∧Q∨┐R)∧S(d)┐(P∧Q)∨┐R∨((Q↔┐P)→R∨┐S)(e)(P↔R)∧(┐Q→S)(f)P∨(Q→R∧┐P)↔Q∨┐S解：做出各个命题的真值表，求出真值。（a）TPQRQ∧RP∨Q∧RTTFFT(b)T(c)T(d)T(e)F(f)T(b)(c)(d)(e)(f)(表略)5．解：（a）PQP→QQ∧(P→Q)Q∧(P→Q)→P00101011101000111111（b）PQRQ∧R┐(P∨Q∧R)(P∨Q)∧(P∨R)┐(P∨Q∧R)(P∨Q)∧(P∨R)00001000010100010010001110101000010101001011000101111010（c）(略)；（d）(略)。6.证明下列公式的真值与他们的变元值无关：(a)P∧(P→Q)→Q(b)(P→Q)→(┐P∨Q)(c)(P→Q)∧(Q→R)→(P→R)(d)(P↔Q)↔(P∧Q∨┐P∧┐Q)证明：做出各个命题的真值表，证明公式的真值与他们的变元值无关(a)PQP→QP∧(P→Q)P∧(P→Q)→Q00101011011000111111(b)(c)(d)(表略)7．证明作真值表：PQPQP→QQ→P（P→Q）∧（Q→P）001111010100100010111111由表可知，PQ在第一，四行上取真值，这时，P→Q，Q→P也为真；另一方面，在第一，四行上P→Q和Q→P同时为真，这时PQ也为真。于是本题得证。8．对P和Q的所有值，证明P→Q与┐P∨Q有同样真值。证明(P→Q)↔(┐P∨Q)总是真的。证明：做出(P→Q)↔(┐P∨Q)的真值表PQ┐PP→Q┐P∨Q(P→Q)↔(┐P∨Q)0011110111111000011101119．解（a）∧、∨、是可交换的。（b）作出P∧Q、Q∧P；P∨Q、Q∨P；PQ、QP和P→Q、Q→P的真值表，由表得出前三对公式等价，后一对公式不等价（表略）。10．设*是具有两个运算对象的逻辑运算符，如果（x*y）*z和x*(y*z)逻辑等价，那么运算符*是可结合的。(a)确定逻辑运算符∧、∨、→、↔那些事可结合的。(b)用真值表确定你的断言。解：(a)∧、∨、↔是可结合的。(b)做出（P∧Q）∧R、P∧(Q∧R)；(P∨Q)∨R、P∨(Q∨R)；(P↔Q)↔R、P↔(Q↔R)；(P→Q)→R、P→(Q→R)的真值表，由表得出前三对公式等价，后一对公式不等价。(表略)11.解：（b）、（c）不是命题公式，因为它们不能根据命题公式的形成规则而得到。（a）和（d）是命题公式，它们的构造过程如下：（a）①P是命题公式根据条款1②Q是命题公式根据条款1③（P∧Q）是命题公式根据①、②条款2④（┐P）是命题公式根据①条款2⑤（（┐P）→（P∧Q））是命题公式根据③、④条款2⑥R是命题公式根据条款1⑦（（┐P→（P∧Q））∨R）是命题公式根据⑤、⑥条款2（d）①P是命题公式根据条款1②Q是命题公式根据条款1③(P→Q)是命题公式根据①、②条款2④(Q∧(P→Q))是命题公式根据②、③条款2⑤(Q∧(P→Q)→P)是命题公式根据①、④条款21.2重言式1.指出下列命题哪些是重言式、偶然式和矛盾式：重言式有：acdefhikl偶然式有：gjmn矛盾式有：b2.(a)=P∨Q∨┐R=┐（┐P∧┐Q∧R）(b)=P∨┐（┐Q∧R）∨P=P∨Q∨┐R=┐（┐P∧┐Q∧R）(c)=┐P∨（┐Q∨R）=T(d)=F(e)=（┐P∨（Q∨┐R））∧┐P∧Q=┐P∧Q=┐（P∨┐Q）(f)=┐P∧┐Q∧（R∨P）=┐P∧┐Q∧R∨┐P∧┐Q∧P=┐P∧┐Q∧R∨F=┐（P∨Q∨┐R）3.(a)=┐（P∧Q）∨P=┐P∨┐Q∨P=T(b)=┐(┐(P∨Q)→┐P)=┐(P∨Q∨┐P)=F(c)=(┐Q∨P)∧(P∨Q)∧T=P(d)=┐P∧P=F4.(a)=┐P∨┐Q∨P=P∨(┐P∨┐Q)=┐P→(P→┐Q)(b)=(┐P∨Q)∧(┐R∨Q)=(┐P∧┐R)∨Q=┐(P∨Q)∨Q=P∨R→Q(c)=┐((P→Q)∧(Q→P)=┐((┐P∨Q)∧(┐Q∨P))=┐(┐P∨Q)∨┐(P∨┐Q)=(P∧┐Q)∨(┐P∧Q)=(P∨┐P)∧(P∨Q)∧(┐Q∨┐P)∧(┐Q∨Q)=(P∨Q)∧┐(P∧Q)(d)=┐(┐P∨Q)=P∧┐Q5．使用恒等式证明下列各式，并写出与他们对偶的公式。(a)(┒(┒P∨┒Q)∨┒(┒P∨Q)P(b)(P∨┒Q)∧(P∨Q)∧(┐P∨┐Q)┐(┐P∨Q)(c)Q∨┐((┐P∨Q)∧P)T证明：(a)(┒(┒P∨┒Q)∨┒(┒P∨Q)((P∧Q)∨(P∧┐Q)(P∧(Q∨┐Q))P对偶公式:(┒(┒P∧┒Q)∧┒(┒P∧Q)(b)(P∨┒Q)∧(P∨Q)∧(┐P∨┐Q)(P∨(┒Q∧Q))∧(┐P∨┐Q)P∧(┐P∨┐Q)P∧┐P∨P∧┐Q┐(┐P∨Q)对偶公式:(P∧┒Q)∨(P∧Q)∨(┐P∧┐Q)(c)Q∨┐((┐P∨Q)∧P)Q∨┐(Q∧P)Q∨┐Q∨┐PT∨┐PT对偶公式:Q∧┐((┐P∧Q)∨P)6.求出下列公式的最简等价式。(a)((P→Q)↔(┐Q→┐P))∧R(b)P∨┐P∨(Q∧┐Q)(c)(P∧(Q∧S))∨(┐P∧(Q∧S))解：(a)((P→Q)↔(┐Q→┐P))∧R((┐P∨Q)↔(Q∨┐P))∧RT∧RR(b)P∨┐P∨(Q∧┐Q)T∨FT(c)(P∧(Q∧S))∨(┐P∧(Q∧S))(P∨┐P)∧(Q∧S)Q∧S7.证明下列蕴含式。(a)P∧Q(P→Q)(b)P(Q→P)(c)(P→(Q→R))(P→Q)→(P→R)证明：(a)方法一：只要证明P∧Q→(P→Q)是永真式P∧Q→(P→Q)┐(P∧Q)∨(┐P∨Q)(┐P∨┐Q)∨(┐P∨Q)┐P∨┐Q∨QT既为永真式，故P∧Q(P→Q)方法二：设P∧Q为T，则P和Q为T，则P→Q为T，故P∧Q⇒(P→Q)方法三：设P→Q为F，则P为F且Q为F，则P∧Q为F，故P∧Q⇒(P→Q)(b)因为P→(Q→P)┐P∨(┐Q∨P)T故P(Q→P)(c)因为(P→(Q→R))→(P→Q)→(P→R)┐(┐P∨(┐Q∨R))∨(┐(┐P∨Q)∨(┐P∨R))(P∧Q∧┐R)∨(P∧┐Q)∨┐P∨R(P∧Q∧┐R)∨((P∨┐P)∧(┐Q∨┐P))∨R(P∧Q∧┐R)∨┐(Q∧P∧┐R)T故(P→(Q→R))(P→Q)→(P→R)8.不构成真值表而证明下列蕴含式。(a)P→QP→P∧Q(b)(P→Q)→QP∨Q(c)((P∨┐P)→Q)→((P∨┐P)→R)(Q→R)(d)(Q→(P∨┐P))→(R→(P∧┐P))(R→Q)证明：证法一：(a)设P→Q为T，则P为F或Q为T。若P为F，则P→P∧Q为T；若Q为T，则P为T时为T，则P→P∧Q为T，P为F时P→P∧Q为T。故P→QP→P∧Q。(b)因为(P→Q)→Q→P∨Q┐(┐(┐P∨Q)∨Q)∨(P∨Q)((┐P∨Q)∧┐Q)∨P∨Q┐P∧┐Q∨P∨QT故(P→Q)→QP∨Q证法二：(a)设P→P∧Q为F，则P为T，Q为F，则P→Q为F，故P→QP→P∧Q。(b)设P∨Q为F，则P为F，Q为F，则(P→Q)→Q为F，故(P→Q)→Q⇒P∨Q。9(a).与非运算符用下述真值表定义，可以看出:P↑Q=¬（P∧Q）,试证明1.)P↑P=¬P2.)(P↑P)↑(Q↑Q)=P∨Q3.)(P↑Q)↑(P↑Q)=P∧Q(b).或非运算符号用下述真值表定义，它与¬（P∨Q）逻辑等价。对下述每一式，找出仅用↓表示的等价式。1.)¬P2.)P∨Q3.)P∧Q10．□和*是具有2个运算符对象的逻辑运算符,如果P□（Ｒ*R）和(P□Q)*(P□R)逻辑等价，那么说□在*上可分配。（a）∧和V可以互相分配吗？（b）∧和Vj及→可以对自己分配吗？(c).数的加法和乘法可以对自己分配马？11．对一个重言式使用代入规则后，仍然得重言式，对一个偶然式和矛盾式，使用代入规则后，结果如何？对一个重言式，使用替换规则后是否仍然得到重言式？对一个偶然式和矛盾式使用替换规则后，结果如何？12求出下列各式的代入实例：（a）.(((P→Q)→P)→P);用P→Q代P,用（（P→Q）→R）代Q.(b).((P→Q)→(Q→P));用Q代P，用Ｐ∧¬Ｐ代Q解答：1.2-9(a)1.)P↑P=¬(P∧P)=¬Ｐ2.)(P↑P)↑(Q↑Q)=¬Ｐ↑¬Q=¬(¬P∧¬Q)=P∨Q3.)(P↑Q)↑(P↑Q)=¬(P↑Q)=¬(¬(P∧Q))b.)1.)¬P=¬(P∨P)=P↓P2.)P∨Q=¬(¬(PVQ))=¬(P∨Q)=(P↓Q)↓(P↓Q)3.)P∧Q=¬(¬(P∧Q))=¬(¬PC¬Q)=¬P↓¬Q=(P↓P)↓(Q↓Q)1.2-101.)证明如下：PQP↓Q000110111000PQP↑Q000110111110PQRP∧(Q∨R)P∧Q∨P∧RP∨(Q∧R)(P∨Q)∧(P∨R)00000000010000010000001100111000011101111111011111111111由表可知，∨和∧可以互相分配2.)∧和∨可以对自己分配，而→对自己不可分配3.)数的加法和乘法对自己不可分配1．2-11偶然式使用代入规则后，不一定是偶然式，例如P∨Q是偶然式，当用¬P代Q时，得P重言式式使用代入规则后，一定是重言式矛盾式使用代入规则后，一定是矛盾式1.2-121.)((((P→Q)→((P→Q))→(P→Q)→(P→Q)2.)(Q→P∧¬P)→(P∧¬P→Q)