comp 210离散结构公告lect2选举.pptxVIP

COMP210

DiscreteStructuresAnnouncement:Today’slectureslidesandHW#1areavailableonthecoursewebpage.Today’scontents:QuantifierNestQuantifier

OverviewPropositionLogicConditionalPropositionTautologyandContradictionLogicalEquivalence

PropositionLogicProposition,YESorNO? 4+5=5 X+4=5 X+3=5foranychoiceofXin{5,6,7} X-3=5forsomeXin{1,2,3}YESYESYESNo

PropositionLogicSupposeP(x,y)=“xy”Proposition,YESorNO? P(x,y) P(3,4) P(x,9)YESNoNo

PropositionalFunction-PredicateApropositionalfunction(orpredicate)P(x)isastatementinvolvingavariablex.Forexample:P(x)=“2xisaneveninteger”xisanelementofasetD,DiscalledthedomainofdiscourseofP(x).Forexample,D={allpositiveintegers},andP(X)istrue.D={0.5,1.5,2.5},andP(x)isfalse

MoreExamplesQ(x,y)=“x-y=y-x”,D={allrealnumbers} Q(x,y)=Tifx=yFifx?y

ForeveryandforsomeMoststatementsinmathematicsandcomputerscienceusetermssuchasforeveryandforsome.Forexample:ForeverysquareS,thesumoftheanglesofSis360degrees.Foreveryintegern,nislessthanp,forsomeprimenumberp.

UniversalQuantifierOnecanwriteP(x)foreveryxinadomainDInsymbols:?xP(x)?iscalledtheuniversalquantifierTheuniversalquantifierofP(x)isaproposition:?xP(x)isTRUEifP(x)istrueforeverysinglex.?xP(x)isFALSEifthereisanxforwhichP(x)isfalse.

UniversalQuantifierExamples:D={allrealnumbers},P(x)=“|x|=0”,Q(x)=“x=0”.?xP(x):foreveryrealnumberx,|x|=0.?xQ(x):foreveryrealnumberx,x=0.TrueFalse

ExistentialquantifierForsomex?D,P(x)istrueifthereexistsanelementxinthedomainDforwhichP(x)istrue.Insymbols:?xP(x)Thesymbol?iscalledtheexistentialquantifier.?xP(x)isFALSEifP(x)isfalseforeverysinglex.?xP(x)isTRUEifthereisanxforwhichP(x)istrue.

ExistentialQuantifierExamples:D={allrealnum