离散数学-习题答案.docx

离散数学 习题 参考答案

习题一
1、构造公式(p∧q)∨ (¬ｐ∧¬q)、p↔ｑ 得真值表。
2、构造公式¬(p∨ｑ)与¬ｐ∧¬q　得真值表。
３、构造公式 p、p∧p、p∨p　得真值表。
4、构造公式　p∨(ｑ∧r)、(p∨q)∧(p∨r)得真值表。
5、构造公式 p∨(p∧ｒ)、ｐ　得真值表、　
6、构造公式 p∧(p∨r)、p 得真值表、　
7、构造公式　p↔ｑ、¬q↔¬p 得真值表。
8、构造公式(p→q)∧(p→¬q)、¬p 得真值表。
9、构造公式 p、¬¬p 得真值表、
1０、构造公式 p∨¬p、p∧¬p 得真值表

略
习题二
一、分别用等算演算与真值表法,判断下列公式就是否存在主析取范式或主合取范式,若有,请写出来。
(1)(¬p→ｑ)→(¬q∨p)　
(2)(¬p→q)→(q∧r)
(3)(p∨(ｑ∧r))→(ｐ∨q∨ｒ)
(4) ¬(q→¬p)∧¬ｐ
(５)(p∧q)∨(¬p∨r)
(6)(ｐ→(p∨q))∨ｒ　
(７)(ｐ∧q)∨ｒ　
(8) (p→q)∧(q→r)
(9)　(ｐ∧q)→q
(1０) ¬(r↔p)∧p∧q
解:(1)
ｐ
q
¬p
(¬ｐ→q)
¬q
(¬q∨p)
(¬p→q)→(¬q∨ｐ)
0
０
1
0
1　
1
1
0
1
1
1
0
0
0
1
0
0　
1
1
1
1　
1
1　
0　
1
0　
1　
１

存在主析取范式=成真赋值对应得小项得析取
=m０0∨ｍ10∨m11=(¬ｐ∧¬q)∨(p∧¬q)∨(ｐ∧q)
主析取范式＝成假赋值对应得大项得合取
=M0１=p∨¬q
等值演算:
(¬p→ｑ)→(¬q∨p)
⇔¬ (¬¬ｐ∨q)∨(p∨¬q)
⇔¬ (p∨q)∨(p∨¬q)
⇔　(¬p∧¬q)∨(p∨¬q)　
⇔　(¬ｐ∨(p∨¬q))∧(¬q∨(ｐ∨¬q))
⇔ (¬ｐ∨p∨¬ｑ)∧(¬ｑ∨p∨¬q)
⇔　(1∨¬q)∧(p∨¬q)　
⇔　(ｐ∨¬q)
这就是大项,故为大项得合取,称为主合取范式

(¬p→ｑ)→(¬q∨ｐ)
⇔ (p∨¬q)
⇔ (ｐ)∨(¬q)
⇔ (p∧1)∨( 1∧¬ｑ)
⇔ (p∧(q∨¬q))∨( (p∨¬p)∧¬q)
⇔ (ｐ∧ｑ)∨ (p∧¬ｑ)∨(p∧¬ｑ)∨(¬p∧¬ｑ)
⇔　(p∧q)∨　(p∧¬q)∨(¬ｐ∧¬q)
因为一个公式得值不就是真,就就是假,因此当我们得到一个公得取值为真得情况时,剩下得组合就是取值为假, 因此当得到小项得析取组成得主析取范式后,可以针对剩下得组合写出主合取范式。
如当我们得到(¬p→q)→(¬q∨p)得大项之合取(p∨¬q)后,使(p∨¬q)为假时(p,q)得值为(０,1),故其标记为Ｍ01,剩余得取值为(０,0),(１,0),(１,1),故小项之析取为m00∨m１0∨m11、
反之,若先得到其小项得析取,也可得到其大项得合取、反正这两者将其所有组合瓜分完毕。

(2)(¬p→q)→(q∧ｒ)
p
q
r
¬p
¬p→q
(q∧ｒ)
结果
0
0
0
１
0
0
1
０
0
1
１
0
０
1
0
1
0
1
1
0
0
0
1
1
1
1
1
1
1
0
０
0
1
0
0
1
0
１
0
1
０
0
1
1
0
0
1
0
0
１
1
１
0
1
1
1

主析取范式＝ｍ000∨m001∨ｍ011∨m11１＝(¬ｐ∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧ｒ)∨(p∧q∧ｒ)
主合取范式=Ｍ０10∧Ｍ１00∧Ｍ101∧M１1０=(p∨¬q∨r)∧(¬p∨q∨r)∧(¬ｐ∨q∨¬r)∧(¬p∨¬q∨r)

(3)(ｐ∨(q∧r))→(p∨ｑ∨r)
p
ｑ
r
(q∧r)
(p∨(q∧ｒ))
(p∨q∨ｒ)
(p∨(ｑ∧r))
→(ｐ∨q∨r)
0
0
0
0
０
0
1
0
０
１
0
0
0
１
0
１
０
０
0
1
1
０
1
１
０
0
1
１
1
０
0
0
１
１
1
1
０
1
０
１
1
1
1
1
0
1
1
1
1
１
1
1
１
１
1
1
永真式,所有小项得析取得到其主析取范式
＝(¬ｐ∧¬ｑ∧¬r)∨(¬p∧¬ｑ∧r)∨(¬p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧¬r)∨(p∧¬q∧ｒ)∨(p∧q∧¬r)∨(ｐ∧ｑ∧ｒ)　
由于没为假得指派,所以没有为假赋值,所对应得大项合取构成得合取,即没有主合取范式、
¬(p∨(q∧r))∨(p∨q∨ｒ)=(¬p∧¬(q∧r))∨(ｐ∨q∨r)＝((¬ｐ∧¬q)∨　(¬p∧¬r))∨(ｐ∨q∨r) ＝
(¬p∧¬q)∨ (¬p∧¬r)∨p∨q∨r=¬(p∨q)∨(¬p∧¬ｒ)∨p∨q∨r=1永真

(4) ¬(q→¬ｐ)∧¬p
p
q
¬p
(q→¬ｐ)
¬(q→¬ｐ)
结果
0
0
1
1
０
0
０
1
1
1
０
0
１　
0
0
１
0
0
1
１　
０
0
1
０

没有成真得赋值,从而没有对应得小项,因此没有小项构成得主析取范式
永假式即矛盾式,为假指派对应得大项合取＝(p∨ｑ)∧(p∨¬ｑ)∧(¬p∨q)∧(¬p∨¬q)　
原式＝¬(¬q∨¬ｐ)∧¬p=(q∧p) ∧¬ｐ=0

(５) (p∧q)∨(¬p∨r)
p
q
r
(ｐ∧q)
¬p
(¬p∨r)
(ｐ∧q)∨(¬p∨r)
０
0
０
0
1
１
１
0
0
1
0
1
1
１
０
1
0
0
１
1
１
0
１
1
0
１
1
1
1
0
0
0
０
０
0
1
０
1
0
0
1
1
1
1
０
1
0
０
1
1
１
１
1
0
1
1

主析取范式
(¬p∧¬q∧¬r)∨( ¬p∧¬q∧r)∨( ¬p∧q∧¬r)∨( ¬p∧q∧r)∨(p∧¬ｑ∧ｒ)∨(ｐ∧ｑ∧¬ｒ)∨(p∧ｑ∧r)
主合取范式
M１０0＝¬ｐ∨q∨r　
原式=((ｐ∧q)∨¬p)∨ｒ＝((p∨¬p)∧(¬p∨q))∨r=(1∧(¬ｐ∨q))∨r=¬p∨q∨r 这就就是大项也
剩下得赋值对应得就就是小项　

(6)(p→(ｐ∨ｑ))∨ｒ
p
q
r
(p∨ｑ)
(p→(p∨ｑ))
(p→(ｐ∨q))∨r
０
0
０
0
1
1
0
0
1
０
1
1
0
1
0
1
１
1
0
1
1
1
1
１
１
0
0
1
1
1
1
０
1
1
1
1
１
1
0
1
１
1
1
１
１
1
1
1

永真式,只有小项组成得主析取范式。
没有为假得赋值,所以没有成假赋值对应得大项得合取,即没有主合取范式、
原式=(¬ｐ∨ (p∨q))∨ｒ＝(1∨q)∨r=1　

(7)(ｐ∧q)∨ｒ
p
q
ｒ
(p∧ｑ)
(p∧ｑ)∨r
0
0
0
0
0
0
0
1
0
1
０
1
0
0
0
0　
１
1
0
1
1
0
０
0
0
１
0
1
0　
1
１
1
0
1
1
1
1
1
1
1

主析取范式=m０01∨m011∨m１０1∨m１1０∨m１11＝
(¬p∧¬q∧r)∨( ¬p∧q∧r)∨(　ｐ∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r)　
主合取范式=M0０0∧M010∧M1０0=(p∨q∨r)∧ (p∨¬q∨ｒ)∧ (¬p∨q∨r)　
(p∧q)∨r　
=(p∧q∧1)∨(1∧1∧r)
＝(p∧q∧(¬r∨ｒ))∨( (¬p∨ｐ)∧ (¬q∨q)∧r)
=(p∧q∧¬r)∨ (p∧q∧ｒ)∨ (¬p∧¬q∧r)∨( ¬p∧q∧r) ∨ (ｐ∧¬q∧r)　
(p∧q)∨r
=(p∨r) ∧(q∨ｒ)
＝(p∨０∨ｒ) ∧(0∨q∨r)
＝(ｐ∨(¬q∧ｑ)∨r) ∧((¬p∧ｐ)∨q∨ｒ)
=(p∨¬ｑ∨r)　∧　(p∨q∨ｒ) ∧(¬p∨q∨r) ∧(ｐ∨ｑ∨r)　
=(p∨¬ｑ∨ｒ) ∧　(p∨q∨r) ∧(¬p∨q∨ｒ)

(8) (p→q)∧(q→r)
p
q
r
(ｐ→ｑ)
(q→r)
(ｐ→ｑ)∧(ｑ→r)
0
0
0
1
1
１
0
0
1
１
1
1
0
1
0
1
0
0
0
１
1
1
１
1
１
0
0
0
1
０
1
0
1
０
1
0
1
1
0
1
0
0
1
1
1
1
1
1
主析取范式=ｍ0０0∨m０01∨m01１∨m1１１
=(¬p∧¬q∧¬ｒ)∨(¬ｐ∧¬q∧r)∨(¬p∧q∧r)∨(p∧q∧r)　
主合取范式=M010∧M10０∧M1０１∧Ｍ110=
＝(p∨¬q∨r)∧(¬p∨q∨r)∧(¬ｐ∨ｑ∨¬r)∧(¬ｐ∨¬ｑ∨r)
(p→q)∧(q→r)＝(¬p∨q)∧(¬q∨ｒ)　
=(¬p∨ｑ∨０)∧(0∨¬q∨r)
=(¬ｐ∨q∨(¬ｒ∧r))∧( (¬p∧p)∨¬q∨r)
＝(¬p∨q∨¬r)∧ (¬p∨q∨r) ∧(¬ｐ∨¬q∨r)∧( p∨¬ｑ∨r)
(p→q)∧(q→r)=(¬ｐ∨ｑ)∧(¬q∨ｒ)
=(¬p∧¬q)∨　(¬p∧ｒ)∨ (q∧¬ｑ)∨ (q∧ｒ)
=(¬ｐ∧¬q∧１)∨ (¬p∧1∧r)∨(1∧ｑ∧r)
=(¬p∧¬q∧(¬r∨r))∨ (¬p∧(¬q∨q)∧r)∨( (¬p∨p)∧ｑ∧r)
=(¬p∧¬q∧¬r)∨ (¬p∧¬q∧r)∨ (¬p∧¬q∧r)∨ (¬p∧q∧r)∨　(　¬ｐ∧ｑ∧r)∨( ｐ∧q∧r)
=(¬p∧¬ｑ∧¬ｒ)∨ (¬p∧¬ｑ∧r)∨ (¬p∧ｑ∧r)∨(　p∧q∧r)
(９) (p∧q)→q
ｐ
q
(p∧q)
(p∧q)→q
0
０
0
1
0
1
０
1
1
0
0
１
1
1
1
1
永真式,只有小项得析取构成得主析取范式＝(¬p∧¬q)∨(　¬p∧q)∨(ｐ∧¬ｑ)∨(p∧q)
没有为假得指派,所以没有由大项得合取构成得主合取范式
(p∧q)→q
=¬(p∧q)∨q
＝(¬p∨¬q)∨q
=¬ｐ∨¬ｑ∨ｑ
＝1

(10) ¬(r↔p)∧p∧ｑ
p
ｑ
r
r↔p
¬(r↔ｐ)
¬(ｒ↔ｐ)∧p∧q
0
0
０
1
0
0
0
0
1
０
１
0
0
1
０
1
0
0
0
1
１
０
1
０
１
0
0
０
1
0
1
０
1
1
0
0
1
1
0
０
１
1
１
1
1
1
0
0
主析取范式=m1１０＝ｐ∧q∧¬r
主合取范式＝M000∧ M００1∧　M０10∧　M011∧　Ｍ100∧ M101∧ M111
=　(p∨q∨ｒ)∧(ｐ∨q∨¬r)∧(p∨¬q∨r)∧(p∨¬ｑ∨¬r)∧(　¬p∨q∨r)∧( ¬ｐ∨ｑ∨¬r)∧( ¬p∨¬q∨¬r)
¬(ｒ↔p)∧p∧q
=¬((¬p∨r)∧ (p∨¬ｒ))∧p∧q
=((ｐ∧¬r) ∨ (¬p∧r))∧p∧q
=(ｐ∧¬r∧ｐ∧q)　∨(¬p∧r∧p∧q)
＝(ｐ∧q ∧¬r)
¬(r↔ｐ)∧p∧q
=¬((p∧r)∨　(¬p∧¬r))∧p∧ｑ
= ((¬p∨¬r)∧(p∨r))∧ｐ∧ｑ
= (¬ｐ∨¬r)∧(p∨ｒ)∧p∧ｑ
= (¬p∨¬r)∧((ｐ∨r)∧p)∧q
= (¬p∨¬ｒ)∧p∧ｑ　
=　(¬ｐ∨(¬q∧q)∨¬r)∧(p∨(¬q∧ｑ)∨ (¬r∧r))∧( (¬ｐ∧ｐ)∨ｑ∨(¬r∧r))
＝(¬p∨¬q∨¬r)∧　(¬p∨q∨¬ｒ)∧
(p∨¬ｑ∨¬r)∧(p∨¬q∨r)∧(p∨ｑ∨¬r)∧ (p∨q∨r) ∧
∧( ¬p∨q∨¬ｒ) ∧( ¬p∨q∨ r) ∧( p∨q∨¬r)　∧( p∨q∨r)
＝　(p∨q∨r)　∧(p∨q∨¬ｒ)∧ (p∨¬q∨ｒ)∧　(ｐ∨¬q∨¬ｒ)∧　( ¬p∨q∨ ｒ) ∧(¬ｐ∨q∨¬r)∧　(¬p∨¬q∨¬ｒ)
=Ｍ00０ ∧M０01∧M0１０∧Ｍ011∧ M100　∧M101∧M１1１

二、应用题　
1、某次课间休息时,１位同学作为主持人与另外3位同学进行猜数游戏,主持人说这个数就是3０、50、70中得某一个,您们三位同学各猜一次,然后主持人分析每人猜数得结果,从而最终确定就是哪个数。
同学１说:这个数就是3０,不就是50　
同学２说:这个数就是５０,不就是70　
同学3说:这个数既不就是30,也不就是50
主持人听后说道:您们3人中,有一人全对,有二人对了一半,请问到底就是哪个数、
解:令Ｓ表示“这个数就是30”,W表示“这个数就是50”,Ｑ表示“这个数就是70”　
同学１得话:S∧¬Ｗ
同学2得话:Ｗ∧¬Q
同学3得话:¬Ｓ∧¬W　
对于每个人来说,只有二个选择:全对、对一半,对一半又分成:第一句对第二句错、第一句错第二句对,因此每个同学得对错情况为:√√、√×、×√,因此3个人共有３*3＊３＝27种可能得情况,其中有些情况不符合“有一人全对,有二人对了一半”而剔除。
我们按“√√、√×、×√”顺序,构造“类真值表"来分析其组合情况

同学1
同学2
同学3
命题公式
分析
√√
√√
√√
不必写
不可能全对
√√
√√
√×
不必写
不可能有2个对
√√
√√
√×
不必写
不可能有2个对
√√
√×
√√
不必写
不可能有2个对
√√
√×
√×
Ｓ∧¬W∧W∧Q∧¬Ｓ∧W＝0
真值为0不对
√√
√×
√×
S∧¬W∧W∧Ｑ∧S∧¬W=0
真值为０不对
√√
√×
√√
不必写
不可能有2个对
√√
√×
√×
Ｓ∧¬W∧¬Ｗ∧Q∧¬S∧Ｗ＝０
真值为0不对
√√
√×
√×
Ｓ∧¬Ｗ∧¬Ｗ∧¬Q∧Ｓ∧¬W=　Ｓ∧¬W∧¬Q
可能对得,就是30
不就是５０,不就是７0
√×
√√
√×
S∧Ｗ∧ Ｗ∧¬Ｑ∧¬S∧ W=0
不可能
√×
√√
√×
S∧W∧ W∧¬Q∧S∧ ¬W＝0
不可能
√×
√×
√√
S∧W∧ W∧Q∧¬S∧¬W=０
不可能
√×
√×
√√
S∧W∧ ¬W∧¬Q∧¬S∧¬Ｗ=０
不可能
√×
√√
√×
× S, ¬W,W, ¬Q,S,W=0
不可能
×√
√√
×√
¬Ｓ,　¬Ｗ,W, ¬Q,S, ¬W=0
不可能
×√
√×
√√
¬Ｓ, ¬W,W,Ｑ, ¬S, ¬W＝0
不可能
×√
×√
√√
¬Ｓ,¬W,¬W,¬Ｑ,¬Ｓ,¬W=
3个数都不就是,不可能

答案就是:就是３０,不就是50,不就是70
同学１说:这个数就是30,不就是5０ 全对
同学2说:这个数就是50,不就是70 第一句错第二句对
同学3说:这个数既不就是３０,也不就是5０　第一句错第二句对

2、设计一个如下得电路图:它有三个输入p1、ｐ2、p３,当其中有2个及以上得值为1时输出得结果为1,其她情况下输出0。请给出其真值表,同时针对此真值表给出主析取范式、主合取范式,并给出其最简单得表达式。
答:与课堂例题一样
在真实得教材将其换成了如下习题

2、设计一个如下得电路图:它有三个输入ｐ1、ｐ２、ｐ3,当其中任意二个得值为0时输出得结果为1,其她情况下输出0。请给出其真值表,同时针对此真值表给出主析取范式、主合取范式,并给出其最简单得表达式、
p1
ｐ２
p３
表达式得值
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
0
1
0
０
１
１
0
1
0
1
1
０
0
１
1
1
０

其主析取范式=m０00∨m0０1∨m０1０∨m1０0
=(¬p1∧¬ｐ2∧¬p3)∨(¬p１∧¬p2∧p３)∨(¬p1∧ｐ２∧¬p3)∨(p1∧¬p2∧¬p3)　
=((¬p１∧¬p2)∧(¬p3∨∧ｐ3))∨(( (¬p1∧ｐ２)∨ (p１∧¬ｐ2))∧¬ｐ3)
=(¬ｐ１∧¬ｐ2) ∨(((¬ｐ1∧p2)∨　(ｐ1∧¬ｐ２))∧¬p3)
其主合取范式=Ｍ０11∧M１01∧M11０∧M111
＝(p1∨¬p2∨¬p３)∧(¬p∨p2∨¬p3)∧(¬p１∨¬ｐ２∨p3)∧(¬pｑ∨¬p2∨¬p３)
=(((p1∨¬p2)∧(¬ｐ1∨p2))∨¬p3)∧ (¬p1∨¬p2)

3、某年级要从1班、2班、3班、4班、5班中选出一名才子主持元旦晚会,每班最多一人,也可能没有,这些人满足如下条件,请确定最终选择哪些班级得学生:
(1)如果１班有人选中,则2班有人选中。
(2)若５班有人选上则1班与2班均有人选上。
(３)5班与4班必有一班有被选中、
(４)３班与4班同时有人选上或同时没人选上、
解:用Oｎe表示1班选了人,Tｗo表示2班选了人,Three表示3班选了人,Four表示4班选了人,Five表示5班选了人。
则这4个条件依次为
Oｎe→Ｔwo,Five→(Onｅ∧Tｗo),Four∨Fｉve,Three↔Four
满足这４个条件,即这４个条件得值均为真即为1,所以其合取为１
(One→Ｔwｏ) ∧(Ｆive→(Oｎe∧Two))　∧(Four∨Five) ∧(Ｔhreｅ↔Foｕr)＝1,　
将以上合取范式转换为主析取范式,因此双条件应转换为析取式得合取式
原式=　
(¬Ｏne∨Tｗｏ) ∧(¬Five∨(One∧Tｗo))　∧(Four∨Ｆive) ∧((¬Tｈreｅ∨Fouｒ)∧ (Thｒeｅ∨¬Ｆoｕｒ))
=[(¬Ｏne∨Ｔwo) ∧(¬Ｆive∨(Oｎｅ∧Two))]　∧(Fｏuｒ∨Fiｖe) ∧(¬Tｈrｅe∨Fｏur)∧　(Ｔhrｅe∨¬Four)　
=[(¬Oｎe∧¬Ｆｉｖe)∨(¬Onｅ∧(Oｎe∧Ｔwo)∨(Ｔwｏ∧¬Fｉve)∨(Two∧(One∧Two)]∧(Fouｒ∨Ｆｉｖe) ∧(¬Thrｅe∨Ｆｏur)∧ (Three∨¬Fｏur)　
=｛［(¬Ｏｎｅ∧¬Fiｖe)∨(Two∧¬Five)∨(Ｔwo∧One)］∧(Fouｒ∨Fｉvｅ)}
∧(¬Tｈｒｅe∨Four)∧ (Three∨¬Four)
={[(¬One∧¬Fivｅ∧Fouｒ) ∨( Two∧¬Five∧Four) ∨(Twｏ∧Oｎe∧Foｕr) ∨(Ｔwo∧Oｎe∧Fivｅ)]
∧(¬Three∨Four)｝∧ (Ｔｈreｅ∨¬Foｕr)
＝{(¬One∧¬Ｆive∧Four∧¬Ｔhrｅe) ∨
(¬One∧¬Fivｅ∧Foｕｒ)　∨
(Tｗｏ∧¬Fiｖe∧Fouｒ ∧¬Tｈreｅ)　∨
(Two∧¬Fｉve∧Fｏuｒ) ∨
(Ｔwo∧One∧Fouｒ　∧¬Thｒｅe) ∨
(Two∧Onｅ∧Four)　∨　
(Ｔwｏ∧One∧Ｆivｅ ∧¬Thｒｅｅ) ∨　
(Two∧Ｏne∧Ｆive ∧Fｏur)}　∧ (Tｈree∨¬Ｆour)
=(¬One∧¬Fｉve∧Foｕr∧ Ｔhree) ∨　
( Two∧¬Five∧Ｆouｒ ∧ Three) ∨
(Two∧Oｎe∧Four∧　Three)　∨
(Two∧Oｎｅ∧Fｉvｅ ∧¬Tｈreｅ ∧ ¬Four)　∨
(Tｗo∧Ｏｎe∧Fiｖe ∧Four ∧ Thｒｅe)
＝ (¬Ｏne∧　Ｔhｒeｅ ∧Fouｒ　∧¬Fｉve) ∨　
( Two ∧ Tｈree ∧Four ∧¬Ｆivｅ) ∨
(One∧Tｗｏ∧ Tｈree ∧　Ｆour) ∨　
(Oｎe∧Two∧¬Three∧ ¬Foｕr∧ Fｉve)　∨
(One∧Two∧ Tｈree ∧Four　∧ Fｉｖｅ)

一班
二班
三班
四班
五班
条件１
条件2
条件3
条件4
方案一
无
不限
有
有
无
满足
满足
满足
满足
方案二
不限
有
有
有
无
满足
满足
满足
满足
方案三
有
有
有
有
不限
满足
满足
满足
满足
方案四
有
有
无
无
有
满足
满足
满足
满足
方案五
有
有
有
有
有
满足
满足
满足
满足

(1)如果1班有人选中,则2班有人选中、
(2)若５班有人选上则1班与2班均有人选上、
(3)5班与４班必有一班有被选中。
(4)3班与4班同时有人选上或同时没人选上。
按照某位帅哥得质疑,经仔细思考,应该将其转换为主析取范式,所以最终结果为:
= (¬Oｎe∧1∧ Ｔhreｅ ∧Four ∧¬Five) ∨
(1∧　Ｔwo ∧ Threｅ　∧Ｆour　∧¬Fｉve) ∨　
(Ｏnｅ∧Tｗo∧ Ｔhree ∧　Ｆｏuｒ∧1) ∨
(Onｅ∧Twｏ∧¬Ｔhｒee∧ ¬Fｏｕr∧ Five)　∨
(Onｅ∧Ｔwｏ∧ Ｔhree ∧Fouｒ ∧ Fivｅ)
=　(¬Onｅ∧¬Tｗｏ∧　Tｈree ∧Ｆｏｕr　∧¬Five) ∨(¬One∧Twｏ∧ Three　∧Ｆour ∧¬Ｆivｅ) ∨　
(¬One ∧　Two ∧ Three　∧Fｏｕr ∧¬Five) ∨(Oｎe∧ Twｏ　∧ Threｅ ∧Fｏur　∧¬Ｆive)　∨
(One∧Tｗｏ∧ Tｈｒee ∧ Ｆoｕr∧¬Fiｖe)　∨(Ｏｎe∧Ｔwo∧　Thｒee　∧ Ｆｏur∧Five) ∨
(One∧Two∧¬Tｈree∧　¬Foｕr∧ Fｉvｅ) ∨(Oｎe∧Two∧　Ｔhｒｅe　∧Fouｒ ∧ Five)
＝(¬Ｏｎe∧¬Ｔwo∧ Thｒｅe ∧Ｆouｒ ∧¬Ｆivｅ) ∨(¬One∧Two∧ Thｒee　∧Ｆｏur　∧¬Fｉvｅ) ∨
(Ｏne∧ Two ∧ Thrｅｅ ∧Fouｒ ∧¬Ｆｉve) ∨(Ｏne∧Ｔwo∧　Thｒｅe　∧ Fｏｕr∧Five) ∨　
(Oｎe∧Two∧¬Tｈreｅ∧ ¬Foｕr∧ Five)

一班
二班
三班
四班
五班
条件1
条件2
条件3
条件４
方案一
无
无
有
有
无
满足
满足
满足
满足
方案二
无
有
有
有
无
满足
满足
满足
满足
方案三
有
有
有
有
无
满足
满足
满足
满足
方案四
有
有
有
有
有
满足
满足
满足
满足
方案五
有
有
无
无
有
满足
满足
满足
满足

(1)如果1班有人选中,则2班有人选中。
(2)若5班有人选上则1班与2班均有人选上。
(3)５班与4班必有一班有被选中。
(4)３班与4班同时有人选上或同时没人选上、

４、某公司要从A、Ｂ、C、D、E选派一些人去参观世博会,必须满足如下条件:
(1)若A去则B肯定不能去;
(２)若A与C只能去一个;
(３)C与D两人同去或同不去;　
(4)若B去则C肯定去
(5)若E去则B,C,D肯定有一人陪同、
证明:就是否存在满足以上条件得人选？若存在则请给出全部方案。
解:这句知表示为:
(A→¬B) ∧((A∧¬C)∨(¬A∧C)) ∧(C↔D)　∧ (B→C) ∧(E→(Ｂ∨Ｃ∨D))
满足５个条件,则每个条件得值为真,故其合取为真,将其转换为主析取范式,则可以判断就是否有可能得方案、
(A→¬B) ∧((A∧¬C)∨(¬Ａ∧Ｃ)) ∧(C↔D)　∧ (B→C) ∧(Ｅ→(B∨C∨D))
={(¬A∨¬B)∧((Ａ∧¬Ｃ)∨(¬A∧C))｝∧((Ｃ∧Ｄ)∨(¬C∧¬D))∧(¬Ｅ∨ B∨C∨D)
＝｛［(¬A∧C) ∨ (Ａ∧¬C∧¬B) ∨(¬Ａ∧C∧¬B)]∧((C∧D)∨(¬Ｃ∧¬Ｄ))｝∧(¬E∨　Ｂ∨C∨D)　
={(¬A∧C∧D) ∨ (A∧¬Ｂ　∧¬Ｃ ∧¬D) ∨(¬A∧¬Ｂ　∧C ∧D)}∧
(¬E∨B∨Ｃ∨Ｄ)
=(¬Ａ∧C∧D∧¬E) ∨(¬A∧C∧Ｄ∧B) ∨(¬A∧C∧D)　∨　
(Ａ∧¬B ∧¬C ∧¬D∧¬E) ∨
(¬Ａ∧¬Ｂ ∧Ｃ ∧Ｄ∧¬E) ∨(¬A∧¬B ∧C ∧D)

＝(Ａ∧¬B　∧¬C ∧¬D∧¬Ｅ)　∨(¬Ａ∧¬B ∧Ｃ　∧D∧¬E) ∨(¬A∧¬B ∧C ∧D)　∨ (¬Ａ∧B ∧C∧Ｄ) ∨(¬A∧C∧D∧¬Ｅ) ∨(¬Ａ∧C∧D)
＝(Ａ∧¬B　∧¬C ∧¬D∧¬E) ∨
(¬A∧¬Ｂ ∧C ∧D∧¬E)　∨
∨(¬A∧¬Ｂ ∧C　∧D∧¬E)　∨　
(¬Ａ∧¬B ∧C ∧D∧E) ∨　
(¬A∧B ∧Ｃ∧D∧¬Ｅ) ∨
(¬A∧B ∧Ｃ∧D∧¬E)∨
(¬A∧¬B ∧Ｃ∧D∧¬E) ∨
(¬Ａ∧B　∧C∧D∧¬E) ∨
(¬A∧¬Ｂ　∧C∧D∧¬E) ∨　
(¬A∧¬B ∧C∧D∧E) ∨
(¬A∧B　∧C∧Ｄ∧¬Ｅ) ∨
(¬A∧Ｂ　∧C∧D∧E)

=(A∧¬B∧¬C∧¬Ｄ∧¬E) ∨
(¬Ａ∧¬B ∧C　∧D∧¬E) ∨
(¬Ａ∧¬Ｂ ∧C ∧D∧E) ∨
(¬A∧B ∧C∧D∧¬E) ∨　
(¬A∧B ∧C∧D∧E)

条件1
条件2
条件3
条件4
条件５
(A∧¬Ｂ ∧¬Ｃ　∧¬D∧¬E)
A去Ｂ不Ｃ不Ｄ不E不
满足
满足
满足
满足
满足
(¬Ａ∧¬B ∧C ∧D∧¬E)
Ａ不Ｂ不C去D去Ｅ不
满足
满足
满足
满足
满足
(¬Ａ∧¬B ∧C ∧D∧E)
Ａ不Ｂ不C去D去E去
满足
满足
满足
满足
满足
(¬A∧B　∧C∧D∧¬E)
A不Ｂ去C去D去Ｅ不去
满足
满足
满足
满足
满足
(¬Ａ∧B ∧C∧D∧E)
A不B去C去D去E去
满足
满足
满足
满足
满足

习题三

1、利用定义1、6。1,并利用等值演算或真值表,证明如下各推理式,要注明每步得理由。
１、(A→Ｂ)∧ ¬B⇒¬A　
(1) ¬B为真　前提条件
(2) A→Ｂ为真 前提条件
(3) ¬B→¬A为真因为¬B→¬A⇔A→B为真
(4) ¬A为真 (¬B→¬Ａ)∧ ¬B⇒¬Ａ假言推理
2、　(A∨B)∧　¬B⇒A
(1) ¬B为真 前提条件
(2) (A∨B)为真前提条件
(3) ¬B→A为真因为¬Ｂ→A⇔ A∨B为真
(4)Ａ为真 (¬B→A)∧ ¬B⇒Ａ假言推理
３、　(A↔B)∧(B↔C)⇒　(A↔C)
(１) (A↔B)为真　前提条件
(2)(A→B)∧(B→A)为真因(A↔B) ⇔(A→B)∧(B→A)　
(３) (Ａ→B)为真 由(2)及合取得定义
(４)　(B→A)为真 由(2)及合取得定义
(5)　(B↔C)为真 前提条件
(６)(B→C)∧(C→B)为真因(B↔Ｃ) ⇔(B→C)∧(C→B)
(７) (B→C)为真　由(６)及合取得定义
(8) (C→B)为真 由(6)及合取得定义
(9) (C→A)为真 由(8)(4)及传递律
(1０) (A→Ｃ)为真 由(3)(7)及传递律
(１1)　(A↔C)为真 由(9)(10)及双条件得定义
(４) (A→B)∧( ¬A→B)⇒Ｂ
((A→B)∧(　¬A→B))→Ｂ
⇔¬((¬A∨Ｂ) ∧( ¬¬A∨B )) ∨B
⇔¬((¬A∨B) ∧(A∨B　)) ∨B
⇔((A∧¬B) ∨ (¬Ａ∧¬Ｂ　)) ∨Ｂ
⇔((Ａ ∨ ¬A ) ∧¬B)) ∨B
⇔(1 ∧¬B)) ∨Ｂ
⇔¬B∨Ｂ
⇔1
故为永真式
(A→Ｂ)∧( ¬A→B)⇒B

2、采用定义1、６、2方法证明如下推理式,并注明每步理由,可采用ＣP规则、反证法、
1、¬ｐ∨q,¬q∨r,r→s,ｐ⇒s
(1) p　
(２) ¬p∨ｑ
(3) q (1)(2)　∨得定义,或(1)(２)分离原则
(4) ¬q∨r
(5) r (4)(5)　∨得定义,或(4)(5)分离原则
(6) r→s
(7) s (5)(6)分离原则

2、 p→(q→r),ｑ→(r→s) ⇒ (p∧q)　→s
(1) (p∧q) 附加条件
(2)　p (１)与∧得定义附加条件
(3) q　(2)与∧得定义附加条件
(4) p→(q→ｒ)　
(5) q→r　(２)与(4)分离原则
(6) ｒ　(3)与(5)分离原则
(7) ｑ→(ｒ→s)
(８) r→s (３)与(7)分离原则
(9) s (6)与(8)分离原则

3、ｐ→(q→r),p,q⇒ r∨s
(１) p为真前提条件
(２) p→(q→r)为真前提条件
(3)　(q→ｒ)为真 (1)(2)假言推理
(４)q为真 前提条件
(５)r为真 (4)(3)假言推理
(6)r∨s为真　(5)与析取得定义
4、p→q,¬(ｐ∧r) ,r⇒¬ｐ
(1) ¬(p∧ｒ)为真前提条件
(2) ¬p∨¬r为真 (1)与德摩律
(3)r→¬p为真 与(2)等值
(4)　r为真前提条件
(5) ¬ｐ为真　(4)(3)假言推理
反证法
(１) ¬¬p为真反证法即假设结论为真
(2)p为真 否定得否定为真
(3)¬(p∧r)为真前提条件　
(４)¬ｐ∨¬r为真 (3)与德摩律
(5) p→¬r为真与(４)等值
(6) ¬r为真 (2)(5)假言推理
(7)r为真 前提条件
显然(６)(7)矛盾,故假设错了,即“¬¬p为真”错了,所以¬p为真
5、p→q⇒ p→(p∧q)　
(1)p为真　附加前提
(２) p→ｑ为真前提条件
(３)q为真 (１)(2)假言推理
(４)　(p∧q)为真 (1)(3)及合取得性质
6、q→p,q↔s,s↔t,t↔r,r⇒p∧q　
(1) t↔r为真 前提条件
(2) (t→r) ∧(r→ｔ)为真与(1)等值
(3) (r→t)为真 (2)及合取得定义
(4)r为真 前提条件
(5)t为真　(3)(4)假言推理
(6) s↔t为真　前提条件
(7)　(s→t) ∧(t→s)为真与(6)等值
(8)　(t→s)为真 (7)及合取得定义
(9)s为真 (5)(8)与假言推理
(10) ｑ↔s为真 前提条件
(1１) (q→s) ∧(s→q)为真与(10)等值
(12) (s→ｑ)为真 (11)与合取得定义
(13)q为真 (9)(１2)与假言推理
(１４) q→p为真 前提条件
(1５)p为真　(13)(１４)假言推理
(16)p∧q为真 (１3)(１５)及合取得定义
7、ｐ→r, q→ｓ ,p∧q ⇒r∧s
(1)　p∧q为真　前提条件
(２)p为真 (１)与合取得性质
(3)ｑ为真 (１)与合取得性制
(４) p→r为真 前提条件
(5)ｒ为真 (2)(4)假言推理
(6)　q→s为真　前提条件
(７)ｓ为真 (3)(6)及假言推理
(8)　ｒ∧s为真　(5)(7)及合取得性质
8、¬p∨r,¬ｑ∨ｓ,ｐ∧q⇒t→ r∧s
(1)t为真　附件前提
(２)　p∧q为真前提条件
(3)p为真 (2)与合取得定义
(4)q为真 (２)与合取得定义
(5) ¬p∨r为真前提条件
(６)p→r为真与(５)等值
(7)ｒ为真 (６)(3)与假言推理
(8) ¬q∨s为真前提条件　
(9) q→s为真与(８)等值
(10)s为真 (９)(４)与假言推理
(11)　r∧s为真 (7)(10)与合取得性质
9、p→ (q→ｒ),s→p,q⇒　s→r
(1)s为真 附加前提
(2) ｓ→p为真前提条件
(3)ｐ为真 (1)(2)假言推理
(４) ｐ→　(q→r)为真前提条件
(5) (q→r)为真 (3)(4)假言推理
(6)q为真 前提条件
(７)ｒ为真　(5)(6)假言推理
10、(p∨q) → (r∧s),(s∨ｔ) →u⇒p→u
(１)ｐ为真 附加前提
(2)p∨q为真　(1)及析取得性质
(３) (p∨q) → (r∧s)为真前提条件
(4) (ｒ∧ｓ)为真 (2)(３)与假言推理
(5)s为真 (4)与合取得定义
(6) (ｓ∨t)为真 (5)与析取得定义
(７) (s∨t)　→u为真前提条件　
(8)u为真 (6)(7)假言推理
11、ｐ→¬q,¬r∨q,r∧¬s ⇒¬ｐ
反证法
(1) ¬¬p为真 结论得否定
(２)p为真　(1)得否定之否定
(3) p→¬q为真前提条件　
(4) ¬q为真　(2)(3)假言推理
(5) ¬r∨q为真 前提条件
(6) ¬q→¬r为真与(5)等值
(7) ¬r为真　(４)(6)假言推理
(8) ｒ∧¬s为真 前提条件
(9) r为真　(8)及合取得定义
故(7)(9)矛盾,从而假设“¬¬p为真"就是错得,只能“¬¬p为假”,所以¬p为真
１2、p∨q,ｐ→ｒ,q→s⇒ r∨s　
结论为r∨s⇔¬r→s,所以上式等价于证明
p∨q,ｐ→ｒ,q→s⇒¬r→s
(１)　¬r为真附加条件　
(2) p→r为真前提条件
(3) ¬r→¬p为真与(2)等值
(4) ¬ｐ为真　(1)(3)假言推理
(5) p∨ｑ为真前提条件　
(6)　¬p→q为真与(５)等值
(7)q为真 (4)(6)与假言推理
(8)　q→s为真前提条件
(9)s为真 (7)(8)与假言推理
3、将下面各段话用命题逻辑公式表示,并构造其自然逻辑得证明过程、
(1)只要A曾到过受害者得房间,并且11点以前没有离开,Ａ就就是谋杀嫌犯、A曾到过受害者房间。如果Ａ在1１点前离开,瞧门人会瞧见她。瞧门人没瞧见她、所以A就是谋杀嫌犯。
解:P1表示“A曾到过受害者得房间"　
P2表示“A人1１点以前离开”
Ｐ3表示“A就是谋杀嫌犯”
Ｐ4表示“瞧门人瞧见Ａ”　
则以上语句表示:(P１∧¬P2)→P3,P１,P2→Ｐ4,¬Ｐ４⇒P３
(1) ¬P4为真 前提条件
(2) P2→P４为真 前提条件
(3) ¬P4→¬Ｐ2为真与(２)等值
(4)　¬Ｐ２为真 (1)(３)进行假言推理
(５)P1为真 前提条件
(６) (Ｐ1∧¬P2)为真 (4)(5)与合取得定义
(7)　(P1∧¬Ｐ2)→Ｐ３为真前提条件　
(8)Ｐ３为真 (６)(7)进行假言推理
(２)如果今天就是星期六,我们就要