资料课件讲义英文版课件2 1

Chapter2第二章LOGIC逻辑,Logicisthediscipline(学科)thatdealswiththemethodsofreasoning(推理).,逻辑是讨论推理方法的一门学科。一般来说，逻辑为确定一个给出的论证是否有效提供各种法则和技巧。逻辑推理在数学里常用来证明定理，在计算机科学里用来检验程序的正确性和证明定理，在自然科学和物理学里用来从实验导出结论，在社会科学和人们日常生活里用来求解大量的问题。确确实实，人们经常使用逻辑推理。在这一章将讨论它的一些基本概念。,Theexampleofreason,IfIamyourteacherthenIshouldgiveyoulessons.Iamyourteacher.SoIshouldgiveyoulessons.Isitright?Maybejustnow!,Anotherexampleofreason,Ifyouinvestinthestockmarketthenyouwillgetrich.Ifyougetrichthenyouwillbehappy.so,ifyouinvestinthestockmarketthenyouwillbehappy.Isitright?Maybejustnow!,Anotherexampleofreason,iftaxesarelowered,thenincomerises.incomerises.so,taxesarelowered.Isitright?Maybejustnow!,2.1PropositionsandLogicalOperations命题与命题逻辑,1.Proposition命题：Astatement(orproposition命题)isadeclarativesentencethatiseithertrueorfalse,butnotboth.命题是或者为真或者为假而不是两者同时成立的一条陈述句.,1+1=2Johnisastudent.TodayisTuesday.2isanoddnumberIamateacher.,Examples：,Truthvalue:Thevalue(result)oftheproposition.OneoftheelementfromsetTrue,False.,MoreExamplesofProposition,DoyouspeakEnglish?Thisisaquestion,notastatement.Letsgo!Itisnotastatement,butacommand.3-x=5.xisavariable,sothetruthvalueofthissentenceisopen.The4-colorguessistrue.Webelievethatitistrueorfalse,butnotbothevenbeforeitwassolved.ThesunwillcomeouttomorrowItisastatementWhatagoodmanheis.ItisnotastatementIamlying.Itisaparadox.,Inlogic,thelettersp,q,r,.denotepropositionalvariables(命题变量);thatis,variablesthatcanbereplacedbystatements.Suchasp:Thesunisshiningtoday.q:Itiscold.Statementsorpropositionalvariablescanbecombinedbylogicalconnectives(联结词)toobtaincompoundstatements(复合命题).wemaycombinetheprecedingstatementsbytheconnectiveandtoformthecompoundstatementpandq:Thesunisshininganditiscold.,2.LogicalConnectivesandCompoundStatements逻辑联结词和复合命题,Asimplestatementcanberepresentedbyanatomproposition.Morethanoneatompropositionscanbecombinedintoacompoundstatement.Thecombinationisachievedusing“connectives”.Usually,theconnectiveroughlycorrespondssomeconjunctiveinthenaturallanguage.,Sowelearnthat,Whatisthetruthvalueofacompoundstatement?Dependsonthetruthvalueofeachatomproposition;Dependsontheconnectives.Theconnectiveisdefinedexactlyusing“truthtable”.,若p为真，则p为假，若p为假，则p为真。严格地讲，“非”不是联结词，因为它不连接两个命题，p不是真正的复合命题。然而，“非”是命题集合的一元运算。若p是命题，那么p也是命题。,themostimportantconnectives,Negation否定,非：Ifpisastatement,thenegation(否定,非)ofpisthestatementnotp,denotedbyp.pisthestatement“itisnotthecasethatp.”,(2)Conjunction合取：Ifpandqarestatements,theconjunction(合取)ofpandqisthecompoundstatement“pandq(p且q)”,denotedbypq.Theconnectiveandisdenotedbythesymbol.Thecompoundstatementp/qistruewhenbothpandqaretrue;otherwise,itisfalse.InthelanguageofSectionl.6,andisabinaryoperationonthesetofstatements.,Truthtablefor,(3)Disjunction析取:Ifpandqarestatements.thedisjunction(析取)ofpandqisthecompoundstatement“porq,”denotedbypq.Theconnectiveorisdenotedbythesymbol.Thecompoundstatementpgistrueifatleastoneofporqistrue;itisfalsewhenbothpandqarefalse.,Truthtablefor,联结词“或”比联结词“且”更复杂，因为在语言里“或”的使用有两种不同的方法。假设说“我星期一去西班牙或我星期五去西班牙”，在这样的复合命题中，有命题析取p:“我星期一去西班牙”和q:“我星期五去西斑牙”当然，两种可能性只有一种发生，不可能两者同时发生。因此联结词“或”是在不兼容(exclusive)的意义上使用的。另一方面，考虑析取“我的数学及格了或我的法语未及格”，在这种情况下，两种可能性至少有一种发生。然而，两者也可同时发生。因此，联结词“或”是在兼容(inclusive)的意义上使用的。在数学和计算机科学中，人们约定总是在可兼容方式上使用联结词“或”。,Ingeneral,acompoundstatementmayhavemanycomponentparts,eachofwhichisitselfastatement,representedbysomepropositionalvariable.,命题s:p(q(pr)包含三个命题:p,q,r,其中每一个又可以独立地取真或假.对于p,q和r真值的组合情况,总共存在23即8种可能.在s的真值表中给出了所有这些情况下s的真或假.,Ifacompoundstatementscontainsncomponentstatements.therewillneedtobe2nrowsinthetruthtablefors.Suchatruthtablemaybesystematicallyconstructedinthefollowingway:,STEP1:表的开始n列用分命题变量标明，其余的列是变量的中间组合，最后一列是完整的整个命题。,STEP2:在开始的n个标题的每一个下面，列出n个分命题2n种可能的n元真值.,STEP3:对余下的列，按次序计算各自的真值.,Howtomakeatruthtable?,3.Predicate谓词,InSection1.1,wedefinedsetsbyspecifyingapropertyP(x)thatelementsofthesethaveincommon.Thus,anelementofxP(x)isanobjecttforwhichthestatementP(t)istrue.SuchasentenceP(x)iscalledapredicate(谓词).因为在英语里,性质在语法上就是谓词.,Ifxisaninteger,“xislargerthan2”isnotaproposition.ItcanbedenotedasP(x),apropositionalfunction(命题函数)，因为x的每种选择产生一个或为真或为假的命题P(x)。ThedomainofPisthesetofallelements,andTherangeofPistrue,falseApropositionalfunctionP(x)isalsocalledapredicate(谓词).,Ifxisaninteger,“xislargerthan2”isnotapropositionLetP(x):xislargerthan2.isP(x)aproposition?No!Howtomakeapredicateproposition?P(3)isapredicateproposition.“Forallx,P(x)”isaproposition.“Thereexistsanx,P(x)”isaproposition.,Theuniversalquantification(全称量化)ofapredicateP(x)isthestatement“Forallvaluesofx,P(x)istrue.”WeassumeherethatonlyvaluesofxthatmakesenseinP(x)areconsidered.TheuniversalquantificationofP(x)isdenotedxP(x).Thesymboliscalledtheuniversalquantifier(全称量词).,UniversalquantificationcanalsobestatedinEnglishas“foreveryx,”“everyx,”or“foranyx.”(“对每一个x”、“所有x”或“任意x”.),4.Quantifiers量词,Giventhedomain,“forallx,P(x)istrue.”isastatement,thatisthesentenceiseithertrueorfalse,butnotboth.WhenP(x):x2,Howaboutthetruthvalueof“forallx,P(x)”?Ifxisrealnumber,andP(x)represents“-(-x)=x”,howaboutthetruthvalueofxP(x)?,谓词可以含有几个变量，全称量化可以施加到每个变量上.例如，交换性质可表示为:xy,xy=yx.,Theexistentialquantification(存在量化)ofapredicateP(x)isthestatement“ThereexistsavalueofitforwhichP(x)istrue.”TheexistentialquantificationofP(x)isdenotedxP(x).Thesymboliscalledtheexistentialquantifier(存在量词).,InEnglishxcanalsoberead“thereisanx,”“thereissomex,”“thereexistsanx,”or“thereisatleastonex.”(“存在一个x”、“存在某个x”、“有一个x”或“至少存在一个x”),WhenP(x):x2,Howaboutthetruthvalueof“thereisanx,P(x)”?Ifa,barerealconstants,ab,P(x)means“axb”,howaboutxP(x)?,NegationofQuantifications量词的否,Domainofrealnumber(-0)isassumedNegationofuniversalquantificationForallx,thesquareofxispositiveThereexistssomex,thesquareofxisnotpositive.NegationofexistentialquantificationThereexistssomex,5x=x.Forallx,5xisnotequaltox.,存在量化可以应用到谓词里的几个变量上，并且量化的次序被认为不影响真值.对于有几个变量的谓词，既可以应用全称量化也可以应用存在量化。在这种情况，与先后次序有关。,MultipleQuantifiers量词的多重使用,ConsideringthesetofrealnumbersandP(x,y)meansx=y+1.WhatisthemeaningandtruthvalueofxyP(x,y)?WhatisthemeaningandtruthvalueofxyP(x,y)?WhatisthemeaningandtruthvalueofxyP(x,y)?WhatisthemeaningandtruthvalueofxyP(x,y)?xyP(x,y)andyxP(x,y)havethesametruthvalues,andtheyarefalse.xyP(x,y)andyxP(x,y)havethesametruthvalues,andtheyaretrue.xyP(x,y)istrue,butxyP(x,y)isfalse.xyP(x,y)istrue,butyxP(x,y)isfalse.,ExamplesofQuantification,