离散数学(第2.1)陈瑜解析.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * 主要内容 量词化逻辑 1.谓词 2.量词 3.全总个体域 4.自由变元与约束变元 5.两个量词量化谓词的真值 第二章:一阶谓词逻辑 命题逻辑是数理逻辑的基础，主要研究命题和命题演算。原子命题是命题演算的基本单位，并把它看作是不可再分解。这就带来了命题逻辑的局限性。命题逻辑研究的范围限制在命题及其外部关系上，无法研究命题内部的成份、结构，命题之间所具有的逻辑特征（如，共同性和差异性） 例1.1 设基本命题，P：李明是大学生；Q：王芳是大学生 R：松树是植物。 很明显，P与Q在内部关系上，应该比R密切得多。然而，命题逻辑无法反映这种区别，也无法反映P、Q间的共同性。 第二章:一阶谓词逻辑 命题逻辑是数理逻辑的基础，主要研究命题和命题演算。原子命题是命题演算的基本单位，并把它看作是不可再分解。这就带来了命题逻辑的局限性。命题逻辑研究的范围限制在命题及其外部关系上，无法研究命题内部的成份、结构，命题之间所具有的逻辑特征（共同性和差异性） 例1.1 设基本命题，P：李明是大学生；Q：王芳是大学生 R：松树是植物。 很明显，P与Q在内部关系上，应该比R密切得多。然而，命题逻辑无法反映这种区别，也无法反映P、Q间的共同性。 §2.1 量词化逻辑——谓词和量词 一、谓词 Predicate 在对命题的内部逻辑关系进行研究时，把基本命题分成客体(个体）和谓词。 客体——命题中所描述的对象。（命题中的主语，客观实体，可以独立存在的物体）。 谓词——命题中描述的个体性质（特征）或关系的部分。 谓词一般用大写字母（串）表示; 个体用小写字母表示。 §2.1 量词化逻辑——谓词和量词 一、谓词 Predicate 在对命题的内部逻辑关系进行研究时，把基本命题分成客体(个体）和谓词。 客体——命题中所描述的对象。（命题中的主语，客观实体，可以独立存在的物体）。 谓词——命题中描述的个体性质（特征）或关系的部分。 谓词一般用大写字母（串）表示; 个体用小写字母表示。 §2.1 量词化逻辑——谓词和量词 一、谓词 Predicate 在对命题的内部逻辑关系进行研究时，把基本命题分成客体(个体）和谓词。 客体——命题中所描述的对象。（命题中的主语，客观实体，可以独立存在的物体）。 谓词——命题中描述的个体性质（特征）或关系的部分。 谓词一般用大写字母（串）表示; 个体用小写字母表示。 与谓词相联系的个体的数目，就是谓词的元数。 ①描述一个个体的性质的谓词叫“一元谓词”。 ②描述两个个体间的关系的谓词叫“二元谓词”。 如A：‘…比…大’ 命题4比3大表示成A（4，3） ③描述三个个体间的关系的谓词叫“三元谓词”。 如B：‘…在…和…之间’ B（n,c,z）：内江在成都与重庆之间。 定义2.1：设D是由客体构成的称为个体域的非空集合，以D中元素为值的变元称为客体变元。由形如 谓词标识符（客体变元1，客体变元2，…，客体变元n） 构成的、其值为“真”或“假”的表达式，称为n元谓词。 即n元谓词是描述n个个体间的关系。 与谓词相联系的个体的数目，就是谓词的元数。 ①描述一个个体的性质的谓词叫“一元谓词”。 ②描述两个个体间的关系的谓词叫“二元谓词”。 如A：‘…比…大’ 命题4比3大表示成A（4，3） ③描述三个个体间的关系的谓词叫“三元谓词”。 如B：‘…在…和…之间’ B（n,c,z）：内江在成都与重庆之间。 定义2.1：设D是由客体构成的称为个体域的非空集合，以D中元素为值的变元称为客体变元。由形如 谓词标识符（客体变元1，客体变元2，…，客体变元n） 构成的、其值为“真”或“假”的表达式，称为n元谓词。 即n元谓词是描述n个个体间的关系。 定义2.1′：设D为非空的个体域，定义在Dn(表示n个客体都在个体域D上取值)上取值于｛0,1｝上的n元函数，称为n元命题函数或n元谓词,记为P(x1,x2,…,xn)。此时，客体变元x1,x2,…,xn的定义域都为D， P(x1,x2,…,xn)的值域为{0，1｝。 注意：n元谓词中的客体或客体变元是有一定次序的。 如A（4，3）为T，A（3，4）为F。 如果谓词中为客体变元,我们称为谓词填式(谓词命名式,n元命题函数)。 如S(x),A(x,y)，不能判断真和假。 只有将具体的客体代替客体变元，才能判断真和假。 定义2.1′：设D为非空的个体域，定义在Dn(表示n个客体都在个体域D上取值)上取值于｛0,1｝上的n元函