逻辑学(北大精品课)04

主讲人：何向东--进入--第四章谓词逻辑第一节谓词逻辑概述2020年9月6日星期日3命题逻辑和谓词逻辑命题逻辑：不分析简单命题内部结构，讨论关于联结词的推理理论。例如：如果某甲作案，那么他一定有作案动机。某甲没有作案动机。所以，某甲没有作案。谓词逻辑：分析简单命题的内部结构，讨论关于量词的推理理论。例如：所有的作案者都有作案动机。某甲没有作案动机。所以，某甲不是作案者。2020年9月6日星期日4命题逻辑和谓词逻辑研究推理形式的有效性时，把命题当做不可分的逻辑单位有时是不够的。例如：（1）张三的朋友都是李四的朋友，王五不是李四的朋友。所以，王五不是张三的朋友。这个推理的形式在命题逻辑中表示为：P，¬q├¬r这个推理事实上是有效的。但仅用命题逻辑的理论不能表明它是有效的推理。（2）所有人都会死，张三是人，所以，张三会死。这是一个正确的三段论推理。但仅用命题逻辑的理论也不能表明它是有效推理。因此，要研究涉及量词的推理，仅用命题逻辑的理论是不够的。只有在命题逻辑的基础上发展谓词逻辑，才能解决这类推理的有效性问题。2020年9月6日星期日5个体词和谓词谓词逻辑就是把命题分解为个体词、谓词、量词以及联结词的逻辑系统。例如：（3）我是学生。（4）王五不是李四的朋友。个体词：表示个体的语词，如：“我”、“王五”、“李四”。谓词：用来说明个体词的性质或关系的语词。如例（3）中“是学生”是一元谓词，例（4）“…是…的朋友”是二元谓词。类似的，还有三元谓词，如“…在…和…之间”以及n元谓词。2020年9月6日星期日6个体词和谓词的符号化个体常项：表示一定范围内确定的个体，记为小写的：a,b,c,…；个体变元：表示一定范围内不确定的个体，记为小写的：x,y,z,…；个体域也称论域：个体变元的变化范围，记为：D。谓词符号：表示性质或关系的符号，记为大写：D、E、F、G…；一元谓词公式，记为：Dx，Ex，Fx，…；二元谓词公式，记为：Dxy，Exy，Hxy，Rxy，…；三元谓词公式，记为：Gxyz，Bxyz，Pxyz，Kxyz，…；n元谓词公式，记为：Sx1x2…xn，Wx1x2…xn，…。个体词和谓词的符号化实例:用a表示“张三”，用Dx表示一元谓词“会死”，则命题“张三会死”可表示为：Da。如是Fxy表示二元谓词“…是…的朋友”，那么：Fab表示“a是b的朋友”;¬Fab表示“a不是b的朋友”。2020年9月6日星期日7开语句P：…是紫色的。Px：x是紫色的。让开语句有真值的方法：（1）用个体常项代替个体变元。用a表示“这朵玫瑰花”，则Pa表示语句“这朵玫瑰花是紫色的”。（2）对个体变元进行量化。例如:命题“存在玫瑰花是紫色的”为真。没有真假的命题函数，即从个体到真值的函数。例如:2020年9月6日星期日8量词全称量词：指称论域D中个体的全部。例如：所有，任何，每一个，…。存在量词：指称论域D中个体至少有一个存在。例如：存在，有，有些，…。符号化的量词：全称量词：所有x，任何x，…，均记为：x。存在量词：有x，存在x，…，均记为：x。全称命题：含有全称量词的命题。特称(存在)命题：含有存在量词的命题。表示论域D中个体数量的语词2020年9月6日星期日9命题的形式化（1）凡事物都是发展的。用x表示个体词，用D表示“是发展的”，形式化为：xDx（2）凡是自然数都大于零。用N表示“是自然数”，用E表示“大于零”，形式化为：x(NxEx）（3）所有大学生都不是儿童。用S表示“是大学生”，用C表示“是儿童”，形式化为：x(SxCx)（4）有的大学生是儿童：x(Sｘ∧Cｘ)（5）小李没有同任何人吵架。a：小李；Ｍ：…是人，D：…同…吵架，形式化为：x（Ｍx→Ｄax）（6）有些大一学生认识小李。a：小李；F：…是大一学生，R：…认识…，形式化为：x(Fx∧Rxa)2020年9月6日星期日10命题的形式化在对以上命题形式化时，没有限制论域，即论域是全域。我们也可在一定的范围内讨论问题，因些个体变元的变域往往被限制在某个特定的范围内。（7）有的学生（Ｓ）作对（Ｒ）所有试题（Ｔ）不限制论域：x（Ｓx∧y(Ty→Rxy)）限制论域：x的变域:X=学生；y的变域:Y=试题则形式为:xyRxy一阶逻辑：量词是只对命题中的个体变元进行量化，而不对谓词变元进行量化。高阶谓词：不仅对个体变元而且对谓词变元进行量化。第四章谓词逻辑第二节一阶语言及其语义解释2020年9月6日星期日12一阶语言L（1）初始符号个体变元符号：x,y,z,…；x1,x2,…若干（可以为0个）个体常项符号：a,b,c…若干（至少一个）谓词符号：D,E,F,G,R，…联结词符号：,∧,∨,→量词符号：,；辅助符号：括号：（，）；逗号：，。（2）形成规则：包括项的形成规则和公式的形成规则。①项的形成规则：单个的个体变元（v，u，w，…）和个体常项（a，b，c，…）称为项。2020年9月6日星期日13一阶语言L②公式的形成规则：1、如果R是n元谓词（n1）,t1…tn是n个项，则Rt1…tn是公式（原子公式）；2、如果A是公式，则A3、如果A和B是公式，则A∧B、A∨B、A→B是公式；4、如果A是公式，v是个体变元，则vA和vA是公式（vA称为全称公式；vA称为存在（特称）公式）。一阶语言L的一个符号串是（合式）公式，当且仅当它符合以上形成规则。一阶语言L的全体（合式）公式，记为Form（L）。一阶语言L是形式语言L′的扩充。（3）定义：用来表示符号串的缩写。如：AB=df(A→B)∧(B→A)。2020年9月6日星期日14量词的辖域量词的辖域：量词的作用范围。量词的辖域可定义为：如果B是vB和vB的子公式，则称B为量词v和v的辖域。在公式中，量词的辖域是该量词及紧接该量词的最短公式。带横线部分指明了存在量词的辖域。(1)xＤx∨Ｅx(2)x（Ｆxy∧yＧy）(3)xy（Ｆxy∧xz（Ｇxz→Ｈyz）2020年9月6日星期日15约束变元和自由变元变元的约束出现：一个变元在公式里的出现是约束的，当且仅当，这种出现是在采用该变元的量词的辖域内。变元的自由出现：一个变元在公式里的出现是自由的,当且仅当，该变元的出现不是约束的。约束变元就是约束出现的变元；自由变元就是自由出现的变元。例如：在xＤx∨Ｅx中，变元x出现了三次，前两次出现是在量词x的辖域中，因而是约束出现的，第三次是自由出现的。2020年9月6日星期日16自由变元的代入如果公式A中有自由变元v，则把该公式记为：A(v)。以个体词t代入A(v)中的v，则记为：A(v/t)。例如：（1）对于公式Px→Qx，用A(x)来表示x是自由变元：A(x)：Px→Qx（2）对于公式x(Qx∧Rxy)，用B(y)来表示y是自由变元：B（y）：x(Qx∧Rxy)；（3）用个体变元y代替A(x)中的自由变元：A(x/y)：Py→Qy；（4）用常元a代替A(x)中的自由变元：A(x/a)：Pa→Qa。自由变元的代入规则：(1)、代换必须处处进行A(x)：Px→Qx以y代换A(x)中的自由变元x：A(x/y)：Py→Qy（正确代换）A(x/y)：Px→Qy（错误代换）(2)、代换不能改变量词的约束关系B(y)：x(Qx∧Rxy)以个体变元来代换B(y)中的自由变元y：B(y/z)：x(Qx∧Rxz)（正确代换）B(y/x)：x(Qx∧Rxx)（错误代换）2020年9月6日星期日17一阶语言L的语义解释一、原子公式的解释：给定一个个体域D，将个体常项解释为个体域中特定的个体，将谓词符号解释成这个个体域中的性质或这个个体域上的关系，则原子公式是否为真可以归结为某个个体是否具有某种性质或某些个体是否具有某种关系。二、全称公式和特称公式的解释：在给定的一个解释下，vA为真要求将v解释成个体域中任何个体时A都为真，而vA为真，则只要将v解释成个体域中至少一个个体时A为真。严格地讲，一阶语言的语义解释就是在把个体词解释成为个体域中的个体、把谓词解释为个体域中的性质或个体域上的关系的基础上，确定公式的真值即给公式赋值。2020年9月6日星期日18一阶语言L的语义解释语义解释也称为模型，记为µ，µ(1)一个个体变元的取值范围——非空集合D(论域、个体域)(2)对每个个体常项a，指定D中一个确定的个体aµ(3)对每个n元谓词符号R，指定D上的一个n元关系Rµ；在一个解释（模型）中，每个闭公式有确定的真值。例如：D=自然数，个体常项a解释为4（aµ=4）；一元谓词P解释为“是偶数（Pµ）”；二元谓词G解释为“＞”（Gµ=＞）；则：Pa的解释是“4是偶数”（真命题）；xPx的解释是“所有自然数是偶数”（假命题）；xyGyx的解释是“对所有自然数总存在大于它的自然数”(真命题)。2020年9月6日星期日19指派和赋值个体变元与它所指称的对象通过指派建立了确定的联系。一个模型上的指派有无穷多个。原子公式的值可以根据模型和指派确定。设ρ是模型µ上的指派，v是变元，d∈D。所谓模型µ上与指派ρ相关联的指派ρ(v/d)如果u≠v,则ρ(v/d)(u)=ρ(u)；如果u=v，则ρ(v/d)(u)=d。不管原指派ρ中v的值是什么，新指派ρ(v/d)总是把v指派成d，而其余变元的值都不变。显然，如果d=ρ(v)，则ρ(v/d)=ρ，即ρ自己也是与其自身相关联的指派。给每个变元指定一个个体的过程称作指派，记为ρ2020年9月6日星期日20谓词逻辑的每个项和公式在赋值δ下都有确定的值。项的基本语义定义:设δ=〈µ,ρ〉是一个赋值，t是任意的项，t在δ下的值δ(t)是论域D中的个体，具体定义如下：(1)如果t是个体变元v，则δ(v)=ρ(v)；(2)如果t是个体常项a，则δ(a)=aµ。模型µ和µ上的一个指派ρ确定一个赋值δ，记为δ=µ,ρ2020年9月6日星期日21公式的基本语义定义设δ=〈µ,ρ〉是一个赋值，A是任意的公式，A在δ下的值记为δ(A)。δ（A）=T，或者δ（A）=F。定义如下：（1）如果A是原子公式R(t1…tn)，则δ(A)=T当且仅当〈δ（t1）,…，δ(tn)〉∈Rµ；（2）如果A是B，则δ（A）=T当且仅当δ（B）=F（3）如果A是B∧C，则δ（A）=T当且仅当δ（B）=T且δ（C）=T；（4）如果A是B∨C，则δ(A)=T当且仅当δ(B)=T或δ(C)=T；（5）如果A是B→C，则δ(A)=T当且仅当δ(B)=F或δ(C)=T；（6）如果A是vB，则δ(A)=T当且仅当对任何d∈D,都有(v/d)(B)=T；（7）如果A是vB，则δ(A)=T当且仅当存在d∈D,使得δ(v/d)(B)=T。2020年9月6日星期日22公式的基本语义定义基本语义解释的直观意义第（1）条只不过是说原子公式R（t1…tn）为真，只要t1，…，tn所指对象具有D上的关系Rµ。第（2）——（5）条只不过说对联结词的解释与第二章中的解释相同。第（6）条不过是说vB为真就是v的值取遍论域时B的值总为真。第（7）条也不过是说vB为真就是论域中至少有一个个体使B为真。2020年9月6日星期日23公式的基本语义定义设一阶语言L包括二元谓词符号G，个体常项a和b，取模型µ，使得个体域D是整数，Gµ是“＜”（整数上的小于关系），aµ=10，bµ=11。δ=〈µ,ρ〉,其中ρ为：ρ(x)=－2，ρ(y)=13，ρ(z)=8，…那么：δ(Gab)=T(命题“10＜11”为真)；δ(Gay)=T(命题“10＜13”为真)；δ(Gyx)=F(命题“13＜－2”为假)。可满足性设A是公式，µ是任意模型；如果存在赋值δ，使得δ（A）=T，则称模型µ满足A，记为：µ=A，否则，称模型µ不满足A，记为：µ≠A。协调性设Γ是公式集(Γ={A1，A2，…An})，µ是任意模型；如果存在赋值δ，使得δ（Γ）=T（即δ（A1）=T，δ（A2）=T,…,δ(An)=T），则