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

《离散数学-2-3谓词公式与翻译》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词逻辑2-3谓词公式与翻译授课人：李朔Email:chn.nj.ls@gmail.com1一、谓词公式简单命题函数与逻辑联结词可以组合成一些命题表达式与命题公式概念类似，不是所有谓词表达式都可以成为谓词公式并进行谓词演算，下面介绍谓词的合式公式的概念。谓词演算原子公式：把A(x1,x2,…,xn)称作谓词演算的原子公式（原子谓词公式），其中x1,x2,…,xn是客体变元。因此命题、命题变元、谓词填式和命题函数都是原子谓词公式。如:Q（可以是命题或命题变元），A(a),A(x,y,z),A(a,y)。2一、谓词公

2、式定义2.2.1按下列规则构成的表达式称为谓词演算的合式公式，简称谓词公式。⑴原子谓词公式是合式公式。⑵若A是合式公式，则¬A是合式公式。⑶若A和B是合式公式，则(A∧B)，(A∨B)，(A→B)和(A↔B)是合式公式。⑷如果A是合式公式，x是A中出现的任意个体变元，则(x)A，(x)A是合式公式。⑸只有有限次地应用⑴、⑵、⑶、⑷所得的公式是合式公式。3二、命题翻译谓词公式也有以下约定：⑴最外层的括号可以省略。⑵如果按¬、∧、∨、→、↔在运算中的优先级别，省略括号后不改变原来的运算次序，可以省略括号，但量词后面括号

3、不能省略。下面举例说明如何用谓词公式表达自然语言中的命题。例题1并非每个实数都是有理数。解：设R(x)：x是实数Q(x)：x是有理数该命题符号化为：¬(x)(R(x)→Q(x))4二、命题翻译例题2没有不犯错误的人。解：设M(x)：x是人F(x)：x犯错误此命题可以理解为：存在一些人不犯错误，这句话是不对的。此时，号化为：¬(x)(M(x)∧¬F(x))也可以理解为：任何人都是要犯错误的。此时，符号化为：(x)(M(x)→F(x))5二、命题翻译例题3尽管有人聪明，但未必一切人都聪明。(P(x),M(x))解：

4、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))6二、命题翻译例题4这只大红书柜摆满了那些古书。解法一：设F(x,y):x摆满了yR(x):x是大红书柜Q(y):y是古书。a:这只b:那些R(a)∧Q(b)∧F(a,b)7二、命题翻译解法二：设A(x):x是书柜B(x):x是大的C(x):x是红的D(y):y是古老的E(y)

5、:y是图书F(x,y):x摆满了ya:这只b:那些A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(a,b)8二、命题翻译由例题4可知，由命题翻译成谓词演算公式，机动性很大，对个体刻划尝试的不同就可翻译成不同的谓词公式。一般的，对日常语言，我们可以有一个大体的准则，根据这些准则可以进行命题的翻译。名词：专用名词（如南京、刘翔等）是客体通用名词（如熊猫、人）一般是谓词9二、命题翻译代词：人称代词（如你、我、她/他等）是客体指示代词（如这个、那个）是客体不定代词（如任何、每个、有些）是量词形容词：一般是谓词。数词：一般

6、是量词。动词：一般是谓词。副词：一般与所修饰的动词合并为谓词，不再分解连接词：一般是命题联结词以上只是一般准则，具体应用时会有例外10三、命题翻译练习练习1：将下列命题符号化，并讨论真值。令M(x):x是人(1)所有的人都长着黑头发。令F(x):x长着黑头发(2)有的人登上过月球。令G(x):x登上过月球(3)没有人登上过木星。令H(x):x登上过木星(4)在美国留学的学生未必都是亚洲人。令F(x):x是在美国留学的学生,G(x):x是亚洲人11三、命题翻译练习(1)令F(x):x长着黑头发。命题(1)符号化为x(M

7、(x)→F(x))<1>设a为某个金发姑娘，则M(a)为真，而F(a)为假，所以M(a)→F(a)为假，故<1>所表示的命题为假。(2)令G(x):x登上过月球。命题(2)的符号化形式为x(M(x)∧G(x))<2>设a是1969年登上月球完成阿波罗计划的一个美国人，则M(a)∧G(a)为真，所以<2>表示的命题为真。12三、命题翻译练习(3)令H(x):x登上过木星。命题(3)符号化形式为┐x(M(x)∧H(x))<3>到目前为止，对于任何一个人(含已经去世的人)都还没有登上过木星，所以对任何人a，M(a)∧H(

8、a)均为假，因而x(M(x)∧H(x))为假，所以<3>表示的命题为真。(4)令F(x):x是在美国留学的学生,G(x):x是亚洲人。命题(4)符号化形式为┐x(F(x)→G(x))  <4>这个命题也为真13三、命题翻译练习例将下列命题符号化:(1)兔子比乌龟跑得快。(2)有的兔子比所有的乌龟跑得快。(3)并不是所有的兔子都比