下载文档原格式
第二章作业评分要求：1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分2. 给出每小题得分(注意: 写出扣分理由)3. 总得分在采分点1处正确设置.一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):说明证1. p ⇔(p ∧q)∨(p ∧¬q)解逻辑方程法设 p ↔((p ∧q)∨(p ∧¬q)) =0, 分两种情况讨论:⎩⎨⎧=⌝∧∨∧=0)()(1)1(q p q p p 或者 ⎩⎨⎧=⌝∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ↔(p ∧q)∨(p ∧¬q)无成假赋值, 为永真式. 等值演算法(p ∧q)∨(p ∧¬q)⇔ p ∧(q ∨¬q)∧对∨的分配率⇔ p ∧1 排中律⇔ p 同一律 真值表法2. (p→q)∧(p→r)⇔p→(q∧r)等值演算法(p→q)∧(p→r)⇔ (¬p∨q)∧(¬p∨r)蕴含等值式⇔¬p∨(q∧r)析取对合取的分配律⇔ p→(q∧r)蕴含等值式3. ¬(p↔q)⇔(p∨q)∧¬(p∧q)等值演算法¬(p↔q)⇔¬( (p→q)∧(q→p) )等价等值式⇔¬( (¬p∨q)∧(¬q∨p) )蕴含等值式⇔¬( (¬p∧¬q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律⇔ (p∨q)∧¬(p∧q)德摩根律4. (p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)等值演算法(p∧¬q)∨(¬p∧q)⇔ (p∨q)∧¬(p∧q)析取对合取分配律, 排中律, 同一律说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):1.2.3.4.1. (¬p→q)→(¬q∨p)解(¬p→q)→(¬q∨p)⇔ (p∨q)→(¬q∨p)蕴含等值式⇔ (¬p∧¬q)∨(¬q∨p)蕴含等值式, 德摩根律⇔ (¬p∧¬q)∨¬q ∨ p结合律⇔ p∨¬q吸收律, 交换律⇔ M1因此, 该式的主析取范式为m0∨m2∨m32. (¬p→q)∧(q∧r)解逻辑方程法设 (¬p→q)∧(q∧r) =1, 则¬p→q=1且 q∧r=1,解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m3∨m7, 主合取范式为M0∧M1∧M2∧M4∧M5∧M6等值演算法(¬p→q)∧(q∧r)(p q)(q r) 蕴含等值式(p q r)(q r) 对分配律, 幂等律(p q r) (p q r)(p q r) 同一律, 矛盾律, 对分配律m7 m3主合取范式为M0∧M1∧M2∧M4∧M5∧M63. (p↔q)→r解逻辑方程法设 (p↔q)→r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析取范式为m1∨m2∨m3∨m4∨m5∨m7等值演算法(p↔q)→r((p q)(q p))r 等价等值式((p q)(q p))r 蕴含等值式(p q)(q p)r 德摩根律, 蕴含等值式的否定(参见PPT)(p q r)(q p r) 对分配律, 矛盾律, 同一律M0 M6主析取范式为m1∨m2∨m3∨m4∨m5∨m74. (p→q)∧(q→r)解等值演算法(p→q)∧(q→r)(p q)(q r) 蕴含等值式(p q)(p r)(q r) 对分配律, 矛盾律, 同一律(p q r)(p q r) (p q r)(p q r)(p q r)(p q r)m1 m0 m3 m7主合取范式为M2 M4 M5 M6.解逻辑方程法设 (p q) (q r) = 1, 则p q =1 且 q r =1.前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1.后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m0m1m3m7, 主合取范式为M2 M4 M5 M6.真值表法公式 (p q) (q r) 真值表如下:p q r(p q) (qr)00010011010001111000101011001111013724 M5 M6.。
离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0(4)（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。
并且，如果3是无理数，则2也是无理数。
另外6能被2整除，6才能被4整除。
”答：p: π是无理数 1q: 3是无理数0r: 2是无理数 1s:6能被2整除 1t: 6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。
19．用真值表判断下列公式的类型：（4）(p→q) →(⌝q→⌝p)（5）(p∧r) ↔(⌝p∧⌝q)（6）((p→q) ∧(q→r)) →(p→r)答：（4）p q p→q ⌝q ⌝p ⌝q→⌝p (p→q)→(⌝q→⌝p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 1 0 0 1 1所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) ⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)⇔(⌝p∨(p∨q))∨(⌝p∨r)⇔⌝p∨p∨q∨r⇔1所以公式类型为永真式(3)P q r p∨q p∧r （p∨q）→(p∧r)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)⇔(p→(q∧r))(4)(p∧⌝q)∨(⌝p∧q)⇔(p∨q) ∧⌝(p∧q)证明（2）(p→q)∧(p→r)⇔ (⌝p∨q)∧(⌝p∨r)⌝p∨(q∧r))p→(q∧r)（4）(p∧⌝q)∨(⌝p∧q)⇔(p∨(⌝p∧q)) ∧(⌝q∨(⌝p∧q)(p∨⌝p)∧(p∨q)∧(⌝q∨⌝p) ∧(⌝q∨q)1∧(p∨q)∧⌝(p∧q)∧1(p∨q)∧⌝(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(⌝p →q)→(⌝q ∨p)⌝(p ∨q)∨(⌝q ∨p)(⌝p ∧⌝q)∨(⌝q ∨p)⇔ (⌝p ∧⌝q)∨(⌝q ∧p)∨(⌝q ∧⌝p)∨(p ∧q)∨(p ∧⌝q)(⌝p ∧⌝q)∨(p ∧⌝q)∨(p ∧q)⇔320m m m ∨∨⇔∑(0,2,3)主合取范式：(⌝p →q)→(⌝q ∨p)⌝(p ∨q)∨(⌝q ∨p)(⌝p ∧⌝q)∨(⌝q ∨p)⇔(⌝p ∨(⌝q ∨p))∧(⌝q ∨(⌝q ∨p))⇔1∧(p ∨⌝q)⇔(p ∨⌝q) ⇔ M 1⇔∏(1)(2) 主合取范式为：⌝(p →q)∧q ∧r ⇔⌝(⌝p ∨q)∧q ∧r⇔(p ∧⌝q)∧q ∧r ⇔0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为：(p ∨(q ∧r))→(p ∨q ∨r)⌝(p ∨(q ∧r))→(p ∨q ∨r)(⌝p ∧(⌝q ∨⌝r))∨(p ∨q ∨r)(⌝p ∨(p ∨q ∨r))∧((⌝q ∨⌝r))∨(p ∨q ∨r))⇔1∧1⇔1所以该式为永真式.永真式的主合取范式为 1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：（2）①⌝(q∧r) 前提引入②⌝q∨⌝r ①置换③q→⌝r ②蕴含等值式④r 前提引入⑤⌝q ③④拒取式⑥p→q 前提引入⑦￢p（3）⑤⑥拒取式证明（4）：①t∧r 前提引入②t ①化简律③q↔s 前提引入④s↔t 前提引入⑤q↔t ③④等价三段论⑥（q→t）∧(t→q) ⑤置换⑦（q→t）⑥化简⑧q ②⑥假言推理⑨q→p 前提引入⑩p ⑧⑨假言推理(11)p∧q ⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明①s 附加前提引入②s→p 前提引入③p ①②假言推理④p→(q→r) 前提引入⑤q→r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p证明：①p 结论的否定引入②p→﹁q 前提引入③﹁q ①②假言推理④￢r∨q 前提引入⑤￢r ④化简律⑥r∧￢s 前提引入⑦r ⑥化简律⑧r∧﹁r ⑤⑦合取由于最后一步r∧﹁r 是矛盾式,所以推理正确.第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意x,均有2=(x+)(x).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x): 2=(x+)(x).G(x): x+5=9.(1)在两个个体域中都解释为)∀，在（a）中为假命题，在(b)中为真命题。
2.13 设解释I为：个体域D I ={-2,3,6},一元谓词F（X）：X≤3，G（X）：X>5,R(X):X≤7。
在I下求下列各式的真值。
（1）∀x(F(x)∧G(x))解：∀x(F(x)∧G(x))⇔(F(-2) ∧G(-2)) ∧(F(3) ∧G(3)) ∧(F(6) ∧G(6))⇔((-2≤3) ∧(-2>5)) ∧((3≤3) ∧(3>5)) ∧((6≤3) ∧(6<5))⇔((1 ∧0))∧((1 ∧0)) ∧((0 ∧0))⇔0∧0∧0⇔0(2) ∀x(R(x)→F(x))∨G(5)解：∀x(R(x)→F(x))∨G(5)⇔(R(-2)→F(-2))∧ (R(3)→F(3))∧ (R(6)→F(6))∨ G(5)⇔((-2≤7) →(-2≤3))∧ (( 3≤7) →(3≤3))∧ (( 6≤7) →(6≤3)) ∨ (5>5)⇔(1 →1)∧ (1 →1)∧ (1→0) ∨ 0⇔1∧ 1∧ 0 ∨ 0⇔0(3)∃x(F(x)∨G(x))解：∃x(F(x)∨G(x))⇔(F(-2) ∨ G(-2)) ∨ (F(3) ∨G(3)) ∨ (F(6) ∨G(6))⇔((-2≤3) ∨ (-2>5)) ∨ ((3≤3) ∨ (3>5)) ∨ ((6≤3) ∨ (6>5))⇔(1 ∨ 0) ∨ (1 ∨ 0) ∨ (0 ∨ 1)⇔1 ∨ 1 ∨ 1⇔12.14 求下列各式的前束范式，要求使用约束变项换名规则。
（1）⌝∃xF(x)→∀yG(x,y)(2) ⌝（∀xF(x,y) ∨∃yG(x,y) ）解：（1）⌝∃xF(x)→∀yG(x,y)⇔⌝∃xF(x)→∀yG(z,y) 代替规则⇔∀x⌝F(x)→∀yG(z,y) 定理2.1（2 ）⇔∃x(⌝F(x)→∀yG(z,y) 定理2.2（2）③⇔∃x∀y(⌝F(x)→G(z,y)) 定理2.2（1）④（2）⌝（∀xF(x,y) ∨∃yG(x,y) ）⇔⌝(∀zF(z,y) ∨∃tG(x,t)) 换名规则⇔⌝(∀zF(z,y) )∧⌝(∃tG(x,t) )⇔∃z⌝F(z,y) ∧∀t⌝G(x,z)⇔∃z (⌝F(z,y) ∧∀t⌝G(x,z))⇔∃z ∀t(⌝F(z,y) ∧⌝G(x,t))2.15 求下列各式的前束范式，要求使用自由变项换名规则。
第一章命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.7.因为p与q不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0(4)（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。
并且，如果3是无理数，则2也是无理数。
另外6能被2整除，6才能被4整除。
离散数学试题第一部分选择题一、单项选择题1．下列是两个命题变元p，q的小项是（C ）A．p∧┐p∧q B．┐p∨qC．┐p∧q D．┐p∨p∨q2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐qC．p∧q D．p∧┐q3．下列语句中是命题的只有（ A ）A．1+1=10 B．x+y=10C．sinx+siny<0 D．x mod 3=24．下列等值式不正确的是（ D ）A．┐(∀x)A⇔(∃x)┐AB．(∀x)(B→A(x))⇔B→(∀x)A(x)C．(∃x)(A(x)∧B(x))⇔(∃x)A(x)∧(∃x)B(x)D．(∀x)(∀y)(A(x)→B(y))⇔(∀x)A(x)→(∀y)B(y)5．谓词公式(∃x)P(x,y)∧(∀x)(Q(x,z)→(∃x)(∀y)R(x,y,z)中量词∀x的辖域是（C ）A．(∀x)Q(x,z)→(∃x)(∀y)R(x,y,z))B．Q(x,z)→(∀y)R(x,y,z)C．Q(x,z)→(∃x)(∀y)R(x,y,z)D．Q(x,z)6．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A，则对应于R的A的划分是（ D ）A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}7．设A={Ø}，B=P(P(A))，以下正确的式子是（A ）A．{Ø,{Ø}}∈B B．{{Ø,Ø}}∈BC．{{Ø},{{Ø}}}∈B D．{Ø,{{Ø}}}∈B8．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（A ）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)9．在自然数集N上，下列定义的运算中不可结合的只有（ D ）A．a*b=min(a,b)B．a*b=a+bC．a*b=GCD(a,b)(a,b的最大公约数)1 / 72 / 7D ．a*b=a(mod b)10.设R 和S 是集合A 上的关系,R ∩S 必为反对称关系的是( ) A ．当R 是偏序关系,S 是等价关系; B ．当R 和S 都是自反关系; C ．当R 和S 都是等价关系; D ．当R 和S 都是传递关系11.设R 是A 上的二元关系,且R ·R ⊆R,可以肯定R 应是( D ) A ．对称关系; B ．全序关系; C ．自反关系; D ．传递关系 12．设R 为实数集，函数f ：R →R ，f(x)=2x ，则f 是（ ） A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射CDACCDAADADB第二部分 非选择题二、填空题1．设论域是{a,b,c}，则(∀x)S(x)等价于命题公式 S(a)∧S(b)∧S(c) ；(x ∃)S(x)等价于命题公式 S(a)∨S(b) ∨S(c) 。
习题 2.11．将下列命题符号化。
(1) 4不是奇数。
解：设A(x)：x是奇数。
a：4。
“4不是奇数。
”符号化为：¬A(a)(2) 2是偶数且是质数。
解：设A(x)：x是偶数。
B(x)：x是质数。
a：2。
“2是偶数且是质数。
”符号化为：A(a)∧B(a)(3) 老王是山东人或河北人。
解：设A(x)：x是山东人。
B(x)：x是河北人。
a：老王。
“老王是山东人或河北人。
”符号化为：A(a)∨B(a)(4) 2与3都是偶数。
解：设A(x)：x是偶数。
a：2，b：3。
“2与3都是偶数。
”符号化为：A(a)∧A(b)(5) 5大于3。
解：设G(x,y)：x大于y。
a：5。
b：3。
“5大于3。
”符号化为：G(a,b)(6) 若m是奇数，则2m不是奇数。
解：设A(x)：x是奇数。
a：m。
b：2m。
“若m是奇数，则2m不是奇数。
”符号化为：A(a)→A(b)(7) 直线A平行于直线B当且仅当直线A不相交于直线B。
解：设C(x,y)：直线x平行于直线y。
设D(x,y)：直线x相交于直线y。
a：直线A。
b：直线B。
“直线A平行于直线B当且仅当直线A不相交于直线B。
”符号化为：C(a,b)↔¬D(x,y)(8) 小王既聪明又用功，但身体不好。
解：设A(x)：x聪明。
B(x)：x用功。
C(x)：x身体好。
a：小王。
“小王既聪明又用功，但身体不好。
”符号化为：A(a)∧B(a)∧¬C(a)(9) 秦岭隔开了渭水和汉水。
解：设A(x,y,z)：x隔开了y和z。
a：秦岭。
b：渭水。
c：汉水。
“秦岭隔开了渭水和汉水。
”符号化为：A(a,b,c)(10) 除非小李是东北人，否则她一定怕冷。
解：设A(x)：x是东北人。
B(x)：x怕冷。
a：小李。
“除非小李是东北人，否则她一定怕冷。
”符号化为：B(a)→¬A(a)2．将下列命题符号化。
并讨论它们的真值。
(1) 有些实数是有理数。
解：设R(x)：x是实数。
离散数学答案第二章习题解答第二章谓词逻辑习题与解答1、将下列命题符号化:(1) 所有的火车都比某些汽车快。
(2) 任何金属都可以溶解在某种液体中。
(3) 至少有一种金属可以溶解在所有液体中。
(4) 每个人都有自己喜欢的职业。
(5) 有些职业就是所有的人都喜欢的。
解 (1) 取论域为所有交通工具的集合。
令x x T :)(就是火车, x x C :)(就是汽车, x y x F :),(比y 跑得快。
“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。
(2) 取论域为所有物质的集合。
令x x M :)(就是金属, x x L :)(就是液体, x y x D :),(可以溶解在y 中。
“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y xD y L y x M x ∧?→?。
(3) 论域与谓词与(2)同。
“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。
(4) 取论域为所有事物的集合。
令x x M :)(就是人, x x J :)(就是职业, x y x L :),(喜欢y 。
“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→?(5)论域与谓词与(4)同。
“有些职业就是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。
2、取论域为正整数集,用函数+(加法),?(乘法)与谓词<,=将下列命题符号化:(1) 没有既就是奇数,又就是偶数的正整数。
(2) 任何两个正整数都有最小公倍数。
(3) 没有最大的素数。
(4) 并非所有的素数都不就是偶数。
解先引进一些谓词如下:x y x D :),(能被y 整除,),(y x D 可表示为)(x y v v =??。
离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨(q∧r)⇔0∨(0∧1)⇔0（2）（p?r）∧(﹁q∨s)⇔（0?1）∧(1∨1)⇔0∧1⇔0.（3）（⌝(4)（176能被2q:3r:2s:619（4）(p（5）(p（6）((p答：（pqp→q⌝0011111011011110010011110011所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1)⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)⇔(⌝p∨(p∨q))∨(⌝p∨r)⇔⌝p∨p∨q∨r⇔1所以公式类型为永真式(3)P qrp∨qp∧r（p∨q）→(p∧r)0000010010014.(2)(p→(4)(p∧证明（2（45.(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(⌝p→q)→(⌝q∨p)⇔⌝(p∨q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∧p)∨(⌝q∧⌝p)∨(p∧q)∨(p∧⌝q)⇔(⌝p∧⌝q)∨(p∧⌝q)∨(p∧q)⇔∑(0,2,3)主合取范式：(⌝p→q)→(⌝q∨p)⇔⌝(p∨q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∨p)⇔(⌝p⇔1∧(p⇔(p∨⇔∏(2)⌝(p→q)⇔(p∧(3)⇔⌝⇔1∧1⇔1所以该式为永真式.永真式的主合取范式为1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14.在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：（2）①⌝(q∧r)前提引入②⌝q∨⌝r①置换③q→⌝r②蕴含等值式④r⑤⌝q⑥p→q⑦￢p（3证明（4①t②t③q④s⑤q⑥（⑦（⑧q⑨q⑩p15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明①s附加前提引入②s→p前提引入③p①②假言推理④p→(q→r)前提引入⑤q→r③④假言推理⑥q前提引入⑦r⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p证明：①p②p③﹁④￢⑤￢⑥r⑦r⑧r3.:(1)均有2=(x+)(x).(2)其中(a)(b)解：F(x):2=(x+)(x).G(x):x+5=9.(1)在两个个体域中都解释为)(x∀，在（a）中为假命题，在(b)中为真命题。
一、 选择题1．下列四个公式正确的是①)()())()((x xB x xA x B x A x ∀∧∀⇒∧∀ ②)()())()((x xB x xA x B x A x ∀∨∀⇒∨∀③)()())()((x xB x xA x B x A x ∃∨∃⇒∨∃ ④))()(()()(x B x A x x xB x xA ∧∃⇒∃∧∃A.①③B.①④C.③④D.②④2. 谓词公式)())()((x Q y yR x P x →∃∨∀中量词∀x 的辖域是( )(A) ))()((y yR x P x ∃∨∀ (B) P (x ) (C ) )()(y yR x P ∃∨ (D) )(x Q3. 谓词公式))()(()(x xQ x Q x x xP ⌝∃→⌝∀→∀的类型是（ ）(A ) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 蕴涵式4. 设个体域为整数集，下列公式中其真值为1的是( )(A ) )0(=+∃∀y x y x (B) )0(=+∀∃y x x y(C))0(=+∀∀y x y x (D) )0(=+∃⌝∃y x y x5. 设个体域{,}A a b =，公式()()xP x xS x ∀∧∃在中消去量词后应为 ( )(A) ()()P x S x ∧ (B ) ()()(()())P a P b S a S b ∧∧∨(C) ()()P a S b ∧ (D) ()()()()P a P b S a S b ∧∧∨6. 在谓词演算中，下列各式正确的是( )(A) (,)(,)x yA x y y xA x y ∃∀⇔∀∃ (B ) (,)(,)x yA x y y xA x y ∃∃⇔∃∃(C) (,)(,)x yA x y x yA x y ∃∀⇔∀∃ (D) (,)(,)x yA x y y xA x y ∀∀⇔∀∀7.下列各式不正确的是( )(A ) (()())()()x P x Q x xP x xQ x ∀∨⇔∀∨∀(B) (()())()()x P x Q x xP x xQ x ∀∧⇔∀∧∀(C) (()())()()x P x Q x xP x xQ x ∃∨⇔∃∨∃(D) (())()x P x Q xP x Q ∀∧⇔∀∧8. 设I 是如下一个解释：D ＝{a,b}, 01 0 1b) P(b,a) P(b,b) P(a,),(a a P 则在解释I 下取真值为1的公式是( ).(A) ∃x ∀yP(x,y) (B)∀x ∀yP(x,y) (C)∀xP(x,x) (D )∀x ∃yP(x,y).9. 设个体变元z y x ,,的论域都为自然数集合，(,,):,P x y z x y z +=(,,),(,):Q x y z x y z R x y x y ⋅=<：，则以下命题中（ ）是假命题.A ．),0,(x x xP ∀B ．),,(y y x yP x ∀∃C ．),,(x x y yQ x ∃∀D ．)0,(x xR ∀10. 下面不是命题的是（ ）A ．()xP x ∀B ．()()x P x ∃C ．()()()x P x P y ∀∨D ．()()(()())x y P x R y ∃∃→11公式()()()()x P x x Q x ∀→∀的前束范式为（ ）A ．()()(()())x y P x Q y ∀∀→B ．()()(()())x y P x Q y ∀∃→C ．()()(()())x y P x Q y ∃∀→D ．()()(()())x y P x Q y ∃∃→12. 公式()(())x P x Q ∀↔⇔（ ）A ．(()())(()())x P x Q Q x P x ∀→∧→∀B ．(()())(()())x P x Q Q x P x ∀→∧→∃C (()())(()())x P x Q Q x P x ∃→∧→∀D ．(()())(()())x P x Q Q x P x ∃→∧→∃13. ()()(,)x y P x y ∀∃的否定是（ ）A ．()()(,)x y P x y ∀∀⌝B ．()()(,)x y P x y ∃∀⌝C ．()()(,)x y P x y ∀∃⌝D ．()()(,)x y P x y ∃∃⌝14.下列谓词公式与()(()())x A x B x ∀↓等价的是（ ）A ．()()()()x A x xB x ∀↓∀ B ．()()()()x A x x B x ∀↑∀C ．()()()()x A x x B x ∃↓∃D ．()()()()x A x x B x ∃↑∃15.在谓词演算中，()P a 是()xP x ∀的有效结论，其理论依据是（ ）A ．USB ．UGC ．ESD ．EG16. 设个体域是整数集合，P 代表∀x ∀y ((x <y )→(x -y <x ))，下面4个命题中为真的是( )(A) P 是真命题 (B ) P 是假命题(C) P 是一阶逻辑公式，但不是命题 (D) P 不是一阶逻辑公式二、填空题1. 设全体域D 是正整数集合，确定下列命题的真值：(1) ()x y xy y ∀∃= ( 0 ) (2) ()+x y x y y ∃∀= ( 0 )(3) ()+x y x y x ∃∀= ( 0 ) (4) (2)x y y x ∀∃= ( 1 )2. 谓词公式()((,)())()((,)()())x P x y Q z y R x y z Q z ∀∨∧∃→∀中量词∀x 的辖域是3. 公式()(()(,)()(,))()x P x Q x y z R y z S x ∀→∨∃→中量的自由变量为 x,y 约束变量为 x,z4. 设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ∀∨∃消去量词后的等值式为 .A (1)∨A (2)∨(B (1)∧B (2)) .5. 设个体域D ＝{a ,b },公式)),()((y x yH x G x ∃→∀消去量词化为. (G (a )→(H (a ,a )∨H (a ,b )))∧ (G (b )→(H (b ,a )∨H (b ,b )))6. 设N (x )：x 是自然数，Z (y )；y 是整数，则命题“每个自然数都是整数，而有些整数不是自然数”符号化为 (()())(()())x N x Z x x Z x N x ∀→∧∃∧⌝7. 谓词公式∀x (F (x )→G (x ))∧⌝∀y (F (y )→G (y ))的类型是 永假式 ．8. 设个体域{1,2},谓词P (1)=1,P(2)=0，Q(1)=0，Q (2)=1，则∀x (P (x )∨Q (x ))的真值是 19.只用联结词,,⌝∀→表示以下公式()(()())x P x Q x ∃∧= ()(()())x P x Q x ⌝∀→⌝()(()()())x P x y Q y ∃↔∀= ()((()()())(()()()))x P x y Q y y Q y P x ⌝∀→∀→⌝∀→ ()(()()())y x P x Q y ∀∀∨⌝= ()(()()())y Q y x P x ∀→∀三、计算及证明1. 求谓词公式))(())((a f R x Q P x ∧→∀的真值．其中P ：4>3，Q （x ）：x >1，R （x ）：x ≤2．f （-3）=1，f （1）=5，f （5）= -3．a ：5．个体域D =（-3，1，5）．解：))(())((a f R x Q P x ∧→∀=))5(())5(())1(())3((f R Q P Q P Q P ∧→∧→∧-→=)3()11()01()01(-∧→∧→∧→R01100=∧∧∧=2.说明公式))(),(()(x xP y x yG x xP ∀→∃→∀是逻辑有效式(永真式)．解：因为))(),(()(x xP y x yG x xP ∀→∃→∀是)(P Q P →→的代换实例，可知 ))(),(()(x xP y x yG x xP ∀→∃→∀是逻辑有效式．或 ))(),(()(x xP y x yG x xP ∀∨⌝∃∨⌝∀1)(),()(⇔∨⌝∃∨⌝∀⇔x P y x yG x xP3. 通过等值演算说明下列等值式成立： )()())()((x xQ x xP x Q x P x ∃→∀⇔→∃证：⇔→∃))()((x Q x P x )()((x Q x P x ∨⌝∃))()(x xQ x P x ∃∨⌝∃⇔)()(x xQ x xP ∃∨⌝∀⇔)()(x xQ x xP ∃→∀⇔4. 求谓词公式),,()),(),((z y x zH y x yG y x xF ∃∧∀→∀的前束范式解：),,()),(),((z y x zH y x yG y x xF ∃∧∀→∀),,()),(),((z y x zH y x yG y x xF ∃∧∀∨⌝∀⇔((,)(,))(,,)u F u y vG x v zH x y z ⇔∃⌝∨∀∧∃((,)(,))(,,))u F u y vG x v zH x y z ⇔∃⌝∨∀∧∃(((,)(,))(,,))u v z F u y G x v H x y z ⇔∃∀∃⌝∨∧(或(((,)(,))(,,))u v z F u y G x v H x y z ⇔∃∀∃→∧)5. 前提：∃xF (x ), ∀x (F (x )→G (x )∧H (x ))结论：∃x (F (x )∧H (x ))6. 构造推理证明))()(()()(x Q x P x x xQ x xP →∀⇒∀→∃． （提示：))()(()()(x B x A x x xB x xA ∨∀⇒∀∨∀.) 证 ① )()(x xQ x xP ∀→∃ 前提引入② )()(x xQ x xP ∀∨⌝∃ T ①,蕴含等值式③ )()(x xQ x P x ∀∨⌝∀ T ②,量词否定 ④ ))()((x Q x P x ∨⌝∀⑤ ))()((x Q x P x →∀ T ④,蕴含等值式 法2：（反证法）① (()())x P x Q x ⌝∀→ 前提引入② (()())x P x Q x ∃∧⌝ T E ①,③ ()()P c Q c ∧⌝ ES ②, ④ ()Q c ⌝ T ③ , ⑤ ()P c T ③,⑥()xP x ∃ EG ⑤ ⑦)()(x xQ x xP ∀→∃ P⑧()xQ x ∀ T ⑦⑨()Q c UG ⑧ ⑩()()Q c Q c ⌝∧ T ④。
