离散数学课件 4.1一阶逻辑命题符号化

第四章

一阶逻辑基本概念苏格拉底三段论所有的人都是要死的。苏格拉底是人。所以，苏格拉底是要死的。试证明此推理。解：令p:所有的人都是要死的,q:苏格拉底是人,r:苏格拉底是要死的，则前提：p，q结论：r推理的形式结构：p

Ù

q

®

r说明：命题逻辑能够解决的问题是有局限性的。第1页命题逻辑的局限性在命题逻辑中,研究的基本单位是简单命题,对简单命题不再进行分解,并且不考虑命题之间的内在联系和数量关系。一阶逻辑所研究的内容为了克服命题逻辑的局限性,将简单命题再细分,分析出个体词、谓词和量词,以期达到表达出个体与总体的内在联系和数量关系。§4.1一阶逻辑命题符号化§4.2一阶逻辑公式及解释§5.1一阶逻辑等值式与置换规则§5.2一阶逻辑前束范式第2页第四章

一阶逻辑基本概念个体词谓词量词一阶逻辑命题符号化第3页§4.1一阶逻辑命题符号化§4.1一阶逻辑命题符号化引例小王是一名大二学生。小李是一名大二学生。3是奇数。小王与小李是好朋友。如果5>4,则4>6。x是奇数。x与y具有关系L。所有的大学生都会讲英语。(9)有的大学生会讲法语。三个基本要素:个体词,谓词,量词。第4页一、个体词1、定义：研究对象中可以独立存在的具体或抽象的客体。如：小王，小李，3，5，6，x，y。2、分类：个体常项：具体或特定的客体，用a,b,c,…表示。个体变项：抽象或泛指的客体，用x,y,z,…表示。3、个体域(论域)：个体变项的取值范围通，常用D表示。有限个体域，如{a,b,c},{1,2}无限个体域，如N,Z,R,…4.全总个体域：由宇宙间一切事物组成的个体域。注：题目中未明确说明时，指的是全总个体域。第5页二、谓词第6页1、定义：表示个体词性质或相互之间关系的词。2.表示：常用大写英文字母F,G,H,…表示引例中：(1)小王是一名大二学生。设a:小王，“是一名大二学生”是谓词,记为F。与 好朋友”是谓词,记为H,则命题符号化为F(a)。(4)小王与小李是好朋友。设a:小王，b:小李“，命题符号化为H(a,b)。(6)x是奇数。x是个体变项,“命题符号化为G(x)。是奇数”是谓词,记为G,二、谓词第7页3、分类谓词常项：表示具体性质或关系的谓词。如:F：“ 是一名大二学生”，G：“ 与 好朋友”。 谓词变项：表示抽象的、泛指的性质或关系的谓词。如:“x与y具有关系L。”中的关系L。4、n(n 1)元谓词：含n个个体变项的谓词。一元谓词(n=1)：表示性质，如F(x)；多元谓词(n 2)：表示事物之间的关系如，H(x,y)。5.0元谓词：不含个体变项的谓词，如F(a),G(3),H(a,b)。例1将下列命题在一阶逻辑中用0元谓词符号化,并讨论真值。第8页(1)只有2是素数，4才是素数。(2)如果5大于4，则4大于6。解:(1)设F(x):x是素数，命题符号化为F(4)®F(2)，命题为真。(2)设G(x,y):x大于y，命题符号化为G(5,4)®G(4,6)，命题为假。三、量词1、定义：表示个体常项或变项之间数量关系的词。如：“所有的大学生都会讲英语。”中“所有的”。“有的大学生会讲法语。”中“有的”。2.全称量词 ：表示所有的，一切的，每一个，任意…◆x说明:xF(x)表示个体域中所有的x具有性质F；x yG(x,y)表示个体域中所有的x和y有关系G。第9页如:设个体域:大学生，F(x):x会讲英语，G(x,y):x和y年龄相同。则xF(x)表示所有的大学生都会讲英语。yG(x,y)表任示意两个大学生年龄相同。三、量词3.存在量词 ：表示存在，有一个，有的，至少有一个…如：设个体域：大学生，F(x):x会讲法语，则xF(x)表示有的大学生会讲法语。说明： xF(x)表示个体域中有一个x具有性质F。如：设个体域:R，G(x,y):x<y，下列各式表示的含义为？x yG(x,y),表示存在两个实数x和y使得x<y。x yG(x,y),表示对每一个数x都存在一个数y使得x<y。x yG(x,y)表示存在一个数x使得对每一个数y都有x<y。说明： x yG(x,y)和 x yG(x,y)表示的含义不同！第10页四、符号化xF(x)xG(x)(1)

x(M(x)

®

F(x))(2)x(M(x)

G(x))特性谓词例2在一阶逻辑中将下面命题符号化。(1)人都爱美。(2)有人用左手写字。个体域分别为:(a)D为人类集合(b)D为全总个体域解:(a)设F(x):x爱美，G(x):x用左手写字，则(b)设F(x):x爱美,G(x):x用左手写字,M(x):x是人,则说明:不同的个体域，命题符号化形式可能不同（也可能相同）。第11页特性谓词 在全总个体域中,表示具体个体域的谓词。特性谓词加入时遵循的原则全称量词(存在量词(x),特性谓词作为蕴涵式前件加入。x),特性谓词作为合取项加入。对于宇宙间的所有个体都是人并且爱美。x(M(x) G(x))表示:存在宇宙间的个体，若这个个体是人，则他用左手写字。如例2

(1)人都爱美。

(2)有人用左手写字。个体域

(b)

D为全总个体域第12页解:设F(x):x爱美，G(x):x用左手写字，M(x):x是人，则(1)注:

♦

x(M(x)x(M(x)®F(x)) (2) x(M(x) G(x))F(x))表示:例3在个体域限制为(a)和(b)条件时,将下列命题符号化,并求真值。对于任意的x，均有x2-3x+2=(x-1)(x-2)。存在x，使得x+5=3。其中(a)个体域N (b)个体域R解:(a)设F(x):x2-3x+2=(x-1)(x-G2()x，):x+5=3。则符号化为:xF(x)，真值为:1。符号化为:xG(x)，真值为:0。(b)符号化同(a)，真值为:1。说明:不同的个体域，命题真值可能不同（也可能相同）。第13页例4在一阶逻辑中将下面命题符号化。(1)所有的人长着黑头发。(2)有的人登上过月球。(3)没有人登上过木星。(4)在美国留学的学生未必都是亚洲人。全总个体域第14页解:(1)设M(x):x是人F，(x):x长着黑头发。符号化为x(M(x)®F(x))。设M(x):x是人，G(x):x登上过月球。符号化为x(M(x) G(x))。令M(x):x是人，H(x):x登上过木星。符号化为﹁ x(M(x) H(x))。令F(x):x是在美国留学的学生，G(x):x是亚洲人。符号化为﹁ x(F(x)®G(x))。例5在一阶逻辑中将下面命题符号化。第15页兔子比乌龟跑得快。有的兔子比有的乌龟跑得快。有的兔子比所有的乌龟跑得快。所有的兔子比有的乌龟跑得快。解:设F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快,(1)xx

(F(x)y(F(x)(y(G(y)

H(x,y)))或G(y)

H(x,

y))(2)x

(F(x)(y(F(y)

H(x,y)))或xy(F(x)F(y)

H(x,

y))(3)x(F(x)y(G(y)

H(x,

y)))(4)x(F(x)y(G(y)

H(x,

y)))例5在一阶逻辑中将下面命题符号化。第16页并不是所有的兔子都比乌龟跑得快。不存在跑的同样快的两只兔子。解:设F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快,L(x,y):