当前位置：文档之家 › 离散数学(2.2命题函数与谓词)

离散数学(2.2命题函数与谓词)

  • 格式：ppt
  • 大小：184.00 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

离散数学第二章

离散数学第二章


P (t1 , t2 , , tn ) 是原子公式。
32
§2.1.3 谓词逻辑公式（公式 ）
定义 谓词公式由下述各条规定组成： （1）原子公式是谓词公式。 （2）若A是谓词公式，则﹁ A也是谓词公式。 （3）若A和B是谓词公式，则A ∨ B，A ∧ B，A → B， 也是谓词公式。
22
2．存在量词
注意：１．在存在量词 的作用下，x不再起变量的作用， 存在量词也“约束”了x的变量作用。 注意：２．在存在量词作用下，命题中的特性谓词与命题 变元之间必须采用联结词合取，而不能用条件。 注意：3．命题的表示形式与个体域密切相关。 例：有些狗是聪明的。 若个体域为所有狗的集合，则该命题表示为：
这种“描述主语性质的谓语结构的抽象形式或描述主语所 涉及对象之间的关系的抽象形式”就是谓词。语句中的主 语称为个体。 在原子命题中引进谓词和个体的概念，这种以命题中的谓 词为基础的分析研究，称为谓词逻辑(或称谓词演算)。
7


§2.1.1 谓词与个体

在谓词逻辑中，将原子命题分解为谓词与个体两部分。
F (a1 , a2 , , an )
例如， T（a）：a是教师。 D（３，２）：３大于２。 C（武汉，北京，广州）：武汉位于北 京和 广州之间。 注意顺序
9
§2.1.1 谓词与个体
在一个谓词中，个体是可以变化的，如 “是大学生” 中个体是可以变化的，可以是“张华是大学生” 也可
以是“何勇是大学生” ，等等。
31
§2.1.3 谓词逻辑公式（公式 ）
定义( 项 ) (1)个体常量符是项；
(2)个体变量符是项；
(3)设f是n元函数符，
t1 , t2 , , tn 为项，则
《应用离散数学》谓词公式及其解释

《应用离散数学》谓词公式及其解释

§2.2 谓词公式及其解释习题2.21. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。

（1）))()((y x Q x P x ，→∀（2）)()(y x yQ y x xP ，，∃→∀ （3）)())()((z y x xR z y Q y x P y x ，，，，∃∨∧∃∀解 （1）x ∀中的x 是指导变元；量词x ∀的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。

（2）x ∀中的x ，y ∃中的y 都是指导变元；x ∀的辖域是)(y x P ，，y ∃的辖域是)(y x Q ，；)(y x P ，中的x 是x ∀的约束变元，y 是自由变元；)(y x Q ，中的x 是自由变元，y 是y ∃的约束变元。

（3）x ∀中的x ，y ∃中的y 以及x ∃中的x 都是指导变元；x ∀的辖域是))()((z y Q y x P y ，，∧∃，y ∃的辖域是)()(z y Q y x P ，，∧，x ∃的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元，)(z y x R ，，中的x 为约束变元，y ，z 是自由变元。

2. 设个体域}21{，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。

（1）))()((x Q x P x →∀ （2）))()((x Q x P x ∧∃解（1）解释1I ：个体域}21{，=D ，0:)(,0:)(>>x x Q x x P 。

（2）解释2I ：个体域}21{，=D ，2:)(,0:)(>>x x Q x x P 。

3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。

（1）)))()(()((y x R y Q y x P x ，∧∃→∀（2）)),()()((y x R y Q x P y x →∧∀∀解 （1）成真解释：个体域D ＝{1,2,3},0:)(<x x P ,2:)(>y y Q ,3:),(>+y x y x R 。

离散数学第2章 谓词逻辑

离散数学第2章 谓词逻辑

命题“凡人要死。”符号化为：(x)F (x) ⑵ 令G(x)：x是研究生。 命题“有的人是研究生。”符号化为：(x)G(x)
在命题函数前加上量词(x)和(x)分别叫做个体变元x 被全称量化和存在量化。一般地说，命题函数不是命题， 如果对命题函数中所有命题变元进行全称量化或存在量化， 该函数就变成了命题。这一结论在例2.3中得到验证。
为假。 ⑵ 如果5大于3，则2大于6。 解：设G(x,y)： x大于y a：5，b：3，c：2，d：6 该命题符号化为：G(a,b)→G(c,d) G(a,b)表示5大于3，它是真命题。G(c,d)表示2大于6，
ห้องสมุดไป่ตู้这是个假命题。所以G(a,b)→G(c,d)为假。
(3) 2 是无理数, 而 3 是有理数 解 ：设F(x): x是无理数, G(x): x是有理数 符号化为 F( 2) G( 3) 真值为 0 (4) 如果2>3，则3<4 解：设 F(x,y): x>y, G(x,y): x<y, 符号化为 F(2,3)G(3,4) 真值为1
谓词：刻划个体性质或个体之间相互关系的模式叫做谓词。谓 词常用大写英文字母表示，叫做谓词标识符。
例如可以用F，G，H表示上面三个命题中谓词： F：„是优秀共产党员。 G：„比„高。 H：„坐在„和„的中间。
第2章 谓词逻辑
一元谓词：与一个个体相关联的谓词。如上例中的F。 二元谓词：与两个个体相关联的谓词。如上例中的G。 三元谓词：与三个个体相关联的谓词。如上例中的H。
返回章目录
第2章 谓词逻辑
课外作业
• 教材P59-60页: 练习题（需要做在练习本上） （1） （2） a)、c) 、d)、e)、 f)、i)、k)、l)
返回章目录
离散数学 谓词逻辑

离散数学 谓词逻辑


例1 给定解释I1如下：
(1)个体域为自然数集合N； (2)N中的特定元素a=0； （3）F(x,y):x大于或等于y. 在解释I1下,求下列各式的真值： (1)(∀x)F(x,a)；(2)(∀x∃y)F(x,y) 解 在解释I1下,公式分别解释为： (1)任何自然数都大于或等于零, 为真命题.
(2)对任一自然数x,都存在一自然数y使得x≥y, 为真命题.
4
例子
［例2-1.1］ 张明是位大学生。 解：设S(x)：x是大学生,c：张明, 一元谓词：表 则原句的谓词形式为S(c)。 示客体性质 ［例2-1.2］我坐在张三和李四中间。 解：设S(x,y,z)：x坐在y和z之间,i：我,z：张 三,l：李四, 多元谓词：表 示客体间关系 则原句的谓词形式为S(i,z,l)。
★从以上两命题的符号化可以看出,同一命题在不同个体域下 符号化的形式可能不同。
11
这里,M(x)称为特性谓词。应该注意 的是,全称量词和存在量词符号化时,引入 特性谓词时的形式是不同的。 用全称量词 符号化时,特性谓词作为条 件式的前件； 用存在量词符号化时则作为合取式的一 项。
12
对于任一给定的实数x,都存在着一个实数y,使得 x+y=0。 如果取个体域为实数集合 ∀ x ∃ y H(x, y ) 然而 ∃ y ∀ x H(x, y )： 存在着一个少数y,对于任一实数x,使得x+y=0
3
谓词的表示
客体词有两种：客体常元和客体变元。客体常 元表示具体的或特定的客体,一般用小写字母 a、b、c等表示；表示抽象的或泛指的客体的 词称为客体变元,常用小写字母x、y、z等表 示。 谓词,通常用大写的字母A、B、C等表示。
谓词填式：单独一个谓词不是完整的命题, 把谓词字母后填以客体所得的式子。
离散数学-2-2 命题函数与量词

离散数学-2-2 命题函数与量词

第二章谓词逻辑
2-2 命题函数与量词 授课人：李朔 Email:chn.nj.ls@
1
一、命题函数
与命题逻辑中命题常量和命题变元的概念 类似，代表个体的个体标识符也可以表示 客体（个体常量） 客体变元 个体变元） 客体变元（ 客体（个体常量）或客体变元（个体变元）
表示具体或特定个体的标识符称作个体常元 个体常元， 个体常元 一般用小写英文字母a、b、c、…或这些英文字 母带下标表示。 将表示任意个体或泛指某类个体的标识符称为 个体变元，常表示为x、y、z、…等或这些英文 个体变元 字母带下标。
13
三、量词
例：用谓词表达式写出下列命题。
（1）爱美之心人皆有之。设F(x):x为人，G(x):x爱美。 为人， 爱美。 为人 爱美 （2）有人爱发脾气。设F(x):x为人，G(x):x爱发脾气。 为人， 爱发脾气。 为人 爱发脾气 （3）说所有人都爱吃面包是不对的。
F(x)：x为人，G(x):x爱吃面包 ： 为人 为人， 爱吃面包
11
三、量词
⑵ 存在量词 “存在”，“有一个”，“有些”，“至少有一个”等 词统称为存在量词 存在量词，将它们符号化为“∃”。并用(∃x)， 存在量词 (∃y)等表示个体域里有些个体，而用(∃x)F(x)和(∃y)G(y) 等分别表示在个体域中存在个体具有性质F和存在个体具 有性质G。 例 (a)存在一个数是质数。 (b)一些人是聪明的。 (c)有些人早饭吃面包。 设P(x)：x是质数。 M(x): x是人。 E(x): x早饭吃面包。 则 (a)记为(∃x)(P(x)) (b)记为(∃x)(M(x)∧R(x)) (c) 记为(∃x)(M(x)∧E(x))
7
二、பைடு நூலகம்体域
例5 (P(x,y) ∧ P(y,z)) → P(x,z)
离散数学作业册

离散数学作业册

离散数学作业册第一章命题逻辑1.1 命题与逻辑联结词1.判断下列语句是否是命题，不是划“×”，是划“√”，且指出它的真值.(1)所有的素数都是奇数. ( ) 其真值( )(2)明天有离散数学课吗？ ( ) 其真值( )(3)326+>． ( ) 其真值( )(4)实践出真知. ( ) 其真值( )(5)这朵花真好看呀！ ( ) 其真值( )(6)5x=． ( ) 其真值( )(7)太阳系外有宇宙人． ( ) 其真值( )2.将下列命题符号化．(1)如果天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.(3)我们不能既划船又跑步．(4)大雁北回，春天来了.3.将下列复合命题分解成若干个原子命题，并找出适当的联结词.(1)天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.1.2 命题公式1. 判断下列各式是否是命题公式，不是的划“×”，是的划“√”．(1)(Q→R∧S). ( )(2)((R→(Q→R)→(P→Q)). ( )(3) (P∨QR)→S. ( )(4)((?P→Q)→(Q→P)). ( )2．写出五个常用命题联结词的真值表.1.3 真值表与等价公式1.指出下列命题的成真赋值与成假赋值．(1)?(P∨?Q).(2)?P→(Q→P).2.构造真值表，判断下列公式的类型．(1)(P∧Q)∧?(P∨Q).(2) P→(P∧┑Q))∨R.3.用等值演算法验证下列各等价式．(1) ((P→Q)∧(Q→R))→(P→R)?T.(2)P→(Q∧R)?(P→Q)∧(P→R).(3)?(P∨Q)∨(?P∧Q)??P．1.4 蕴涵式及其他联结词1.试证明下列各式为重言式．(1)(P→Q)∧(Q→R)?(P→R)．(2) (P→Q)→Q?P∨Q．(3)?(P↓Q)??P↑?Q．2.将下列公式化成与之等价且仅含{┑，∨}中联结词的公式．(1) (P∨Q)∧┑P(2) (P→(Q∨┑R))∧(┑P∧Q)3.证明{?，∧}是最小全功能联结词组.4.设A、B、C为任意的三个命题公式，试问下面的结论是否正确？(1)若A∧C?B∧C，则A?B．(2)若?A??B，则A?B．(3)若A→C?B→C，则A?B．1.6 对偶与范式1.试给出下列命题公式的对偶式．(1)T∨(P∧Q)．(2)?(P∧Q)∧(?P∨Q)．2.试求下列各公式的主析取范式和主合取范式．(1) (P→(Q∧R))∧(┑P→(┑Q→R))．(2)(?(P→Q)∧Q)∨R．(3)(P→(Q∨R))∧(?P∨(Q?R)).3.试用将公式化为主范式的方法，证明下列各等价式．(1) (┑P∨Q)∧(P→R)?P→(Q∧R)(2) ┑(P?Q)?(P∧┑Q)∨(┑P∧Q)1.7 推理理论1.试用推理规则，论证下列各式．(1) ┑(P∧┑Q),┑Q∨R,┑R?┑P(2) P∨Q,Q→R,P→S,┑S?R∧(P∨Q)(3) ┑P∨Q,┑Q∨R,R→S?P→S(4) P∨Q,P→R,Q→S?R∨S第二章谓词逻辑2.1 词的概念与表示1.用谓词表达写出下列命题．(1)高斯是数学家，但不是文学家.(2)小王既是运动员也是大学生.(3)张宁和李强都是三好学生.(4)若是x奇数，则2x不是奇数.2.2 命题函数与量词1.用谓词表达式写出下列命题．(1)每个计算机系的学生都学离散数学.(2)直线A平行于直线B当且仅当直线A不相交于直线B.(3)不存在既是奇数又是偶数的自然数.(4)没有运动员不是强壮的.(5)有些有理数是实数但不是整数.(6)所有学生都钦佩某些教师.2.3 谓词公式与变元的约束1.利用谓词公式翻译下列命题． (1)没有一个奇数是偶数.(2)一个整数是奇数，如果它的平方是奇数.2. 设个体域为自然数集N ，令P(x)：x 是素数；E(x)：x 是偶数；O(x)：x 是奇数；D(x ，y)：x 整除y ．将下列各式译成汉语．(1)?x(E(x)∧D(x ，6))．(2)?x(O(x)→?y(P(x)→?D(x ，y)))．3.指出下列表达示中的自由变元和约束变元，并指明量词的辖域．(1)()()(,)()()x F x Q x y xP x R x ?∧→?∨．(2)?x(P(x ，y)∨Q(z))∧?y(R(x ，y)→ ?zQ(z))．4.设个体域为A ＝{a ，b ，c}，消去公式?xP(x)∧?xQ(x)中的量词．2.4 谓词演算的等价式与蕴含式1.试证下列等价式或蕴涵式,其中A(x),B(x)表示含x自由变量的公式,A,B 表示不含变量x（不论是自由的还是约束的）的公式.(1)（?x A(x)→B）?(?x(A(x)→B))．(2)（?x A(x)→B）??x(A(x)→B)．2.试将下列公式化成等价的前束范式．(1)?x（（┑?yP(x,y)）→(?zQ(z)→R(x))）．(2)?x(F(x)→G(x))→(?xF(x)→?xG(x))．2.5 谓词演算的推理理论1.证明下列推理．(1)所有有理数都是实数，某些有理数是整数。

离散数学第二章谓词逻辑

离散数学第二章谓词逻辑

一般来说，当多个量词同时出现时， 它们的顺序不能随意调换。
*
第二章 谓 词 逻 辑 命题函数与量词
当个体域为有限集合时，如D={a1, a2 …, an}，对任意谓词A(x)，有 xA(x)A(a1)∧A(a2)∧…∧A(an ) xA(x)A(a1)∨A(a2)∨…∨A(an )
特性谓词常作合取项，如x(M(x)∧ G(x))。
第二章 谓 词 逻 辑
命题函数与量词
*
第二章 谓 词 逻 辑 2.2 命题函数与量词
例如：在实数域上用H(x,y)表示x+y=5，则命题“对于任意的x，都存在y使得x+y=5”可符号化为：xyH(x,y)，其真值为1。若调换量词顺序后为： yxH(x,y) , 其真值为0。
*
第二章 谓 词 逻 辑 2.2 命题函数与量词
*
令S(x): x吸烟。则符号化为：
（x）(M(x)∧S(x))
令D(x): x登上过木星。则符号化为：
令Q(x):x是清华大学的学生。H(x):x是高
第二章 谓 词 逻 辑 2.2 命题函数与量词
*
小结:本节介绍了n元谓词、命题函数、全称量词和存在量词等概念。重点掌握全称量词和存在量词及量化命题的符号化。
添加标题
x(M(x) F(x)).
添加标题
第二章 谓 词 逻 辑
添加标题
命题函数与量词
*
当个体域为全体学生的集合时：
01
令P(x): x要参加考试。则（2）符号化为
02
xP(x).
03
当个体域为全总个体域时：
04
令S(x): x是学生。则（2）符号化为
05
x(S(x) P(x)).
离散数学(2.3谓词公式与翻译)

离散数学(2.3谓词公式与翻译)

离散数学(Discrete Mathematics)
1
第二章 谓词逻辑（Predicate Logic）
2.1谓词的概念与表示(Predicate and its expression) 2.2命题函数与量词(Propositional functions & Quantifiers) 2.3谓词公式与翻译(Predicate formulae) 2.4变元的约束(Bound of variable) 2.5谓词演算的等价式与蕴含式(Equivalences &
implications of predicate calculus)
2.6前束范式(Prenex normal form)
2.7谓词演算的推理理论(Inference theory of predicate calculus)
2
第二章 谓词逻辑（Predicate Logic）
2.3谓词公式与翻译(Predicate formulae)
5
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
• 例2：在谓词逻辑中将下列命题符号化. （1）所有运动员都钦佩某些教练. （2）有些运动员不钦佩教练. 设：L(x):x是运动员 J(y):y是教练 A(x,y):x钦佩y (1) (x)(L(x) （y)(J(y)∧A(x,y)))
(Q(δ,0)∧(Q(δ , x a)Q(ε,
f ( x) f ()a ) ). ))
8
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
离散数学 谓词逻辑

离散数学 谓词逻辑

中原子谓词公式，简称原子公式。 下面，由原子公式出发，给出Lp中的合式 谓词公式的归纳定义。
定义2.2.3 合式谓词公式当且仅当由下列规 则形成的符号串 ① 原子公式是合式谓词公式； ② 若A是合式谓词公式，则(A)是合式谓 词公式； ③ 若A，B是合式谓词公式，则(A∧B)， (A∨B)，(A→B)和(AB)都是合式谓词公式； ④ 若A是合式谓词公式，x是个体变元，则 (x)A、(x)A都是合式谓词公式； ⑤ 仅有有限项次使用①、②、③和④形成 的才是合式谓词公式。
当n=1时，称一元谓词；当n=2时，称为二 元谓词，…。特别地，当n=0，称为零元谓词。
零元谓词是命题，这样命题与谓词就得到了统
一。
n元谓词不是命题，只有其中的个体变元用 特定个体或个体常元替代时，才能成为一个命 题。但个体变元在哪些论域取特定的值，对命 题的真值极有影响。
例如，令S(x)：x是大学生。若x的论域为 某大学的计算机系中的全体同学，则S(x)是真 的；若x的论域是某中学的全体学生，则S(x)是 假的；若x的论域是某剧场中的观众，且观众中 有大学生也有非大学生的其它观众，则S(x)是 真值是不确定的。
④ 有的自然数是素数。
解 令S(x)：x是大学生，L(x)：x热爱祖国，
N(x)：x是自然数，R(x)：x是实数，I(x)：x有
远大理想，P(x)：x是素数。
则例中各命题分别表示为：
①(x)(S(x)L(x))
③(x)(S(x)I(x))
②(x)(N(x)R(x))
④(x)(N(x)P(x))
③找出恰当量词。应注意全称量词(x)后 跟条件式，存在量词(x)后跟合取式。 ④用恰当的联结词把给定命题表示出来。
例2.2.2 将命题“没有最大的自然数”符号 化。 解 命题中“没有最大的”显然是对所有的 自然数而言，所以可理解为“对所有的x，如果 x 是自然数，则一定还有比 x 大的自然数”，再 具体点，即“对所有的 x 如果 x 是自然数，则一 定存在 y ， y 也是自然数，并且 y 比 x 大”。令 N(x):x 是自然数， G(x,y):x 大于 y ，则原命题表 示为：(x)(N(x)(y)(N(y)G(y,x)))。
左孝凌离散数学课件2.1谓词概念与表示-2.2命题函数与量词

左孝凌离散数学课件2.1谓词概念与表示-2.2命题函数与量词


①若x，y，z ∈ R（实数），且P(x,y)：x小于y，则这个式子表 示“若x小于y且y小于z，则x小于z”。这是一永真式。
②若 x，y，z ∈人，且P(x,y)解释为：x为y的儿子，则这个式 子表示“若x为y的儿子且y是z的儿子则x是z的儿子”。这是一 个永假式。
③若x，y，z ∈地面上的房子，且P(x,y)：x距离y 10米，则这 个式子表示“x距离y10米且y距离z10米则x距离z10米”。这 个命题的真值将由x，y，z的具体位置而定，它可能为T， 也可能为F。
的取值范围有关。
2.2命题函数与量词
三、量词 • 量词：全称量词()和存在量词() 1.全称量词：用来表达“一切”、“所有”、“凡”、
“每一个”、“任意”等词，用符号“” 表示，
– ｘ表示对个体域里的所有个体 – ｘＦ(ｘ)表示个体域里的所有个体具有性质F. – 符号“”称为存在量词.
15
2.2命题函数与量词
18
2.2命题函数与量词
解: (1)令Q(x): x是有理数。则（1）符号化为ｘQ(x)。 （2）当个体域为人类集合时：
令G(x): x活百岁以上。则（2）符号化为xG(x)。
当个体域为全总个体域时： 令M(x): x是人。则（2）符号化为
x(M(x) ∧ G(x))
19
2.2命题函数与量词
三、量词
2.1谓词的概念与表示
一、基本概念
1. 客体 2. 谓词 3. 表示方法：谓词用大写字母，客体用小写字母 例1、采用谓词表示下列命题
1) 地球绕着太阳转； 2）济南位于北京与南京之间； 3）张三是大学生，李四是工人 解：1）设：L:……绕着……转，a：地球；b：太阳
即，L(a，b) 2）设：L：…位于…与…之间，a：济南；b：北京；c：南京
谓词逻辑 离散数学

谓词逻辑 离散数学

11
实例3
例3 在谓词逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 解 注意：题目中没给个体域，一律用全总个体域 (1) 令F(x)：x为正数，G(y)：y为负数, L(x,y)：x>y x(F(x)y(G(y)L(x,y))) 或者 xy(F(x)G(y)L(x,y)) (2) 令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：x>y x(F(x)y(G(y)L(x,y))) 或者 xy(F(x)G(y)L(x,y)) 可见：命题符号化在谓词逻辑中不是唯一的。
12
实例4
例4 在一阶逻辑中将下面命题符号化 (1) 没有不呼吸的人 (2) 不是所有的人都喜欢吃糖 解 (1) F(x): x是人, G(x): x呼吸
x(F(x)G(x))
x(F(x)G(x))
(2) F(x): x是人, G(x): x喜欢吃糖 x(F(x)G(x)) x(F(x)G(x))
21
约束变元换名（2/2）
例 对(x)(P(x)R(x,y))Q(x,y)换名。 解：可换名为：(z)(P(z)R(z,y))Q(x,y)。 但是不能换名为：(y)(P(y)R(y,y))Q(x,y)、 (z)(P(z)R(x,y))Q(x,y)。
22
自由变元代入（1/2）
10
实例2
例 2 在谓词逻辑中将下面命题符号化 (1) 人都爱美 (2) 有人用左手写字 个体域分别为 (a) D为人类集合 (b) D为全总个体域 解 (a) (1) xG(x), G(x)：x爱美 (2) xG(x), G(x)：x用左手写字 (b) F(x)：x为人，G(x)：x爱美 (3) x(F(x)G(x)) （对 ，特性谓词做蕴含的前件） (4) x(F(x)G(x)) （对 ，特性谓词做合取项） 1. 引入特性谓词F(x) ，用于限制全总个体域的范围； 2. (3),(4)是谓词逻辑中两个“基本”公式。

离散数学知识点总结

离散数学知识点总结离散数学是数学中的一个分支，研究离散对象及其关系的数学理论。

它与连续数学形成鲜明的对比，连续数学主要研究连续对象和其性质。

离散数学在计算机科学、信息科学、电子工程等领域具有重要的应用价值。

下面将对离散数学的主要知识点进行总结。

1.命题逻辑：命题逻辑研究由命题符号组成的复合命题及其逻辑关系。

其中命题是一个陈述性的语句，可以是真或假。

命题逻辑包括命题的逻辑运算、真值表、命题的等价、充分必要条件等。

2.谓词逻辑：谓词逻辑是对命题逻辑的扩充，引入了量词、谓词和项。

它的研究对象是命题函数，可以表示个体之间的关系。

谓词逻辑包括谓词的运算、量词的运算、公理化和推理规则等。

3.集合论：集合论是研究集合及其操作的数学分支。

集合是一种由确定的对象组成的整体。

集合论包括集合的基本运算（交、并、差、补）、集合的关系（包含、相等、子集、真子集）以及集合的运算律和推导定理等。

5.组合数学：组合数学是研究物体的组合与排列问题的数学分支。

它包括排列、组合、分配、生成函数等内容，经常应用于计数和概率问题中。

6.图论：图论是用来描述物体间其中一种关系的图形结构的数学理论。

它研究的对象是由顶点和边构成的图，包括无向图、有向图、带权图等。

图论研究的内容包括图的性质、连通性、路径、回路、树、图的着色等。

7.代数系统：代数系统是一种由一组元素及其相应的运算规则构成的数学结构。

常见的代数系统有群、环、域、格等，它们分别研究了集合上的不同运算规律和结构。

8.布尔代数：布尔代数是一种应用于逻辑和计算机的代数系统。

它以真和假为基础，通过逻辑运算（与、或、非）构成了布尔代数。

布尔代数在计算机硬件设计和逻辑推理中广泛应用。

9.图的同构与图的着色：图的同构是指两个图在结构上相同，也就是说，它们具有相同的顶点和边的连接关系。

图的同构判断是一个NP难问题，需要借助于图的着色等方法来判断。

图的着色是给图的顶点分配颜色，使得相邻顶点的颜色不同。

离散数学中,谓词公式和命题公式的区别

离散数学是一门研究离散对象及其性质的数学分支，它在计算机科学、信息技术以及工程领域具有重要的应用价值。

在离散数学中，谓词公式和命题公式是两个重要的概念，它们在逻辑推理和证明中起着至关重要的作用。

本文将对谓词公式和命题公式进行详细的比较与分析。

1. 谓词公式谓词公式是一种含有变量的复合命题，它通常用来描述对象之间的关系或者属性。

谓词公式由谓词符号和变量组成，例如P(x)、Q(x, y)等。

在谓词公式中，变量可以取代具体的对象，从而得到一个具体的命题。

谓词公式一般可以表示为∀x(∃yP(x, y))，其中∀表示全称量词，∃表示存在量词，P(x, y)表示谓词公式。

谓词公式的真假取决于变量的取值范围和具体的谓词定义。

谓词公式的真假可以通过逻辑运算和推理来确定，通常需要使用证明方法或者真值表等工具来进行验证。

2. 命题公式命题公式是一个不含变量的简单命题，它通常用来表示一个完整的陈述或者断言。

命题公式可以是一个简单的原子命题，也可以是多个原子命题通过逻辑连接词组合而成的复合命题。

“今天下雨”、“2加2等于4”等都可以看作是命题公式。

命题公式的真假只取决于公式本身的内容，它只有两种取值：真和假。

命题公式可以通过真值表的方法来验证其真假，并且可以使用逻辑等价和逻辑推理来进行推导和证明。

3. 谓词公式和命题公式的区别从上面的比较可以看出，谓词公式和命题公式在以下几个方面有着明显的区别：3.1 变量的使用谓词公式使用变量来表示对象之间的关系，而命题公式不含有变量，它是一个固定的陈述或者断言。

谓词公式可以根据变量的取值范围得到不同的命题，而命题公式的真假只取决于公式本身的内容。

3.2 真假的判断谓词公式的真假取决于变量的取值范围和具体的谓词定义，需要使用证明方法或者真值表来进行验证；而命题公式的真假只取决于公式本身的内容，可以通过真值表的方法来验证其真假，并且可以使用逻辑等价和逻辑推理来进行推导和证明。

3.3 表达的含义谓词公式通常用来描述对象之间的关系或者属性，它具有一定的泛化和普适性；而命题公式通常用来表示一个完整的陈述或者断言，它具有明确的含义和指向性。

离散数学(2.2命题函数与谓词)

19
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
小结:本节介绍了n元谓词、命题函数、全称量 词和存在量词等概念。重点掌握全称量词和 存在量词及量化命题的符号化。 作业：P59 （2）单数
20
x(M(x) F(x)).
11
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers) (2) 当个体域为全体学生的集合时： 令P(x): x要参加考试。则（2）符号化为xP(x). 当个体域为全总个体域时： 令S(x): x是学生。则（2）符号化为 x(S(x) P(x)). (3) 当个体域为全体整数的集合时： 令P(x): x是正的。N(x): x是负的。则（3）符号化为 x(P(x)∨N(x)) . 当个体域为全总个体域时： 令I(x): x是整数。则（3）符号化为 x(I(x)(P(x)∨N(x))).
8
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
• 在命题函数中，客体变元的取值范围称为 个体域，又称之为论域。个体域可以是有 限事物的集合，也可以是无限事物的集合。 • 全总个体域：宇宙间一切事物组成的个体 域称为全总个体域。
10
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)

离散数学 第二章 谓词逻辑-2-3节


河南工业大学离散数学课程组
个体域 (论域)
个体域的给定形式有两种： （1）具体给定。
如：{a,b,c}
（2）全总个体域/任意域。 所有个体域的总和，即世间一切万物的主体。
河南工业大学离散数学课程组 3、量词：在命题中表示客体数量的词，称之为量词。
：全称量词 ：存在量词
Anyone
Exit
河南工业大学离散数学课程组
例
（2）每一个大学生都会说英语； 无特性谓词： Q(x):x会说英语。(x)Q(x) x∈{大学生}
Q(x):x会说英语。U(x):x是大学生。 (x) (U(x) → Q(x))
（3）有一些自然数是素数。 无特性谓词：T(x)：x是素数。(x) T(x) x∈{自然数}
一、谓词演算的原子公式
定义2-3.1 ：称n元谓词P(x1,x2,...,xn)为原子谓词公式， 简称原子公式。即不出现命题联结词和量词。 例如 P、Q(x)、A(x,f(x),a)都是谓词演算的原子公式。
二、谓词演算的合式公式(WFF)(Well Formed formulas) 定义2-3.2：谓词合式公式递归定义如下： (1)原子谓词公式是合式公式。
河南工业大学离散数学课程组
将命题函数→命题的两种方法
1）将变元取定具体的值，如P(a),P(b)。 2）将谓词量化。如(x)P(x), (x)P(x)。
河南工业大学离散数学课程组
命题函数举例
例.设S(x)表示“x学习很好”, W(x)表示“x工作很 好”, A(x)表示“ x身体好” S(x) 表示“x学习不是很好”, S(x) ∧W(x) 表示“x学习和工作都很好”。 A(x)→(S(x)∧W(x)) 表示“如果x身体不好，则x的学习与工作都不 会好”。 S(x), W(x)是简单命题函数, 而S(x), S(x)W(x), A(x)→(S(x)∧W(x))是 复合命题函数。

离散数学

第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题的表示（一个命题标识符（比如P）表示确定的命题）重点：如何判断语句是否为命题。

1.2 联结词否定⌝合取∧析取∨条件→双条件↔重点：五种联结词的含义、真值表1.3 命题公式与翻译命题公式符号化：所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。

命题符号化的重要性命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。

重点：命题的符号化符号化应该注意下列事项:①确定给定句子是否为命题。

②句子中连词是否为命题联结词。

③要正确地表示原子命题和适当选择命题联结词。

1.4 真值表与等价公式真值表的构造方法(1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价关系的含义等价式的判别方法•真值表法•等价演算法基本等价式（必须掌握）(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R重点：等价式的证明、基本等价式1.5 重言式与蕴含式重言式或永真公式定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

离散数学谓词

离散数学谓词
谓词是离散数学中的一个重要概念，它是用来描述一个命题中的主语和谓语之间的关系的。

在离散数学中，谓词可以分为两类：命题谓词和函数谓词。

命题谓词是指一个命题中的主语和谓语之间的关系，它可以是真或假。

例如，“x是偶数”就是一个命题谓词，当x为偶数时，该命题为真，否则为假。

函数谓词是指一个函数中的参数和返回值之间的关系，它可以是任意类型的。

例如，“f(x)=x+1”就是一个函数谓词，当x为任意数时，该函数返回值为x+1。

在离散数学中，谓词可以用来描述集合、关系、函数等概念。

例如，我们可以用谓词来描述一个集合中的元素是否满足某个条件，或者用谓词来描述两个元素之间的关系是否成立。

谓词在离散数学中有着广泛的应用，它可以用来描述逻辑、集合论、图论等领域中的概念。

例如，在逻辑中，我们可以用谓词来描述命题的真假性；在集合论中，我们可以用谓词来描述集合中元素的性质；在图论中，我们可以用谓词来描述图中节点之间的关系。

谓词是离散数学中一个非常重要的概念，它可以用来描述各种各样的数学概念和问题。

在学习离散数学时，我们需要深入理解谓词的概念和应用，才能更好地掌握离散数学的知识。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Quantifiers)
• 2.2.1 命题函数 (Propositional functions) • 2.2.2 量词(Quantifiers)
3
第二章 谓词逻辑（Predicate Logic）
• 2.2.1 命题函数 (Propositional functions)
2.2命题函数与量词(Propositional functions & Quantifiers)
6
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
• 解:(1) 设F(x): x是素数. G(x): x是偶数. 则命题符号化为： F(2)∧G(2) (2) 设L(x,y) ：x大于y. 则命题符号化为： L(2,3) L(2,4) (3) 设 H(x,y): x比y高. a:张明 b:李民 c：赵亮 则命题符号化为： H(a,b)∧H(b ,c)H(a,c) 注意:命题函数中,客体变元在哪些范围内取特定的值,对 命题的真值极有影响.
12
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers) 2.存在量词(The Existential Quantifiers) 对日常语言中的“有一个”、“有的”、“存在着”、“至 少 有一个”、 “存在一些”等词，用符号“” 表示， ｘ 表 示存在个体域里的个体， ｘＦ(ｘ)表示存在个体域里 的个体具有性质F.符号“”称为存在量词. 例4：在谓词逻辑中将下列命题符号化. （1）一些数是有理数。 （2）有些人活百岁以上。
4
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
• H(x)、L(x,y) 、A(x,y,z)本身并不是一个命题.只有用 特定的客体取代客体变元x,y,z后，它们才成为命题。我 们称H(x)、L(x,y) 、A(x,y,z)为命题函数。一般地我们 有 • 定义2.2.1:由一个谓词H和n个客体变元组成的表达式 H(x1, x2 , …, xn)称为n元简单命题函数. • 由定义可知, n元谓词就是有n个客体变元的命题函数.当 n=0时,称为0元谓词.因此,一般情况下,命题函数不是命题; 特殊情况0元谓词就变成一个命题.
设谓词H表示“是劳动模范”, a表示客体名称张明, b表示 客 体名称李华,c表示客体名称这只老虎，那么H(a) 、 H(b)、 H(c)表示三个不同的命题, 但它们有一个共同的形式,即 H(x).一般地， H(x)表示客体x具有性质H。这里x表示 抽象的或泛指的客体，称为客体变元，常用小写英文字 母 x,y,z, …表示。相应地，表示具体或特定的客体的词称为 客体常项，常用小写英文字母a,b,c, …表示。 同理，客体变元x，y具有关系L，记作L(x,y);客体变元 x,y,z具有关系A，记作A(x,y,z).
5
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
•
复合命题函数:由一个或几个简单命题函数以及逻辑联 结词组合而成的表达式. 例1:若x的学习好,则x的工作好 设S(x):x学习好；W(x):x工作好 则有S(x) W(x) 例2:将下列命题用0元谓词符号化. (1) 2是素数且是偶数. (2) 如果2大于3,则2大于4. (3) 如果张明比李民高, 李民比赵亮高,则张明比赵亮高.
15
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
（ 3 ）约定以后如不指定个体域，默认为全总个 体域。对每个客体变元的变化范围,用特性谓词 加以限制. 特性谓词:限定客体变元变化范围的谓词(如例3中 的M（x）). 一般而言，对全称量词，特性谓词常作蕴含的前 件，如（x）(M(x) F(x))；对存在量词，特 性 谓词常作合取项，如（ x）(M(x)∧ G(x)).
19
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
小结:本节介绍了n元谓词、命题函数、全称量 词和存在量词等概念。重点掌握全称量词和 存在量词及量化命题的符号化。 作业：P59 （2）单数
20
10
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
例3：在谓词逻辑中将下列命题符号化. （1）凡是人都呼吸。 （2）每个学生都要参加考试。 (3) 任何整数或是正的或是负的。 解: (1) 当个体域为人类集合时： 令F(x): x呼吸。则（1）符号化为xF(x) 当个体域为全总个体域时： 令M(x): x是人。则（1）符号化为
9
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
• 2.2.2 量词(Quantifiers)
• 量词：分为全称量词()和存在量词() 1.全称量词(The Universal Quantifiers) 对日常语言中的“一切”、“所有”、“凡”、“每 一 个”、“任意”等词，用符号“” 表示， ｘ表示 对个体域里的所有个体， ｘＦ(ｘ)表示个体域 里的所有个体具有性质F.符号“”称为全称量词.
Quantifiers)
（x）(M(x) F(x))
18
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
（2） 令S(x): x吸烟。则符号化为： （x）(M(x)∧S(x)) （3） 令D(x): x登上过木星。则符号化为： （x）(M(x)∧D(x)) （4）令Q(x):x是清华大学的学生。H(x):x是高 素质的。则符号化为： （x）(Q(x) H(x))
7
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
例如: H(x,y)∧H(y ,z)H(x,z)
• 若H(x,y)解释为: x大于y,当x,y,z都在实数中取值时,
则这个式子表示“若x大于y 且y 大于z，则x大于 z” 。这是一个永真式。 如果H(x,y)解释为: “x是y的儿子”, 当x,y,z都指人 时，则这个式子表示“若x为y的儿子 且y 是z的儿 子，则x是z的儿子” 。这是一个永假式。 如果H(x,y)解释为: “x距y10米”, 当x,y,z为平面上 的点，则这个式子表示“若x距y10米且y距z10米， 则x距z10米” 。这个命题的真值将由x,y,z的具体 位置而定，它可能是1，也可能是0。
13
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
解: (1)令Q(x): x是有理数。则（1）符号化为ｘQ(x)。 （2）当个体域为人类集合时：
令G(x): x活百岁以上。则（2）符号化为xG(x)。
意 谓词A(x),有
Quantifiers)
(x) A(x)A(a1)∧A(a2)∧…∧A(an ) （x）A(x)A(a1)∨A(a2)∨…∨A(an )
17
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
例6：在谓词逻辑中将下列命题符号化. （1）所有的人都长头发。 （2）有的人吸烟。 （3）没有人登上过木星。 （ 4 ）清华大学的学生未必都是高素质的。 解：令 M(x): x是人。（特性谓词） （1） 令F(x): x长头发。则符号化为：
8
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
• 在命题函数中，客体变元的取值范围称为 个体域，又称之为论域。个体域可以是有 限事物的集合，也可以是无限事物的集合。 • 全总个体域：宇宙间一切事物组成的个体 域称为全总个体域。
当个体域为全总个体域时： 令M(x): x是人。则（2）符号化为 x(M(x)
∧ G(x))
14
第二章 谓词逻辑（Predicate Logic）
2.2命题函数与量词(Propositional functions &
Quantifiers)
有时需要同时使用多个量词。 例5. 命题“对任意的x,存在y, 使得x+y=5”, 取个体域为 实 数集合,则该命题符号化为: x y H(x,y). 其中H(x,y): x+y=5. 这是个真命题. 3. 使用量词时应注意的问题 （1 ）在不同的个体域，同一命题的符号化形式可能相 同也可能不同。 （2 ）在不同的个体域，同一命题的真值可能相同也可 能不同。 ( 如 ,R(x) 表示 x 为大学生。如果个体域为大 学里的某个班级的学生，则 x R(x)为真；若个体域 为中学里的某个班级的学生，则x R（x）为假.).
离散数学(Discrete Mathematics)
1