当前位置:文档之家› 自考离散数学第一章命题演算

自考离散数学第一章命题演算

自考离散数学第一章命题演算
自考离散数学第一章命题演算

一、命题概念(领会)

学习本章首先要深刻理解命题的概念。理解原子命题与复合命题的关系,在了解复合命题的基础上,

理解联结词的定义。

命题:具有唯一真值的陈述句称为命题,又简称语句。注意,这里有两个条件,首先它是一个陈述句,

其次,它具有唯一的一个真值。

真值:就是语句为真或假的性质。一个语句的真值可以为真也可以为假。真值不是说该语句的值必为

真。

任一命题必有其真值,也称这个命题的值。既然是命题了,那它必有一个确定的真值,不管这个真值为真还是为假。当一个陈述句能够分辩其值的真假时(也就是说,总可以肯定是其中的某一个),它就是命

题,即使我们不知道它是真还是假。

另外要理解命题常量、命题变元及指派的含义。

复合命题就是一些原子命题经过一些联结词复合而成的命题。常用的联结词有:(1)否定、(2)合取、(3)

析取、(4)条件、(5)双条件

复合命题与联系词是密切相关的,不包含联结词的命题就是原子命题,至少包含一个联结词的命题才

是复合命题。

复合命题的真值只取决于构成它们的各原子命题的真值,而与它们的内容含义无关。对联结词所联结的两原子命题之间有无关系无关。(这一条很重要,因为一个命题用自然语言表达时,我们往往会受到自然逻辑的影响,比如"我如果不上班,那么天下雨"这种命题,在自然的逻辑里,是不成立的,一个人不上班怎么会导致天下雨呢? 但是在这里,这个复合命题的值实际上是由两个原子命题的真值决定的,与它的含义无关,这个复合命题是|P->Q ,前一个原子命题的真值为假,后一命题值为真,根据条件的定义,这个复

合命题值为真)

∧、∨、←→具有对称性,|、→无对称性,(教材提示,也可用iff表示双向箭头←→,由于字符集的限制,本网页在表示否定关联词时用"|",请在书写时注意规范写法。对称性是指真值表中复合命题的真值

与原子命题的真值之间的关系。)

命题公式与命题不同,在一个由命题标识符组成的式子中,如果标识符表示确定的命题,则该式就是命题。如果标识符只表示命题的位置,可由任何命题代替,则该式子就为命题公式。命题变元P用特定命

题替代时,称为对P的指派。

不是所有由命题变元、联结词及有关括号组成的字符串都能成为命题公式。要成为一个命题公式(合式

公式),应当符合规定。这个规定是:

(1)单个命题变元本身是一个合式公式。

(2)如果A是合式公式,那么|A是合式公式。

(3)如果A和B是合式公式,那么(A∧B)、(A∨B)、(A→B)和(A←→B)都是合式公式。

(4)当且仅当有限次地应用(1)(2)(3)所得到的包含命题变元、联结词和圆括号的符号串是合式公式。

总的理解就是说,单个命题变元是合式公式,由合式公式作为命题变元,有限次地运用联结词及括号组成的符串才能是合式公式。即命题公式,简称公式。

命题变元只有进行指派后才可能确定其所在命题公式的真值。当一个命公式中的所有命题变元用一组真值指定后,就称为对命题公式的指派。想一想,什么是真指派、什么是假指派? 这个比较简单。

一个命题的真值表应该列出其所有指派的取值情况。一般来说,由n个命题变元组成的命题公式共有

2n种真值情况。

联结词的简化,按照两个等价的命题公式,可以看到一个有较多联结词的公式可以简化为含有一个联

结词的公式。这里有两个等值公式应当记一下:

(|P∨Q)<=>(P→Q)

我们要弄清什么是"重言式(永真式)"、什么是"矛盾式(永假式)"以及"可满足式"。这其中涉及到指派及

命题公式的取值,容易理解。

课本中表1.3.6列出的常用的命题公式等价定理应该记住的.

二、等价变换(简单应用)

当两个合式公式中相应变元的任一种真值指派情况下,这两个公式的真值均相同,则这两个合式公式

是等价的。可以相互置换。

有两个命题公式A、B,A<=>B,当且仅当A←→B为一重言式(永真式)。这是什么意思呢? 就是说,如果有两个命题A、B,只有在命题公式(A←→B)(双条件式)的值是永真的时候,这两个命题才是等价的。

蕴含式又称永真条件式。永真条件式更清楚地表达了它的定义,就是一个条件式P→Q,当且仅当它是重言式时,就称P蕴含Q (P=>Q)。什么时候P→Q不是蕴含式呢? 很明显,当P为真、Q为假时,它不是

一个蕴含式。

蕴含式有四个性质:

(1) 对任意公式A,有A=>A,即公式蕴含本身。

(2) 对任意公式A,B和C,若A=>B、B=>C 则A=>C。

(3) 对任意公式A,B和C,若A=>B、A=>C 则A=>(B∧C)

证明如下:

如果A的值为T,由A→B、A→C为重言式可得B为T、C为T,此时B∧C为T。

如果A的值为F,则无论B、C为T或F,A→(B∧C)为T,所以A→(B∧C)是重言式,即A=>(B∧C)。

(4) 对任意公式A,B和C,若A=>C、B=>C 则(A∨B)=>C

证明如下:

如果A的真值为T,由A→C为重言式可得C为T,此时不论B为何值,(A∨B)为T,(A∨B)->C为

T。

若B为T,由B→C为重言式可得C为T,此时不论A为何值,(A∨B)为T,(A∨B)->C为T。

若A和B均为F,则不论C为何值,(A∨B)→C为T。所以(A∨B)=>C。

设P、Q为任意两个命题公式,P<=>Q的充分必要条件是P=>Q,Q=>P.就是说,若要证明两个命题公式等价,只要证明两个公式互相蕴含。反过来,如果两个公式是互为蕴含的,那么,这两个公式是等价的。

同样,第14页的表1.4.1也应记住。

三、最小联结词组与范式:(简单应用)

通过等价变换,我们可以把带→、←→ 的公式全部化成只带{|、∧}或只带{|、∨}的命题公式,这种

只带此两种联结词的公式就是标准形式,即范式。

注意,单独的|、∧、∨及{∨、∧}都不能是命题公式的最小联结词组。只有{|、∧}、{|、∨}是命题公

式的最小联结词组。

范式根据其形式的不同又分为合取范式和析取范式。注意合取范式并不是只带|和∧的公式。它要求各个子公式均是由命题变元及其否定组成的析取式。而析取范式则恰恰相反。

由n个命题变元(不是命题公式)组成的合取式,就称为布尔合取或小项,其中每个变元与它的否定不能同时存在,但两者必须出现(其中之一)且仅出现一次。就是说每个变元或其否定必在一个小项内出现。

小项的三个性质为:

(1)每个小项具有一个相应编码,当该编码与其真实指派相同时,该小项真值为T。其余各种指派情况

下均为F。

(2)任意两个不同小项的合取式永假。因为每个小项有唯一不同的编码,当指派与一个小项的编码相同

时,必与另一个小项的编码不同,所以总有一个小项为假。

(3)全体小项的析取式为永真。因为在任一指派情况下,总有一个小项为真。

主析取范式是对应于原命题公式而言的,它是原命题公式的一个等价公式,而且仅由小项的析取所组成。那么要最直接地找到一个命题公式的主析取范式,就可以应用真值表,一个使公式真值为T的指派所

对应的小项的析取就是此公式的主析取范式。

有了小项,则有大项(布尔析取),大项与小项定义的不同之处就是把合取变成了析取。

在真值表中一个公式的值为F的指派所对应的大项的合取,即为此公式的合取范式。对于任意含有n 个命题变元的非永真命题公式A,其合取范式是唯一的。

下面我们将小项与大项作一对比,以利记忆。

小项(布尔合取) 大项(布尔析取) 定义n个命题变元的合取式n个命题变元的析取式

形式P∧Q,P∧|Q,|P∧Q,|P∧|Q,P∨Q,P∨|Q,|P∨Q,|P∨|Q,主范式命题变换得主析取范式命题变换为主合取范式

真值表法求主范

式公式真值为T的指派所对应的小项的析

公式真值为F的指派所对应的大项的合

主范式形式

m00∨m01∨m02 (Σ0,1,2...)

小项的m用小写,析取就是相当于连加

M00∧M01∧M02 (Π0,1,2..)

大项的M用大写,合取就相当于连乘

记忆变元合取是小项;

小项尖尖头朝上;

公式值真对主析;

析取小项换命题。

变元析取好大项,

大项宽宽口朝天。

公式值假对大项,

合取大项主合范。

对课本中的例题应认真学习掌握。

1.6 推理理论(简单应用)

推理就是把一些假设前提作为T,并使用一些公论的规则,得到另外的命题形成结论,这种过程很有意思,大侦探福尔摩斯就是深谙此道的人,如果我们学会了推理,那么在做一些智力题时是很有帮助的,就象是本章最后的那几道题,一般人要翻来覆去考虑很久,看看我们能不能用公式来解开它。

对于推理理论,主要要掌握的是判别有效结论的过程也就是论证过程。

有真值表法、主范式方法、等值演算法和构造论证法。其中构造论证法是本节的重点。

使用构造论证法,首先要确定推理定律及等值定律,也就是我们前面学过的定律及公式可以直接应用的,其次是要确定已知的前提,假设其值为真。推理过程就是一系列命题公式序列,其中每个命题公式或者是已知的前提,或者是由某些前提应用推理规则得到的结论。那么常用的推理规则有:

(1)P规则:前提引入规则,就是在证明的任何步骤上都可以引入前提。

(2)T规则:结论引入规则,就是在证明的任何步骤上证明的结论都可以为后续证明的前提。

(3)转换规则:也是T规则,就是可以在证明的任何步骤上进行命题公式的等值替换。

还有一个定理就是CP规则:若H1∧H2∧...Hn∧R=>C,则H1∧H2∧...Hn=>R→C

这些内容相当抽象,除了认真仔细地做习题外,光这么看是无法掌握的,所以我们要好好地做完习题。考试大收集整理

离散数学答案命题逻辑

第二章 命题逻辑 习题.解 ⑴不是陈述句,所以不是命题。 ⑵x 取值不确定,所以不是命题。 ⑶问句,不是陈述句,所以不是命题。 ⑷惊叹句,不是陈述句,所以不是命题。 ⑸是命题,真值由具体情况确定。 ⑹是命题,真值由具体情况确定。 ⑺是真命题。 ⑻是悖论,所以不是命题。 ⑼是假命题。 2.解 ⑴是复合命题。设p :他们明天去百货公司;q :他们后天去百货公司。命题符号化为q p ∨。 ⑵是疑问句,所以不是命题。 ⑶是悖论,所以不是命题。 ⑷是原子命题。 ⑸是复合命题。设p :王海在学习;q :李春在学习。命题符号化为p q 。 ⑹是复合命题。设p :你努力学习;q :你一定能取得优异成绩。p q 。 ⑺不是命题。 ⑻不是命题 ⑼。是复合命题。设p :王海是女孩子。命题符号化为:p 。 3.解 ⑴如果李春迟到了,那么他错过考试。 ⑵要么李春迟到了,要么李春错过了考试,要么李春通过了考试。 ⑶李春错过考试当且仅当他迟到了。 ⑷如果李春迟到了并且错过了考试,那么他没有通过考试。 4.解 ⑴p (q r )。⑵p q 。⑶q p 。⑷q p 。 习题 1.解 ⑴是1层公式。 ⑵不是公式。 ⑶一层: p q ,p 二层: p q 所以,)()(q p q p ??→∨是3层公式。 ⑷不是公式。 ⑸(p q )(q ( q r ))是5层公式,这是因为 一层:p q ,q ,r 二层:q r 三层:q ( q r ) 四层: (q ( q r )) 2.解 ⑴A =(p q )q 是2层公式。真值表如表2-1所示: 表2-1 p q q p ∨ A 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 ⑵p q p q A →→∧=)(是3层公式。真值表如表2-2所示:

离散数学第一章命题逻辑知识点总结

数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题,陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题):简单陈述句构成的命题 复合命题:由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1)表示 简单命题 用“1”表示真,用“0”表示假 例如,令p:是有理数,则p 的真值为 0 q:2 + 5 = 7,则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题,复合命题“非p”(或“p的否定”)称 为p的否定式,记作p. 符号称作否定联结词,并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式,记作p∧q. ∧称作合取联结词,并规定 p∧q为真当且仅当p 与q同时为真 注意:描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明,而且用功. (3) 王晓虽然聪明,但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p:王晓用功,q:王晓聪明,则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生,s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学,t 是简单命题 . 说明:

离散数学考试题详细答案

离散数学考试题(后附详细答案) 一、命题符号化(共6小题,每小题3分,共计18分) 1.用命题逻辑把下列命题符号化 a)假如上午不下雨,我去瞧电影,否则就在家里读书或瞧报。 设P表示命题“上午下雨”,Q表示命题“我去瞧电影”,R表示命题“在家里读书”,S表示命题“在家瞧报”,命题符号化为:(?P?Q)∧(P?R∨S) b)我今天进城,除非下雨。 设P表示命题“我今天进城”,Q表示命题“天下雨”,命题符号化为:?Q→P或?P→Q c)仅当您走,我将留下。 设P表示命题“您走”,Q表示命题“我留下”,命题符号化为: Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不就是有理数 设R(x)表示“x就是实数”,Q(x)表示“x就是有理数”,命题符号化为: ?x(R(x) ∧?Q(x)) 或??x(R(x) →Q(x)) b)对于所有非零实数x,总存在y使得xy=1。 设R(x)表示“x就是实数”,E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为: ?x(R(x) ∧?E(x,0) →?y(R(y) ∧E(f(x,y),1)))) c) f 就是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b、 设F(f)表示“f就是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为:F(f)??a(A(a)→?b(B(b) ∧ E(f(a),b) ∧?c(S(c) ∧ E(f(a),c) →E(a,b)))) 二、简答题(共6道题,共32分) 1.求命题公式(P→(Q→R))?(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋 值。(5分) (P→(Q→R))?(R→(Q→P))?(?P∨?Q∨R)?(P∨?Q∨?R) ?((?P∨?Q∨R)→(P∨?Q∨?R)) ∧ ((P∨?Q∨?R) →(?P∨?Q∨R))、 ?((P∧Q∧?R)∨ (P∨?Q∨?R)) ∧ ((?P∧Q∧R) ∨(?P∨?Q∨R)) ?(P∨?Q∨?R) ∧(?P∨?Q∨R) 这就是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 (?P∧?Q∧?R)∨(?P∧?Q∧R)∨(?P∧Q∧?R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R) 2.设个体域为{1,2,3},求下列命题的真值(4分) a)?x?y(x+y=4) b)?y?x (x+y=4) a) T b) F 3.求?x(F(x)→G(x))→(?xF(x)→?xG(x))的前束范式。(4分) ?x(F(x)→G(x))→(?xF(x)→?xG(x)) ??x(F(x)→G(x))→(?yF(y)→?zG(z))??x(F(x)→G(x))→?y?z(F(y)→G(z)) ??x?y?z((F(x)→G(x))→ (F(y)→G(z))) 4.判断下面命题的真假,并说明原因。(每小题2分,共4分) a)(A?B)-C=(A-B) ?(A-C) b)若f就是从集合A到集合B的入射函数,则|A|≤|B| a) 真命题。因为(A?B)-C=(A?B)?~C=(A?~C)?(B?~C)=(A-C)?(B-C) b) 真命题。因为如果f就是从集合A到集合B的入射函数,则|ranf|=|A|,且ranf?B,故命题 成立。

离散数学(命题逻辑)课后总结

离散数学(课件上习题) 第一章 例1-1.1 判定下面这些句子哪些是命题。 ⑴2是个素数。 ⑵雪是黑色的。 ⑶2013年人类将到达火星。 ⑷如果a>b且b>c,则a>c 。(其中a,b,c都是 确定的实数) ⑸x+y<5 ⑹请打开书! ⑺您去吗? ⑴⑵⑶⑷是命题 例1-2.1 P:2是素数。 ?P:2不是素数。 例1-2.2 P:小王能唱歌。 Q:小王能跳舞。 P∧Q:小王能歌善舞。 例1-2.3. 灯泡或者线路有故障。(析取“∨”) 例1-2.4. 第一节课上数学或者上英语。(异或、排斥或。即“?”) 注意:P ?Q 与(P∧?Q)∨(Q∧?P ) 是一样的。 归纳自然语言中的联结词,定义了六个逻辑联结词,分别是:(1)否定“?”(2) 合取“∧”(3) 析取“∨”(4) 异或“?”(5) 蕴涵“→”(6) 等价“?” 例1-2.5:P表示:缺少水分。 Q表示:植物会死亡。 P→Q:如果缺少水分,植物就会死亡。 P→Q:也称之为蕴涵式,读成“P蕴涵Q”,“如果P则Q”。 也说成P是P→Q 的前件,Q是P→Q的后件。 还可以说P是Q的充分条件,Q是P的必要条件。 以下是关于蕴含式的一个例子 P:天气好。Q:我去公园。 1.如果天气好,我就去公园。 2.只要天气好,我就去公园。 3.天气好,我就去公园。 4.仅当天气好,我才去公园。 5.只有天气好,我才去公园。 6.我去公园,仅当天气好。 命题1.、2.、3.写成:P→Q 命题4.、5.、6.写成:Q→P 例1-2.6:P:△ABC 是等边三角形。Q :△ABC是等角三角形。 P?Q :△ABC 是等边三角形当且仅当它是等角三角形。

离散数学之命题逻辑考试参考答案2

离散数学之命题逻辑考试 1、分析下列语句那些是命题,哪些不是命题。(每小题1分,正确 “T ”错误写 “F ”,共10分) (1)、北京是中国首都。 (2)、大连是多么美丽啊! (3)、素数只有有限个。 (4)、请勿吸烟! (5)、6+8≥14。 (6)、明天有离散数学课吗? (7)、不存在最大素数。 (8)、9<+Y X 。 (9)、所有素数都是奇数。 (10)实践出真理。 2、设P 表示命题“我学习努力”。Q 表示命题“我考试通过”。R 表示命题“我很快乐”。(每小题2分,共6分) 试用符号表示下列命题: 1) 我考试没通过,但我很快乐。 2) 如果我努力学习,那么我考试通过。 3) 如果我学习努力并且考试通过,那么我很快乐。 3、将下列命题符号化:(每小题2分,共14分) 1) 我美丽而又快乐。 2) 如果我快乐,那么天就下雨。 3) 电灯不亮,当且仅当灯泡或开关发生故障。 4) 仅当你去,我将留下。 5) 如果老张和老李都不去,他就去。 6) 你不能既吃饭又看电视。 7) 张刚总是在图书馆看书,除非图书馆不开门或张刚生病。 4、给出下列公式的真值表 (每小题5分,共10分) ⑴ )(R Q P ∨→ ⑵ )(Q P ∨??)(Q P ?∧? 5、证明下列等价式。(每小题3分,共12分) 1) P Q P Q P ??∧∨∧)()( 2) P Q Q P P ?→??→→)(

3) C B A C B A →?∧?∨→)()( 4) C A D B C D B C B A →→∧?∨→∧→∧))(())(())(( 6、求下列命题公式的主析取范式和主合取范式。(每小题10分,共20分) 1) )()(Q R Q P →∧→ 2) R Q P →∨?)( 7、对于下列一组前提,请给出它们的有效结论并证明。(每小题4分,共8分) a) 如果我努力学习,那么我能通过考试,但我没有通过考试。 b) 统计表有错误,其原因有两个:一个原因是数据有错误;另一个原因是 计算有错误。现在查出统计表有错误,但计算没有错误。 8、符号化下述论断,并证明其有效性。(6分) 如果今天是周一,则要进行离散数学或C 语言程序设计两门课中的一门课考试。如果C 语言程序设计老师有会,则不考C 语言程序设计。今天是周一,C 语言程序设计老师有会,所以进行离散数学考试。 9、符号化下列命题,并推证。(6分) 如果厂方拒绝增加工资,则罢工不会停止,除非罢工超过一年并且工厂厂长辞职。因此,若厂方拒绝增加工资,而罢工又刚刚开始,罢工是不会停止的。 11、请根据下面事实,找出凶手:(8分) 1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理,则谋害不会发生在午夜前。 3.如果秘书的证词是正确的,则谋害发生在午夜前。 4.如果秘书的证词不正确,则午夜时屋里灯光未灭。 5. 如果清洁工富裕,则他不会谋害经理。 6.经理有钱且清洁工不富裕。 7.午夜时屋里灯灭了。 令A:清洁工谋害了经理。 B:秘书谋害了经理。 C:谋害发生在午夜前。 D:秘书的证词是正确的. E:午夜时屋里灯光灭了。H:清洁工富裕. G:经理有钱.

离散数学命题逻辑练习题

离散数学命题逻辑练习 题 TTA standardization office【TTA 5AB- TTAK 08- TTA 2C】

一、选择题 1. 设命题公式) ?,记作G,使G的真值指派为1的P,Q,R的真值是( ) P∧ → (R Q 2. 与命题公式P(QR)等价的公式是( ) A () →→ D () P Q R P Q R →∨ P Q R ∨→ B () P Q R ∧→ C () 3. 下列各组公式中,哪组是互为对偶的 ( ) A ,P P B ,P P A A** D ,A A ? C ,() (其中P为单独的命题变元,A为含有联结词的公式) 4. 命题公式(P∧(P→Q))→Q是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中,哪个是最小联结词 ( ) A {,} ∧→ ?∧∨ C {}↑ D {,} ? B {,,} 6. 命题公式() ?∧→的主析取范式种含小项的个数为 ( ) P Q R A 8 B 3 C 5 D 0 7. 如果A B ?成立,则以下各种蕴含关系哪一个成立 ( ) A B A ?? ??? D A B ??? C B A ? B A B 8. 命题公式()() →∧→的主析取范式中包含小项 ( ) P Q P R A P Q R ∧?∧? ∧?∧ D P Q R ∧∧? C P Q R ∧∧ B P Q R 9. ,, A B C为任意命题公式,当()成立时,有A B ?。 A A B ∧?∧ D C A C B →?→??? B A C B C ∨?∨ C A C B C 10. 下面4个推理定律中,不正确的是 ( ) A () ∨∧?? A B A B A A B ?∧ B () C () →∧??? A B B A A B A B →∧? D ()

离散数学命题逻辑练习题

一、选择题 1. 设命题公式)(R Q P ∧→?,记作G ,使G 的真值指派为1的P ,Q ,R 的真值是( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 2. 与命题公式P →(Q →R )等价的公式是( ) A ()P Q R ∨→ B ()P Q R ∧→ C ()P Q R →→ D ()P Q R →∨ 3. 下列各组公式中,哪组是互为对偶的 ( ) A ,P P B ,P P ? C ,()A A ** D ,A A (其中P 为单独的命题变元,A 为含有联结词的公式) 4. 命题公式(P ∧(P →Q))→Q 是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中,哪个是最小联结词 ( ) A {,}?€ B {,,}?∧∨ C {}↑ D {,}∧→ 6. 命题公式()P Q R ?∧→的主析取范式种含小项的个数为 ( ) A 8 B 3 C 5 D 0 7. 如果A B ?成立,则以下各种蕴含关系哪一个成立 ( ) A B A ? B A B ??? C B A ??? D A B ?? 8. 命题公式()()P Q P R →∧→的主析取范式中包含小项 ( ) A P Q R ∧∧ B P Q R ∧∧? C P Q R ∧?∧ D P Q R ∧?∧? 9. ,,A B C 为任意命题公式,当( )成立时,有A B ?。 A A B ??? B A C B C ∨?∨ C A C B C ∧?∧ D C A C B →?→ 10. 下面4个推理定律中,不正确的是 ( ) A ()A A B ?∧ B ()A B A B ∨∧?? C ()A B A B →∧? D ()A B B A →∧??? 11. 下列命题公式是等价公式的为( ). A .?P ∧?Q ?P ∨Q B .A →(?B →A) ??A →(A →B) C .Q →(P ∨Q )??Q ∧(P ∨Q ) D .?A ∨(A ∧B) ?B

离散数学-第1章-习题解答

习题1.1 1. 下列句子中,哪些是命题?哪些不是命题?如果是命题,指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗? ⑶不存在最大素数。 ⑷21+3<5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以p。 ⑾只有6是偶数,3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨,他就乘班车上班。 解:⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题,其中⑴⑶⑽⑾是真命题,⑷⑹⑿是假命题,⑸⑺⒀的真值目前无法确定;⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷,所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影,那么我也不看电影。 ⑺我既不看电视也不外出,我在睡觉。 ⑻除非天下大雨,否则他不乘班车上班。 解:⑴本命题为原子命题; ⑵p:天气冷;q:我穿羽绒服; ⑶p:天在下雨;q:湿度很高; ⑷p:刘英上山;q:李进上山; ⑸p:王强学过法语;q:刘威学过法语; ⑹p:你看电影;q:我看电影; ⑺p:我看电视;q:我外出;r:我睡觉; ⑻p:天下大雨;q:他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭,一面听音乐。 ⑵3是素数或2是素数。

⑶若地球上没有树木,则人类不能生存。 ⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数,则a+b是偶数。 解:⑴p:他吃饭;q:他听音乐;原命题符号化为:p∧q ⑵p:3是素数;q:2是素数;原命题符号化为:p∨q ⑶p:地球上有树木;q:人类能生存;原命题符号化为:p→q ⑷p:8是偶数;q:8能被3整除;原命题符号化为:p?q ⑸p:停机;q:语法错误;r:程序错误;原命题符号化为:q∨r→p ⑹p:四边形ABCD是平行四边形;q:四边形ABCD的对边平行;原命题符号化为:p?q。 ⑺p:a是偶数;q:b是偶数;r:a+b是偶数;原命题符号化为:p∧q→r 4. 将下列命题符号化,并指出各复合命题的真值。 ⑴如果3+3=6,则雪是白的。 ⑵如果3+3≠6,则雪是白的。 ⑶如果3+3=6,则雪不是白的。 ⑷如果3+3≠6,则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1,O2的面积相等,则它们的半径相等,反之亦然。 ⑻当王小红心情愉快时,她就唱歌,反之,当她唱歌时,一定心情愉快。 解:设p:3+3=6。q:雪是白的。 ⑴原命题符号化为:p→q;该命题是真命题。 ⑵原命题符号化为:p→q;该命题是真命题。 ⑶原命题符号化为:p→q;该命题是假命题。 ⑷原命题符号化为:p→q;该命题是真命题。 ⑸p:3是无理数;q:加拿大位于亚洲;原命题符号化为:p?q;该命题是假命题。 ⑹p:2+3=5;q:3是无理数;原命题符号化为:p?q;该命题是真命题。 ⑺p:两圆O1,O2的面积相等;q:两圆O1,O2的半径相等;原命题符号化为:p?q;该命题是真命题。 ⑻p:王小红心情愉快;q:王小红唱歌;原命题符号化为:p?q;该命题是真命题。

离散数学命题逻辑练习题

一、选择题 1、 设命题公式)(R Q P ∧→?,记作G ,使G 的真值指派为1的P ,Q ,R 的真值就是( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 2、 与命题公式P →(Q →R )等价的公式就是( ) A ()P Q R ∨→ B ()P Q R ∧→ C ()P Q R →→ D ()P Q R →∨ 3、 下列各组公式中,哪组就是互为对偶的 ( ) A ,P P B ,P P ? C ,()A A ** D ,A A (其中P 为单独的命题变元,A 为含有联结词的公式) 4、 命题公式(P ∧(P →Q))→Q 就是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5、 下面命题联结词集合中,哪个就是最小联结词 ( ) A {,}?€ B {,,}?∧∨ C {}↑ D {,}∧→ 6、 命题公式()P Q R ?∧→的主析取范式种含小项的个数为 ( ) A 8 B 3 C 5 D 0 7、 如果A B ?成立,则以下各种蕴含关系哪一个成立 ( ) A B A ? B A B ??? C B A ??? D A B ?? 8、 命题公式()()P Q P R →∧→的主析取范式中包含小项 ( ) A P Q R ∧∧ B P Q R ∧∧? C P Q R ∧?∧ D P Q R ∧?∧? 9、 ,,A B C 为任意命题公式,当( )成立时,有A B ?。 A A B ??? B A C B C ∨?∨ C A C B C ∧?∧ D C A C B →?→ 10、 下面4个推理定律中,不正确的就是 ( ) A ()A A B ?∧ B ()A B A B ∨∧?? C ()A B A B →∧? D ()A B B A →∧??? 11、 下列命题公式就是等价公式的为( ). A.?P ∧?Q ?P ∨Q B.A →(?B →A) ??A →(A →B) C.Q →(P ∨Q )??Q ∧(P ∨Q ) D.?A ∨(A ∧B) ?B

离散数学答案命题逻辑

第二章 命题逻辑 习题2.11.解 ⑴不是陈述句,所以不是命题。 ⑵x 取值不确定,所以不是命题。 ⑶问句,不是陈述句,所以不是命题。 ⑷惊叹句,不是陈述句,所以不是命题。 ⑸是命题,真值由具体情况确定。 ⑹是命题,真值由具体情况确定。 ⑺是真命题。 ⑻是悖论,所以不是命题。 ⑼是假命题。 2.解 ⑴是复合命题。设p :他们明天去百货公司;q :他们后天去百货公司。命题符号化为q p ∨。 ⑵是疑问句,所以不是命题。 ⑶是悖论,所以不是命题。 ⑷是原子命题。 ⑸是复合命题。设p :王海在学习;q :李春在学习。命题符号化为p ∧q 。 ⑹是复合命题。设p :你努力学习;q :你一定能取得优异成绩。p →q 。 ⑺不是命题。 ⑻不是命题 ⑼。是复合命题。设p :王海是女孩子。命题符号化为:?p 。 3.解 ⑴如果李春迟到了,那么他错过考试。 ⑵要么李春迟到了,要么李春错过了考试,要么李春通过了考试。 ⑶李春错过考试当且仅当他迟到了。 ⑷如果李春迟到了并且错过了考试,那么他没有通过考试。 4.解 ⑴?p →(q ∨r )。⑵p →q 。⑶q →p 。⑷q → p 。 习题2.2 1.解 ⑴是1层公式。 ⑵不是公式。 ⑶一层: p ∨q ,?p 二层:?p ?q 所以,)()(q p q p ??→∨是3层公式。 ⑷不是公式。 ⑸(p →q )∧?(?q ?( q →?r ))是5层公式,这是因为 一层:p →q ,?q ,?r 二层:q →?r 三层:?q ?( q →?r ) 四层:?(?q ?( q →?r )) 2.解 ⑴A =(p ∨q )∧q 是2层公式。真值表如表2-1所示: 表2-1 ⑵p q p q A →→∧= )(是3层公式。真值表如表2-2所示:

离散数学答案命题逻辑

第二章 命题逻辑 习题2、11.解 ⑴不就是陈述句,所以不就是命题。 ⑵x 取值不确定,所以不就是命题。 ⑶问句,不就是陈述句,所以不就是命题。 ⑷惊叹句,不就是陈述句,所以不就是命题。 ⑸就是命题,真值由具体情况确定。 ⑹就是命题,真值由具体情况确定。 ⑺就是真命题。 ⑻就是悖论,所以不就是命题。 ⑼就是假命题。 2.解 ⑴就是复合命题。设p :她们明天去百货公司;q :她们后天去百货公司。命题符号化为q p ∨。 ⑵就是疑问句,所以不就是命题。 ⑶就是悖论,所以不就是命题。 ⑷就是原子命题。 ⑸就是复合命题。设p :王海在学习;q :李春在学习。命题符号化为p ∧q 。 ⑹就是复合命题。设p :您努力学习;q :您一定能取得优异成绩。p →q 。 ⑺不就是命题。 ⑻不就是命题 ⑼。就是复合命题。设p :王海就是女孩子。命题符号化为:?p 。 3.解 ⑴如果李春迟到了,那么她错过考试。 ⑵要么李春迟到了,要么李春错过了考试,要么李春通过了考试。 ⑶李春错过考试当且仅当她迟到了。 ⑷如果李春迟到了并且错过了考试,那么她没有通过考试。 4.解 ⑴?p →(q ∨r )。⑵p →q 。⑶q →p 。⑷q → p 。 习题2、2 1.解 ⑴就是1层公式。 ⑵不就是公式。 ⑶一层: p ∨q ,?p 二层:?p ?q 所以,)()(q p q p ??→∨就是3层公式。 ⑷不就是公式。 ⑸(p →q )∧?(?q ?( q →?r ))就是5层公式,这就是因为 一层:p →q ,?q ,?r 二层:q →?r 三层:?q ?( q →?r ) 四层:?(?q ?( q →?r )) 2.解 ⑴A =(p ∨q )∧q 就是2层公式。真值表如表2-1所示: 表2-1 ⑵p q p q A →→∧= )(就是3层公式。真值表如表2-2所示:

华南理工《离散数学》命题逻辑练习题(含答案)(最新整理)

第一章命题逻辑 1.1 命题与联结词 一、单项选择题 1、 A.明年“五一”是晴天。 B.这朵花多好看呀!。 C.这个男孩真勇敢啊! D.明天下午有会吗? 在上面句子中,是命题的是( ) 2. A.1+101=110 B.中国人民是伟大的。 C.这朵花多好看呀! D.计算机机房有空位吗? 在上面句子中,是命题的是( ) 3. A.如果天气好,那么我去散步。 B.天气多好呀! C.x=3。 D.明天下午有会吗? 在上面句子中( )是命题 4.下面的命题不是简单命题的是( ) A.3是素数或4是素数 B.2018年元旦下大雪 C.刘宏与魏新是同学 D.圆的面积等于半径的平方与π之积 5.下面的表述与众不一致的一个是( ) A.P:广州是一个大城市 B.?P:广州是一个不大的城市 C.?P:广州是一个很不小的城市 D.?P:广州不是一个大城市 6.设,P:他聪明;Q:他用功。在命题逻辑中,命题: “他既聪明又用功。” 可符号化为:( ) A.P ∧Q B.P→Q C.P∨?Q D.P∧?Q 7.设:P :刘平聪明。Q:刘平用功。在命题逻辑中,命题: “刘平不但聪明,而且用功”可符号化为:( ) A.P ∧Q B.?P∨Q C.P∨?Q D.P∧?Q 8.设:P:他聪明;Q:他用功。则命题“他虽聪明但不用功。” 在命题逻辑中可符号化为( ) A.P ∧Q B.P→Q C.P∨?Q D.P∧?Q 9.设:P:我们划船。Q:我们跑步。在命题逻辑中,命题: “我们不能既划船又跑步。” 可符号化为:( ) A.P→Q B.?(P ∧Q) C.P∨Q D.P∧?Q 10.设:P:王强身体很好;Q:王强成绩很好。命题“王强身体很好,成绩也很好。”在命题逻辑中可符号化为( ) A.P ∨Q B.P→Q C.P∧?Q D.P∧Q 11.设:P:你努力;Q:你失败。则命题“除非你努力,否则你将失败。”

《离散数学》同步练习参考答案

华南理工大学网络教育学院 《离散数学》练习题参考答案 第一章命题逻辑 一填空题 (1)设:p:派小王去开会。q:派小李去开会。则命题: “派小王或小李中的一人去开会”可符号化 为:(p∨?q) ∧ (?p∨q) 。 (2)设A,B都是命题公式,A?B,则A→B的真值是T。 (3)设:p:刘平聪明。q:刘平用功。在命题逻辑中,命题: “刘平不但不聪明,而且不用功”可符号化为:p∧q。 (4)设A , B 代表任意的命题公式,则蕴涵等值式为 A → B??A∨B。 (5)设,p:径一事;q:长一智。在命题逻辑中,命题: “不径一事,不长一智。”可符号化为:? p→?q 。 (6)设A , B 代表任意的命题公式,则德?摩根律为 ?(A ∧ B)??A ∨?B)。 (7)设,p:选小王当班长;q:选小李当班长。则命题:“选小王或小李中的一人当班长。”可符号化为:(p∨?q) ∧ (?p∨q) 。(8)设,P:他聪明;Q:他用功。在命题逻辑中,命题: “他既聪明又用功。”可符号化为:P∧Q 。 (9)对于命题公式A,B,当且仅当 A → B 是重言式时,称“A蕴含B”,并记为A?B。 (10)设:P:我们划船。Q:我们跑步。在命题逻辑中,命题:“我们不能既划船又跑步。”可符号化为:? (P∧Q) 。(11)设P , Q是命题公式,德·摩根律为: ?(P∨Q)??P∧?Q)。 (12)设P:你努力。Q:你失败。在命题逻辑中,命题:“除非你努力,否则你将失败。”可符号化为:?P→Q。

(13)设p:小王是100米赛跑冠军。q:小王是400米赛跑冠军。在命题逻辑中,命题:“小王是100米或400米赛跑冠军。”可符号化为: p∨q。 (14)设A,C为两个命题公式,当且仅当A→C为一重言式时,称C可由A逻辑地推出。 二.判断题 1.设A,B是命题公式,则蕴涵等值式为A→B??A∧B。(?) 2.命题公式?p∧q∧?r是析取范式。(√) 3.陈述句“x + y > 5”是命题。(?) 4.110 (p=1,q=1, r=0)是命题公式((?(p∧q))→r)∨q 的成真赋值。(√) 5.命题公式p→(?p∧q) 是重言式。(?) 6.设A,B都是合式公式,则A∧B→?B也是合式公式。(√) 7.A∨(B∧C)?( A∨B)∨(A∨C)。(?) 8.陈述句“我学英语,或者我学法语”是命题。(√) 9.命题“如果雪是黑的,那么太阳从西方出”是假命题。(?) 10.“请不要随地吐痰!”是命题。(?) 11.P →Q ??P∧Q 。(?) 12.陈述句“如果天下雨,那么我在家看电视”是命题。(√) 13.命题公式(P∧Q)∨(?R→T)是析取范式。(?) 14.命题公式(P∧?Q)∨R∨ (?P∧Q) 是析取范式。(√) 三、选择题:在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的内。 1.设:P:天下雪。Q:他走路上班。则命题“只有天下雪,他才走路上班。” 可符号化为(2)。 (1)P→Q (2)Q → P (3)? Q →? P (4)Q ∨?P 2.(1 ) 明年国庆节是晴天。

最新离散数学答案命题逻辑

第二章 命题逻辑 1 习题2.11.解 ⑴不是陈述句,所以不是命题。 2 ⑵x 取值不确定,所以不是命题。 3 ⑶问句,不是陈述句,所以不是命题。 4 ⑷惊叹句,不是陈述句,所以不是命题。 5 ⑸是命题,真值由具体情况确定。 6 ⑹是命题,真值由具体情况确定。 7 ⑺是真命题。 8 ⑻是悖论,所以不是命题。 9 ⑼是假命题。 10 2.解 ⑴是复合命题。设p :他们明天去百货公司;q :他们后天去百货11 公司。命题符号化为q p 。 12 ⑵是疑问句,所以不是命题。 13 ⑶是悖论,所以不是命题。 14 ⑷是原子命题。 15 ⑸是复合命题。设p :王海在学习;q :李春在学习。命题符号化为p q 。 16 ⑹是复合命题。设p :你努力学习;q :你一定能取得优异成绩。p q 。 17 ⑺不是命题。 18 ⑻不是命题 19 ⑼。是复合命题。设p :王海是女孩子。命题符号化为:p 。 20 3.解 ⑴如果李春迟到了,那么他错过考试。 21 ⑵要么李春迟到了,要么李春错过了考试,要么李春通过了考试。 22

⑶李春错过考试当且仅当他迟到了。 23 ⑷如果李春迟到了并且错过了考试,那么他没有通过考试。 24 4.解 ⑴p (q r )。⑵p q 。⑶q p 。⑷q p 。 25 习题2.2 26 1.解 ⑴是1层公式。 27 ⑵不是公式。 28 ⑶一层: p q ,p 29 二层:p q 30 所以,)()(q p q p ??→∨是3层公式。 31 ⑷不是公式。 32 ⑸(p q )(q ( q r ))是5层公式,这是因为 33 一层:p q ,q ,r 34 二层:q r 35 三层:q ( q r ) 36 四层:(q ( q r )) 37 2.解 ⑴A =(p q )q 是2层公式。真值表如表2-1所示: 38 表2-1 39 p q q p ∨ A 0 0 0 0 0 1 1 1

离散数学命题逻辑练习题

一、选择题 1.设命题公式) → P∧ ?,记作G,使G的真值指派为1的P,Q,R的真值是Q (R () 2.与命题公式P?(Q?R)等价的公式是() A() →→D() P Q R P Q R →∨ P Q R P Q R ∨→B() ∧→C() 3. A ( 4. A 5. A 6. A 7. A 8. A 9.,, A B C为任意命题公式,当()成立时,有A B ?。 A A B →?→ ∧?∧D C A C B ???B A C B C ∨?∨C A C B C 10.下面4个推理定律中,不正确的是() A() ∨∧?? A B A B A A B ?∧B() C() →∧??? A B B A A B A B →∧?D()

11.下列命题公式是等价公式的为(). A.?P??Q?P?Q B.A?(?B?A)??A?(A?B) C.Q?(P?Q)??Q?(P?Q)D.?A?(A?B)?B 12.命题公式) ?的主析取范式是(). P→ (Q A.Q ?D.Q ∨ P∨ P? ?C.Q P? ∧B.Q P∧ 13 14. A 15 (A (C 16 17. 1. 2.若命题变元P,Q,R赋值为(1,0,1),则命题公式G=) ∨ P∨ ∧的 Q → ? ) ( ) ((Q P R 真值是 3.公式() ?∧∨的等价式为,它的对偶式为, P Q R ∨→的只含联接词,, 4.命题公式() →∨的真值是. P Q P

5.对于前提(),, ∧→?∨?,其有效结论为, P Q R R S S 6.命题公式() ?→的主析取范式为,其编码表示为,主合取范式的编码为. P Q 7.一个命题公式(,,) A P Q R的成真指派为000,001,010,100,110,则其主合取范式为. 8.任意两个不同小项的合取为式,全体小项的析取式必为. 9.设(重 10. 六、?和→。

离散数学命题逻辑练习题

一、选择题 1. 设命题公式) ?,记作G,使G的真值指派为1的P,Q,R的真值是( ) P∧ → (R Q 2. 与命题公式P?(Q?R)等价的公式是( ) A () →→ D () P Q R P Q R →∨ P Q R ∨→ B () P Q R ∧→ C () 3. 下列各组公式中,哪组是互为对偶的 ( ) A ,P P B ,P P A A** D ,A A ? C ,() (其中P为单独的命题变元,A为含有联结词的公式) 4. 命题公式(P∧(P→Q))→Q是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中,哪个是最小联结词 ( ) A {,} ∧→ ?∧∨ C {}↑ D {,} ?€ B {,,} 6. 命题公式() ?∧→的主析取范式种含小项的个数为 ( ) P Q R A 8 B 3 C 5 D 0 7. 如果A B ?成立,则以下各种蕴含关系哪一个成立 ( ) A B A ?? ??? D A B ??? C B A ? B A B 8. 命题公式()() →∧→的主析取范式中包含小项 ( ) P Q P R A P Q R ∧?∧? ∧?∧ D P Q R ∧∧? C P Q R ∧∧ B P Q R 9. ,, A B C为任意命题公式,当()成立时,有A B ?。 A A B ∧?∧ D C A C B →?→??? B A C B C ∨?∨ C A C B C 10. 下面4个推理定律中,不正确的是 ( ) A () ∨∧?? A B A B A A B ?∧ B () C () →∧??? A B B A A B A B →∧? D ()

离散数学命题逻辑练习题教学内容

离散数学命题逻辑练 习题

一、选择题 1. 设命题公式) ?,记作G,使G的真值指派为1的P,Q,R的真值 P∧ → Q (R 是( ) 0,0,0) A ( 1,0,0)B( 0,0,1) D ( 0,1,0)C( 2. 与命题公式P→(Q→R)等价的公式是( ) A () →→ D () P Q R →∨ P Q R ∧→ C () ∨→ B () P Q R P Q R 3. 下列各组公式中,哪组是互为对偶的 ( ) A A** D ,A A A ,P P B ,P P ? C ,() (其中P为单独的命题变元,A为含有联结词的公式) 4. 命题公式(P∧(P→Q))→Q是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中,哪个是最小联结词 ( ) A {,} ∧→ ?€ B {,,} ?∧∨ C {}↑ D {,} 6. 命题公式() ?∧→的主析取范式种含小项的个数为 ( ) P Q R A 8 B 3 C 5 D 0 7. 如果A B ?成立,则以下各种蕴含关系哪一个成立 ( ) A B A ?? ??? D A B ? B A B ??? C B A 8. 命题公式()() →∧→的主析取范式中包含小项 ( ) P Q P R A P Q R ∧?∧? ∧?∧ D P Q R ∧∧ B P Q R ∧∧? C P Q R 9. ,, A B C为任意命题公式,当()成立时,有A B ?。 A A B →?→ ∧?∧ D C A C B ∨?∨ C A C B C ??? B A C B C 10. 下面4个推理定律中,不正确的是 ( ) A () ∨∧?? A B A B ?∧ B () A A B

相关主题
相关文档 最新文档