离散07—08期末考试题(B卷).pdf

良辰美景奈何天，便赏心乐事谁家院。则为你如花美眷，似水流年。——《汤显祖》 四川大学期末考试试题（闭卷B） （2007-2008 学年第1 学期） 1．下列命题公式是永真式的是（ ） A．（P∧～P）↔Q B．（～（P→Q）∧Q）→Q C．（P→Q）∨Q D．（P∨P）∧（P→～P） 2．命题公式A 不存在主合取范式，则A 是 （ ） A．矛盾式 B．可满足式 C．永真式 D．都不对 3．谓词公式（x）P （X ）→（x）P（X）是（ ） A．可满足式 B．矛盾式 C．无法判别 D．永真式 4．公式（x）（y）（P（x,y）∧Q（z））→R（x） 中的x （ ） A．仅是约束变元 B．仅是自由变元 C．既是约束变元又是自由变元 D．既不是约束变元也不是自由变元 5．设S={I，Q，R} ，下列命题哪个正确 （ ） A．IQ，QR 则IR B．-1∈I，I∈S则-1∈S C．D．都不正确 6．下面的表达哪个不正确 （ ） A．{a}{{a}} B．{a}∈{{a}} C．{a}{a，{a}} D．{a}∈{a，{a}} 7．若集合A 中共有n 个元素，那么A 上不同二元关系的个数为 （ ） 2 2 2 A．n B． n C． n -1 D．都不对 2 2 8．下列判断正确的是 （ ） A．若R，S 是自反的，则R-S 是自反的 B．若R，S 是对称的，则R○S 是对称的 C．若R，S 是传递的，则R∩S 是传递的 D．若R，S 是传递的，则R ∪S 是传递的 9．设R，S 是非空集合上的等价关系，则R ∪S 是（ ） A．一定具有自反性，但不一定保持对称性 B．一定具有对称性，但不一定保持自反性 C．一定具有自反性和对称性 D．是等价关系 10．在5 个元素的集合上可以定义的单射数目为 （ ） A．5 B．10 C．60 D．120 11．设函数f：X→Y；X，Y是有限集合， f 是单射，那么下列关系一定不成立的是 （ ） A．|X|=|Y| B．|X|﹥|Y| C．|X|﹤|Y| D．X ∈Y 12．平面非连通图 G，n-m+f 的值为 （ ） A．2 B．ω （G） C．ω （G）+1 D．3 13．若一棵树 G （n，n-1 ）只有两个叶节点，则 （ ）不正确 A．不包含点度大于等于 3 的枝点 B．节点总度数大于等于 4 C．最少包含 2 个节点 D．节点总度数=2+2 （n-2 ） 注：试题字迹务必清晰，书写工整。 本题6页，本页为第1页 老当益壮，宁移白首之心；穷且益坚，不坠青云之志。——唐·王勃 教务处试题编号： 宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。——《洪应明》 课程名称： 任课教师： 学号： 姓名： 14．设10 阶简单连通图有32 条边，则最少要去掉 （ ）条边才能使其成为平面图 A．10 B．12 C．32 D．8 15．下列代数系统，（ ）是群 A．〈S1={1，1/2，2，1/3，1/4，4}，*：为普通乘法〉 B．〈S2={ai | ai ∈R，i=1，2，3…n}，o：ai，aj ∈S2→ aioaj=ai〉 C．〈S3={0，1}，*：为普通乘法〉 D．〈S4={-1，1}，+：为普通加法〉 二、多项选择题（本大题共5 小题，每小题2 分，共10 分 ）在每小题列出的五个备选项中有二个至五个是符合题 目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。 1.设A＝{1,2,3}，则右图所示A上的关系具有（ ）。