一、证明题(10分)
1) (p∧q∧ac)∧(ap∨q∨c) (a∧(pq))c。p<->q=(p->q)合取(q->p)
证明: (p∧q∧ac)∧(ap∨q∨c)
p∨q∨a∨c)∧(a∨p∨q∨c)
(p∨q∨a)∧(a∨p∨q))∨c反用分配律。
(p∧q∧a)∨(a∧p∧q))∨c
a∧((p∧q)∨(p∧q)))c再反用分配律。
a∧(pq))∨c
a∧(pq))c
2) (pq) pq。
证明:(pq)((p∧q))(p∨q))pq。
2、分别用真值表法和公式法求(p(q∨r))∧p∨(qr))的主析取范式与主合取范式,并写出其相应的成真赋值和成假赋值(15分)。
主析取范式与析取范式的区别:主析取范式里每个括号里都必须有全部的变元。
主析取范式可由析取范式经等值演算法算得。
证明:公式法:因为(p(q∨r))∧p∨(qr))
p∨q∨r)∧(p∨(q∧r)∨(q∧r))
p∨q∨r)∧(p∨q)∧(p∨r))∨q∧r))分配律。
p∨q∨r)∧(p∨q∨q)∧(p∨q∨r)∧(p∨r∨q)∧(p∨r∨r)
p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)
∧使(非p析取q析取r)为0所赋真值,即100,二进制为4
所以,公式(p(q∨r))∧p∨(qr))为可满足式,其相应的成真赋值为:成假赋值为。
真值表法:由真值表可知,公式(p(q∨r))∧p∨(qr))为可满足式,其相应的成真赋值为:成假赋值为。
三、推理证明题(10分)
1)p∨q,q∨r,rsps。
证明:1)p附加前提。
2)p∨qp
3)qt(1)(2),i(析取三段论)
4)q∨rp
5)rt(3)(4),i(析取三段论)
6)rsp7)st(5)(6),i(假言推理)
8)pscp
2) x(p(x)q(y)∧r(x)),xp(x)q(y)∧x(p(x)∧r(x))
证明(1)xp(x)
2)p(a)
3)x(p(x)q(y)∧r(x))
4)p(a)q(y)∧r(a)
5)q(y)∧r(a)
6)q(y)
7)r(a)
8)p(a)
9)p(a)∧r(a)
10)x(p(x)∧r(x))
11)q(y)∧x(p(x)∧r(x))
五、已知a、b、c是三个集合,证明(a∪b)-c=(a-c)∪(b-c) (10分)
证明:因为。
(a∪b)-c∈(a∪b)-c
(a∪b)∧c
∈a∨∈b)∧c
∈a∧c)∨(b∧c)
(a-c)∨∈b-c)
(a-c)∪(b-c)
所以,(a∪b)-c=(a-c)∪(b-c)。
八、证明整数集i上的模m同余关系r=是等价关系。其中,xy(mod m)的含义是x-y可以被m整除(15分)。x(modm)=y(modm)
证明:1)x∈i,因为(x-x)/m=0,所以xx(mod m),即xrx。
2)x,y∈i,若xry,则xy(mod m),即(x-y)/m=k∈i,所以(y - x)/m=-k∈i,所以yx(mod m),即yrx。
3)x,y,z∈i,若xry,yrz,则(x-y)/m=u∈i,(y-z)/m=v∈i,于是(x-z)/m=(x-y+y-z)/m=u+v ∈i,因此xrz。
九、若f:a→b和g:b→c是双射,则(gf)-1=f-1g-1(10分)。
证明:因为f、g是双射,所以gf:a→c是双射,所以gf有逆函数(gf)-1:c→a。同理可推f-1g-1:c→a是双射。
因为∈f-1g-1存在z(∈g-1∈f-1)存在z(∈f∈g)∈gf∈(gf)-1,所以(gf)-1=f-1g-1。
一、证明题(10分)
1)((p∨q)∧(p∧(q∨r)))p∧q)∨(p∧r)t
证明: 左端((p∨q)∧(p∨(q∧r)))p∨q)∧(p∨r))(摩根律)
((p∨q)∧(p∨q)∧(p∨r))∨p∨q)∧(p∨r))(分配律)
((p∨q)∧(p∨r))∨p∨q)∧(p∨r)) 等幂律)
t (代入)
2) xy(p(x)q(y))(xp(x)yq(y))
证明:xy(p(x)q(y))xy(p(x)∨q(y))
x(p(x)∨yq(y))
xp(x)∨yq(y)
xp(x)∨yq(y)
xp(x)yq(y))
二、求命题公式(pq)(p∨q) 的主析取范式和主合取范式(10分)
解:(pq)(p∨q)(pq)∨(p∨q)
p∨q)∨(p∨q)
p∧q)∨(p∨q)
p∨p∨q)∧(q∨p∨q)
p∨q)m1析取要使之为假,即赋真值001,即m1
m0∨m2∨m3使之为真。
三、推理证明题(10分)
1)(p(qs))∧r∨p)∧qrs
证明:(1)r
2)r∨pp
3)pt(1)(2)析取三段论。
4)p(qsp
5)qst(3)(4)i假言推理。
6)qp7)st(5)(6)i假言推理。
8)rscp
2) x(a(x)yb(y)),x(b(x)yc(y)) xa(x)yc(y)。
证明:(1)x(a(x)yb(yp
(2)a(a)yb(yt(1)es
3)x(b(x)yc(yp
4)x(b(x)ct(3)es
5)b()ct(4)us
6)a(a)bt(2)us
7)a(a)ct(5)(6)i假言三段论。
8)xa(x)ct(7)ug
9)xa(x)yc(yt(8)eg
四、只要今天天气不好,就一定有考生不能提前进入考场,当且仅当所有考生提前进入考场,考试才能准时进行。所以,如果考试准时进行,那么天气就好(15分)。
解 :设p:今天天气好,q:考试准时进行,a(e):e提前进入考场,个体域:考生的集合,则命题可符号化为:pxa(x),xa(x)qqp。
1)pxa(xp
2)pxa(xt(1)e
3)xa(x)pt(2)e
4)xa(x)qp
5)(xa(x)q)∧(qxa(xt(4)e
6)qxa(xt(5)i
7)qpt(6)(3)i
五、已知a、b、c是三个集合,证明a∩(b∪c)=(a∩b)∪(a∩c) (10分)
证明: x a∩(b∪c) x a∧x(b∪c) x a∧(xb∨xc)( x a∧ xb)∨(x a∧xc) x(a∩b)∨x a∩c x(a∩b)∪(a∩c)∴ab∪c)=(a∩b)∪(a∩c)
六、a=,b=,r=,求其关系矩阵及关系图(10分)。有就是1,没就是0
七、设r=,求r(r)、s(r)和t(r),并作出它们及r的关系图(15分)。
r(r)=(自反闭包)
s(r)=(对称闭包)
t(r)=(传递闭包)
九、设f:ab,g:bc,h:ca,证明:如果hgf=ia,fhg=ib,gfh=ic,则f、g、h均为双射,并求出f-1、g-1和h-1(10分)。
解因ia恒等函数,由hgf=ia可得f是单射,h是满射;因ib恒等函数,由fhg=ib可得g是单射,f是满射;因ic恒等函数,由gfh=ic可得h是单射,g是满射。从而f、g、h均为双射。
由hgf=ia,得f-1=hg;由fhg=ib,得g-1=fh;由gfh=ic,得h-1=gf。
离散数学考试题
一 选择题 10 2 1.设l x x是演员,j y y是老师,a x,y x佩服y.那么命题 所有演员都佩服某些老师 符号化为 ab c d 2.令f x x是有理数,g x x是实数。将命题 所有的有理数都是实数,但有的有实数不是有理数 符号化为 3 设r是集合a 上的二元关系,r 则r具有关系...
离散数学考试试题a
一。8分 求与公式 x2 or not x1 x3 逻辑等值的主合取范式和主析取范式。二。8分 判断下列各公式是 1.永真式 2.永假式 3.其它。1 p q r q p r 2 not p or q p and p and q 3 not p or q and not q or not r and...
离散数学考试试题
天水师范学院 2012 2013学年第1学期。数统学院数应专业 10级 离散数学 考试试题。注 可参考笔记与课本。一 20分 一个排队线路,输入a,b,c,输出fa,fb,fc.本线路在同一时间只能有一个信号通过,若同时。有两个或两个以上信号申请输出时,则按a,b,c的顺序输出,写出fa,fb,fc...