离散数学题目及答案.doc
数理逻辑习题判断题1任何命题公式存在惟一的特异析取范式 （ ）2 公式是永真式 （ ）3命题公式是永真式 （ ）4命题公式的成真赋值为010 （ × ）5 （ ）6命题“如果123，则雪是黑的”是真命题 （ × ）7 （ ）8是永真式 （ × ）9“我正在撒谎”是命题 （ × ）10 是永真式（ ）11命题“如果120，则雪是黑的”是假命题 （ × ）12 （ ）13是永假式 （ × ）14每个命题公式都有唯一的特异（主）合取范式 （ ）15若，则是永真式 （ ）16每个逻辑公式都有唯一的前束范式 （ × ）17的特异（主）析取式为 （ × ）18命题公式 的成假赋值是110 （ ）19一阶逻辑公式是闭式（ × ）单项选择题1 下述不是命题的是（ A ） A 花儿真美啊! B 明天是阴天。 C 2是偶数。 D 铅球是方的。2谓词公式（y）（x）（P（x）R（x,y）yQ（x,y）中变元y （ B） A 是自由变元但不是约束变元B 是约束变元但不是自由变元 C 既是自由变元又是约束变元D 既不是自由变元又不是约束变元3下列命题公式为重言式的是（ A ）Ap （pq）B（pp）qCqqDpq4 下列语句中不是命题的只有（ A ）A花儿为什么这样红？B2+2=0C飞碟来自地球外的星球。D凡石头都可练成金。5在公式中变元y是（ B ）A自由变元B约束变元C既是自由变元，又是约束变元D既不是自由变元，又不是约束变元6下列命题公式为重言式的是（ A ）Ap （pq）B（pp）qCqqDqp7给定如下4个语句: （1）我不会唱歌。 （2）如果天不下雨,我就上街。 （3）我每天都要上课。 （4）火星上有人吗? 其中不是复合命题的是（ B ）A（1）（4） B（3）（4） C（1）（3） D（1）（3）（4） 8下列含有命题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）9设个体域为整数集,则下列公式中值为真的是（ A ）。 A （y）（x）（x·y=2） B（x）（y）（x·y=2） C （x）（xy=x） D（x）（ y）（x+y=2y）10 下述不是命题的是（ D ） A 花儿是红色的 B 月亮上有水 C 3是偶数 D 11 用P表示：天下大雨；Q表示：他乘公共汽车上班。将“如果天下大雨，他就乘公共汽车上班。”符号化正确的是（ A ）AP®Q BQ®P CPÙQ DPÚQ12谓词公式（y）（x）（P（x）R（x,y）xQ（x,y）中变元y （ C ） A 是自由变元但不是约束变元B 是约束变元但不是自由变元 C 既是自由变元又是约束变元D 既不是自由变元又不是约束变元13下列命题公式为永假式的是（ C ）Ap （pq）BpqqCqqDpq14下列语句中，不是命题的是（ C ）A 铅球不是球。B 要是他不上场，我们就不会输。C 刘翔跨110米栏用了不到13秒钟，你说他是不是运动健将呢?D 刘翔跨110米栏用了不到13秒钟，他是一个真正的运动健将。13关于命题变元P和Q的成假赋值为01对应的极大项是（ C）APQ BPQCPQ DPQ14谓词公式（y）（x）（P（x）R（x,y）yQ（x,y）中变元y （ B ） A 是自由变元但不是约束变元B 是约束变元但不是自由变元 C 既是自由变元又是约束变元D 既不是自由变元又不是约束变元15 设开关A开，：开关B开,则“开且只开A、B中一个开关”的命题公式是（ C ） A B C （）（） D （）（）16下列等价式正确的是（ C ）AABCAD17在论域D=a,b中与公式（）A（x）等价的不含存在量词的公式是（B ）A B C D 18下列命题公式为重言式的是（ C ）Ap （pq）B（pp）qCppDpq19下列命题中真值为1的是（ B ）A若2+2=4, 则3+3¹6B若2+2=4, 则3+3=6C2+2=4, 当且仅当3+3¹6D2+2¹4, 当且仅当3+3=620设个体域为整数，下列公式中真值为1的是（ B ）A "x"y（x + y = 1） B "x$y（x + y = 1）C $x"y（x + y = 1） D Ø $x$y（x + y = 121 下列命题中真值为0的是（ C ）A若2+2=5, 则3+3¹6 B若2+2=4, 则3+3=6C2+2=5, 当且仅当3+3¹6 D2+2¹4, 当且仅当3+3=622谓词公式中变元 （ C ） A 是自由变元但不是约束变元B 是约束变元但不是自由变元 C 既是自由变元又是约束变元D 既不是自由变元又不是约束变元23设个体域为整数，下列公式中真值为1的是（ B ）A "x"y（x + y = 1） B"x$y（x + y = 1）C $x"y（x + y = 1） DØ $x$y（x + y = 1填空题1个命题变元的极小项有 2n 个。2设是奇数，则的真值是 1 。3含n个命题变项的重言式的特异（主）合取范式为 1 4设个体域为整数集合Z，命题）的真值为 1 5公式xP（x）ÚxQ（x）的前束范式为 x(P(x)Q(x) 6设p：我很累，q：我去学习，命题：“我很累，但我还去学习”的符号化为 7设P表示：天下大雨；Q表示：他乘公共汽车上班，则命题“如果天下大雨，他就乘公共汽车上班。”的符号化是 8设P：2+24，Q：3是奇数,则命题“2+24，当且仅当3是奇数”的符号化为 9 含n个命题变项的矛盾式的特异（主）析取范式为 0 10命题公式成假的解释是 01,10 11的成假解释为 01,10 计算题1 求的前束范式。解： 2求的真值表，并写出它的特异（主）析取范式和特异（主）合取范式。解：真值表如下：故主析取范式为主合取范式为 3 求命题公式的成真赋值。解： = = = = 成真赋值 100，010，101，110，111 4 将公式化为前束范式。解： 5 求公式 （p（qr）（pqr） 的特异（主）析取范式，并求成真赋值。解： 成真赋值为：000，001，010，111 6 用谓词公式表示“有人喜欢吃所有的食物”。解：是人，是食物 喜欢吃 符号化： 7 用作真值表方法确定下列命题公式的类型： 解： 设原式=A，真值表如下： 则原式为永真式。 8用逻辑式表示“某些计算机与某些外部设备之间不能相联”。 解：是计算机，：为外部设备，：与相联 符号化为 9 在个体域，消去公式的量词。 解：原式 10 给定一阶逻辑公式，求该公式的前束范式。解：原式 11 用逻辑式表示“某些计算机与某些外部设备之间能相联”。解： ：是计算机，：为外部设备，：与相联 符号化为 12 用等值演算求命题公式（pq）（qr）的特异（主）析取范式，并判断该公式的类型。解：原式 公式类型为非永真的可满足式。13 设一阶逻辑公式 ，试将G化成与其等价的前束范式。解：14 设公式G的真值表如下，试求出G的特异（主）析取范式和特异（主）合取范式。p q rG0 0 010 0 100 1 010 1 111 0 001 0 111 1 001 1 10解：主析取范式 主析取范式15 求公式的前束范式。解：原式 证明题1 用等值演算证明等值式。证明： 2设是三个命题，构造下列推理证明：前提：结论：证明：3证明下列推断 前提：，结论：证明：（1） 附加前提引入 （2） 前提引入 （3） (1)（2）拒取 （4） 前提引入 （5） (3)(4)假言推理 （6） 前提引入 （7） (5)(6) 假言推理 4用构造证明法证明下列推理：前提：结论：证明： 否定结论引入 前提引入 置换 析取三段论 前提引入 简化 简化 析取三段论 合取 5 证明：。证明：左边 右边6证明公式G（PQ） （QP）P） P是永真式。证明： 1 G为永真式
