逻辑演算

夏理雾棋

逻辑演算的基本概念

要读懂现代逻辑学书籍就需要准确掌握一些基本概念。下面试着由浅及深的列一些，缺项和不准确处请高手补正。 一、关于逻辑演算和形式系统的一些基本概念 1、逻辑演算 所谓逻辑演算是指命题演算和谓词演算，即命题逻辑和谓词逻辑的形式系统。 2、命题逻辑 在考察问题时，以命题为基本形式，把命题只分解到其中所含的简单命题，不再把简单命题分解成非命题形式（主词、谓词、量词），只研究由简单命题出发经使用联结词所构成的复合命题的逻辑形式及其推理关系。命题逻辑适用于有效性只完全依赖于命题之间互相联结的形式，而不涉及命题本身的组成形式的推理和论证。 3、谓词逻辑 在考察问题时不以命题为基本形式，而把命题分析为主词（个体词）、谓词和量词，然后研究其之间的逻辑推理关系。谓词逻辑中的推理形式，与量词的特征密切相关，故也称为量词逻辑。对于逻辑推理的有效性涉及命题本身的组成形式时，其推理和论证就需要使用谓词逻辑。 4、形式系统 所谓形式系统就是用形式语言表述的公理系统。一般由四部分组成：1）初始符号，即初始概念的抽象；2）形成规则，由初始符号构成合式公式的规则。因为初始符号可以组成各种符号串（序列），符合形成规则的符号串，称为合式公式；3）初始公式，即用自然语言表述的公理抽象，它是作为形式系统出发点的合式公式；4）变形规则，即由某些合式公式推出某个合式公式的形式规则，是推理规则的抽象。 二、研究命题逻辑和命题演算需要掌握的基本概念 由于命题逻辑规律反映的是复合命题的逻辑特征，而复合命题的特征又决定于联结词所反映的客观关系，所以命题逻辑又称为联结词逻辑。其基本概念包括：真值联结词、真值形式、真值表、有效性等基本概念。 5、真值联结词 所谓真值联结词是反映复合命题和支命题之间真假关系的联结词，它是普通联结词的逻辑抽象。命题逻辑中有五个与普通联结词对应的真值联结词： ┓ 否定 ------并非 ∨ 析取 ------或 ∧ 合取 ------并且 → 蕴涵 ------如果...，那么... ≡ 等值 ------当且仅当(注等值符号打不出来,用≡暂代) 6、真值形式 与复合命题相当的由真值联结词构成的形式结构。命题逻辑中的公式都是真值形式。当用p、q表示命题时，可以得到五个基本真值式： ┓ p -----------否定式 p∨q -----------析取式 p∧q -----------合取式 p→q -----------蕴涵式 p≡q -----------等值式 否定式只有一个支命题，其余四式均有两个支命题。 7、真值表 使用真值联结词由支命题的真假确定复合命题的真假，并以T、F分别表示真、假，列出基本真值式与支命题之间真假关系的图表。上述五个基本真值式的真值表为： p ∣┓ p --------- T ∣F F ∣T p ∣q ∣p∨q ∣p∧q∣p→q∣p≡q --------------------------------- T ∣T ∣T ∣T ∣T ∣T T ∣F ∣T ∣F ∣F ∣F F ∣T ∣T ∣F ∣T ∣F F ∣F ∣F ∣F ∣T ∣T 注：上述真值表中，关于蕴涵式p→q的真值表规定的合理性存在争议，即仅当前件真后件假时蕴涵式假，其他情况即使前件假（不管后件真假，后件真（不管前件真假）时，蕴涵式皆真。在现行的数理逻辑推导中均按上述真值表操作。 7、重言式命题 一个命题是重言式：当且仅当，在对式中出现的各个命题符号指派所有可能的真值时，该式总是真的。 8、矛盾式命题 一个命题形式是矛盾式，当且仅当，对在式中出现的各命题符号指派所有可能的真值时，该式总是假的。 9、有效推理（正确推理） 如果推理的结论是它的前提的合乎逻辑的结果，这个推理就是有效推理。所谓合乎逻辑是指：如果前提真，所得的结论也必然真。 10、无效推理 推理形式A1，A2，...,AN所构成的命题A是无效的：如果能够对出现在A1，A2，...,AN中的命题符号指派真值，使得A1，A2，...,AN都真，而A却为假，则此推理形式是无效的。 11、可靠推理 前提为真的有效推理。 注：1、有效推理尽管当前提都真时，结论真，但它并不要求前提和结论必须为真，因此可靠推理比有效推理要求更高。 2、重言式概念是核心概念。在此给出一个一般的判别定理：推理形式A1，A2，...,AN；所构成的命题A是有效的，当且仅当，与之相当的命题形式（A1∧A2∧...∧AN）→A是重言式。这样推理形式的有效性检验就可以转化为对蕴涵式的重言性质的检验，而这又可以通过真值表来解决问题。三、与一致性定理和完备性定理证明密切相关的基本概念 塔斯基说过：在日常语言那样丰富的语言中，逻辑规律在其中成立的条件下，想无矛盾地使用语言是不可能的。 形式语言是具有精确规则的符号系统，它运用符号表示概念、判断，能够把推理转化为符号的变换，把逻辑转换成演算，由于形式语言表述的逻辑规则十分精确，因而能避免悖论。 为后边说明方便，首先引入一个形式系统L，它是重言式的公理系统： (一)初始符号（无限）： p1，p2，p3，... ┓,→,(,) (二)形成规则: 1)pi是一个合式公式,其中i≥1. 2)如果A,B是合式公式,那么┓A,(A→B)是合式公式. 3)所有合式公式由1),2)生成. (三)初始公式:有无限多的初始公式,不能一一列出,但可以通过三个公理模式将它们全部列出.对于任何公式A,B,C.下列是初始公式: (L1) (A→(B→A)) (L2) (A→(B→C))→((A→B)→(A→C)) (L3) ((┓A)→(┓B))→(B→A) (四)变形规则:只有一个分离规则(记作MP),断定符号├表示本系统对后面跟着的合式公式是断定的.即从├A,和├A→B；可得├B。 大家可以使用真值表验证上述（L1）、（L2）、（L3）均为重言式。 13、证明的定义 L中的一个证明是公式的一个有序列A1，A2，...,AN，它满足以下条件：对每个i（1≤i≤n） （1）Ai是L的一条公理，或 （2）Ai由在前的两个公式Aj和Ak（j＜i，k＜i）分离而得。即Ai是对Aj和Ak使用MP规则的直接后承。这样的一个证明可称为An在L中的一个证明，An也称为L的定理。显然，序列中的任一在前片段，A1，A2，...,Ak也是L的一个证明，Ak也是定理。 14、演绎的定义 令Γ是L中的一组公式，它们可以是L中的定理和公理，也可以不是，L中以Γ为前提的演绎是公式的一个有序列A1，A2，...,AN，它满足以下条件：对每个i（1≤i≤n） （1）Ai是L的一条公理，或 （2）Ai是公式组Γ中的一个 （3）Ai由在前的两个公式Aj和Ak（j＜i，k＜i）分离而得。如果这样的一个演绎存在，则标有下标的最后一个公式An称为以Γ为前提可演绎的，或称An为L中Γ的后承，记作Γ├LAn，注意L中的关于空前提的演绎就是L中的一个证明。 注：1）在研究形式系统L时，实际是把一种形式语言当作研究对象，即L为对象语言。而在这里还需要一种工作语言，简称为语法语言或元语言。2）├符号并非形式系统中的符号，而是语法语言中的符号，也叫语法符号，上边├A的含义是明确的，它表示A是定理。 15、赋值 系统L中的一个赋值是一个函数v，v的定义域是L中的一切合式公式集，值域是（T，F），对L中任意公式A、B，满足： （1）v（A）=┓v（┓A） （2）v（A→B）=F，当且仅当，v（A）=T和v（B）=F。 由上述赋值定义，可以给L中的公式A作一个新的重言式定义： L中的一个公式A是重言式，当且仅当，对每一赋值v，v（A）=T。 16、一致性定义 一个形式系统是一致的，当且仅当，对系统中的任何合式公式A，A和┓A不能都是L的定理。 17、形式系统的扩充 形式系统L*是L的一个扩充，当且仅当，L*是一个通过改变和扩大L的公理集而得到的形式系统，并且使得L的所有定理保持为L*的定理。 结合上面的一致性定义，可以给出扩充一致性的定义：L的扩充是一致的，当且仅当，对L中的任何公式A，A和┓A不能都是扩充的定理。 18、完全性的定义 L是完全的，当且仅当，对于合式公式A，或者A或者┓A是L的一个定理。同上可以定义关于扩充的完全性。 由上述定义，可以证明L上的一致性定理、可靠性定理以及完备性定理。 命题演算L是可靠的，指的是L中的定理都是重言式；命题演算是一致的，指的是L中没有矛盾；命题演算是完备的，指的是重言式都是L中的定理。 四、谓词逻辑中的一些基本概念 对简单命题解析，可以拆分为主词、谓词、量词这样的更基本的成分。 19、主词 所谓主词，就是命题中表示思维对象的词项。它可以是专有名词性的个体常元，也可以是确定的某类事物中的变元。其中常元一般用a、b、c表示，变元用x、y表示。 20、谓词 是表示思维对象的属性（性质、关系）的词。一般用大写字母表示，如“大象是动物”可用符号表示为 P（a），a表大象。如果P表示一个对象的性质，就称为一元谓词，依次可以有表示n个体之间关系的n元谓词。 21、量词 量词是命题中表示数量的词。量词的作用有二，一是区分变项的自由和约束，二是表达谓词逻辑中的各种命题形式。量词有全称量词、存在量词两种，全称量词符号用“￥”（注：应为大写A倒过来，此符号打不出来，抱歉），存在量词符号用"Ξ"表示（注：应为大写E的镜象，打不出来）。在合式公式（￥xi）A中，A是量词的辖域，当量词后无括号时，量词后的最短公式是辖域。 22、函数符号 对于特殊表达，如“X+Y-4”，“自然数1的后继”等，需要一些能表达“+”，“-”，“后继”的符号，称之为函数符号。用 f1^1,f2^1,f1^2,f2^2,...;表示，（注：因打不出上下标，前面f后的第一个数字表示下标，^号后的数字表示上标）。上标表示函数自变元的个数，下标数字用于区别自变元个数相同但函数关系不同的函数。如fi^n表示第i个n元函数. 同理，可以用Pi^n表示第i个n元谓词. 23、项 一阶语言￡中的项是 （1）个体常元、个体变元，或 （2）fi^n(t1,...,tn),其中fi^n是函数符号,t1,...,tn是￡中的项. （3）所有的项由（1）、（2）生成。 24、原子公式 ￡中的原子公式是这样的一符号串Pi^n(t1,...tn),其中Pi^n是谓词符号,t1,...tn,是￡中的项. 25、合式公式 ￡中的合式公式是 （1）￡中的每一个原子公式，或 （2）（┓A），（A→B），（￥xi）A，其中A、B是合式公式，xi是任意个体变元。 （3）￡中的所有合式公式由（1）、（2）生成。 下面可以将一阶语言￡的初始符号列出如下： a1，a2，... 个体常元 x1,x2,... 个体变元 f1^1,f2^1,...;f1^2,f2^2,...;... 函数 P1^1,P2^1,...;P1^2,P2^2,...;... 谓词 ┓,→ 联结词 ￥,Ξ 量词 (,) 括号 五、逻辑演算中涉及到的一些基本语义学概念 把逻辑处理成演算，可以完全不提及符号表达式的意义和涵义。但是逻辑分析的最终还是要回到意义层面。符号表达式和它的意义之间的关系研究属于语义学范畴，它涉及到一些语义学基本概念，如“满足”、“真”、“解释”、“模型”等。 所谓一种语言的解释，就是确定该语言里的符号表达式怎样同某个现实或可能世界间建立联系。它们随着所取世界的不同，可以有完全不同的意义。解释给出了语言中的指词符号所指称的那个世界中的对象，而表达式又是指称对象的外延，故而也可以说，解释就是给出语言中指词符号的外延。 26、解释的一般定义 ￡的一个解释I是由一个非空集合DI，一组特指元素（*a1，*a2，...),一组定义在DI上的函数(*f1^1,*f2^1,...;*f1^2,*f2^2,...;...),一组定义在DI上的关系(*P1^1,*P2^1,...;*P1^2,*P2^2,...;...)一起组成. 其中集合DI就是个体域也称论域,即一种世界的可能存在方式.特指元素是论域中一些特定成员,它们是￡中个体常元的指称对象.类似地,定义在DI上的函数和关系,是￡中函数符号和谓词符号的指称对象. 注:同一个形式语言,可以有实质上不同的解释. 27、解释中的赋值 在解释I中的赋值是一个满足条件(1)、(2)的函数v,它的定义域是￡中的项集合,值域是DI. (1)v(ai)=*ai对￡中的每个个体常元ai. (2)v(fi^n(t1,...tn))=*fi^n(v(t1),...,v(tn)),其中fi^n是￡中的任意函数符号,t1,...,tn是￡中的任意项. 注:条件(1)表明￡中个体常元ai的指称对象是论域DI中固定的个体.对解释I的各种赋值,这种对应关系不变.条件(2)表明,赋值是保运算不变的,即项t1,...,tn先经fi^n运算然后赋值,与先在赋值v下取t1,...,tn的象后,再行*fi^n运算,所得结果相同. 28、i-等值赋值 今有两个赋值v,v′,它们分别由如下序列给定: v(x1)=b1,v(x2)=b2,...,v(xi)=bi,... v′(x1)=b1,v′(x2)=b2,...,v′(xi)=bi′,... 它们除了对第i个变元xi的赋值v(xi),v′(xi)可以不同外,对所有其他变元xj(j≠i),都有 v(xj)=v′(xj) 就称v和v′是i-等值的,或称v′ i-等值于v. 29、赋值满足公式A(赋值真) 令I是￡的一个解释,A是￡中的一个合式公式,I中的一个赋值v如果归纳地遵循下列四个条件,就称赋值v满足公式A: (1)v满足原子公式Pj^n(t1,...,tn),当且仅当,*Pj^n(v(t1),...,v(tn))在DI中真. (2)v满足（┓B）,当且仅当,v不满足B. (3)v满足(B→C),当且仅当,v满足（┓B）,或v满足C. (4)v满足（￥xi）B,当且仅当,每个i-等值于v的v′,满足B. 注:1)上述定义核心是,公式A对于任何赋值v,只有两种选择:或者v满足A,或者v满足（┓A）,但不能两者都满足.2)￡中的一个公式A,如果至少存在一个解释I中的赋值满足A,就A称是可满足的. 30、解释真定义 一个￡中的一个公式A对解释I真,当且仅当,解释I中的每个赋值都满足A,此时又称解释I为公式A的模型.A对解释I为假,当且仅当,I中没有一个赋值满足A.A在I中真,使用记号I∣=A表示.(注:这里∣=和前面使用的断定符号├一样,都是语义符号,不同在于├只涉及形式,而∣=却和符号的意义、公式的真假相联.) 注:1)由于对某个特殊的公式来说,有可能存在I中某些赋值满足它,另一些赋值不满足它,这样的公式对解释I既不真也不假.因此,定义中的解释真比可满足要求高,解释真必可满足,但可满足不必解释真.2)考虑到对同一个赋值,不能既满足A又满足（┓A）,因此不可能存在任何公式A,A和（┓A）皆对解释真. 31、逻辑真 ￡中的一个公式A是逻辑真的,当且仅当,A在￡的每个解释中皆真.A是矛盾的,当且仅当,A在￡的每个解释中皆假. 注:1)逻辑真亦称普遍有效式,逻辑假亦称矛盾式.2)上面关于命题有三个层次的真:赋值真,解释真,逻辑真,真的程度依次递增. 32、模型 令Γ是￡的一组公式,I为￡的一个解释,如果Γ中的每个公式都对解释I真,就称I为Γ的一个模型,可用I∣=Γ表示. 显然当Γ只有一个公式A的情况下,I是A的模型与A对I解释真意义相同.