第3 编数理逻辑第7 章命题逻辑

《第3 编数理逻辑第7 章命题逻辑》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3编数理逻辑第7章命题逻辑1在命题逻辑中，原子为基本单位，不能再分，因此具有局限性，使有些简单命题无法判断。例：著名的“苏格拉底三段论”：P:凡人都是要死的。Q:张三是人。R:张三要死的。P∧Q→R应该是永真式，但在命题逻辑中无法证明。解决方法：命题分解成个体词、谓词、量词。27.1谓词概念与表示个体词：可以独立存在的客体。可以是具体的事物，也可以是抽象的概念。用小写字母表示：a,b,c,...,x,y,z.定义：用以刻划个体词的性质或关系的词(命题函数)称为谓词。用大写字母表示：F(),G().个体域D：个体词的取值范围。全总个体域D：包含宇宙间所有的事物

2、组成的个体，是研究问题中最大的个体域。谓词的取值范围：{0,1}.3例：是无理数。小王是程序员。小李比小王高2厘米。H(x):x是程序员。H(小王)。G(x,y):x比y高2厘米。G(小李,小王)。F(x)、H(x)是一元联结词；G(x,y)是二元联结词。含n个个体词的谓词称n元谓词。P(x1,x2,...,xn).不含个体词的谓词称零元谓词。符号化：设F(x):x是无理数。F()，F()。4对于个体词具有数量的概念。如所有的人都要死的。有的人活百岁以上。定义：“任意x”称全称量词，记x。“存在一个x”称存在量词，记x。对上面的例子，可设F(x):x

3、要死的。xF(x).G(x):x活百岁以上。xG(x).这两个命题的真值都为T.7.2命题函数与量词5注意：①x的定义域D不同，符号可能不一样。如：D={人类}，符号同上；如：D为全总个体域，加特性谓词：M(x):x是人。x(M(x)→F(x))......(1)x(M(x)∧G(x))......(2)②没有给定定义域，则为全总个体域。③全称量词和存在量词的符号化形式不同：见(1),(2)式。6④但定义域有限时，设D={a1,a2,...,an}xF(x)F(a1)∧F(a2)∧∧F(an).xG(x)G(a1)∨G(a2)∨∨G(an)

4、.⑤不能随意颠倒量词的顺序。例：“对任意的x，存在y，使x+y=5”。D=R,H(x,y):x+y=5.则xyH(x,y)T。但yxH(x,y)F。77.3谓词公式的翻译与解释定义1字母表如下：(1)个体常项：a,b,c,…(2)个体变项：x,y,z,…(3)函数符号：f(),g(),…(4)谓词符号：P(),Q(),…(5)量词符号：,(6)逻辑符号：¬,∨,∧,→,,(7)括号与逗号：(,),，个体词D注意函数与谓词的区别8定义2：谓词逻辑中的项，被递归定义为：(1)任意的个体常项或个体变项是项；(2)若f(x1,x2,…xn,)是

5、n元函数符号,t1,t2,…tn是项,则f(t1,t2,…tn)是项；(3)所有项都是有限次使用(1)(2)生成的符号串。例：a是项，x是项，g(x)是项，f(x,y)是项，f(g(x),a)是项.定义3:若P(x1,x2,…xn,)是n元谓词,t1,t2,…,tn是项,则P(t1,t2,…tn)是原子公式。9定义4合式公式是如下定义的一个符号串(1)原子公式是合式公式；(2)若A,B是合式公式，则如下符号串(¬A),(AB),(AB),(AB),(AB),(AB)也是合式公式；(3)若A是合式公式，则xA,xA是合式公式；(4)所有合式公

6、式(谓词公式)都是有限次使用(1)(2)(3)得到的符号串。例：(1)x(P(f(x))∧Q(x,f(a)));(2)x(P(x)∧Q(x,a)).两个符号串都是公式。10命题符号化：确定谓词——确定个体词及量词——依量词确定逻辑关系。x(M(x)→F(x))......(1)x(M(x)∧G(x))......(2)11例1：每一个有理数都是实数。某些实数是有理数。不是每一个实数都是有理数。解：设P(x):x是有理数。Q(x):x是实数。x(P(x)→Q(x)).x(Q(x)∧P(x)).¬x(Q(x)→P(x)).■12例2:(1)所有的

7、正数均可开平方；(2)没有最大的自然数。解：(1)设R(x):x是实数。G(x,y):x>y。S(x):x可以开平方。x(R(x)∧G(x,0)→S(x)).(2)设N(x):x是自然数。G(x,y):x>y。x(N(x)→y(N(y)∧G(y,x)).■13例3不管黑猫白猫，抓住老鼠就是好猫。解：设B(x):x是黑猫；W(x):x是白猫；M(x):x抓住老鼠；G(x):x是好猫。x((B(x)∨W(x))∧M(x)G(x)).■14定义5：公式xA(x,y)或xA(x,y)中，x为指导变元，A为x的作用域或辖域.x作用域内的x称为约束变元，非约

8、束的y称为自由变元。例1：(1)x(