数理逻辑部分
选择、填空及判断
?下列语句不是命题的（ A ）。
(A) 你打算考硕士研究生吗？ (B) 太阳系以外的星球上有生物。
(C) 离散数学是计算机系的一门必修课。 (D) 雪是黑色的。
?命题公式P→(P∨?P)的类型是（ A ）
(A) 永真式(B) 矛盾式
(C) 非永真式的可满足式(D) 析取范式
?A是重言式，那么A的否定式是( A )
A. 矛盾式
B. 重言式
C. 可满足式
D.不能确定
?以下命题公式中，为永假式的是( C )
A. p→(p∨q∨r)
B. (p→┐p)→┐p
C. ┐(q→q)∧p
D. ┐(q∨┐p)→(p∧┐p)
?命题公式P→Q的成假赋值是( D )
A. 00,11
B. 00,01,11
C.10,11
D. 10
?谓词公式)
x
xP∧
?中，变元x是 ( B )
R
(
,
x
)
(y
A. 自由变元
B. 既是自由变元也是约束变元
C. 约束变元
D. 既不是自由变元也不是约束变元
?命题公式P→(Q∨?Q)的类型是( A )。
(A) 永真式 (B) 矛盾式
(C) 非永真式的可满足式 (D) 析取范式
?设B不含变元x，)
A
x→
x
?等值于( A )
)
(
(B
A. B
( D. B
?)
xA→
x
?)
(
(
? C. B
x∧
A
x
( B. )
?)
xA→
x
x∨
)
A
(
x
(B
?下列语句中是真命题的是( D )。
A．你是杰克吗？ B．凡石头都可练成金。
C．如果2+2=4，那么雪是黑的。 D．如果1+2=4，那么雪是黑的。
?从集合分类的角度看，命题公式可分为( B )
A. 永真式、矛盾式
B. 永真式、可满足式、矛盾式
C. 可满足式、矛盾式
D. 永真式、可满足式
?命题公式﹁p∨﹁q等价于( D )。
A. ﹁p∨q
B. ﹁(p∨q)
C. ﹁p∧q
D. p→﹁q
?一个公式在等价意义下，下面写法唯一的是( D )。
(A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式
?下列含有命题p，q，r的公式中，是主析取范式的是( D )。
(A) (p ∧ q ∧ r) ∨ (?p ∧ q) (B) (p ∨ q ∨ r) ∧ (?p ∧ q)
(C) (p ∨ q ∨ r) ∧ (?p ∨ q ∨ r) (D) (p ∧ q ∧ r) ∨ (?p ∧ q ∧ r)
?设个体域是整数集合，P代表?x?y((x (A) P是真命题(B) P是假命题 (C) P 是一阶逻辑公式，但不是命题 (D) P 不是一阶逻辑公式 ? 对一阶逻辑公式((,)(,))(,)x y P x y Q y z xP x y ??∧∧?的说法正确的是( B ). (A) x 是约束的，y 是约束的，z 是自由的； (B) x 是约束的，y 既是约束的又是自由的，z 是自由的； (C) x 是约束的，y 既是约束的又是自由的，z 是约束的； (D) x 是约束的，y 是约束的，z 是约束的； ? n 个命题变元可产生( D )个互不等价的布尔小项。 (A) n (B) n 2 (C) 2n (D) 2n ? 命题“没有不犯错误的人”符号化为（ D ）。 设x x M ：)(是人，x x P ：)(犯错误。 (A) ))()((x P x M x ∧? (B) )))()(((x P x M x ?→?? (C) )))()(((x P x M x ∧?? (D) )))()(((x P x M x ?∧?? ? 下列命题公式等值的是（ C ） B B A A Q P Q Q P Q B A A B A A Q P Q P ),()D (),()C ()(),()B (,)A (∧∨?∨∨?∨→→→?→→∨?∧? ? 给定命题公式：)(R Q P ∧∨，则所有可能使它成真赋值为（ B ），成假赋值为（ C ）。 (A) 111，011；000 (B) 111，011，100，101，110； (C) 000，010，001； (D) 000，110，011，001，100。 ? 给定前提：R P Q S Q P ?∨→→,,)(，则它的有效结论为：（ B ）。 (A) S ； (B) S R →； (C) P ； (D) Q R →。 ? 命题：“所有的马都比某些牛跑得快”的符号化公式为：（ C ）。 假设：)(x H ：x 是马；)(x C ：x 是牛；),(y x F ：x 比y 跑得快。 (A) ))),()(()((y x F y C y x H x ∧?∧?； (B) ))),()(()((y x F y C y x H x →?→?； (C) ))),()(()((y x F y C y x H x ∧?→?； (D) ))),()(()((y x F y C x H x y ∧→??。 ? 设P ：a 是偶数，Q ：b 是偶数.R ：a +b 是偶数，则命题“若a 是偶数，b 是偶数，则a +b 也是偶数”符号化为( C )． (A) P ∧Q ∧R (B) P ∧Q ?R (C) P ∨Q →R (D) P ∧Q →R ? 表达式))(),(())(),((z zQ y x R y z Q y x P x ?→?∧∨?中x ?的辖域是( B )． (A) P (x ,y ) (B) P (x ,y )∨Q (z ) (C)R (x ,y ) (D)P (x ,y )∧R (x ,y ) ? 判断一个语句是否为命题，首先要看它是否为陈述句，然后再看它是否有唯一的真值。 ? 命题公式(P ∨Q)→R 的只含联结词?和∧的等值式为： ))((R Q P ?∧?∧???。 ? B A B A ?∧→)(为假言推理规则。 ? 在一阶逻辑中符号化命题“有会说话的机器人。”设M(x):x 是机器人； S(x):x 是会说话 的；上述句子可符号化为： (?x)(M(x)∧S(x)) 。 ? 设p:我们爬山,q:我们划船,在命题逻辑中，命题“我们不能既爬山又划船”的符号化形式为?（p ∧q ） . ? 设p:小王走路,q:小王唱歌,在命题逻辑中，命题“小王边走路边唱歌”的符号化形式为 （p ∧q ） . ? 量词否定等值式???)(x xA )(x A x ??。 ? 设F(x):x 是人，H(x,y):x 与y 一样高，在一阶逻辑中，命题“人都不一样高”的符号化形 式为(()()(,))x y F x F y H x y ??∧→. ? 若含有n 个命题变项的公式A 是矛盾式，则A 的主合取范式含 2n 个极小项。 ? 取个体域为全体整数的集合，给出下列各公式： (1) ()()()()x y z x y z ???-= (2) ()()x xy x ?= (3) ()()(2)x y x y y ??+= 其中公式 (1) 的真值为真，公式 (3) 的真值为假。 ? 若含有n 个命题变项的公式A 是重言式，则A 的主合取范式为 1或T 。 ? 命题公式)(R Q P ∧∨的所有成假赋值为 000,001,010 。 ? 谓词公式()()xP x xQ x ?→?的前束范式为(()())x P x Q x ??∨。 ? 在一阶逻辑中，将命题“没有不能表示成分数的有理数”符号化为 ? ))()((x G x F x ?∧??或))()((x G x F x →?（设)(x F ：x 是有理数；)(x G ：x 能表示成分数。） ? 设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 A (1)∨A (2)∨( B (1)∧B (2)) . ? 设P ，Q 是两个命题，当且仅当P ，Q 的真值均为1时，Q P ?的值为1。( × ) ? 谓词公式A 是q q p ∧→?)(的代换实例，则A 是重言式。 ( × ) ? 重言式的主析取范式包含了该公式的所有的极小项。 ( √ ) ? 命题公式A →(B →C)与(A ∧B)→C 等价。 ( √ ) ? 设A ，B ，C 为命题公式，若,A B B C ??，则A C ?。 ( √ ) ? 在一阶谓词公式中，同一变元符号不能够既约束出现又自由出现。( × ) ? 在一阶逻辑中，公式的前束范式是唯一的。 ( × ) 计算 ? 求命题公式(((p ∨q)∧?p)→q)∧r 的主析取范式。 答案：m 1∨m 3∨m 5∨m 7 ? 用等值演算法求公式(())P Q R P ∨→∧?的主析取范式，并由主析取范式求主合取范式。 解：主析取范式： 013 (())()()()()()()()() P Q R P P Q R P P P Q P R P P Q R P Q R P Q R P Q R m m m ∨→∧??∨?∨∧??∧?∨?∧?∨∧???∧?∧?∨?∧?∧∨?∧?∧∨?∧∧?∨∨ 主合取范式为：24567M M M M M ∧∧∧∧ ? 求公式（P ∧Q ）∨（﹁P ∧R ）的主析取范式，并由主析取范式求主合取范式。 解：（P ∧Q （﹁P ∧﹁Q ∧R ）∨（﹁P ∧Q ∧R ）∨（P ∧Q ∧﹁R ）∨（P ∧Q ∧R ） 主合取范式为： （P ∨R ∨Q ）∧（﹁Q ∨P ∨R ）∧（﹁P ∨Q ∨R ）∧（﹁P ∨Q ∨﹁R ） ? 化公式))]},(),((),([),(){(y x B x y A y y x B y x y x yA x →?∧??→???为前束范式。 解：原式))]},(),((),([),({)(y x B x y A y y x B y x y x yA x →?∧??∨????? ))]},(),((),([),(){(y x B x y A y y x B y x y x yA x →??∨???∧??? ))]},(),((),([),(){(w u B u w A w v u B v u y x yA x →??∨???∧??? ))]},(),((),([),({w u B u w A v u B w v u y x A y x →?∨????∧??? ))]},(),((),([),({w u B u w A v u B y x A w v u y x →?∨?∧?????? （或))]},(),((),([),({w u B u w A v u B y x A w v u y x ?∧∨?∧??????） 证明 ? 构造下面推理的证明： 任何自然数都是整数；存在着自然数。所以存在着整数。个体域为实数集合R 。 证明：先将原子命题符号化：设() G x：x为整数。则 F x：x为自然数，() 前提：(()()) ?→，() x F x G x xF x ? 结论：() ? xG x ①() ?前提引入 xF x ②() F c① ES规则 ③(()()) ?→前提引入 x F x G x ④()() F c G c →③ US规则 ⑤() G c②④假言推理 ⑥() xG x ?⑤ EG规则 ?用自然推理系统中，证明下列推理： (?x)(A(x)→B(x)) ? ((?x)A(x)→(?x)B(x)) 证明： ①(?x)A(x) 附加前提引入 ②A(c) ①- ? ③(?x)(A(x)→B(x)) 前提引入 ④A(c)→B(c) ③- ? ⑤B(c) ②④假言推理 ? ⑥(?x)B(x) ⑤+ ⑦(?x)A(x)→(?x)B(x) ①⑥CP规则 ⑧t ⑤⑥假言推理 ? 在自然推理系统P 中构造下面推理的证明： 前提：q p r q p ,),(→→ 结论：s r ∨ 证明：○ 1)(r q p →→ 前提引入 ○ 2p 前提引入 ○ 3r q → ○1○2假言推理 ○ 4q 前提引入 ○ 5r ○3○4假言推理 ○ 6s r ∨ ○5附加律 ? 判断下面推理是否正确，并证明你的结论。 如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。 解： 设p:小王今天家里有事，q:小王来开会，r:小张今天看到小王 本题推理的形式结构是： 前提：p q →?,r q →,r 所以 (?x)(A(x)→B(x)) ? ((?x)A(x)→(?x)B(x)) ? 判断下面推理是否正确，并证明你的结论。 如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI 语言而且学过C++语言。只要他学过DELPHI 语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。 证明：令p ：他是计算机系本科生 q ：他是计算机系研究生 r ：他学过DELPHI 语言 s:他学过C++语言 t:他会编程序 前提：(p ∨q)→(r ∧s),(r ∨s)→t 结论：p →t 证①p 附加前提 ②p ∨q ①附加律 ③(p ∨q)→(r ∧s) 前提引入 ④r ∧s ②③假言推理 ⑤r ④化简律 ⑥r ∨s ⑤附加律 ⑦(r ∨s)→t 前提引入 结论：p ? 证明：1. r q → 前提引入 2. r 前提引入 3. q 1,2假言推理 4. p q →? 前提引入 5. p ? 3,4拒取式 集合论部分 选择、填空及判断 ? 设集合A ={1,2,3,4},B ＝{2,4,6,9}，那么集合A ，B 的对称差A ⊕B ＝（ C ）. (A) {1,3} (B) {2,4,6} (C) {1,3,6,9} (D) {1,2,3,4,6,9} ? 集合A = { 1 , 2 , 3 , 6 }，A 上的小于等于关系具有的性质是 （ D ）。 (A) 自反的，对称的，传递的； (B) 反自反的，对称的，传递的； (C) 反自反的，反对称的，传递的；(D) 自反的，反对称的，传递的。 ? 设A ={a ，b ，c }，R ={，}，则R 具有性质( C ). (A) 自反的 (B) 反自反的 (C) 反对称的 (D) 等价的 ? 设A,B,C 为任意集合，下面结论正确的是( D ) A. 如果C A B A =,则B=C B. 如果φ=-B A ,则A=B C. A A A =⊕ D. B A B A ?=- ? 设B A S ??，下列各式中( B )是正确的 A. domS ?B B. domS ?A C. ranS ?A D. domS ? ranS = S ? 令A={1,2,3,4},R={<1,2>,<3,4>,<2,2>},则s(R)=( B )。 (A){<1,2>,<3,4>,<2,2>} (B){<1,2>,<2,1>,<3,4>,<4,3>,<2,2>} (C){<1,2>,<3,4>,<1,1>,<2,2>,<3,3>} (D){<1,2>,<2,2>} ? 设A={1，2，3}，则A 上的二元关系有（ C ）个。 (A) 23 (B) 32 (C) 332? (D) 223? ? 设集合A={1,2,3,5,6,8}，A 上的二元关系R={ =( B )。 (A) {1,2} (B) {2,5,8} (C) {3,6} (D) {1} ? 偏序关系具有的性质是 ( D ) A. 自反的，对称的，传递的 B. 反自反的，对称的，传递的 C. 反自反的，反对称的，传递的 D. 自反的，反对称的，传递的 ? 等价关系具有的性质是 ( A )。 A. 自反的、对称的、传递的 B. 反自反的、对称的、传递的 C. 反自反的、反对称的、传递的 D. 自反的、反对称的、传递的
相关主题
文本预览