离散数学-2-3谓词公式与翻译.ppt

1,第二章谓词逻辑,2-3 谓词公式与翻译 授课人：李朔 Email:,2,一、谓词公式,简单命题函数与逻辑联结词可以组合成一些命题表达式 与命题公式概念类似，不是所有谓词表达式都可以成为谓词公式并进行谓词演算，下面介绍谓词的合式公式的概念。 谓词演算原子公式：把A(x1,x2,xn)称作谓词演算的原子公式（原子谓词公式），其中x1,x2,xn是客体变元。因此命题、命题变元、谓词填式和命题函数都是原子谓词公式。 如:Q（可以是命题或命题变元），A(a), A(x,y,z), A(a,y)。,3,一、谓词公式,定义2.2.1按下列规则构成的表达式称为谓词演算的合式公式，简称谓词公式。 原子谓词公式是合式公式。 若A是合式公式，则A是合式公式。 若A和B是合式公式，则(AB)，(AB)， (AB)和(AB)是合式公式。 如果A是合式公式，x是A中出现的任意个体变 元，则(x)A，(x)A是合式公式。 只有有限次地应用、所得的公式是合式公式。,4,二、命题翻译,谓词公式也有以下约定： 最外层的括号可以省略。 如果按、在运算中的优先级别，省略括号后不改变原来的运算次序，可以省略括号，但量词后面括号不能省略。 下面举例说明如何用谓词公式表达自然语言中的命题。 例题1 并非每个实数都是有理数。 解：设R(x)：x是实数 Q(x)：x是有理数 该命题符号化为：(x)(R(x)Q(x),5,二、命题翻译,例题2 没有不犯错误的人。 解：设M(x)：x是人 F(x)：x犯错误 此命题可以理解为：存在一些人不犯错误，这句话是不对的。此时，号化为： (x) (M(x)F(x) ) 也可以理解为：任何人都是要犯错误的。此时，符号化为： (x) (M(x)F(x),6,二、命题翻译,例题3 尽管有人聪明，但未必一切人都聪明。(P(x),M(x) 解：x(M(x)P(x)(x)(M(x)P(x) 例 并不是所有的兔子都比所有的乌龟跑得快。 解：设F(x)：x是兔子。 G(x)：x是乌龟。 H(x,y)：x比y跑得快。 该命题符号化为： (x) (y) (F(x)G(y)H(x,y),7,二、命题翻译,例题4 这只大红书柜摆满了那些古书。 解法一：设F(x,y): x摆满了y R(x):x是大红书柜 Q(y):y是古书。 a:这只 b:那些 R(a)Q(b)F(a,b),8,二、命题翻译,解法二：设A(x): x是书柜 B(x): x是大的 C(x): x是红的 D(y): y是古老的 E(y): y是图书 F(x,y): x摆满了y a:这只 b:那些 A(a)B(a)C(a)D(b)E(b)F(a,b),9,二、命题翻译,由例题4可知，由命题翻译成谓词演算公式，机动性很大，对个体刻划尝试的不同就可翻译成不同的谓词公式。 一般的，对日常语言，我们可以有一个大体的准则，根据这些准则可以进行命题的翻译。 名词：专用名词（如南京、刘翔等）是客体 通用名词（如熊猫、人）一般是谓词,10,二、命题翻译,代词：人称代词（如你、我、她/他等）是客体 指示代词（如这个、那个）是客体 不定代词 （如任何、每个、有些）是量词 形容词：一般是谓词。 数词：一般是量词。 动词：一般是谓词。 副词：一般与所修饰的动词合并为谓词，不再分解 连接词：一般是命题联结词 以上只是一般准则，具体应用时会有例外,11,三、命题翻译练习,练习1：将下列命题符号化，并讨论真值。 令M(x) :x是人 (1)所有的人都长着黑头发。令F(x):x长着黑头发 (2)有的人登上过月球。令G(x):x登上过月球 (3)没有人登上过木星。令H(x):x登上过木星 (4)在美国留学的学生未必都是亚洲人。 令F(x):x是在美国留学的学生,G(x):x是亚洲人,12,三、命题翻译练习,(1)令F(x):x长着黑头发。 命题(1)符号化为 x(M(x)F(x) 设a为某个金发姑娘，则M(a)为真，而F(a)为假，所以M(a)F(a)为假，故所表示的命题为假。 (2)令G(x):x登上过月球。 命题(2)的符号化形式为 x(M(x)G(x) 设a是1969年登上月球完成阿波罗计划的一个美国人，则M(a)G(a)为真，所以表示的命题为真。,13,三、命题翻译练习,(3)令H(x):x登上过木星。 命题(3)符号化形式为 x(M(x)H(x) 到目前为止，对于任何一个人(含已经去世的人)都还没有登上过木星，所以对任何人a，M(a)H(a)均为假，因而x(M(x)H(x)为假，所以表示的命题为真。 (4)令F(x):x是在美国留学的学生,G(x):x是亚洲人。 命题(4)符号化形式为 x(F(x)G(x) 这个命题也为真,14,三、命题翻译练习,例 将下列命题符号化: (1) 兔子比乌龟跑得快。 (2) 有的兔子比所有的乌龟跑得快。 (3) 并不是所有的兔子都比乌龟跑得快。 (4) 不存在跑得同样快的两只兔子。 令F(x):x是兔子，G(y):y是乌龟， H(x,y):x比y跑得快，L(x,y):x与y跑得一样快,15,三、命题翻译练习,解:因为本例中出现二元谓词，因而引入两个客体变元x与y.令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快，L(x,y):x与y跑得一样快。这4个命题分别符号化为 xy(F(x)G(y)H(x,y) x(F(x) y(G(y)H(x,y) xy(F(x)G(y)H(x,y) xy(F(x)F(y)L(x,y) 还可以符号化为xy(F(x)G(y)H(x,y) 还可以符号化为xy(F(x)F(y)L(x,y),16,本课小结,谓词公式 命题翻译,17,课后