最新数理逻辑课件PPT.ppt 95页

'数理逻辑 数理逻辑形式逻辑主要是研究推理的。归纳推理：由若干个别事实推出一般结论。如：铜能导电。铁能导电。锡能导电。铅能导电。……一切金属都导电。演绎推理：由一般规律推出个别事实。形式逻辑主要是研究演绎推理的。例1：如果天下雨，则路上有水。(一般规律)天下雨了。(个别事实)推出结论：路上有水。(个别结论) 数理逻辑数理逻辑是用数学的方法研究形式逻辑。所谓“数学方法”：是建立一套有严格定义的符号，即建立一套形式语言，来研究形式逻辑。所以数理逻辑也称为“符号逻辑”。它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切联系。这里只讨论“命题逻辑”和“谓词逻辑”。下面就前面两个例子，说明如何将推理符号化的。 命题逻辑一个命题所作的判断有两种可能：是正确的判断或者是错误的判断。所以一个命题的真值有两个：“真”或“假”真值为真:一个命题所作的判断与客观一致,则称该命题的真值为真,记作T(True)。真值为假:一个命题所作的判断与客观不一致,则称该命题的真值为假,记作F(False)。例1中(1)(4)的真值为真,(2)的真值为假,(3)暂时不能定，等到2013年确定。 命题逻辑简单命题(原子命题)：由最简单的陈述句构成的命题(该句再不能分解成更简单的句子了)。通常用大写英字母表示,如P,Q等。例1中的(1)、(2)、(3)是原子命题。复合命题(分子命题)：由若干个原子命题通过一些联接词组成的较为复杂的命题。例1中的(4)是由三个原子命题(a>b、b>c、a>c)构成的复合命题。 命题逻辑联结词复合命题的构成：是用“联结词”将原子命题联结起来构成的。归纳自然语言中的联结词，定义了五个逻辑联结词，分别是：(1)否定“”(2)并且“∧”(3)或者“∨”(4)蕴含“”(5)等价“” 命题逻辑否定“”表示：“…不成立”，“不…”，“非”，“没有”，“无”，“并非”，“并不”。用于:对一个命题P的否定,写成P,并读成“非P”。P的真值：与P真值相反。例1中P：2是素数。P：2不是素数。PPTFFT 命题逻辑并且“∧”(合取)表示：“并且”、“不但…而且...”、“既…又...”“尽管…还…”，“和”，“与”，“同”，“以及”，“而且”。例如P：小王能唱歌。Q：小王能跳舞。P∧Q：小王能歌善舞。P∧Q读成P并且Q。P∧Q的真值为真，当且仅当P和Q的真值均为真。PQP∧QFFFFTFTFFTTT 命题逻辑或者“∨”（析取）表示“或者”，“或者”有二义性，看下面两个例子：例1.灯泡或者线路有故障。例2.第一节课上数学或者上英语。例1中的或者是可兼取的或。即或者“∨”例2中的或者是不可兼取的或，也称之为异或、排斥或。即“”. 命题逻辑P：灯泡有故障。Q：线路有故障。例1中的复合命题可表示为：P∨Q，读成P或者Q，P∨Q的真值为F，当且仅当P与Q均为F。PQP∨QFFFFTTTFTTTT 命题逻辑P：第一节上数学。Q：第一节上英语。例2中的复合命题可写成PQ，读成P异或Q。PQ的真值为F，当且仅当P与Q的真值相同。FFFFTTTFTTTFPQPQ 命题逻辑蕴含(条件)“”表示“如果…则…”，“当...则...”,“若...那么...”，“假如...那么...”例如：P表示：缺少水分。Q表示：植物会死亡。PQ：如果缺少水分，植物就会死亡。PQ：也称之为蕴含式，读成“如果P则Q”。也说成P是PQ的前件，Q是PQ的后件。还可以说P是Q的充分条件，Q是P的必要条件。 PQ的真值为假，当且仅当P为真、Q为假。在这里，当前件P为假时，则不论后件是真还是假此蕴含式一定为真。如“如果明天天气晴朗则举行运动会。”此蕴含式是对“明天天气晴朗”条件成立而言，此时如举行运动会则为真，不举行则为假。但是如果明天天气不晴朗，此蕴含式并没有考虑这种情况，则不管举行还是不举行运动会都认为真。PQPQFFTFTTTFFTTT 命题逻辑充分条件：就是只要条件成立，结论就成立，则该条件就是充分条件。上例中，“缺少水分”就是“植物会死亡”的充分条件。在自然语言中表示充分条件的词有：如果…则…，只要…就…，若…则…必要条件：就是如果该条件不成立，那么结论就不成立,则该条件就是必要条件。上例中，“植物死亡”就是“缺少水分”的必要条件(植物未死亡，一定不缺少水分)。在自然语言中表示必要条件的词有：只有…才…；仅当…，…;…,仅当…。 命题逻辑等价“”表示“当且仅当”、“充分且必要”,"相同"，“相等”，“一样”例如：P：⊿ABC是等边三角形。Q：⊿ABC是等角三角形。PQ：⊿ABC是等边三角形当且仅当它是等角三角形。 命题逻辑PQ的真值为真，当且仅当P与Q的真值相同。PQPQFFTFTFTFFTTT 命题逻辑常值命题与命题变元常值命题：即是我们前面所说的命题。它是有具体含义(真值)的。例如：“3是素数。”就是常值命题。命题变元：用大写的英字母如P、Q等表示任何命题。称这些字母为命题变元。对命题变元作指派(给命题变元一个解释)：将一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值“T”或“F”的过程。注意：命题变元本身不是命题，只有给它一个解释，才变成命题。 命题逻辑命题公式定义：⑴单个命题变元是个命题公式。⑵若A是命题公式，则A是命题公式。⑶若A和B是命题公式，则(A∧B)，(A∨B)，(AB)和(AB)都是命题公式。⑷当且仅当有限次地应用⑴，⑵，⑶所得到的含有命题变元、联结词和括号的符号串是命题公式。这里所谓的命题公式可以解释为由命题变元,命题联接词及圆括号组成的符号。 命题逻辑下面的式子不是命题公式：P∧Q，PR，（P∨Q）∧R）下面的式子才是命题公式：(P∧Q)，(PR)，((P∨Q)∧R)按照合式公式定义最外层括号必须写。约定：为方便，最外层括号可以不写，上面的命题公式可以写成：P∧Q，PR，(P∨Q)∧R 命题逻辑命题公式的真值表一个命题公式不是命题，所以它没有真值，但是给其中的所有命题变元作指派以后它就有了真值。可以以表的形式反应它的真值情况，例如命题公式(PQ)∨Q的真值表如下所示：PQPPQ(PQ)∨QFFTFFFTTTTTFFTTTTFTT 命题逻辑由于对每个命题变元可以有两个真值(T,F)被指派，所以有n个命题变元的命题公式A(P1,P2,…,Pn)的真值表有2n行，每个指派对应公式的一个确定的值。公式值的确定是按公式中联结词出现的先后顺序及括号顺序逐步应用命题联结词的真值表规定而得到的。 命题逻辑所谓命题符号化，就是用命题公式的符号串来表示给定的命题。命题符号化的方法1.首先要明确给定命题的含义。2.对于复合命题，找联结词，用联结词断句，分解出各个原子命题。3.设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。4.为了减少括号的使用，在此做下列规定：(1)5个联接词的结合能力从强到弱顺序为：“否定”，“合取”，“析取”，“蕴含”，“等价”。(2)规定具有相同结合能力的联接词，按照出现的先后次序，先出现者先运算，凡符合此要求者，括号均可除去。(3)最外层括号可省去。 命题逻辑例1.说离散数学无用且枯燥无味是不对的。P：离散数学是有用的。Q：离散数学是枯燥无味的。该命题可写成：(P∧Q)例2.如果小张与小王都不去，则小李去。P：小张去。Q：小王去。R：小李去。该命题可写成：(P∧Q)R例3.如果小张与小王不都去，则小李去。该命题可写成：(P∧Q)R也可以写成：(P∨Q)R 命题逻辑例4.仅当天不下雨且我有时间，才上街。P：天下雨。Q：我有时间。R：我上街。分析：由于“仅当”是表示“必要条件”的，既“天不下雨且我有时间”，是“我上街”的必要条件。所以该命题可写成：R(P∧Q)例5.人不犯我，我不犯人；人若犯我，我必犯人。P：人犯我。Q：我犯人。该命题可写成：(PQ)∧(PQ)或写成：PQP是Q的必要条件P是Q的充分条件P是Q的充分且必要条件 命题逻辑重言式(永真式)与矛盾式(永假式)例子：PP∨PP∧PFTFTTF可见不论P取什么真值P∨P的真值总是为真，P∧P的真值总是为假。故称P∨P为重言式(永真式)，称P∧P为矛盾式(永假式)。 命题逻辑重言式(矛盾式)定义A(P1,P2,…,Pn)是含有命题变元P1,P2,…,Pn的命题公式，如不论对P1,P2,…,Pn作任何指派，都使得A(P1,P2,…,Pn)为真(假)，则称之为重言式(矛盾式),也称之为永真式(永假式)。重言式的证明方法方法1：列真值表。方法2：公式的等价变换，化简成“T”。方法3：用公式的主析取范式。 命题逻辑方法1.列真值表。例如，证明(P∧(PQ))Q为重言式。PQPQP∧(PQ)(P∧(PQ))QFFTFTFTTFTTFFFTTTTTT永真式的真值表的最后一列全是“T” 命题逻辑永真式的性质1).如果A是永真式，则A是永假式。2).如果A，B是永真式，则(A∧B)、(A∨B)、(AB)和(AB)也都是永真式。有些重言(永真)式，如(P∧(PQ))Q，公式中间是“”联结词，是很重要的，称之为重言蕴含式。 命题逻辑重言(永真)蕴含式定义：如果公式AB是重言式，则称A重言(永真)蕴含B，记作AB。注意符号“”不是联结词，它是表示公式间的“永真蕴含”关系，也可以看成是“推导”关系。即AB可以理解成由A可推出B，即由A为真，可以推出B也为真。 命题逻辑性质1).有自反性：对任何命题公式A，有AA2).有传递性：若AB且BC，则AC3).若AB且AC，则AB∧C4).若AB且CB，则A∨CB我们可以通过列真值表(即列永真式的真值表)来证明重言(永真)蕴含式。 命题逻辑重要的重言蕴含式(如教材第182页所示)I1.P∧QPI2.P∧QQI3.PP∨QI4.QP∨QI5.PPQI6.QPQI7.(PQ)PI8.(PQ)QI9.P(QP∧Q)I10.P∧(P∨Q)QI11.P∧(PQ)QI12.Q∧(PQ)PI13.(PQ)∧(QR)PRI14.(P∨Q)∧(PR)∧(QR)RI15.AB(BR)(AR)I16.AB(RB)(A∨RB) 命题逻辑等价公式例子看下面三个公式的真值表PQPQP∨QQPFFTTTFTTTTTFFFFTTTTT从真值表可以看出，不论对P、Q作何指派，都使得PQ、P∨Q和QP的真值相同，表明它们之间彼此等价。 命题逻辑定义：A、B是含有命题变元P1,P2,…,Pn的命题公式，如不论对P1,P2,…,Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价，记作AB,或者称A与B相等，记作A=B.显然PQ=P∨Q=QP重要的等价公式（p178)⑴对合律P=P⑵幂等律P∨P=PP∧P=P⑶结合律P∨(Q∨R)=(P∨Q)∨RP∧(Q∧R)=(P∧Q)∧R⑷交换律P∨Q=Q∨PP∧Q=Q∧P 命题逻辑⑸分配律P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)⑹吸收律P∨(P∧Q)=PP∧(P∨Q)=P⑺德-摩根定律(P∨Q)=P∧Q(P∧Q)=P∨Q⑻同一律P∨F=PP∧T=P⑼零律P∨T=TP∧F=F⑽互补律P∨P=TP∧P=F⑾PQ=P∨Q⑿PQ=QP⒀PQ=(PQ)∧(QP)⒁PQ=(P∨Q)∧(P∨Q)⒂PQ=(P∧Q)∨(P∧Q) 命题逻辑为便于记忆，将等价公式(前10个)与集合论的公式比较，(书p7)请看集合公式：⑴对合律~~AA~A表示A的绝对补集⑵幂等律A∪AAA∩AA⑶结合律A∪(B∪C)(A∪B)∪CA∩(B∩C)(A∩B)∩C⑷交换律A∪BB∪AA∩BB∩A⑸分配律A∪(B∩C)(A∪B)∩(A∪C)A∩(B∪C)(A∩B)∪(A∩C)⑹吸收律A∪(A∩B)AA∩(A∪B)A⑺德-摩根定律~(A∪B)~A∩~B~(A∩B)~A∪~B⑻同一律A∪ΦAA∩EAE表示全集⑼零律A∪EEA∩ΦΦ⑽否定律A∪~AEA∩~AΦ 命题逻辑例题1.求证(P∨Q)→(P∧Q)P证明(P∨Q)→(P∧Q)(P∨Q)∨(P∧Q)(公式E11)(P∧Q)∨(P∧Q)(摩根定律)(P∧Q)∨(P∧Q)(对合律)P∧(Q∨Q)(分配律)P∧T(互补律)P(同一律） 命题逻辑例题2.化简(P∧Q)→(P∨(P∨Q))解原公式(P∧Q)∨((P∨P)∨Q)(E11,结合)(P∧Q)∨(P∨Q)(对合律，幂等律)(P∧Q)∨(Q∨P)(交换律)((P∧Q)∨Q)∨P(结合律)（Q∨(Q∧P)）∨P（交换律）Q∨P(吸收律) 命题逻辑等价公式的对偶性从前面列出的等价公式看出，有很多是成对出现的。⑴对偶式：在一个只含有联结词、∨、∧的公式A中，将∨换成∧，∧换成∨，T换成F，F换成T，其余部分不变，得到另一个公式A*，称A与A*互为对偶式。例如:：AA*PPQ∧RQ∨R(P∨T)∧Q(P∧F)∨Q 命题逻辑对偶原理：令A(P1,P2,…,Pn)、B(P1,P2,…,Pn)是只含有联结词、∨、∧的命题公式，则如果A(P1,P2,…,Pn)B(P1,P2,…,Pn)则A*(P1,P2,…,Pn)B*(P1,P2,…,Pn)下面我们验证一下对偶原理：P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)P∨TTP∧FF 命题逻辑命题逻辑推理推理就是根据一个或几个已知的判断得出一个新的判断的思维过程。称这些已知的判断为前提。得到的新的判断为前提的有效结论。实际上，推理的过程就是证明永真蕴含式的过程，即令H1，H2，…，Hn是已知的命题公式(前提)，若有H1∧H2∧....∧HnC则称C是H1，H2，…Hn的有效结论，简称结论。记为H1，H2，....，HnC 命题逻辑在推理过程中，还要应用永真蕴涵式I1-I16和等价公式E1-E22(常用的公式要熟记)。下面主要介绍推理方法：直接推理，就是从前提直接推出结论。上面讲到推理的过程实际上是证明永真蕴含式的过程。反证法的主要思想是：假设结论不成立，可以推出矛盾的结论(矛盾式)。 命题逻辑范式就是命题公式形式的规范形式。分为析取范式与合取范式1.析取范式：公式A如果写成如下形式：A1∨A2∨...∨An(n≥1)其中每个Ai(i=1,2..n)是合取式，称A的析取范式。2.合取范式：公式A如果写成如下形式：A1∧A2∧...∧An(n≥1)其中每个Ai(i=1,2..n)是析取式，称A的合取范式。 命题逻辑可以看出:在析取范式与合取范式中只含有联结词,∧,∨,并且在命题变元之前例如，PQ的析取范式与合取范式：PQ(P∧Q)∨(P∧Q)----析取范式PQ(P∨Q)∧(P∨Q)----合取范式注:∵P∨PPP∧PP∴P是合(析)取式. 命题逻辑析取范式与合取范式的写法⑴先用相应的公式去掉和。公式E16PQP∨Q公式E21PQ(P∧Q)∨(P∧Q)公式E20PQ(PQ)∧(QP)再用E16PQ(P∨Q)∧(P∨Q)⑵用公式的否定公式或摩根定律将后移到命题变元之前。A(P1,P2,…,Pn)A*(P1,P2,…,Pn)底-摩根定律(P∨Q)P∧Q(P∧Q)P∨Q⑶用分配律、幂等律等公式进行整理，使之成为要求的形式。 命题逻辑例如求(PQ)R的析取范式与合取范式(PQ)R((P∨Q)∧(P∨Q))∨R(P∧Q)∨(P∧Q)∨R------析取范式(PQ)R((P∧Q)∨(P∧Q))∨R((P∨Q)∧(P∨Q))∨R(P∨Q∨R)∧(P∨Q∨R)---合取范式 命题逻辑主析取范式与主合取范式一个公式的析取范式与合取范式的形式是不唯一的。下面定义形式唯一的主析取范式与主合取范式。主析取范式（特异析取范式）1.小项定义：是n个命题变元的合取式，其中每个变元必出现且仅出现一次，称这个合取式为小项。例如，有两个变元的小项：P∧Q、P∧Q、P∧Q、P∧Q小项可编码:用1表变元本身,0表变元的否定形式,则 命题逻辑m00P∧Qm01P∧Qm10P∧Qm11P∧Q(2)小项的性质m11m10m01m00PQP∧QP∧QP∧QP∧Q00FFFFFT01FTFFTF10TFFTFF11TTTFFFa).有n个变元，则有2n个小项。 命题逻辑b).每个小项当且仅当其真值指派与编码相同时,其真值为T;其余2n-1组真值指派均使该小项的真值为F。c).全体小项的析取式为永真式,记为:∑mi=m0∨m1∨…∨m2n-1⇔T2.主析取范式定义若一个命题公式的析取范式为A1∨A2∨...∨An,,其中每个Ai(i=1,2..n)都是小项，则称之为该命题公式的主析取范式。 命题逻辑例如求PQ和PQ的主析取范式PQPQPQFFTTFTTFTFFFTTTTPQm00∨m01∨m11(P∧Q)∨(P∧Q)∨(P∧Q)PQm00∨m11(P∧Q)∨(P∧Q)一公式的真值表中，使其为T的指派所对应的小项构成的析取范式为主析取范式。 命题逻辑主合取范式（特异合取范式）大项：是n个命题变元的析取式，其中每个变元必出现且仅出现一次。例如，有两个变元的大项及其真值表：M00M01M10M11PQP∨QP∨QP∨QP∨Q00FFFTTT01FTTFTT10TFTTFT11TTTTTF 命题逻辑可看出大项的编码正好与小项相反:用0表变元本身,1表变元的否定形式。M00P∨QM01P∨QM10P∨QM11P∨Q大项的性质a).有n个变元，则有2n个大项。b).每个大项当且仅当其真值指派与编码相同时,其真值为F;其余2n-1组真值指派均使该大项的真值为T。c).全体大项的合取式必为永假式∑Mi=M0∧M1∧…∧M2n-1⇔F 命题逻辑主合取范式定义若一个命题公式的合取范式为A1∧A2∧...∧An,,其中每个Ai(i=1,2..n)都是大项，则称之为该命题公式的主合取范式。例如求PQ和PQ的主合取范式PQPQPQFFTTFTTFTFFFTTTTPQM10P∨QPQM01∧M10(P∨Q)∧(P∨Q)一公式真值表中使其为F的指派所对应的大项的合取即为主合取范式。 谓语逻辑问题的提出：(即命题逻辑的局限性)在前一章,一个原子命题只用一个字母表示，而不再对命题中的句子成分细分。这样有一些逻辑问题无法解决。请看下面的例子。例1.令Ｐ：小张是大学生。Ｑ：小李是大学生。从符号Ｐ、Ｑ中不能归纳出他们都是大学生的共性。我们希望从所使用的符号那里带给我们更多的信息，比如可以看出他们的共性。这种想法在前一章是无法实现的。 谓语逻辑例2.令Ａ：所有自然数都是整数。Ｂ：８是自然数。Ｃ：８是整数。这是著名的三段论推理，A是大前提，B是小前提，C是结论。显然，由Ａ和Ｂ可以推出结论Ｃ。这个推理是有效的，但是这个推理在前一章也是无法实现的。所以就要另外考虑表示命题的方法。 谓语逻辑解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念。令S(x)表示x是大学生，a:小张，b:小李命题P表示成S(a):小张是大学生。命题Q表示成S(b):小李是大学生。从符号S(a)、S(b)可看出小张和小李都是大学生的共性.令N(x):x是自然数。I(x):x是整数。表示所有的。A:x(N(x)→I(x))B:N(8)C:I(8) 谓语逻辑个体与个体变元定义：能够独立存在的事物，称之为个体。它可以是具体的，也可以是抽象的事物。通常用小写英文字母a、b、c、...表示。例如，小张、小李、8、a、沈阳、社会主义等等都是个体。定义：用小写英文字母x、y、z...表示任何个体，则称这些字母为个体变元。 谓语逻辑谓词定义：一个大写英文字母后边有括号，括号内是若干个个体变元，用以表示个体的属性或者个体之间的关系，称之为谓词。如果括号内有n个个体变元，称该谓词为n元谓词。例如S(x):表示x是大学生。一元谓词G(x,y)：表示x>y。二元谓词B(x,y,z)：表示x在y与z之间。三元谓词一般地P(x1,x2,…,xn)是n元谓词。 谓语逻辑命题函数谓词本身并不是命题，只有谓词的括号内填入足够的客体，才变成命题。例如，a表示小张，b表示小李，则S(a):小张是大学生。S(b):小李是大学生。Ｇ(7,3)表示:７>３。如果c表示锦州，d表示沈阳，e表示山海关，则B(c,d,e)表示：锦州在沈阳与山海关之间。这时S(a)、S(b)、G(7,3)、B(c,d,e)才是命题。 谓语逻辑令谓词S(x):x是大学生，括号内填入不同的人名，就得到不同的命题，故谓词S(x)相当于一个函数，称之为命题函数。定义：n元谓词P(x1,x2,…,xn)称之为简单命题函数。规定：当命题函数P(x1,x2,…,xn)中n=0时，即0元谓词，表示不含有客体变元的谓词，它本身就是一个命题变元。定义：将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。简单命题函数与复合命题函数统称为命题函数。 谓语逻辑给定简单命题函数：A(x)：x身体好，B(x)：x学习好，C(x)：x工作好，复合命题函数A(x)→(B(x)∧C(x))表示如果x身体不好，则x的学习与工作都不会好。个体域定义：在命题函数中命题变元的取值范围，称之为个体域。 谓语逻辑定义：由所有客体构成的个体域，称之为全总个域。它是个“最大”的个体域。下面用谓词命名式表示下列日常用语：例子（p197）一般讲，对日常语句可给出一个大体的准则：名词：专用名词为个体通用名词一般可为谓词。形容词：谓词动词：谓词代名词：人称代词，指示代词是个体，不定代词是量词。 量词例如：有些人是大学生。所有事物都是发展变化的。“有些”,“所有的”,就是对客体量化的词。定义：在命题中表示对客体数量的词，称之为量词。 谓语逻辑定义了两种量词：(1).存在量词：记作，表示“有些”、“一些”、“某些”、“至少一个”等。(2).全称量词：记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。定义：量词后边要有一个客体变元，指明对哪个客体变元量化，称此客体变元是量词后的指导变元。例如x(读作“任意x”)，x(读作“存在x”)，其中的x就是量词后的指导变元。 谓语逻辑例题１.所有的自然数都是整数。设N(x)：x是自然数。I(x)：x是整数。此命题可以写成x(N(x)→I(x))例题２.有些自然数是偶数。设E(x)：x是偶数。此命题可以写成x(N(x)∧E(x))例题3.每个人都有一个母亲。设P(x):x是个人。M(x,y):y是x的母亲。此命题可以写成x(P(x)→y(P(y)∧M(x,y))) 谓语逻辑谓词公式及命题符号化命题逻辑中有命题公式，类似地，在谓词逻辑中，要研究谓词公式。客体函数有些命题中，可能有若干个客体，其中有些客体之间有函数关系，例如例题1.如果x是奇数，则2x是偶数。其中客体x与客体2x之间就有函数关系，可以设客体函数g(x)=2x，谓词O(x)：x是奇数，E(x)：x是偶数，则此命题可以表示为：x(O(x)→E(g(x))) 谓语逻辑例题2小王的父亲是个医生。设函数f(x)=x的父亲，谓词D(x):x是个医生，a:小王，此命题可以表示为D(f(a)).例题3如果x和y都是奇数，则x+y是偶数。设h(x,y)=x+y，此命题可以表示为:xy((O(x)∧O(y))→E(h(x,y))像上述的g(x)、f(x)、h(x,y)就是客体函数，一般地用小写的英文字母f,g,h….表示客体函数。 谓语逻辑注意:客体函数与谓词是不同的，不可混淆.要注意区分客体函数与谓词间的区别：设例题1的个体域是自然数集合N。客体函数中的客体变元用客体带入后的结果依然是个客体(3∈N,g(3)=6，所以g(3)∈N)。谓词中的客体变元用确定的客体带入后就变成了命题，其真值为Ｔ或者为Ｆ(3∈N,O(３)是个命题,真值为T)。 谓语逻辑原子谓词公式定义：称n元谓词P(x1,x2,...,xn)为原子谓词公式。例如P、Q(x)、A(x,f(x))、B(x,y,a)都是原子谓词公式。谓词逻辑公式定义：谓词逻辑公式递归定义如下：1.原子谓词公式是公式。2.如果A、B是合式公式，则A、(A∧B)、(A∨B)、(A→B)、(AB)都是公式。3.如果A是公式，x是Ａ中的任何客体变元，则xＡ和xＡ也是公式。4.只有有限次地按规则(1)至(3)求得的公式才是公式。 谓语逻辑下面都是公式：P、(P→Q)、(Q(x)∧P)、x(A(x)→B(x))、xC(x)而下面都不是公式：xyP(x)、P(x)∧Q(x)x注意：公式x(A(x)→B(x))中x后边的括号不是最外层括号，所以不可以省略。 谓语逻辑定义：在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。例如xA(x)中x的辖域为A(x).x((P(x)∧Q(x))→yR(x,y))中x的辖域是((P(x)∧Q(x))→yR(x,y))y的辖域为R(x,y)。xyz(A(x,y)→B(x,y,z))∧C(t)x的辖域z的辖域y的辖域 谓语逻辑自由变元与约束变元在谓词公式中的客体变元可以分成两种，一种是受到量词约束的，一种是不受量词约束的。请看下面公式：x(F(x,y)→yP(y))∧Q(z)Ｆ(x,y)中的x在x的辖域内，受到x的约束，而其中的y不受x的约束。P(y)中的y在y的辖域内，受y的约束。Q(z)中的z不受量词约束。 谓语逻辑定义：如果客体变元x在x或者x的辖域内，则称x在此辖域内约束出现，并称x在此辖域内是约束变元。否则x是自由出现，并称x是自由变元。上例中x(F(x,y)→yP(y))∧Q(z)F(x,y)中的x和P(y)中的y是约束变元。而F(x,y)中的y和Q(z)中的z是自由变元。 谓语逻辑对约束变元和自由变元有如下几点说明：(1).对约束变元用什么符号表示无关紧要。就是说xA(x)与yA(y)是一样的。这类似于计算积分与积分变元无关，即积分∫f(x)dx与∫f(y)dy相同。(2).一个谓词公式如果无自由变元，它就表示一个命题。例如A(x)表示x是个大学生。xA(x)或者xA(x)就是个命题了，因为它们分别表示命题“有些人是大学生”和“所有人都是大学生”。 谓语逻辑(3).一个n元谓词P(x1,x2,…,xn)，若在前边添加k个量词，使其中的k个客体变元变成约束变元，则此n元谓词就变成了n-k元谓词。例如P(x,y,z)表示x+y=z，假设个体域是整数集。xyP(x,y,z)表示“任意给定的整数x，都可以找到整数y，使得x+y=z”。如果令z=1，则xyP(x,y,1)就变成了命题“任意给定的整数x，都可以找到整数y，使得x+y=1”,…。每当给z指定个整数a后，xyP(x,y,a)就变成了一个命题。所以谓词公式xyP(x,y,z)就相当于只含有客体变元z的一元谓词了。 谓语逻辑在一个谓词公式中，如果某个客体变元既以约束变元形式出现，又以自由变元形式出现，就容易产生混淆。为了避免此现象发生，可以对客体变元更改名称。如x(F(x,y)→yP(y))∧Q(z)(1).对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的辖域内此客体变元出现的各处同时换名。(2).改名后用的客体变元名称，不能与该量词的辖域内的其它变元名称相同。 谓语逻辑例如x(P(x)→Q(x,y))∨(R(x)∧A(x))此式中的x就是以两种形式出现。可以对x改名成z(P(z)→Q(z,y))∨(R(x)∧A(x))对自由变元也可以换名字，此换名叫代入。上例也可以对自由变元x作代入，改成x(P(x)→Q(x,y))∨(R(z)∧A(z)) 谓语逻辑1.所有大学生都喜欢一些歌星。令S(x)：x是大学生，X(x)：x是歌星，L(x,y)：x喜欢y。则命题的表达式为x(S(x)→y(X(y)∧L(x,y)))2.没有不犯错误的人。此话就是“没有人不犯错误”，“没有”就是“不存在”之意。令P(x)：x是人，F(x)：x犯错误，此命题的表达式为x(P(x)∧F(x))或者x(P(x)→F(x)) 谓语逻辑定义：若将给定的谓词公式中的命题变元，用确定的命题代替，对公式中的客体变元用个体域中的客体代替，这个过程就称之为对谓词公式作指派，或者称之为对谓词公式赋值。定义：给定谓词公式A，E是其个体域，如果不论对公式A作任何赋值，都使得A的真值为真，则称公式A在论域E上是永真式。如果不论对什么论域E，都使得公式A为永真式，则称A为永真式。 总复习复习重点第一章命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.永真式的证明.4.永真蕴涵式的证明,记住并能熟练应用常用公式.5.等价公式的证明,记住并能熟练应用常用公式.6.会写出命题公式的范式. 总复习第一章命题逻辑1.联结词：定义了六个逻辑联结词，分别是：(1)否定“”(2)合取“∧”(3)析取“∨”(4)异或“”(5)蕴涵“”(6)等价“”要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。：否定表示“不”∧：合取表示“不但…,而且...”“并且”∨：析取表示“或者－可兼取的或”；异或表示“或者－不可兼取的或”：蕴涵表示“如果…,则...”:等价表示“当且仅当”“充分且必要”可以将这六个联结词看成六种“运算”。 总复习联结词的定义(包括真值表和含义).特别要注意：“”的用法，它既表示“充分条件”也表示“必要条件”,即要弄清哪个作为前件,哪个作为后件.PQP∧QP∨QPQPQPQFFFFTTFFTFTTFTTFFTFFTTTTTTTF 总复习2.会命题符号化.例如P:我有时间.Q:我上街.R:我在家.表示P是Q的充分条件:如果p,则Q.只要P,就Q.PQ表示P是Q的必要条件:仅当P,才Q.只有P,才Q.QP如果P,则Q;否则R.(PQ)(PR)3.永真式的证明.方法1.列真值表.(R(QR)(PQ))P方法2.用公式的等价变换,化简成T. 总复习4.永真蕴涵式的证明,记住常用的公式.永真蕴涵式:AB是永真式,则称A永真蕴涵B.(AB)方法1.列真值表.方法2.假设前件真,推出后件真.(即直接推理)方法3.假设后件假,推出前件假.(即反证法)对于给定一个题,究竟是用哪种方法,原则上哪种都可以.但是哪个方法简单,要根据具体题而定.ABABFFTFTTTFFTTT 谓语逻辑5.等价公式的证明,记住常用的公式.方法1.列真值表.方法2.用公式的等价变换.必须记忆一些常用的公式永真蕴涵式:I1,I3,I9,I10,I11,I12,I13,等价公式:E1,E16,E18,E19,E20,E21, 6.命题公式的范式1)析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)是合取式.2)合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)是析取式.3)析取范式与合取范式的写法.4)小项及小项的性质.m3m2m1m0PQP∧QP∧QP∧QP∧Q00FFFFFT01FTFFTF10TFFTFF11TTTFFF 6)大项及其性质.M0M1M2M3PQP∨QP∨QP∨QP∨Q00FFFTTT01FTTFTT10TFTTFT11TTTTTF7)主析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)小项.8)主合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)大项. Dell网上直销典范(B2C) 网上零售——Dell(制造商直销的典范)Dell全球最大的计算机直销公司，1984年由MichaelDell(大学生)创建经营理念：为顾客定制生产计算机，减少中间环节，满足顾客的技术需求意识为各类企业以及政府、个人提供计算机产品和服务在德克萨斯州奥斯汀总部直接接受订单可通过电话、传真、互联网为Dell客户提供支持2001年的$319亿的收入中有一半来自网上销售 网上零售——Dell(制造商直销的典范)商业模式简化了公司的运作，消除了对批发商和零售商的依赖，降低了产品价格，并使Dell能够完全控制自己的客户数据库组装速度与直接从库存取货一样迅速库存周期：5天~2.5天(Compaq,IBM50~90天)网络服务：产品查询、完成订单、商品采购、实时跟踪订单、营销数据库 网上零售——Dell(制造商直销的典范)财务分析 网上零售——Dell(制造商直销的典范)战略分析经营策略增加新业务：担保、网络接入、软件等(称为机箱外收入：占18%；利润：占37％)销售和营销手段：网络、电视、商业贸易出版物，营销队伍竞争对手：PC传统提供商 网上零售——Dell(制造商直销的典范)技术：生产能力、管理能力依赖于其复杂的MIS'