PDF《离散数学作业 Problem set 3》

离散数学作业 Problem set

3 Problem

1 令P(x) 为"x 会说俄语",令Q(x) 为"x 懂计算机语言 C++".

使用 P(x), Q(x),量词和逻辑连接词表示下面的句子.其中量词域由所在学校的所有 学生组成. a) 存在一个学生既会说俄语又懂 C++. b) 存在一个学生会说俄语但不懂 C++. c) 每个学生要么会说俄语要么懂 C++. d) 没有一个学生会说俄语或者懂 C++. Problem

2 令Q(x) 表示"x = x2 ".如果变量的论域为整数集合,判断下列各语句的真 值. a) P(0) d) P(?1) b) P(1) e) ?xP(x) c) P(2) f) ?xP(x)

1 2 Problem

3 假设命题函数 P(x) 的定义域为 {?5, ?3, ?1, 1, 3, 5}.使用"来 代替量词表达下列语句. a) ?xP(x) c) ?x((x ?= 1) → P(x)) e) ?x(?P(x))∧?x((x < 0) → P(x)) b) ?xP(x) d) ?x((x ≥ 0) ∧ P(x)) Problem

4 使用谓词、量词和逻辑连接词将下列语句转换为逻辑表达式. a) 有些命题是重言式 b) 矛盾式的否定是重言式 c) 两个可能式的析取可能是重言式 d) 两个重言式的合取是重言式 Problem

5 证明下列逻辑等价式,其中 x 在A中不作为自由变元出现.假设论域非空. a) (?xP(x)) ∨ A ≡ ?x(P(x) ∨ A) b) (?xP(x)) ∨ A ≡ ?x(P(x) ∨ A) Problem

6 下列语句的真值是什么?

3 a) ? !xP(x) → ? xP(x) b) ? xP(x) → ? !xP(x) c) ? !x?P(x) → ?? xP(x) Problem

7 使用谓语、量词、逻辑联结词和数学运算符表达语句"每个正整数是四个整 数的平方和". Problem

8 假定命题函数 P(x, y) 的论域由 x 和y的序偶组成,其中 x 是

1、2 或3, y 是

1、2 或3.用析取式和合取式写出下列命题. a) ? x? y P(x, y) b) ? y? x P(x, y) Problem

9 假定个体域为所有人组成的集合,在谓词逻辑中符号化下列命题,并论证以 下推理的有效性:每个学生或是勤奋的或是聪明的,所有勤奋的人都会有所 作为,并非每个学生都有所作为,所以有些学生是聪明的.(注意论证的格 式) Problem

10 证明两个语句 ??x?yP(x, y) 和?x?y?P(x, y) 是逻辑等价的,这里两个 P(x, y) 第一个变元的量词具有相同的论域,两个 P(x, y) 第二个变元的量 词也具有相同的论域.