### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DISCRETE STRUCTURES II CS 251

PSU

GPA 3.91

### View Full Document

## 52

## 0

## Popular in Course

## Popular in ComputerScienence

This 67 page Class Notes was uploaded by Orrin Rutherford on Tuesday September 1, 2015. The Class Notes belongs to CS 251 at Portland State University taught by Martin Cenek in Fall. Since its upload, it has received 52 views. For similar materials see /class/168276/cs-251-portland-state-university in ComputerScienence at Portland State University.

## Reviews for DISCRETE STRUCTURES II

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/01/15

Discrete Structures CS 251 Lecture 8 Examples Section 82 552009 Example xx1xlt5 We can use the AA to construct the precondition from the post condition as xllt5 x x1xlt5 Example Considerthe following statement xlt3xx1xlt5 Is this statement correct Yes but we ve seen that x1lt5xx1xlt5 2 is also correct but the two preconditions don t match How can be prove that 1 is correct Example Contd Prove the correctness of xlt3 x x1xlt5 Proof 1 x1lt5x x1xlt5 AA 2 xlt3 3 x1lt5 T 4 xlt3 x1lts 2 3 CP 5 xlt3 x xl xlt5 Consequence Rule QED Consequence Rule PAR andRSQ P SQ P ST andTgtQ P SQ Nate Each cunsequence rule requirestwu pruufs a pruuf ur curredness and a pruuf ur an implicatiun Example Prove the correctness of x lt 3 x x 1x lt 3 AAgives usxlt4xx lxlt3 The two preconditions don t match The proof of the wff requires the proof of l Implication x lt 3 x lt 4 2 Which can be included in the proof of correctness of the wff Example Prove the correctness of x lt 3 x x 1x lt 3 Proof lxlt4xx lxlt3 AA 2xlt3 P 3xlt4 2T 4xlt3xlt4 23CP 5xlt3xx 1xlt3 QED 552009 l 4 Consequence Example Prove the correctnessof axw2xlyy33xw2x1l Proof 13x1v32x1lvv33xlv2x1l AA 23xlv2xl P 3V2c 41v2cllv32c3l 32c3 6v321c1l1 73xlv32x1 are 83xlv2xl3xlv32x1l 27CP 9 3x w 2xlv v sax w 2x 1 1 8 Consequence QED 2 n EE where m x 3 3 4 MP Composition of two statements Most basic control structure Composition of two statements 51 and 52 denoted by SlSZ Read as execute Sl thenSZ Composition Rule P 31 Q andQ 32 R P St s2 R 1 Can be used to prove the composition of two statements 2 Extends naturally to any number of program statemenm Example Prove the correctness of 39 2xxy 3xlt 1 Proof 1y 3lt1xy 3xlt1 AA equiv x as m 3 2x 3 lt1y 2x x y 3xlt 1 1 2 Composition 4Xlt2 P 52xlt4 4T 62x 3lt1 5T 7 x lt 2 gt2X 3 lt1 4 6 CP 8 x lt 2y 2x x y 3xlt 1 3 7 Consequence QED IfThen Rule PACSQandPmCgtQ 39PifCthenSQ A typical lfaThen Stateme nt Statement lPl lflcondilion lcn Then lstalemenl lsn Endl Statement CU Example Prove the correctness oflxgt a ifgtltgt 1 then xx71xgt a Free 1x71gt0xx71xgt0 AA 2lxgt0llxgt1l P 3xgt1 2 Simp 4x 3 T 5lxgt0llxgt1llxm1gt0l 6lxgt0llxgt1lxx71xgt0 7lxgtulAalxgt1l 8xgt0 7 Simp 9lxgtulAalxgt1llxgtul 78CP 10 lxgtugt ifxgt1thenxx71xgt0 s 9 lfrThen QED 2 4 CP 1 5 Consequence P 552009 IfThenElse Rule P A ClsilQ and P A a ClsalQ P if CLhen S elseS2 Q Atyglcal lfrTherirElse statement statement statement o While Rule P ACSP P While Cdo S P mC A tyglcal WhilerDu statement statement p E R a statement p 1 since the statements may etecute more than once there must be close connection between the recondition and oostcondiu39ons Z P is called the loop invariant because it must be true before and after the execution of the statements Prove the correctness ofthe followingwff where intx means x is an integer This wff matches the conclusion of the while rule where M So by the while rule the wff will be correct if we can prove the correctness of Example mm A 0 hile everix do x xZ iritgt o x P iritxx gt 0 Ceverix and s P Clx xZ P Example Contd FAQX xZ P Proof 1 intlxZl A lxZ gt 0x xZ lintlxl A lx gt all l AA 2intlxllxgt0levenlx PlThisisPACl 2 Simp xZ gt 0 5 intlxl A evenlxl 2 Simp s intlxl A evenlxl a intlxZl T 7 int x 2 5 6 8 intlx2l A lx2 gt 0 4 7 Conj 9 intlxl A lx gt 0 A evenlxl a intlxZl A lxZ gt 0 8 CP 2 1o lStatement to be provedl 1 9 Consequence QED Discovering a loop invariant 39 two integers x s v the can be calculated by the formula ix vi 1 v 7x on The sum can 9 lt en Example sumxlx1l v also be talculated by the following program intlxl A intlvl A ix 5 vi Precondition A s i Xi whileiltvdo i i1 s7si 0d 5 ix W l v ix llZ Postcondition B Example Contd To prove the correctness or this program wrtA and a we need to rind a loop invariant P tor the whiiestaternent Then we need to prove the roiiowing three staternene As x P Pwhileiltydoii139s siodPiilty P a i lt y a B Notice that P should be a staternent involving the variables i s x and v 1 Can we assign PB7 No because B does notcontain y 2 Arter sorne trial and error a candidate tor P appears to be the statement sx iiex 1Zi y 552009 Array Assignment Suppose we trv to prove the correctness ofthe following wff ii ilA lalil 1 EU I 2 am 2 lfllve start the proofby using AA we obtain 2 ail2 all2 tail lfllve trv to use the consequence rule Butthe following lvffisfalse li ll lalil 1l 9 all 2 50 AA can t be used to prove correctness for arrav assignment We need a new axiom Array Assignment Axiom P ai t Qwhere P is obtained from 1 by Replace all occurrences ofai in 1 by t Replace alloccurrences ofaj in vaulfj ithent else ajquot Restriction An expression a may not occur in the expressions ian j Note lifAthen B else c A9 BlA laA cl so we can write lifjithentelseaj jltlAllizjlajl Example Prove the correctness of i j ai 1 alil 2 all 2 Proof ithen 2 else ajl zlali 2 aj 2 AAA ilAlalil1l P 3 39 4li jl9122l EATltriviall 5 li ll 9 Mi 2i 3AddT lorvacuousl 6ll39 399122llAlliiHlaiii2ll 4r5rC quotl 7lifj ithenZelseajl2 6T s lijllai 1i llifj ithenZelseajl2l 2 7c QED 1 s Consequence Termination of Loops The correctness of P S Q assumes that S terminates So we have to prove termination to have total correctness The state ofa computation at some point in time is the tuple of variable values at the point in the computation Idea for proving that a loop terminates Find a wellfounded set W lt and associate the state ofthe i h iteration ofthe loop with an element x E W such that x1 gt x gt x gt Since W is wellfounded the chain stops Therefore the loop terminates RECAPA partially ordered set set x R is called a wellrfounded setit Eg consider the set 12345 Then 123 ltgt is a well rounded set 552009 Termination Condition Given the followingwhileaprogmm with loop invariant P lehile c do 5 P A a c To prove that the program terminates perform the following actionswhere s is the state before S executes and t is the state afterSexecutes 1 Findawellafounded set ltwltgt 2 Find an expression f ofthe progmm variables 3 Prove that if P and C are true for state sthen flsliflllEW and flslgtflll Exa m p e Show that the following program terminates where intlx meansx is an integer intlx A x gt a while evenlx do x xZ intlx A x gt Dleddlxl lThentlx2l Choose the wellafounded set ltNltgt tet fix Assume inllxlA x gt 0 A evenlxl Thean NxgtDandx2kf0r some k6 Nwith kgt0 Sofislflxlx N and fill fix2 xZ k e N and 15 e x 2k gt k fill Therefore the program terminates ow Example The rollowmg program terminateswhere qx meansx isa rational number MXM QM whilexltv do Xi MXM aw MX 2V y12ud i l uf tet s x v Theri t x r 1v 12 choosethe wellafuurided set N ltgt Now try out some possible detimtioris or f x vexlsthisoilt tet x 12 and v 2 Then 5 x v 12 2 27 12 32 3 N 2 fxy Lv 7x1 lsthis ox Notetx 12andv 1Thenfsf121L112JL12JU e N Also 0 e x r 1v 12 32 32 i 327321 i a J a e n But 5 e t 3 x v iv ax39l lsthis ox NO Why Answer Letxlandy2 Then fs fxy li 2 l2 1il1l16N Also ft fx ly 12 Hz 52 i52 2ii12i1 EN Butfsft Example Prove termination with fx y i2y x Proof Assume qx qy xlt y Then fs fx y i2y x i i2v Zx i 2 1 We also have t fx 1 y 12 i2y 12 x 1 i2y 2x 172 0 So fs E N t 6 N and fs i 2y 2x igti2y 2x 1 t Therefore the program terminates QED Example Therollowmg program terminateswhere qx meansx is a rational number qx A qv A V gt 0 whilexgtvdo Xiexav od qx MWM V gt UM X 5 0 Proof Chuusethewelliuunded set ltNlt ng pDSSlbiE derimtions or f do nutwurk vTheritxavv show hat eachufthefolluwl 1 Km xiv NO tet 2 ari d v 14Therifsf1214 127 14 14 3 N x av 2 and v 1s Then 5 12 1s l12a 1s39l l3s39l 1 e n 12 a 1s1si3s a 1s L i14 l 1 e n But 5 e t 39l v 14 Then 5 12 14 i12 l 1 e r N EllAEI 1 e N But 5 1 x NOLE39L 2 and Alsuft f12a1414f1 4 1 4 552009 Example Prove termination with fx y erV l Proof Assume qx qy y gt 0 x gtyThen xy gt 1 Calculate fs and t fs fx Vl erV l E N and lxv l 2 2 because xy gt 1 flt flx v v ilx vlvT Tlxvl 1T lxyl 1 E N because lxyl 2 2 Also we have fs lxyl gt lxyl 1 ft So the program terminates QED 83 Higher order logic I A logic is higherorder ifit allows predicate names or function names to be quantified or to be arguments of a predicate Example The sentence quotThere is a function with a fixed pointquot can be formalized as Elf Elx Pfx x where P denotes equality Higher order logic and Sets I We can define higherorder logic in terms of sets because predicates and functions are sets I Example predicates Px is true iffx E P If Q is a set of 2tuples Qx y is true iff x y E Q I So a higherorder logic allows sets to be quantified or to be elements of other sets Functions and sets I Recap function can be thought of as a set of Ztuples fx y where xyE N then fllxi vll X y E N leivl Means x is mapped to y by f I fx y ifffxy is true iff x y E 1 Note 1 fx is a term 1 is a set or a predicate 2 Afunction cannot have a predicate as an argument But a predicate can have a predicatefunction as a argument Classifying logics by Order Order of a predicate The order of a predicate is 1 if its arguments are terms Otherwise the order is n l where n is the maximum order of the arguments that are not terms The order of a function is always 1 since it s arguments are always terms Examples 1 In the wff Px Qx P the order of p is one and the order of q is two 2 In the wff Px Qp Rq the orders of p q and r are l 2 and 3 respectively Note We agree that a set cannot be defined in terms of itself so we don39t allow something like PlQl QlPl in the same wff since itwould mean as Pand PE 11 Order of a quantifier The order of a quantifier is 1 if it quantifies a variable and 2 if it quantifies a function Otherwise the order is n l where n is the order of the predicate being quantified The order of wff is the maximum of the orders of its predicates and quantifiers An nthorder logic is a logic with wffs having order n or less 552009 Example 1 The wff Elf Elx Pfx x has order 2 2 What is the order of the following wff VB HB 6 EIR Elw BR Rw Answer The order is 3 As sets we have w E R E B E H where w is a variable Semantics A wff has meaning only with respect to an interpretation Choose a domain D 2 o Assign constants and free variables to elements of D o Assign free functions to functions over D o Assign free predicates to relations with respect to D Example Given the wff Vx EIP Px SP The predicate p has order 1 and the predicate S has order 2 So Px A SP can be written as xEPandPESoerPES So for any domain D we have x E D P E powerD and S E powerpowerD So P c Dand s c powerD We ll examine some different interpretations ofthe wff Example Interpretations Given the wff w vX 3P lPlxl sipii Let I be the interpretation with domain D a b There are four possible predicate definitions for s meditate De nition tors Sat Definition for s and am are buthtrue sa e istrue and am isfalse 542 isfalse and 5e istrue sbl and am are buthfalse 513 Example Contd Case 1 l S a b Since x varies over a b the wff W wrt I can be written as W EIP Pa SP EIP Pb SP E true true Let P a for the first part So a E P and P E S Let P b for the second part So b E P and P65 E true Example Contd Case 23 Given the wff W Vx EIP Px A SP 2 Let I be the interpretation with domain D a b and S b Since x varies over a b the wffW wrt I can be written 5 W 3P Pa A SP A 3PPb A SP E false A true Foreach P E S it followsthat pa is false ie a E P Efalse 552009 Example Contd Case 4 Given the wff W Vx EIP Px A SP 3 Let I be the interpretation with domain D la b and s 0 Then SlPl is false for all P c D So Wis false wrt i Example Given the wff w 3x VP lPlxl A SlPll W is unsatisfiable because for any interpretation with domain D P must vary over all predicates including P 0 wh39ch means plxl is false for all x E n Formal Proofs The quantifier inference rules extend to higherorder logics Terminology a lowercase letter p is used to represent an instantiation of P Example Provethat Vx ElP Px is valid 13x VP Px PforIPT 2 VP Pt 1 El 3 Pt 2 UI 4 a Pt 2 UI 5 Pt A Pt 3 4 Gen 6 false Example Alternate proof Prove that Vx EIP Px is valid Proof 1 Elx VP Px PforIPT 2 VP PM 1 El 3 truec 2 UI 4 false 3 T QED 1 4 IP Example Prove that EIP Vx Px is valid Proof l7 P Elx Px PforIPT 2 Elx truex 1 UI 3 truec 2 El 4 false 3 T QED 1 4 IP 552009 Exa m pl e Suppuse sameane mterpras tnetnnd tandem ya HB 9 3R 3w am A mm wttn dumzm D at sets HB means a e H am means RE a and Rw meanswe R A passtbxetarmax nterpretztmn LE39L D betne set uf an wmduws Then we havethequuwmg statements wvznes aye D Suwvznes werwmdaws saweu et a mum be a set at wmdaws HB meansa S aset at ase ufwmdaws 5a HB meansa tsa set ufmums 5a HB meansa tsa 5a tne w rmght be descnbed by Every bundtng a set uf mums tnat S a nause a bundtngwtn 10 Dr 255 mums nas a mom a set ufwmduws wttn a wmduw Example n tne brewbus aamp e we ebnsrdered tne we order wff a HB a 3R 3w am A Rw wnatrtwe wanttb tnrnk bt nbuse room and wrndbw as brewsates tb desen39be tnrngs Le tne dbmarn D rs the set of 3H tnrngs For aamp e nbusem means x rs a nbuse rOOmX means x rs a room an wrndbwot means x rs a wrn bw wa wou d we formah39ze tne sentence usrng tnese e57 Sohm39on vx nousem 9 av rOOmV A gtltv A 32 wrndbwa VZ ess rn r e sbmu39bn Rep ace nbuse by H room by R and wrndbw by w vx HX 9 av RV A gtltv A 32 wz VZ Q What Is the order of the WW 3 Discrete Structures CS 251 Settion 10 104 5192009 103 Abstract Data Types as Algebra An abstract data type ADT is an algebra in which the carriers i e the data sets and the operations can be programmed We ll look at some basic abstract data types Propositional log39cBool true false not and c i Boollme false Operations not B001 gt B001 and B001 x B001 B001 Review Cartesian product A x Bab l aEA and bEB Axioms nottrue false notfalse true andxy true iffx y true Natural Numbers We knowthe followingfacls about natural numbers 1 2 There is a function s N gtN called quotsuccessorquot with the property if xeN then sxeN shew 22 2 no 56 mx int 42 uctiph property if qX is a property pfx such that am is true and qX implies qSX then qX is true for all x eN Algebraic operations using natural numbers plus can be defined in terms of s plulervlv pluslslxlrvlslplulervllpluler slvll Multiplication lmultl can also be defined in terms of s multlo yl0 mu ltlslxlylplusl mu ltlxylyl Program operations using ifthen else Define plxl asthe predecessor relation such that plslxllx pluslxyl 39fx0henyelseslpluslplxlyll or pluslxyl lfx0 then yelse pluslplxlslyll Similarly multlxyl ifx0 then 0 else pluslmulllplxlylyl Thusthe basic operations can be programmed usinglhe succ and pred relations Abstract data type of natural numbers Natural numbers N Baal 0 iszero succ predgt Note Bool is included in the carrier to contain true or false remllsfor the test for Zero Carriers N Boolean Operations 0 e N iszeru N a Boolean succ N a N pred N gt N Axioms iszerolDltrue iszerolsucclxllfalse pred olo predlsicclxllx Example rne nonzero elements of N are distinctbecause socc is an iniection ie succx soccy implies x y Prove tnat socc is an iniection Proof lf succx soccy then apply pred to get x predsuccx predsuccy y Example Other useful operations equaD Letequal u xquot a Bool oe atest forequzlity To oerinetne equal reiation using oniytne prirnitives u healgebra consioer tneroiioiuing exarn equal23 equal12 equal01 false We replace each zgument by its predecessor until one of the zguments is zero We can oenine eooai asroiiows equal00 troe eooaiosoccy raise equalsuccx0 raise equzlsuccxsuccy equalxy r en we can cornpotetne eooai operation osingtnerecorsive oerinition Equalxr l iriszerox anoisze eiseir iszerux uriszemy tnen raise eise equzlpredx predy Example Other useful operations less than tet iesstnan quotX N gt Bool pe a test for lessrthari reiation To define the iesstnan reiation using only the prirnitives ortne algebra consioer tneroiioWing example ie 23less12lessU1true We can define eooai asroiiows se lessL7 succy troe sssuccx o ra se lesssuccx so ccy lessx y Then we can cornpote tne iess operation using the recursive oerinition lessxy ir iszeruythen raise eise ir iszeruxtheri troe eise lesspredx predy Lists The set of iists listslAl over a set A can be defined inductiver by usinglhe empty list lt gt and the cons operation lwith the infix form l as constructors We have the following inductive definition Basisltgte lislslAl induction lfx EAand L e listslAlthen conslxLl e lislslAl Abstract data type of lists Carriers listsA A Boolean perations ltgt 6 listsA isemptyL listsAgtBoolean cons A x listsA gt listsA head listsA gt A tall listsA gt listsA Axioms isemptyLltgt true isemptyLconsaL false headconsxLx tailconsxLL Example Let last listslAl AA return the rightmost element ofa nonempty list We can define last as follows lastlxl if isemptylxl then error else if isemptyllaillxll then headlxl eise lastltaillxll Strings Strings are similar to lists in that they both have length and their constructions are similar The set of all strings over an alphabet A can be defined inductively from the em t string A and the append operation to attach a letter to a string Let A denote the set of all strings over A we have the following inductive definition Basis AeA Induction ifx eA and seA then x s eA Abstract data type of strings rriers AA Boolean Operations A isemptyS AgtBoolean A XA gt Aquot heads Aquot gtA tailS Aquot gt Aquot Axioms isemptySA true isemptySa s false headSasa tailSass Stacks A stack is a structure satisfyingthe LIFO property of last in first out The main stack operations are 1 Push which pushes a new element onto stack Popwhich removes the top element from the stack Top which examines the top element ofa stack lsemptywhich checks is the stack is empty PENquot Abstract data type of stacks For any set A let StkslAl denote the set of stacks whose elements from ltA StksA aooieen Errurs emptystk isemptystk push pup tap Carriers A StksA aooieen Errors 0 rations emptySt e StksA isemptyStkStksA aooieen ush A x StksA gt StksA Axioms isemptyStkemptyStk true isemptyStkpushas false mpwusma 5 pupempty5tllt stackErmr tuppushas a tupempty5 k valueErmr Queues A queue is a structure satisfyingthe FIFO property offirst infirst out The main operations on a queue involve 1 Adding a new element 2 Examiningthefrontelement 3 Deletingthe front element Abstract data type of queues LetA oes setand om bethe set or queues werA ltA CA Boolean emptyQ isemptyt addQ frontQ delQgt Carriers Boolean Operations empty 6 Axioms isemptyQemptyQtrue isemptyQaddQaqfalse frontQaddQaq if isemptyQq then a e se frontQ o delQaddQaq if isemptyQq then o else addQa delQq Binary Trees Let BA denote the set of binary trees over a set A The main operations on binary trees involve l constructing a tree 2 picking the root and 3 picking the left and right subtrees 5192009 Abstract data types of binary trees if aEA and l r e BA let treel a r deribte a tree whbse rbbt is a and the left subtree is l and the right subtree is r abbl emptyTree isernptyTree tree rbbt left right s A BA abbleen ibns emptyTree e BA iserrlptyTree BA a abbleen 23 ltA at Carrier oberet Axibrns roottreelara Example Let leaves BlAl gt N return the number of leaves in a binaly tree We can define leaves as follows assuming we havethe ADT for natuml numbers leaveslernptyrl 0 leavesltreelemptyT x emptyTll 1 leavesltreelt x Rll leavesltl leaveisl ifsthenselse definition for leaves leaveslrl if isernptylrl then 0 else if isernptyllertlrll and isemptylrightlTll then 1 else leaveslleftlTll leaveslrightlTll Priority queues A priority queue is a structure satisfyingthe BIFO property best infirst out The main opemtions ofa priority queue include 1 Adding a new element 2 Accessingthe best element 3 Deletingthe best element Abstract data type of priority queues ltA m abbl emptyP insert better best delbestgt Carriers m bblesn oberstibn ernbty m ise ptyP leleabblesn better Aer a l best PAgtA insert AxPAygt m Axiums isernbtyvlernptyv tru lsemptyPlnsenap false bestlnsertap itisernptyvlblthens elself betterls bestp then 2 else bestlb delBestlnsertap it lsemptyPpthen emptyP elseitbetterls bestp then b seinsertls delBestp Examples How can we implement a stack with a priority queue Answer Let push insert pop delbest top best and better true 5192009 104 Relational Algebras Operations An algebra is called relational algebra if its Se39e mpe39a m h 39 t e carrier is a set of relations Operations on the 39 39 tt39b t relations are select prOJect and Jam 3 quot es ltrelation select project joingt Pmiectmnerat n 39 39 tuples indexed by a subset of the attributes or the relation Join Operatio L 39 39 tuples that are indexed by the union or the attributes or the two relations strrierr with I Nun I II I4vi mam 39 R S SeleCKRAti projRAC din R K running i2 rs 5 lti i in n Zl tx B rirrrtznr II C l lt B D l B H r t sinii 1 It39fk lenn Lin b a C 0 b L 039 x Ltnwlit lSi HM Hii x b gt r y a b c w z a n a r 11 r 1 Usetne students database to construct twa databases 5 and M rartne 5E CS department database and the Math department databa nsw a seiecti tudents Majar cs lBFranklin 123 S 75lTJeiquotferson 217cs 94 and M selectismdents Majar Mat lB Franklin 123 Math 75 rh n m id m1 credits or students who are double majoring in math and cs 39 le ID 39 39 le ID Fr dirll Then D juinlA B Example Contd Properties 3 From the database Family who are the children of Thomas Answer projectselectFamily Father Thomas Name ALincoln 2 Join is associative R gt4 Sgtlt T R gt4 S gt4 T 4 From the database Family who are E Franklin39s parents 3 selectselectRAalBblselectselectRBblAal Answer 4 proectselectRAalXl selectproectRXlAal iffAEX projectselectFamily Name E Franklin Mother Father Let I and J be the attribute sets for R an S Abiah Josiah 5 If I m then joinRSl R x S From the database Family who are children by Jane and 6 Let I J thenthe following four properties hold Peter al joinRSl R m 5 Notation joinR Si is sometimes denoted by R gtlt1 S 5quot Answer V blselectRUSAalselectRAaluselectSAal erircets lattgs grnilvr Father Peter Mothe39r Jimelr ci selectR m5 A al selectR A al mseiectis A al 39 dl selectR S A al selectR A al selectS A al 5192009 Example Prove tnatioin is associative R Igt q sygt lt T R M s IgtltT Proof Letl J K be the attribute sets of R S T Letx E w Sgtlt T Then thereaisttuples u 6RIgtltS and te T such natxA uA tor all A e lol and xA tA tor all A e K Sinceu e qu s thereaisttuples r ER and s e Ssuch tnatuA rA tor allA e l anduA sA tor all A e J 50 we havexA rA tor all A e l xA sA torallA e J and xA tA tor all A e K Letw e SIgtltT be de ned by wA sA tor all A e J and wA tA tor all A e J 50 we havexA wA tor all A e J U K SincexA rA tor all A e l it tollows thatx e RlgtltSlgtltT Therefore Rlgtlt sygtlti c R gtltltsgtltn The otner containment is sirnilar QED Functional Algebra ltFunctions operationsgt tuneu39ons to combine data obleets programming language leelt To do this we need sorne rules to do sorne reasoning The rules are axioms in the algebra ot n programs n tunetions are de ned on a set ot obleets tnat include atorns and lists Notation fx flglxll feg rlx lfaxthen bx elseolx 29b upleof mctluns tgnl Constant eg2 Primitive ageratlans id Theldentltymndlon ldx x ndtl Hezdzndell zpndlzpndr conszndthecunsR 1 2 selectors andunnut aaalean functions null testforempt list atarn testforan lt empty i5 und l at nedsymbu eq testforequzllty uftwu atarns ltrgtrr r antnrnetlo relations and operations Axioms in FF 1 faabcaafbfc or g such thatg if a then b else 0 if a then fb else fc Z aabc dad abdc org 7 if ad then bd else Cd 3 liar inl B G g ingl 4 l l l a c af bf c These axioms are the ruleswhich are used to reason about programs in programming language Example Define a function using FP called eoo tnattests its argurnents for 0 or eooxeoioxo er eo id 01 i 3 or eqid30 Example Write an FP definition of a function thatsubtracts 1 from its argumenm Ans Subl lio 11 462009 Proof Notes Let W denote the wff A gt B gt B Note this wff is not a tautology eg AB false Discrete Structures Now considerthe proof 1 A a P cs 251 Week 2 z A a a 12MP QED 130 lsec mm 64 711 I What is wrongwith the proof of W I Write down the statementthat the quotproofquot proves The conjunction of all the premises that you used to prove something is precisely the antecedent ofthe conditional that you proved Proof Notes 64 Formal axiom systems Suppose we have a wff that is not a tautology 39 What do we Want from proofs A A A s B V c s B We want our proofs to yield theorems that are 1 A P tautologies and we want any tautology to be provable as a theorem 3 B 12 MP Saundness All proofs yield theorems that are QED 123 CP tautologies What is wrong with the proof Completeness All ta utologies are provable as lDon39t apply inference rules to subexpressions of wffs I theorems 641 An example axiom system FregeLukasiewicz Axioms In the last class we studied that a formal Example FregeLukasiewicz Axioms where A reasoning system consists of d b B C represent any wff generate A set of wf39fs a set of axioms a set of inference rules prOPOSltlonal varlables and the two Is there a formal system for which the connectives and a propositional calculus is both sound and 1 A H B HA complete 2 A a B a C gt A gt B gtA gt C YESl 3quotAgtquotBgtBgtA Proof of CP rule A A A is a theorem provable from the FL axioms Lemma 1 A A A Proof 1 AABAgtAAgtA AgtAAgtBAgtAAgtAAgtA By axiom 2 where B B A A and CA 2AABAA AA Axiom 1 3AABAAAAAA By12MP 4AAgtBAgtA Axiom 1 5AAA 34MP QED 462009 Proof of CP rule fA is a premise in a proof of B then there is a proof ofA A B that does not use A as a premise Proof Assumption A is a premise in the proof of B Suppose B1 Bquot is a proof of B that uses the premise A We ll show by induction for each k in the interval is k s n that there is a proof of A A Bkthat does not use A as the premise Proof of CP rule Proof Contd If k1 then either B A or 813Xi0m or premise otherlhan A if B A then AA 31 AA A which by lemma 1 has a proofthat does not useA as a premise If Bfaxiom or premise other hanAthen 1 31 An axiom or premise otherlhan A 2 81AAAgt Bji Axiom1 AB 12 MP Proof Contd Assumefor each ilt kthereis a proofs a that does not useA as a premise Show that A A B does not use A as a premise Case 1 5A c se 2 5Axiom or a premise other than A For case 12 proof similar for k1 Case 3 5 Nolan axiom ora premise nah i as a human Hypothetical Syllogism lFrom the premises AA Band BA c here is a proof ofA A C Proof 1 AAgtB P 2 BAgtC P 3A P 4 B 1 3 MP 5 c 2 4 MP 6AA c 3 5 CP ED Note We can use CP rule to H810 saythat from the premise AA Blhere is a proofofiBA C A A A C 2 Asia sai a swap 3 iAAiBABJiAiAABiAiAABJ Axiamz 4 iAAaiAisAag 23MP S A ak 14MP Letk ma a QED Six Tautologies A A A A A B A A A A A A A A A A AABAABAAA AAABAAAAB AABAAAABAB 9WP9 N2 Proofs using only axioms MP Hs and previously proven results 462009 Proofl A A B Proofl A P 2 A Ba A Axioml 3 B A 12MP 4 Ba A AaBAxiom3 5A B 34MP QED 15CP Proof3 Aa A Proof L Aa A Proon 2 Aa AaAa A Ax3 3A A 12MP QED Proof5 Aa Ba AaB Proof1A P 2 AgtB P 3 B 12MP 4AgtBgtB 23CP 5 A gtB gtB gt a Bgt a Agt B Proof4 a aa maa 45MP QED 16CP Proof2 AaA Proofl A P 2 Aa Aa A Proofl 3 A A 12MP 4 Aa Aa AaAAx3 5 AgtA 34MP 6 A 15MP QED 16CP Proof4 AaBa Ba A Proof 1 AgtB P 2 AgtA Proof2 3 AgtB 12HS 4Bgt B Proof3 5 Agt B 34HS 6 Aa Ba Ba AAx3 7 Bgt A 56MP QED 17CP Proof6 2A a ae A mqu AA 12MP A Aaa p 5 AB a 5 ABA a Pruuf 7 A a gtB gt A a ae aa Aaa AXZ aea aa gta 57w 9 AB A 52w m aBeaAgtBgtAgtBgtB Axmms 11 Ae m p 12 a 111MP 13 Aaa a 4120 QE 113 cw 462009 Completeness of the axiom system Lemma 2 Let W be a wff with propositional variables P1Pm Let QlQm be defined by letting each 0 k1m be either Pk true or PkFalse From the premises 01Qm there is a proof of either Wor AW Proof Self Study Theorem Completeness Any tautology can be proven as a theorem in the axiom system Proof of completeness theorem Let W be a tautology with propositional variables P1 Prn There is a proof of w from premises o1 rn Each ois either P or aP so there are two proofs ofW one with oP and another with oaP Suppose om maraPm Prove Q1 A om A Pm aw and Q1 A om A aPm aw combining the two proofs 1 Pm aw ternrna 2 2 aPm aw ternrna 2 3 PM amattaPmamaw from targets 4 aPm aw aw fro P s w from 2 3 MP Other axiom systems Frege s axioms A B gtA A B ac a A gtB a A ac A B ac a B a A ac A 8 a AB a AA A gt A A gt A Six axioms MP rule Frege s axiom system P P PP P fuf cP i l H5 is proved using cP A a c can repesent any wff generated by propositional variables and the canneetiyes a a HilbertAckermann Axioms AVAgtA AgtAVB AVB gt B VA AaBaCvA CvB Four axioms MP rule HA axiom system PWN Note A B C can represent any wff generated by propositional variables and the connectives gt v Review Soundness of an axiom system How can you be sure that a system is sound Ans Soundness All proofs yield theorems that are aulologies 1 Check that Inference rules used maps true statements to true statements 2 Check that the axioms are true 462009 Review Suppose we are given the following three axioms plus the MP rule Here A a B is an abbreviation for A A B 1 AgtAA 2 AAAgtA 3 A a B B A C 4C A A Prove the following statement 14A BAB ac a h CAA Review AgtB BgtC a hCAA Proof 1 A a B P 2 B ac P 3 Agt B gt B a c a ah c A Ax3 4 BA ca cAA 13MP 5 BA C 2 Abbreviation 6 hcA A 45 MP QED 16 CP Chapter 7 Predicate Logic used to analyze a widervariety of arguments and statements than propositional logic Example All computer science majors own a personal computer Socrates does not own a personal computer Therefore Socrates is not a computer science major How do you represent the words All own not that are importantto under Lanu 39 Predicate Predicate is part of a sentence that gives a property of the subject Logic point of view predicate is am Example px could mean quotx owns a personal computerquot If we replace x with a definite value xSocrates then we obtain the proposition pSocrates with a value False Quantifiers Existential quantifier quotThere exists an x such that pxquot 3x px Example Let px mean that x is an odd integer p2 vp3 vp4 vp5 means quotThere exists an x in the set 2345 such that px is truequot Quantifiers Universal quantifier quotFor everyal x in D px is truequot Vx px Example Let px mean that x is an odd integer PlllA PM A ME A W Dl357 quotFor every x in D px is truequot 462009 Using Quantifiers Formalizing a sentence If pxy is a predicate and we let the variables xy Let Cx mean x is a computer science major vary overthe set D 01jthen the proposition Let PM mean that X owns a personal P0i0 V P0i1 A P1i0 V P1i1 computer Can be representEd by VX 3V PXiY quotAll computer science majors own a personal Proof computerquot lel v plOi1l 3v plOivl VX cm a px plLOl v pl 1i1l 3v pilivl lel v Will A piliOl v pililll 3v i110le 3v pilivl X Formalizing sentenses llfirstorder predicate calculus 139 Every natural quotumber hasa successor Quantifiers can quantify only variables that For each xENlhere exists a ythal is a successorofxquot occur In PFGdICates r In chapter 8 we ll discuss higherorder logics 2 There is no natural number whose successor is 0 quotThere does not exist XENSuCh that the successor ofx is 0 a 3x ss a where a0 Chapter 7 Predicate Predicate Logic used to analyze a widervariety of Predicate is part ofa sentence that gives a arguments and statements than proposmonal logic property of the subjects In a sentence Example Logic point of view predicate is a relation All computerscience majors own a personal computer Example pX could mean Socrates does not own a personal computer quotX owns a personal computerquot Therefore Socrates is not a computerscience major If we replace X With a definite value XSocrates then we obtain the proposition pSocrates How do you represent the words All ownjthat are 39 with a value False important to undei Laiiu 462009 Examples Quantifiers 1 pr is the quotis primequot predicate and x is prime Existential quantifier indicates disjunction then we write px for quotx is primequot quotThere exists an x such that pxquot 2 If q is the quotis parent ofquot predicate and x is a 3X l3le parent ofy then we write qx y for quotx is the parent ofyquot Example Let px mean that x is an odd integer pZ vp3 vp4 vp5 means quotThere exists an x in the set 2345 such that px is truequot Example Quantifiers How would you represent Universal quantifier indicate conjunction pvr a v pvr b v pvr c For everyall x in D px is truequot using an existential quantifier W Ple Example Let px mean that x is an odd integer Ans 3x py x where xea b c 91A p3 A pS A W D1357 For every x in D px is truequot Vx px Examples How to read quantifier formulas Read rrdrn lerttd right may X A pb X A pc X Forexarnplelettne universe petnesetdrairplanes and letFx y denote quotx flies faster tnan yquot Then VX v F can be translated initially as quotFor every airplanex tne following ndldsx is faster tnan every any airplane yquot X By Fx y can be read initially as quotFor every airplane xthe following ndlds rdr sdrne airplane y x is faster tnan l sirnpler English itrneans quotEvery airplane is faster tnan sdrne air equot 3 xVy Fx y represenm quotThere a Ans Vy py x where ye a b c ist an airplane xwhich satisfies tne tnat rdr every airplane y x is faster tnan yquot in sirnpler ys quotThere is an airplane which is faster tnan eyery airplanequot or airplane is faster tnan every airplanequot y reads quotrdr sdrne airplanex tnere aists an airplaney su c thatxis faster many which rneans quotsdrne airplane is faster tnan sdrne airplanequot 462009 Using Quantifiers If px y is a predicate and we let the variables x y vary over the set D 01 then the proposition Pl0r0 V P0r1 A Pl1r0 V P1r1 can be represented by Vx 3y px y Proof lel v plOr1l 3v p10er lel v pl M 3v pllrvl lel V lel A lel V will 3v NW A 3v pllrvl X Example If x y 6 01 then 3x Vy px y 2 VypO y2 ny91 2 200Z201Z vplOZApllz OR 3x px02 A px l 2 p0 0 2Ap0 l 2 v pl 0 2Apl l 2 Note Order is important Ifx y 6 01 then Vy 3x px y 2 Ans 3x px 0 2 A 3x px l 2 Pl0r 0r Z v pllr 0r Z A PlOr 1r Z v pllr 1r 2 p0 0 2 A p0 l 2 v pl 0 2 A pl l 2 Order of application of quantifiers The oostu39ohs ot the sarhe type or ouahttrtets tah be switched wtthout arreetthg the truth vatue as long as there are ho ouahttrters or the other e 3y32Pxyz e 3y3x32Pxy 2 323y3xpltxyz tt ts the same tor the uhtversat ouahttrter However the oostttohs ot ottterehr types of quantifiers can not be switched P x y ts hot eoutvateht to 3y m P x y For etarhote tet P x y representx y for the setor hurhoers as the universe Then vX 3y P x y reads quotfor every hurhoer x there ts a hurhoer y thatts greater thah xquot which ts true whtte 3y m P x y reads quotthere ts a hurhoer that isgreater thah every ahy hurhoerquot which ts hottrue Formalizing a sentence Let Cx mean x is a computer science major Let Px mean that x owns a personal computer quotAll computer science majors own a personal computerquot Vx Cx Px Formalizing sentences 1 Every natural number has a successor For each XENthere exists a y that is a successor ofxquot Vx 3y sx y 2 There is no natural number whose successor is 0 quotThere does not exist XENSuCh that the successor ofx is 0 a 3x ss a where a0 Well formed formulas Individual variables x y 2 Individual constants a b 6 Function constants f g h Predicate constants p q r Connective symbols A v 9WP9 NI Punctuation symbols 462009 Definitions Term Terms are nonlogical things constants a b c or variables x y z or function symbols applied to terms fa gx fy Atomic Formula Atom Atoms are predicate symbols applied to terms px qa fx Wffs Any atom is a wff Or if U and V are wffs then the following expressions are also wffs U UV U vV U av Elx UVx Uand U Hierarchy Hierarchy in the absence of parentheses A Elx Vx highest V 9 lowest and it is left associative group rightmost operatorwith smallest wffto its right Example Vx Ely px y 9 Vx qx W I 3y I3er v 9 W qu Scope Bound and Free The scope of Elx in Elx W is W The scope of Vx in Vx Wis W An occurrence ofx is bound ifit occurs in either Elx or Vx or in their scope Otherwise the occurrence ofx is free ExampleEllx p1lt97 y q1lt i l BBBFB Interpretation I An interpretation for a firstorderwf f consists of a nonempty set D called the domain of interpretation togetherwith an assignment that associates the symbols ofthe wf39fto values of D as follows Predicate symbols are assigned to relations over D Function symbols are assigned to functions over D Constant symbols are assigned to elements of D Free occurrences of va riables are assigned to elements of D PP P Substitution for free variables Ifx is free in Wand d E D then Wxd denotes the wffobtained from W by replacing all free occurrences ofx by d We also write Wd Wxd Example LetW Vy px y 9 qx Then Wlxd W pd v 9 qld Properties of Substitutions 1 xt distributes over the connectives 99gt Example 9A xt 9 Axt A B xt Axt Bxt 2 fx y then xt distributes over Vy and y Example VyWxtVyWxt 3 Ifx is not free in W then WxtW Example VXWxt VXW 462009 Meaning of a wff truth value wrt an interpretation Let I be an interpretation with domain D Then the meaning of a wff wrt to I is the truth value obtained by applying the following rules 1 Ifthe wff has no quantifiers the meaningwrt I is the truth value ofthe proposition obtained by applyinglto thewff 2 Ifthe wff contains Vx W then Vx W istrue wrt I iff Wlxdl is truewrt Iforalld E D 3 Ifthe wff contains 3x W then 3x W istrue wrt I iff Wlxdl is truewrt Ifor some d E D Example I Let Wpx We can define an interpretation I by letting D N px means x is odd and x 4 Then Wis false wrt I because Wx4 p4 quot4 is addquotwhich is false I If we let J be the same as I except that we assign x 3 then Wis true wrt because Wx3 03 quot3 is addquot which is true Exa m p e Let W Vx px 9 ax y Here are two interpretations of W 1 Let I be defined by D in 1 pin true p1 false am 1 true atnerwise a y is false and y 1 Then W is true wrt I because it becomes VX PM 9 qlxi 1 I ll 9 W7 1NP19 all 1 ltrue 9 truel lfalse 9 falsel E true true E true 2 If has any domain D p is true a is false andy any Value of D then W is false wrt J Example Let W 3 px I ax Here are two interpretations of W 1 Letbe defined by DN px meansx is prime and ax means x is odd Then W istrue wrt I because we can choose a number xfrom the domain D such that p3 q3 true A true E true 2 Ichonsists ofD N px means x is even and ax means x is odd then W is false wrt I because we can never choose an x in D such that the wff is true example x3 13 I 173 false I true Efalse Models and Countermodels An terpretat nthat makesawfftru scalled amodel An terpretat nthat makesawfffals called a countermodel xample Let W be thefollowing w f VX rx a a PM 9 3y 09 y I fly 0I dly XII 1 Any interpretation for which r is alwaysfalse is a modefor W 2 Any interpretation for which r is always true 2 is always fa se and d is alwaysfalse is a countermodel for W Validity Awff is valid if every interpretation is a model Otherwise the wff is invalid A wff is unsotisfioble if every interpretation is a cou ntermodel Otherwise the wff is sotisfioble 39 QEvery wff has exactly two of these four properties What are the possible pairs of propertiesthat a wff can ave Answer WIid sotisfioble toutalagy unsotisfioble invalid cantrodictian sotisfioble invalid contingency Example Check if the following wff is valid VX PM 9 PM Answer The wff is valid because px 9 px is truefor all interpretations Example Check is the following wff is satisfiable VX PM A PM Answer The wff is unsatisfiable because px I a px is alwaysfase Example Prove the following wff is valid EIX Ax I BX 9 3XAX I 3x BX We can t check every interpretation there are too many 50 we need to reason informally with interpretations Example Contd Prove that the following wffisvalid ax Ax A Bx a 3x Ax A 3x Bx Direct Proof Let I be an interpretation with domain D for the wffand assume that the antecedent is true wrl i Then Ad A Bd is true wrt to i for some and 3x BX are true wrl I So the consequentistrue wrl to i Thuinsa model for the wff Since Iwas an arbitrary interpretation for the wff every interpretation for the wff isa model Therefore the wffisvalid QED Some Valid Conditionals Whose Converses Are Invalid VXAX 9 3XAX EIX Ax I BX 9 3XAX I 3XBX c VXAX IWBX 9 WAX lBX Vx AX 9 BX 9 WAN 9 W800 e EIX WPX y 9 W 3x PX y 462009 462009 Example The wffpx ys The un Example The wffpx A s pm is satis Th rlv Closure Me a Wffwlmflee vananles x1 xri Then we have Mefallowlrlg LE39L de nlllons39 tney dun t aswe can see in tnerulluWing exambles pyissatisnanle mdmvalld Contingency iyersal clusure VX Vy px l py is salls a le andlrlvalld stential clusure axsy px l pyl5 valld tautology ane mdmvalld Contingency A i ersal clusure VX mp x py is unsmls a le Contradiction stential clusure axsy px A s pylssallsiahle a dlnvalld Closure Properties proofs in text 1 Awf f is valid ifand only if its universal closure is valid 2 wf39f is unsatisfiable if and only if its existential closure is unsatisfiable Example The w pm 9 7y py is valid and its universal closure VX pX 9 7ypy is also valid Example The w pm I by py is unsatisfiable and its existential closure 3X pX I W py is also 39 bl unsatisfla e Decidability Solvability brublem and naltsirtne answer isyes but mignt nut nalt irtne answer is nu Example The Validity Prublenlfur Prupusltlunzl Calculus The brublem ur determlrllrlg wnetner a brubusitiunal wff is a tautulugy is decidable n alguritnm can build atrutn tablerurtne wff and tnen check it Example he Validity Prublem fur Flrserrder Predlczte Calculus The brublem at determining wnetner arirstarderwrr isyalid isundecidable because tnere are many interpretatiuns ur a wff But it is partially decidable Tw artial in cnabter s 462009 Proof Notes Let W denote the wff A gt B gt B Note this wff is not a tautology eg AB false Discrete Structures Now considerthe proof 1 A a P cs 251 Week 2 z A a a 12MP QED 130 lsec mm 64 711 I What is wrongwith the proof of W I Write down the statementthat the quotproofquot proves The conjunction of all the premises that you used to prove something is precisely the antecedent ofthe conditional that you proved Proof Notes 64 Formal axiom systems Suppose we have a wff that is not a tautology 39 What do we Want from proofs A A A s B V c s B We want our proofs to yield theorems that are 1 A P tautologies and we want any tautology to be provable as a theorem 3 B 12 MP Saundness All proofs yield theorems that are QED 123 CP tautologies What is wrong with the proof Completeness All ta utologies are provable as lDon39t apply inference rules to subexpressions of wffs I theorems 641 An example axiom system FregeLukasiewicz Axioms In the last class we studied that a formal Example FregeLukasiewicz Axioms where A reasoning system consists of d b B C represent any wff generate A set of wf39fs a set of axioms a set of inference rules prOPOSltlonal varlables and the two Is there a formal system for which the connectives and a propositional calculus is both sound and 1 A H B HA complete 2 A a B a C gt A gt B gtA gt C YESl 3quotAgtquotBgtBgtA Proof of CP rule A A A is a theorem provable from the FL axioms Lemma 1 A A A Proof 1 AABAgtAAgtA AgtAAgtBAgtAAgtAAgtA By axiom 2 where B B A A and CA 2AABAA AA Axiom 1 3AABAAAAAA By12MP 4AAgtBAgtA Axiom 1 5AAA 34MP QED 462009 Proof of CP rule fA is a premise in a proof of B then there is a proof ofA A B that does not use A as a premise Proof Assumption A is a premise in the proof of B Suppose B1 Bquot is a proof of B that uses the premise A We ll show by induction for each k in the interval is k s n that there is a proof of A A Bkthat does not use A as the premise Proof of CP rule Proof Contd If k1 then either B A or 813Xi0m or premise otherlhan A if B A then AA 31 AA A which by lemma 1 has a proofthat does not useA as a premise If Bfaxiom or premise other hanAthen 1 31 An axiom or premise otherlhan A 2 81AAAgt Bji Axiom1 AB 12 MP Proof Contd Assumefor each ilt kthereis a proofs a that does not useA as a premise Show that A A B does not use A as a premise Case 1 5A c se 2 5Axiom or a premise other than A For case 12 proof similar for k1 Case 3 5 Nolan axiom ora premise nah i as a human Hypothetical Syllogism lFrom the premises AA Band BA c here is a proof ofA A C Proof 1 AAgtB P 2 BAgtC P 3A P 4 B 1 3 MP 5 c 2 4 MP 6AA c 3 5 CP ED Note We can use CP rule to H810 saythat from the premise AA Blhere is a proofofiBA C A A A C 2 Asia sai a swap 3 iAAiBABJiAiAABiAiAABJ Axiamz 4 iAAaiAisAag 23MP S A ak 14MP Letk ma a QED Six Tautologies A A A A A B A A A A A A A A A A AABAABAAA AAABAAAAB AABAAAABAB 9WP9 N2 Proofs using only axioms MP Hs and previously proven results 462009 Proofl A A B Proofl A P 2 A Ba A Axioml 3 B A 12MP 4 Ba A AaBAxiom3 5A B 34MP QED 15CP Proof3 Aa A Proof L Aa A Proon 2 Aa AaAa A Ax3 3A A 12MP QED Proof5 Aa Ba AaB Proof1A P 2 AgtB P 3 B 12MP 4AgtBgtB 23CP 5 A gtB gtB gt a Bgt a Agt B Proof4 a aa maa 45MP QED 16CP Proof2 AaA Proofl A P 2 Aa Aa A Proofl 3 A A 12MP 4 Aa Aa AaAAx3 5 AgtA 34MP 6 A 15MP QED 16CP Proof4 AaBa Ba A Proof 1 AgtB P 2 AgtA Proof2 3 AgtB 12HS 4Bgt B Proof3 5 Agt B 34HS 6 Aa Ba Ba AAx3 7 Bgt A 56MP QED 17CP Proof6 2A a ae A mqu AA 12MP A Aaa p 5 AB a 5 ABA a Pruuf 7 A a gtB gt A a ae aa Aaa AXZ aea aa gta 57w 9 AB A 52w m aBeaAgtBgtAgtBgtB Axmms 11 Ae m p 12 a 111MP 13 Aaa a 4120 QE 113 cw 462009 Completeness of the axiom system Lemma 2 Let W be a wff with propositional variables P1Pm Let QlQm be defined by letting each 0 k1m be either Pk true or PkFalse From the premises 01Qm there is a proof of either Wor AW Proof Self Study Theorem Completeness Any tautology can be proven as a theorem in the axiom system Proof of completeness theorem Let W be a tautology with propositional variables P1 Prn There is a proof of w from premises o1 rn Each ois either P or aP so there are two proofs ofW one with oP and another with oaP Suppose om maraPm Prove Q1 A om A Pm aw and Q1 A om A aPm aw combining the two proofs 1 Pm aw ternrna 2 2 aPm aw ternrna 2 3 PM amattaPmamaw from targets 4 aPm aw aw fro P s w from 2 3 MP Other axiom systems Frege s axioms A B gtA A B ac a A gtB a A ac A B ac a B a A ac A 8 a AB a AA A gt A A gt A Six axioms MP rule Frege s axiom system P P PP P fuf cP i l H5 is proved using cP A a c can repesent any wff generated by propositional variables and the canneetiyes a a HilbertAckermann Axioms AVAgtA AgtAVB AVB gt B VA AaBaCvA CvB Four axioms MP rule HA axiom system PWN Note A B C can represent any wff generated by propositional variables and the connectives gt v Review Soundness of an axiom system How can you be sure that a system is sound Ans Soundness All proofs yield theorems that are aulologies 1 Check that Inference rules used maps true statements to true statements 2 Check that the axioms are true 462009 Review Suppose we are given the following three axioms plus the MP rule Here A a B is an abbreviation for A A B 1 AgtAA 2 AAAgtA 3 A a B B A C 4C A A Prove the following statement 14A BAB ac a h CAA Review AgtB BgtC a hCAA Proof 1 A a B P 2 B ac P 3 Agt B gt B a c a ah c A Ax3 4 BA ca cAA 13MP 5 BA C 2 Abbreviation 6 hcA A 45 MP QED 16 CP Chapter 7 Predicate Logic used to analyze a widervariety of arguments and statements than propositional logic Example All computer science majors own a personal computer Socrates does not own a personal computer Therefore Socrates is not a computer science major How do you represent the words All own not that are importantto under Lanu 39 Predicate Predicate is part of a sentence that gives a property of the subject Logic point of view predicate is am Example px could mean quotx owns a personal computerquot If we replace x with a definite value xSocrates then we obtain the proposition pSocrates with a value False Quantifiers Existential quantifier quotThere exists an x such that pxquot 3x px Example Let px mean that x is an odd integer p2 vp3 vp4 vp5 means quotThere exists an x in the set 2345 such that px is truequot Quantifiers Universal quantifier quotFor everyal x in D px is truequot Vx px Example Let px mean that x is an odd integer PlllA PM A ME A W Dl357 quotFor every x in D px is truequot 462009 Using Quantifiers Formalizing a sentence If pxy is a predicate and we let the variables xy Let Cx mean x is a computer science major vary overthe set D 01jthen the proposition Let PM mean that X owns a personal P0i0 V P0i1 A P1i0 V P1i1 computer Can be representEd by VX 3V PXiY quotAll computer science majors own a personal Proof computerquot lel v plOi1l 3v plOivl VX cm a px plLOl v pl 1i1l 3v pilivl lel v Will A piliOl v pililll 3v i110le 3v pilivl X Formalizing sentenses llfirstorder predicate calculus 139 Every natural quotumber hasa successor Quantifiers can quantify only variables that For each xENlhere exists a ythal is a successorofxquot occur In PFGdICates r In chapter 8 we ll discuss higherorder logics 2 There is no natural number whose successor is 0 quotThere does not exist XENSuCh that the successor ofx is 0 a 3x ss a where a0 Chapter 7 Predicate Predicate Logic used to analyze a widervariety of Predicate is part ofa sentence that gives a arguments and statements than proposmonal logic property of the subjects In a sentence Example Logic point of view predicate is a relation All computerscience majors own a personal computer Example pX could mean Socrates does not own a personal computer quotX owns a personal computerquot Therefore Socrates is not a computerscience major If we replace X With a definite value XSocrates then we obtain the proposition pSocrates How do you represent the words All ownjthat are 39 with a value False important to undei Laiiu 462009 Examples Quantifiers 1 pr is the quotis primequot predicate and x is prime Existential quantifier indicates disjunction then we write px for quotx is primequot quotThere exists an x such that pxquot 2 If q is the quotis parent ofquot predicate and x is a 3X l3le parent ofy then we write qx y for quotx is the parent ofyquot Example Let px mean that x is an odd integer pZ vp3 vp4 vp5 means quotThere exists an x in the set 2345 such that px is truequot Example Quantifiers How would you represent Universal quantifier indicate conjunction pvr a v pvr b v pvr c For everyall x in D px is truequot using an existential quantifier W Ple Example Let px mean that x is an odd integer Ans 3x py x where xea b c 91A p3 A pS A W D1357 For every x in D px is truequot Vx px Examples How to read quantifier formulas Read rrdrn lerttd right may X A pb X A pc X Forexarnplelettne universe petnesetdrairplanes and letFx y denote quotx flies faster tnan yquot Then VX v F can be translated initially as quotFor every airplanex tne following ndldsx is faster tnan every any airplane yquot X By Fx y can be read initially as quotFor every airplane xthe following ndlds rdr sdrne airplane y x is faster tnan l sirnpler English itrneans quotEvery airplane is faster tnan sdrne air equot 3 xVy Fx y represenm quotThere a Ans Vy py x where ye a b c ist an airplane xwhich satisfies tne tnat rdr every airplane y x is faster tnan yquot in sirnpler ys quotThere is an airplane which is faster tnan eyery airplanequot or airplane is faster tnan every airplanequot y reads quotrdr sdrne airplanex tnere aists an airplaney su c thatxis faster many which rneans quotsdrne airplane is faster tnan sdrne airplanequot 462009 Using Quantifiers If px y is a predicate and we let the variables x y vary over the set D 01 then the proposition Pl0r0 V P0r1 A Pl1r0 V P1r1 can be represented by Vx 3y px y Proof lel v plOr1l 3v p10er lel v pl M 3v pllrvl lel V lel A lel V will 3v NW A 3v pllrvl X Example If x y 6 01 then 3x Vy px y 2 VypO y2 ny91 2 200Z201Z vplOZApllz OR 3x px02 A px l 2 p0 0 2Ap0 l 2 v pl 0 2Apl l 2 Note Order is important Ifx y 6 01 then Vy 3x px y 2 Ans 3x px 0 2 A 3x px l 2 Pl0r 0r Z v pllr 0r Z A PlOr 1r Z v pllr 1r 2 p0 0 2 A p0 l 2 v pl 0 2 A pl l 2 Order of application of quantifiers The oostu39ohs ot the sarhe type or ouahttrtets tah be switched wtthout arreetthg the truth vatue as long as there are ho ouahttrters or the other e 3y32Pxyz e 3y3x32Pxy 2 323y3xpltxyz tt ts the same tor the uhtversat ouahttrter However the oostttohs ot ottterehr types of quantifiers can not be switched P x y ts hot eoutvateht to 3y m P x y For etarhote tet P x y representx y for the setor hurhoers as the universe Then vX 3y P x y reads quotfor every hurhoer x there ts a hurhoer y thatts greater thah xquot which ts true whtte 3y m P x y reads quotthere ts a hurhoer that isgreater thah every ahy hurhoerquot which ts hottrue Formalizing a sentence Let Cx mean x is a computer science major Let Px mean that x owns a personal computer quotAll computer science majors own a personal computerquot Vx Cx Px Formalizing sentences 1 Every natural number has a successor For each XENthere exists a y that is a successor ofxquot Vx 3y sx y 2 There is no natural number whose successor is 0 quotThere does not exist XENSuCh that the successor ofx is 0 a 3x ss a where a0 Well formed formulas Individual variables x y 2 Individual constants a b 6 Function constants f g h Predicate constants p q r Connective symbols A v 9WP9 NI Punctuation symbols 462009 Definitions Term Terms are nonlogical things constants a b c or variables x y z or function symbols applied to terms fa gx fy Atomic Formula Atom Atoms are predicate symbols applied to terms px qa fx Wffs Any atom is a wff Or if U and V are wffs then the following expressions are also wffs U UV U vV U av Elx UVx Uand U Hierarchy Hierarchy in the absence of parentheses A Elx Vx highest V 9 lowest and it is left associative group rightmost operatorwith smallest wffto its right Example Vx Ely px y 9 Vx qx W I 3y I3er v 9 W qu Scope Bound and Free The scope of Elx in Elx W is W The scope of Vx in Vx Wis W An occurrence ofx is bound ifit occurs in either Elx or Vx or in their scope Otherwise the occurrence ofx is free ExampleEllx p1lt97 y q1lt i l BBBFB Interpretation I An interpretation for a firstorderwf f consists of a nonempty set D called the domain of interpretation togetherwith an assignment that associates the symbols ofthe wf39fto values of D as follows Predicate symbols are assigned to relations over D Function symbols are assigned to functions over D Constant symbols are assigned to elements of D Free occurrences of va riables are assigned to elements of D PP P Substitution for free variables Ifx is free in Wand d E D then Wxd denotes the wffobtained from W by replacing all free occurrences ofx by d We also write Wd Wxd Example LetW Vy px y 9 qx Then Wlxd W pd v 9 qld Properties of Substitutions 1 xt distributes over the connectives 99gt Example 9A xt 9 Axt A B xt Axt Bxt 2 fx y then xt distributes over Vy and y Example VyWxtVyWxt 3 Ifx is not free in W then WxtW Example VXWxt VXW 462009 Meaning of a wff truth value wrt an interpretation Let I be an interpretation with domain D Then the meaning of a wff wrt to I is the truth value obtained by applying the following rules 1 Ifthe wff has no quantifiers the meaningwrt I is the truth value ofthe proposition obtained by applyinglto thewff 2 Ifthe wff contains Vx W then Vx W istrue wrt I iff Wlxdl is truewrt Iforalld E D 3 Ifthe wff contains 3x W then 3x W istrue wrt I iff Wlxdl is truewrt Ifor some d E D Example I Let Wpx We can define an interpretation I by letting D N px means x is odd and x 4 Then Wis false wrt I because Wx4 p4 quot4 is addquotwhich is false I If we let J be the same as I except that we assign x 3 then Wis true wrt because Wx3 03 quot3 is addquot which is true Exa m p e Let W Vx px 9 ax y Here are two interpretations of W 1 Let I be defined by D in 1 pin true p1 false am 1 true atnerwise a y is false and y 1 Then W is true wrt I because it becomes VX PM 9 qlxi 1 I ll 9 W7 1NP19 all 1 ltrue 9 truel lfalse 9 falsel E true true E true 2 If has any domain D p is true a is false andy any Value of D then W is false wrt J Example Let W 3 px I ax Here are two interpretations of W 1 Letbe defined by DN px meansx is prime and ax means x is odd Then W istrue wrt I because we can choose a number xfrom the domain D such that p3 q3 true A true E true 2 Ichonsists ofD N px means x is even and ax means x is odd then W is false wrt I because we can never choose an x in D such that the wff is true example x3 13 I 173 false I true Efalse Models and Countermodels An terpretat nthat makesawfftru scalled amodel An terpretat nthat makesawfffals called a countermodel xample Let W be thefollowing w f VX rx a a PM 9 3y 09 y I fly 0I dly XII 1 Any interpretation for which r is alwaysfalse is a modefor W 2 Any interpretation for which r is always true 2 is always fa se and d is alwaysfalse is a countermodel for W Validity Awff is valid if every interpretation is a model Otherwise the wff is invalid A wff is unsotisfioble if every interpretation is a cou ntermodel Otherwise the wff is sotisfioble 39 QEvery wff has exactly two of these four properties What are the possible pairs of propertiesthat a wff can ave Answer WIid sotisfioble toutalagy unsotisfioble invalid cantrodictian sotisfioble invalid contingency Example Check if the following wff is valid VX PM 9 PM Answer The wff is valid because px 9 px is truefor all interpretations Example Check is the following wff is satisfiable VX PM A PM Answer The wff is unsatisfiable because px I a px is alwaysfase Example Prove the following wff is valid EIX Ax I BX 9 3XAX I 3x BX We can t check every interpretation there are too many 50 we need to reason informally with interpretations Example Contd Prove that the following wffisvalid ax Ax A Bx a 3x Ax A 3x Bx Direct Proof Let I be an interpretation with domain D for the wffand assume that the antecedent is true wrl i Then Ad A Bd is true wrt to i for some and 3x BX are true wrl I So the consequentistrue wrl to i Thuinsa model for the wff Since Iwas an arbitrary interpretation for the wff every interpretation for the wff isa model Therefore the wffisvalid QED Some Valid Conditionals Whose Converses Are Invalid VXAX 9 3XAX EIX Ax I BX 9 3XAX I 3XBX c VXAX IWBX 9 WAX lBX Vx AX 9 BX 9 WAN 9 W800 e EIX WPX y 9 W 3x PX y 462009 462009 Example The wffpx ys The un Example The wffpx A s pm is satis Th rlv Closure Me a Wffwlmflee vananles x1 xri Then we have Mefallowlrlg LE39L de nlllons39 tney dun t aswe can see in tnerulluWing exambles pyissatisnanle mdmvalld Contingency iyersal clusure VX Vy px l py is salls a le andlrlvalld stential clusure axsy px l pyl5 valld tautology ane mdmvalld Contingency A i ersal clusure VX mp x py is unsmls a le Contradiction stential clusure axsy px A s pylssallsiahle a dlnvalld Closure Properties proofs in text 1 Awf f is valid ifand only if its universal closure is valid 2 wf39f is unsatisfiable if and only if its existential closure is unsatisfiable Example The w pm 9 7y py is valid and its universal closure VX pX 9 7ypy is also valid Example The w pm I by py is unsatisfiable and its existential closure 3X pX I W py is also 39 bl unsatisfla e Decidability Solvability brublem and naltsirtne answer isyes but mignt nut nalt irtne answer is nu Example The Validity Prublenlfur Prupusltlunzl Calculus The brublem ur determlrllrlg wnetner a brubusitiunal wff is a tautulugy is decidable n alguritnm can build atrutn tablerurtne wff and tnen check it Example he Validity Prublem fur Flrserrder Predlczte Calculus The brublem at determining wnetner arirstarderwrr isyalid isundecidable because tnere are many interpretatiuns ur a wff But it is partially decidable Tw artial in cnabter s Discrete Structures Sections 101 Abstract versus concrete Abstrattversuscnntrate Snmaa gahrasare abstrattinthesens thanhe arriarsarenntmntrateknnwnsets SnthEDveratmnsmusthe estrihe bv mpinnmermaigema 530 wnereassanuimf ixix 5 tnthistasewetan amainsthe mtesmafs ements a ai Piai fora x 5mm 5 Piai f tai Fiai my 5 swam a 55 Axiom Plxix Binary operation tables winmwnpmmananmmmmwzmmpmmimmumm whzrnhzMINmmwxirmmtvmnvismzviwzan Eximptz tame 1 2 3ndi2xVX39Vi m4 rm m operation 3th m is mum to u o x z t a n o A lv 1 2 mm mm in ma mm Examptz 5m wmmn mm aw Dr 5 mmmvumz mmm mm mm mm 5 NE is ammm m mm a no mm m Wm 04 m m m2 Newng pmpzmz AHSWEY mmmvn 2 scan 1 5192009 101What is Algebra sigma mm my mm mm mm m mm minim mm BMW 2 mimewnm Em W n s r aHE tamer and mm mara vera innsn a DD ratn entatte thesignaturen h 5mm tamer then a semitntnn thenthi Dveratnrs m the 5mm L14 0 1 m sntve Drnhtemswith an aigem meanstn he 3mm apniv mums nfthe operations tnthaa g hra L14 u1gt thefniiawmgpmpemeshniu x4Dxx1xx VV xx vv m Nuix wx Lan snnn Properties of binary operations Lat he a hinarv Dveratmn an 5 1 Iismmmmativeifxl 1 swimvi n2EmameESisani entigfnrifxE xfnraHxES 4 AnetementliSisa fvrifxll 1 nraHxES 5 myssweisaniuenmmnenwsanimmennmwyx 2 Example LetSr ah3n tetlheahinarvnveratmnnns ineamtasemnuan nuiratmntahtafnrlthatsatis esthigivennn itmns hiss 12m 3 isani entttv marvetemem mean hasaninverse m is mmmutative 1 istnmmutativahutnntassnnative isassntiativehutnntmmmutativ Answer a i iii i i y ianwhzh lhc m mum m Wumumum warma y vomvzsswwu unwivu w um ian H IE 5 5g mum Using properties of operations Example Suppuse we want to pruvethe rniinvving statement about integers ni i an anan nai a Pruuf r a is identity fur t ex isthe inverse of xwith respect to t ta x t x t ex t is associative extex hyputhesis u atistheimersenrxwthresnectta t QED Nutice inthe examniethat we used several nrnpertiesarthe algebra z u t t r Uniqueness of an identity Any binary operation has at rnost one identity Proof Let o be abinary operation on the sets Assume u and e are identities for o We ll show that we By de nition ofidentity we know that uoxx uxande xx exforalleS e e o u u QED Uniqueness of inverses In a monoid ifan element has an inverse the inverse is unique Proof tetltM ugtbe a monoid We ll show that ity and z are both inverses otx then yz H u u is the identity tor z u is the identity tor QED 5192009 Example Given the algebra z o Prove the cancellation iaw x eyzez y0 v zyzimpliesxy o is identity tor s e2 is the inverse or with respect to is associative hypot esis is associative e2 is the inverse or z with respectto o is identity tor QED Algebras with One Binary Operation Any algebra of the form A u Groupoid o is a binary opemlion Semigroup o is an associative binaw opemlion Monoid Group 0 is an associative binary operation with identity 0 is an associative binaw opemtion with an identity and every element has an inverse GroupE Monoid E Semigroup E Groupoid Ring and Field A ring is an algebra with the structure 0 0i 1gt where A 0 is a commutative group A l is a monoid A field is a ring with an additional property that AO l is a commutative group Examples Is the ring Z 0 l a field Is the ring Q 0 l a field Using properties of operations Example Suppuse we want to pruvethe tollnwmg statement about integers ni i an onan naioi i Pruuf a is identity tor r ex istne inverse or xwitn respect to r hyputhesls am neirrverseotxwtnrespecttn r QED Notice intne examplethat we used several propertiesottne algebra z u r r r is associative Uniqueness of an identity Any binary operation has at rnost one identity Proof Let o be abinary operation on the sets Assume u and e are identities for o We ll show that we By de nition ofidentity we know that noxtonxanoieoxtoexfora11xes e e o u u QED 5192009 102 Properties of binary operations Let be a binary operation on s 39scommotativeitxv yx torallxves xvztorallxves ulsassociativeiixy Ari elernente e sis an identigior x e ex x forallx e S An elementzE sis a ior itx z x z torallx e s lfx y e s and e is an identity tnen y is an erseofxifxyyxe EI PP N Example Given tine algebra z o Prove tne cancellation law zyzimpliesxy Answer x x o o is identity tor x 2 72 72 is tne inverse of with respect to x s z s 72 s is associative v z 72 nvootnesis v z 72 is associative v o 72 is tne inverse of z witn resoectto v o is identity tor QED Algebras with One Binary Operation Any algebra of the form A Groupoid o is a binary opemlion Semigroup o is an associative binaw opemlion Monoid o is an associative binary operation with identity Group 0 is an associative binaw opemtion with an identity and even element has an inverse GroupE Monoid E Semigroup E Groupoid Uniqueness of inverses In a monold if an element has an inverse the inverse is unique Proof LetM u be a monoid Well show that ify and z are both inverses of x t en yz yy u lu isthe identity for o Volxoz lzisaninverseofx ely x o z i is associative eu oz ly is an inverse of x z lu isthe identityfor o QED Exa m pl es Is the ring ltZ 0 1gt a field Is the ring Q 0 1gt a field Example Contd These two algebras are concrete examples of a Boolean algebra B 0 1 gt which has the following properties A respectively 2 and distribute over each other 3 X 0 Complement of x or negation of x 5192009 Ring and Field Aring is an algebra with the structure ltA 0 1gt where ltA 0gt is a commutative group ltA 1gt is a monoid A field is a ring with an additional property that ltA0 1gt is a commutative group Boolean Algebra the ageua of sets and the algebra of propositional wffs mislporrurolwd 110 mi v r it means 3 x it r Prol mes 25 lvlalsc Avltlv HAVHIvfl 4 Hlllil AABHAA Jaimew t l lABA L39lb ll IA Bi Ar wb39 l Awl vrle Annlvlelirl Al391RI4Illl39 lll4l lr4l AvKH iMMHMFAVU ls ue e 4 l e mi 2 Properties of Boolean algebra operations Forany pmperty of the operations there is a dual pmperty obtained by interchanging o with 1 and with Similarly any proof has a dual proof obtained in the same my H are some basic properties ofthe operations idempotent propenyll Zero and One properties 12 AbsorptionlsA Uniqueness of complement is involution 15 De Morgan s Lawl7 2 0x0and1e 3 1 A and1 39 Proofx Xy amy leof39xirfy txvgttxy H 6 fA Proof Txlandx 0 So 7 7 f and n Proof Show a 1 and X 39Yj 0 Then use 5 to oblotutesulx 5192009 Example Digital Circuits Simplify the expression 39J A digital circuit or logic circuit is an electronic representation of a truth iii Minimin function L a E Answer rrrnnngtstn icon t n titanium circuit vmmmme nIl manna rthut mlt mtl uerwmn if n rig AND gale OR gate NOT gate 1m em 2 2 Example Simplify the fcillowing digital circuit Sai39iumii Tl um var39 m VIA39 follnvzm Mi u rll wimp mmiir an ldnmhmPl i t n H n illuulyllun iluulphum 39 i new mil mlimrmiii Discrete Structures ll CS 251 Section 91 92 Automatic Reasoning I Recallthat a ver W is valid if39f a W is unsatisfiable tautology valid satisfiable contingencyinvalid satisfiable contradictioninvalid unsatisfiable Resolution is an inference rule used to prove unsatisfiability in a mechanical way To prove that a ver is valid prove a W is unsatisfiable using the resolution rule Note We denote false by a box D in applying resolution we assumeAv B E B vAand v EA Aand B are falsethen the rule is simplified as shown L D 582009 Computational Logic Can logic be automated Yes for some logics Automating the quotnatural deductionquot method is difficult because there are many inference rules that can be applied in many different ways Introduce a single inference rule ca led resolution that can be used automatically by a computer Resolution for Propositional Logic 39 Cancellation rule The resolution rule for propositions is shown belowwhereA and B are disjunctions of literals Notation A7 p denotes Awith all occurrences of p removed and B a a p denotes B with all occurrences ofa p removed va ipo ApVBlp To prove a wff isvalid 1 Z 3 Example Prove p e o o e r e p e r is a tautology SolutionTransform the wff into CNF a p vq a q v r p a r Proof Proof negate tne wt and convert it to CN write down tne fundamental disiunctions as premises use resolution to find a false statemen 1apq LaoVr P 3p P 4ar P so 13R 6r 25R 7D 46R 582009 Example Clausal Forms A clause is a disiunction of zero or more literals lavamleecnomlaemnelcnmvlmn M r Saiutian Negatethewtiandtranstorntheresultintotwr t rrni itb ravariable ii an iaiun i n lAvBlAlAvclAlAvomlEvillBvFlAlcvDlAlEvFl applied to W 1 AVE P arguments that are terms Z Av 3 AvD 4 M A ciausai torn is the universai closure ot a coniunction of clauses EEVFD NotationA ciausai torn is also represented as a set ot its clauses o 7 ry r 5 Av c Exampie The ciausai torn BV VX VY9XQXrYVVX PXV5Y to Bv a 1 Av is represented y t e set 12 um am v V n rxr n W V SM is oro Sk AI 39th E oems gOI39I m xampe Not every wffisequivalenl to a clauEl form For emmple the wax Find a clausal form for each wff pm is not equivalent to a clausal form But we have the following 1 3X Aix result ofSkolem which is suf cient for resolution 2 W 3V Bixr v Every wff can be associated with a clausal form in which the 3 W W 31 C09 lr 1 two are either both Etis able or both ungtisliable 4 VX 3V 31 D99 Vi 1 1 Construct the prenex cw tor the wtt z Repiace all occurrences ot each free variable by a new constant Answers 3 Eliminate the etistential quantitiers by Skoiem s Ruie A it 3x Wx is not inside the scope ot a universai ouantitier then replace 2 VX 309 W save some WWW WWW may depend W 3x WX by wc tor a new constant c 3 Vx Vy CXr Ir 09 0 a it 3x WX is inside the scope otw1 quotmquot then replace 3x WX by 4 W Dx fgtltr i500 Wfx1 x tor a new tunction symboi f Example Substitutions and Unification Put the wtt in orenex NF Ham Agglm ga nd gto an Exgress n P YV31QWVZ remuved 9 i n nr i n d e d 3x f x39yy V azz iq mM fzin NEE Did obtained trorn E by replacing all tree occurrences otx with t Vy 3x a a px yV o rz nd 3 outside Examp es39 Xi Vi WM Vi Vi Z Vy 3x S ta px y v qw a px y v r m mnstructed aw DXr yr Zvl z p09 l Zr Z A substitution is a finite set of bindingswith dis nctnumerators Use lowercase greek letters tor substitutions Exampie e xy yfz and 0 y a zb are substitutions W e NibMW am WW v V ew So there are two clauses int e clausal torrn which can be denoted by the set in NibMW W e WW v V ew of Expressions Applying a Substitution to an Expression or a Set men Ee obtained trorn E by simultaneously applying the bindings in e to E Example if e Xvi vl Zi the 9Xi in Z9 9Xi vi ZXvivl z 9vi l Zi Z by applying 9 to each etpression or s Example if e Xvi WW and S 909 W CW BZi the 59 Wi Wei CW BOW Nii l Zi ql Zi Bu it s is a setot etpressions then se is the set or etpressions obtained trorn s Exa m pl e Let 9 xyy zl and o y al zb Calculate eo Step 1 Construct xyo y zla lX al vflbl Step 2 No deletions So no changes step 3 Delete y al from o lbecause y is a numerator orelto obtain zb step 4 The union of sets from steps 2 and 3 give eo x al Vflblr Zbl 582009 Composing Substitutions from the application Example we calculate Perr1e PerrZeH ptvr Hz zllu we W b so op iXf2rvfbr zbl 1 construct lxtpl Delete any xxrrurn step 1 sDelete ys malfylsa numerat r to u u p isthe union urthe substitutlurlsfrurn steps 2 and s By grep E6u We can calculate so by applying it to an atom that cuntalrls all the Properties of Composition 1 EBo E9o 2 98 89 9 where e l U n lfl er A unifer ofa set S of express39ons is a substitution 9 such that 9 isa singleton set Exam le 1 xa is a uni er ofiplxl plal because plxl plalXxa plai 2 What are som nili pix al ply 2 er Since a is a constant any uni er must include the binding za A unilier might also include xy or yx So two uniliers ofS are lxy za and lyx za betause Sixv 13 plv alland Sivx Za pl Notice also that xt yt za is a uni er x al ofS for any term t because Sixl WI 13 pit al Most general unifier mgu most general uni er lmgul ofa sets orexpress39ons is a unirer ore ofS such that any other unilier o some substitution at Mgu isa Example et 5 lplx al ply zl from the preoeding example The uni ersofS are lxy za and lyx za and lxt yt za fol any term The uni er xy z a isan mgu foerecause vx 13 xlr ZalivX and xl WI 13 WV Zalivtl rs can be written aso ed for factor ofanv other uni er 39nue the example and show that lyx z aisan mgu of 5 Proof xv Za vx ZaXxv and xt vt Za vx Zaxt QED Disagreement Set a a A in the following way Find the longest common substring that starts at the left end of each literal ofS The disagreement set ofS isthe set ofall the termsthat occur in the literal s that are immediately to the right oflhe lorgest common subslr n t N Example Slplgtlt lel W plxiv ll pix llal bl The longest common substring for the literalsin the string is plx The termsthat occurimmediately tot e right of this string are flxl y and lial Thus the diggreement set ofS isllixl y flal 582009 U nification algorithm Robinson For a finite set S of atoms find whether S has an mgu 1 k 0 67 a go to Step 2 2 If SBk is a singleton then stop with mgu Bk Othenlvise construct Dk set of terms in leftmost position of disagreement go to Step 3 lf Dk has a Va riable v and a term t such that v does not occur in tthen em Bklvt k k 1 go to Step 2 Othenlvise stop S is not unifiable w Exa m pl e Trace the algorithm for S px hx gy y px ha z b 1 k o a 7 c 2 sea Se px hx gy y px ha z o is nota singleton Du x a 391 e lxa xa k 1 z 561 pa ha gyy pa ha z o is nota singletonD1 gm 2 3921 91UBVxai 2 i k z 562 pa ha gy y pa ha gy o is nota singleton D2 y o 3 9 ealvb xai zglbli W 3 2 sex pa ha go o is a singleton stop with rngu e xa zglbwb E S MartelliMontanari o see whether two atoms A and a have an rngu form the setA a and apply the rollowing rules repeatedly in any order r and g are either function or predicate sym o s 1 Replace 51 squot 9 tquot with eouations s1 t1 2 it 51 squot gt1 t with f g or m e n then stop with failure 3 Deietex 4 Replace t x where t is not a variable with x t 5le tandx does notoccur in t apply xt to the other equations that contain X 6le tand t is nota variable and x occurs in t then stop with tailure it there is no failure and the rules cannot be applied then transform x t to mgu xp Example Trace the algorithm for A px hx gy y and B px ha z o plxihlxiglvllivplxihlaizlib AB XXihlxiglvhai2ivb Rule 1 hlxiglvhai2yb lea xaigy2yb Rulel i glvli We ll x a z glb y b Dorie The rngu i39s xa zgb yb o Apply the algorithm to the two atoms px x and py fy solution px x py y and Rule 1 giyes x y x fy Apply Ru e 5 to get x y y fly Apply Rule 6 to get failure Resolution Rule R Given the following two clauses LivLkCand a ijvaM v D where L and M are atoms and C and D are disjunction of other literals Assume also that 1 The clauses haye distinct sets ofvariable names rename it necessary 2 e is the rngu of L1 Lk M1 3 Set N L18 where L1 Then we have L1 vLk VC M1VVMn VD C67NVD67hN Resultant NlneN Example Given tne two clauses in one following proof segment k Ma v V Mar 2 V qltgtltr yr 2 k1 PlerlbVWr VrgW inese two clauses nave tne form t1 v t2 v c and M1 v D The two clauses have distinct sets of variables Y r Mar 2 pw in nu Notice that War Y War Z PlWr fbe Mar W 50 the resolution rule can be applied to the two clauses to obtain the resoivant k 2 qXr i br fb V rar Vr ga 582009 K k 1r K War v b Zi b To prove a wff is valid 1 Negate the wff and convert it to clausal form 2 Write down the clauses as premises 3 Use resolution to find a false statement Exa m pl e use resoiution to pmvethefollowing w isva d 3x W pm v VVI qxr1ltgt W PerV V qer soiution 1 ngztethew 3x W pm v VVI qxr1ltgt W pow V qXr v 2 convertittooiausairorm 3x W px v V VI ox 1 gt w pxw v oxw renamedvanaoies Vx vy px v sz ox 1 A 3w pxw A oxw removed gt and movm right Vx 3w vy px v sz ox 1 A pxw A oxw moved 3w iert vxiwvvvz px v v ox 1 A pxw A oxw mwedvy aride iert vxvv v2 px v v ox 1 A px fx A ox x removed 3w ov Skolem so he set or oiauses l5 px v v ox1 px fx ox fx ov making eachthethrseclzuses apremiserenametoget 5 2 a q i n v 4 ou 1 1r2rerX rVflul m 34 R wu 1fu QED Section 92 Logic Programming Example tet pXr v mean x is a parent ory and ietgx v mean x is a grandparent ofy Here are someways to representa definition or tne grandparent relation Firstrorder iogio w w Vz px 1 A p1 y a gx y Firstrorder clause gxyvpx1vp1y togio programming gx y e px 1 p1 y Proiog gx v 7 px 2 p2 v QueryGoal ine sometning is a sequence of one or more atoms and one question is wneoner there is a substitution tnat can be appiied to tne atoms so tnattne resuiting atoms are inferred by tne rogram Example suppose we nave tne following iittie logic program pa o po d abs v 6 NXr 2 ML v tetga w be a query it asks wnetner a nas a grandcniid lfwe iet e wd tnen ga we ga d wnicn says a nas a grandcniid d inis roiiows from me two program facts pa o and po d and tne derinition org so ga d is inferred by tne program Formal representation of a query clusure or a cumunctiun or one ormore atoms r l Tn rn r m e a to inter 3w gaw rnererore tne program irrersaw ga w Exampie rne ouerv gaw p u w isrormaiiv represented ov 3w au ga w puw if we iet e wd uo tnen ga w puwe ga d Apo d wnion roiiowsrrom tnetwo exampie program raotspa o and po d and tne dennition or g so ga d Apo d isinrerred ovtne program a a 3w au ga w pu w 582009 Logic Programming Representation of a Query u see whether 2 query can be interreq frurri 2 prugrzm 2 resoiution proot is attempted The premises are the prugrzm clausestugether withthe negatiuri or the query which can be written as 2 clause with oniy negative literals Example Given the query g2 w puw ltsfurmzl meaning is 3w au g puw so we negate it one cumer itto 2 clause Here are sumewzystu represent the negatiuri or the query w Vu e gz w pu w Firstrurder lugic39 Firstrurder clzu s Lugicgrugrzmming e Prulug i s 3w au gz w pu w gzw vs pu w 7 33r Wr PM W g2r Wr PM W SLD Resolution SLDrresulutiun l5 2 farm or resoiution used to execute lugic prugrzms stD means each resulvzm depends otthe previuus resulvzm an Derinite clauses arethe clauses or 2 lugic prugrzm r i iisteq intirstorqertorrn W W Mar b Mar b Pbr d Pbr d ggtltr 6 Pgtltr 1 PZr V gwwe Pgtltr ZW PZr V The query 633rwrpurw Pg2rWVPPurW Example Contd The resolution proof togiePrograrnrning Firstrorder Clauses 1pa o pa o P oo o P lam6 PszrPer gerVePszVePer P 4 gawpu w ogaw vopuw P 5 e Ma 2 ML vi PM v e Par 2 V e PZr v V e PM v 3r 4 xar wv 6epbryrp my ePbrvVe my 1r5rRrZb 7 e pu o e pu 2 6 R yd 8I I Z7Rub QED Computation Trees oueryi it represents all possible retutztions oy resoiution 39 39 39 tii ii u i39uia program clause t rr listed below the leaf of each successful refutation Example Example Given the roiiowing logic program and query 93 b Pc b e giw d Nb xwu gltxr y 6 Mn zr PZr v plwr rm Query e w wa zb wb zdl The computation tree for MK m the query is pictured enlbm en mi elated l l tenure El Suuess Suuess w a w t Example Letexn rn mean the elteeution or pn on 1 Prn Write a program tor the predicate ex soiution ann Pn 9n rn e n ltrn on k isn 1 9k rn Example Suppose we need to consuuctthe se Ln 1sns50andpnr r us warn Pro og s setof predr39eare we edmd nd rne answer wr39tn rne query pr semrw 1 lt N N lt 50 pN L wrrndutrne serdr predreare we need to de ne a predr39eare to do mejob Sohm39on Assume rnar rne rne foHowL39ng query wm constructthe set L we set1 50 1 L r39nr39rm dr 1 39 nr39npn r39s true Then we can de ne rne predreare set as foHows setLuwer Upper L L setLuwer Upper L x L Luwer gt Upper uwer N rs Luwer r 1 sedN Upper Luwer L L x set uwer Upper L x nN rs Luwer r 1 setN Upper L x 582009 Discrete Structures ll CS 251 Section 91 92 Automatic Reasoning I Recallthat a ver W is valid if39f a W is unsatisfiable tautology valid satisfiable contingencyinvalid satisfiable contradictioninvalid unsatisfiable Resolution is an inference rule used to prove unsatisfiability in a mechanical way To prove that a ver is valid prove a W is unsatisfiable using the resolution rule Note We denote false by a box D in applying resolution we assumeAv B E B vAand v EA Aand B are falsethen the rule is simplified as shown L D 582009 Computational Logic Can logic be automated Yes for some logics Automating the quotnatural deductionquot method is difficult because there are many inference rules that can be applied in many different ways Introduce a single inference rule ca led resolution that can be used automatically by a computer Resolution for Propositional Logic 39 Cancellation rule The resolution rule for propositions is shown belowwhereA and B are disjunctions of literals Notation A7 p denotes Awith all occurrences of p removed and B a a p denotes B with all occurrences ofa p removed va ipo ApVBlp To prove a wff isvalid 1 Z 3 Example Prove p e o o e r e p e r is a tautology SolutionTransform the wff into CNF a p vq a q v r p a r Proof Proof negate tne wt and convert it to CN write down tne fundamental disiunctions as premises use resolution to find a false statemen 1apq LaoVr P 3p P 4ar P so 13R 6r 25R 7D 46R 582009 Example Clausal Forms A clause is a disiunction of zero or more literals lavamleecnomlaemnelcnmvlmn M r Saiutian Negatethewtiandtranstorntheresultintotwr t rrni itb ravariable ii an iaiun i n lAvBlAlAvclAlAvomlEvillBvFlAlcvDlAlEvFl applied to W 1 AVE P arguments that are terms Z Av 3 AvD 4 M A ciausai torn is the universai closure ot a coniunction of clauses EEVFD NotationA ciausai torn is also represented as a set ot its clauses o 7 ry r 5 Av c Exampie The ciausai torn BV VX VY9XQXrYVVX PXV5Y to Bv a 1 Av is represented y t e set 12 um am v V n rxr n W V SM is oro Sk AI 39th E oems gOI39I m xampe Not every wffisequivalenl to a clauEl form For emmple the wax Find a clausal form for each wff pm is not equivalent to a clausal form But we have the following 1 3X Aix result ofSkolem which is suf cient for resolution 2 W 3V Bixr v Every wff can be associated with a clausal form in which the 3 W W 31 C09 lr 1 two are either both Etis able or both ungtisliable 4 VX 3V 31 D99 Vi 1 1 Construct the prenex cw tor the wtt z Repiace all occurrences ot each free variable by a new constant Answers 3 Eliminate the etistential quantitiers by Skoiem s Ruie A it 3x Wx is not inside the scope ot a universai ouantitier then replace 2 VX 309 W save some WWW WWW may depend W 3x WX by wc tor a new constant c 3 Vx Vy CXr Ir 09 0 a it 3x WX is inside the scope otw1 quotmquot then replace 3x WX by 4 W Dx fgtltr i500 Wfx1 x tor a new tunction symboi f Example Substitutions and Unification Put the wtt in orenex NF Ham Agglm ga nd gto an Exgress n P YV31QWVZ remuved 9 i n nr i n d e d 3x f x39yy V azz iq mM fzin NEE Did obtained trorn E by replacing all tree occurrences otx with t Vy 3x a a px yV o rz nd 3 outside Examp es39 Xi Vi WM Vi Vi Z Vy 3x S ta px y v qw a px y v r m mnstructed aw DXr yr Zvl z p09 l Zr Z A substitution is a finite set of bindingswith dis nctnumerators Use lowercase greek letters tor substitutions Exampie e xy yfz and 0 y a zb are substitutions W e NibMW am WW v V ew So there are two clauses int e clausal torrn which can be denoted by the set in NibMW W e WW v V ew of Expressions Applying a Substitution to an Expression or a Set men Ee obtained trorn E by simultaneously applying the bindings in e to E Example if e Xvi vl Zi the 9Xi in Z9 9Xi vi ZXvivl z 9vi l Zi Z by applying 9 to each etpression or s Example if e Xvi WW and S 909 W CW BZi the 59 Wi Wei CW BOW Nii l Zi ql Zi Bu it s is a setot etpressions then se is the set or etpressions obtained trorn s Exa m pl e Let 9 xyy zl and o y al zb Calculate eo Step 1 Construct xyo y zla lX al vflbl Step 2 No deletions So no changes step 3 Delete y al from o lbecause y is a numerator orelto obtain zb step 4 The union of sets from steps 2 and 3 give eo x al Vflblr Zbl 582009 Composing Substitutions from the application Example we calculate Perr1e PerrZeH ptvr Hz zllu we W b so op iXf2rvfbr zbl 1 construct lxtpl Delete any xxrrurn step 1 sDelete ys malfylsa numerat r to u u p isthe union urthe substitutlurlsfrurn steps 2 and s By grep E6u We can calculate so by applying it to an atom that cuntalrls all the Properties of Composition 1 EBo E9o 2 98 89 9 where e l U n lfl er A unifer ofa set S of express39ons is a substitution 9 such that 9 isa singleton set Exam le 1 xa is a uni er ofiplxl plal because plxl plalXxa plai 2 What are som nili pix al ply 2 er Since a is a constant any uni er must include the binding za A unilier might also include xy or yx So two uniliers ofS are lxy za and lyx za betause Sixv 13 plv alland Sivx Za pl Notice also that xt yt za is a uni er x al ofS for any term t because Sixl WI 13 pit al Most general unifier mgu most general uni er lmgul ofa sets orexpress39ons is a unirer ore ofS such that any other unilier o some substitution at Mgu isa Example et 5 lplx al ply zl from the preoeding example The uni ersofS are lxy za and lyx za and lxt yt za fol any term The uni er xy z a isan mgu foerecause vx 13 xlr ZalivX and xl WI 13 WV Zalivtl rs can be written aso ed for factor ofanv other uni er 39nue the example and show that lyx z aisan mgu of 5 Proof xv Za vx ZaXxv and xt vt Za vx Zaxt QED Disagreement Set a a A in the following way Find the longest common substring that starts at the left end of each literal ofS The disagreement set ofS isthe set ofall the termsthat occur in the literal s that are immediately to the right oflhe lorgest common subslr n t N Example Slplgtlt lel W plxiv ll pix llal bl The longest common substring for the literalsin the string is plx The termsthat occurimmediately tot e right of this string are flxl y and lial Thus the diggreement set ofS isllixl y flal 582009 U nification algorithm Robinson For a finite set S of atoms find whether S has an mgu 1 k 0 67 a go to Step 2 2 If SBk is a singleton then stop with mgu Bk Othenlvise construct Dk set of terms in leftmost position of disagreement go to Step 3 lf Dk has a Va riable v and a term t such that v does not occur in tthen em Bklvt k k 1 go to Step 2 Othenlvise stop S is not unifiable w Exa m pl e Trace the algorithm for S px hx gy y px ha z b 1 k o a 7 c 2 sea Se px hx gy y px ha z o is nota singleton Du x a 391 e lxa xa k 1 z 561 pa ha gyy pa ha z o is nota singletonD1 gm 2 3921 91UBVxai 2 i k z 562 pa ha gy y pa ha gy o is nota singleton D2 y o 3 9 ealvb xai zglbli W 3 2 sex pa ha go o is a singleton stop with rngu e xa zglbwb E S MartelliMontanari o see whether two atoms A and a have an rngu form the setA a and apply the rollowing rules repeatedly in any order r and g are either function or predicate sym o s 1 Replace 51 squot 9 tquot with eouations s1 t1 2 it 51 squot gt1 t with f g or m e n then stop with failure 3 Deietex 4 Replace t x where t is not a variable with x t 5le tandx does notoccur in t apply xt to the other equations that contain X 6le tand t is nota variable and x occurs in t then stop with tailure it there is no failure and the rules cannot be applied then transform x t to mgu xp Example Trace the algorithm for A px hx gy y and B px ha z o plxihlxiglvllivplxihlaizlib AB XXihlxiglvhai2ivb Rule 1 hlxiglvhai2yb lea xaigy2yb Rulel i glvli We ll x a z glb y b Dorie The rngu i39s xa zgb yb o Apply the algorithm to the two atoms px x and py fy solution px x py y and Rule 1 giyes x y x fy Apply Ru e 5 to get x y y fly Apply Rule 6 to get failure Resolution Rule R Given the following two clauses LivLkCand a ijvaM v D where L and M are atoms and C and D are disjunction of other literals Assume also that 1 The clauses haye distinct sets ofvariable names rename it necessary 2 e is the rngu of L1 Lk M1 3 Set N L18 where L1 Then we have L1 vLk VC M1VVMn VD C67NVD67hN Resultant NlneN Example Given tne two clauses in one following proof segment k Ma v V Mar 2 V qltgtltr yr 2 k1 PlerlbVWr VrgW inese two clauses nave tne form t1 v t2 v c and M1 v D The two clauses have distinct sets of variables Y r Mar 2 pw in nu Notice that War Y War Z PlWr fbe Mar W 50 the resolution rule can be applied to the two clauses to obtain the resoivant k 2 qXr i br fb V rar Vr ga 582009 K k 1r K War v b Zi b To prove a wff is valid 1 Negate the wff and convert it to clausal form 2 Write down the clauses as premises 3 Use resolution to find a false statement Exa m pl e use resoiution to pmvethefollowing w isva d 3x W pm v VVI qxr1ltgt W PerV V qer soiution 1 ngztethew 3x W pm v VVI qxr1ltgt W pow V qXr v 2 convertittooiausairorm 3x W px v V VI ox 1 gt w pxw v oxw renamedvanaoies Vx vy px v sz ox 1 A 3w pxw A oxw removed gt and movm right Vx 3w vy px v sz ox 1 A pxw A oxw moved 3w iert vxiwvvvz px v v ox 1 A pxw A oxw mwedvy aride iert vxvv v2 px v v ox 1 A px fx A ox x removed 3w ov Skolem so he set or oiauses l5 px v v ox1 px fx ox fx ov making eachthethrseclzuses apremiserenametoget 5 2 a q i n v 4 ou 1 1r2rerX rVflul m 34 R wu 1fu QED Section 92 Logic Programming Example tet pXr v mean x is a parent ory and ietgx v mean x is a grandparent ofy Here are someways to representa definition or tne grandparent relation Firstrorder iogio w w Vz px 1 A p1 y a gx y Firstrorder clause gxyvpx1vp1y togio programming gx y e px 1 p1 y Proiog gx v 7 px 2 p2 v QueryGoal ine sometning is a sequence of one or more atoms and one question is wneoner there is a substitution tnat can be appiied to tne atoms so tnattne resuiting atoms are inferred by tne rogram Example suppose we nave tne following iittie logic program pa o po d abs v 6 NXr 2 ML v tetga w be a query it asks wnetner a nas a grandcniid lfwe iet e wd tnen ga we ga d wnicn says a nas a grandcniid d inis roiiows from me two program facts pa o and po d and tne derinition org so ga d is inferred by tne program Formal representation of a query clusure or a cumunctiun or one ormore atoms r l Tn rn r m e a to inter 3w gaw rnererore tne program irrersaw ga w Exampie rne ouerv gaw p u w isrormaiiv represented ov 3w au ga w puw if we iet e wd uo tnen ga w puwe ga d Apo d wnion roiiowsrrom tnetwo exampie program raotspa o and po d and tne dennition or g so ga d Apo d isinrerred ovtne program a a 3w au ga w pu w 582009 Logic Programming Representation of a Query u see whether 2 query can be interreq frurri 2 prugrzm 2 resoiution proot is attempted The premises are the prugrzm clausestugether withthe negatiuri or the query which can be written as 2 clause with oniy negative literals Example Given the query g2 w puw ltsfurmzl meaning is 3w au g puw so we negate it one cumer itto 2 clause Here are sumewzystu represent the negatiuri or the query w Vu e gz w pu w Firstrurder lugic39 Firstrurder clzu s Lugicgrugrzmming e Prulug i s 3w au gz w pu w gzw vs pu w 7 33r Wr PM W g2r Wr PM W SLD Resolution SLDrresulutiun l5 2 farm or resoiution used to execute lugic prugrzms stD means each resulvzm depends otthe previuus resulvzm an Derinite clauses arethe clauses or 2 lugic prugrzm r i iisteq intirstorqertorrn W W Mar b Mar b Pbr d Pbr d ggtltr 6 Pgtltr 1 PZr V gwwe Pgtltr ZW PZr V The query 633rwrpurw Pg2rWVPPurW Example Contd The resolution proof togiePrograrnrning Firstrorder Clauses 1pa o pa o P oo o P lam6 PszrPer gerVePszVePer P 4 gawpu w ogaw vopuw P 5 e Ma 2 ML vi PM v e Par 2 V e PZr v V e PM v 3r 4 xar wv 6epbryrp my ePbrvVe my 1r5rRrZb 7 e pu o e pu 2 6 R yd 8I I Z7Rub QED Computation Trees oueryi it represents all possible retutztions oy resoiution 39 39 39 tii ii u i39uia program clause t rr listed below the leaf of each successful refutation Example Example Given the roiiowing logic program and query 93 b Pc b e giw d Nb xwu gltxr y 6 Mn zr PZr v plwr rm Query e w wa zb wb zdl The computation tree for MK m the query is pictured enlbm en mi elated l l tenure El Suuess Suuess w a w t Example Letexn rn mean the elteeution or pn on 1 Prn Write a program tor the predicate ex soiution ann Pn 9n rn e n ltrn on k isn 1 9k rn Example Suppose we need to consuuctthe se Ln 1sns50andpnr r us warn Pro og s setof predr39eare we edmd nd rne answer wr39tn rne query pr semrw 1 lt N N lt 50 pN L wrrndutrne serdr predreare we need to de ne a predr39eare to do mejob Sohm39on Assume rnar rne rne foHowL39ng query wm constructthe set L we set1 50 1 L r39nr39rm dr 1 39 nr39npn r39s true Then we can de ne rne predreare set as foHows setLuwer Upper L L setLuwer Upper L x L Luwer gt Upper uwer N rs Luwer r 1 sedN Upper Luwer L L x set uwer Upper L x nN rs Luwer r 1 setN Upper L x 582009 Discrete Structures CS 251 Week 3 Equivalent Formulas Two wffs A and B are equivalent written A E B if they have the same truth value for every interpretation That is they are either both true for any interpretation g they are both false for any interpretation AEBijfA9BAB9Aisvalid ff A9 B and B 9 A are both valid 4142009 Example 1 Find examples of wffs with the given properties The variable x has three bound occurrences and one free occurrence 3X l3le X 9 W The variable x has four bound occurrences and the variable y has two bound occurrence and one free occurrence 3X Vv plxyx 9 qlxyvll A plxyv N Propositional Equivalence Gives Rise to First Order Equivalence I In other words if two propositional w39f39fs are equivalent and each occurrence of a propositional variable is replaced by a first order w f f then the resulting two first order w39f39fs called instances are equivalent Example We know thatA 9 B E A V B So by lettingA Vx px and B Elx px we get Vx px 9 Elx px E Vx px V 3xpx Basic Equivalences 1 Proof second equivalence Let I be an arbitrary interpretation with domain D Then 3X W is true wrtl iff 3X Wis false wrtl iff WXd is false wrt lfor all d6 D iff WXd is true wrt lfar all d E D iff Vx a W is true wrt I Since I was arbitrary the wffs are equivalent QED Example Example Vx px 9 Elx px E prx V Elx px instance of propositional wff P 9 Q E P V O E Elx px V Elx px basic equivalence 1 Basic Equivalence 2 Proof first equivalence Let I be an arbitrary interpretation with domain D Then Vx Vy W is true wrt I iff Vy WXd istrue wrt Ifor all d E D iff WXd ye is true wrt Ifor all d e E D iff Wye Xd is true wrt Ifor all d e E D iff Vx Wye is true wrt Ifor all e E D iff Vy Vx W is true wrt I Since I was arbitrary the wffs are equivalent QED 4142009 Basic Equivalence 3 EIX AX 9 BX E VXAlX 9 EIXB Proof Let I be an arbitrary interpretation with domain D Assume LHS is true wrt I Then NEH 3a istrue wrtlfor some cED Cons39der the possible values ofAl fAi is true wrt i then 3a istrue wrt i 50 3x BX istrue forl which implies RHS istrue for i fAi isfalse wrt I then mm isfalse wrt I which implies RHS is true for I So LHS 9 RHS isvalid Similarly you an prove RHS 9 LHS Basic Equivalence 4 Proof EIX AX V BX E EIX AlX 9 BX instance of propositional wff EVX AX 9 EIXBX 3 E EIXAX 9 EIXBX l E EIXAX V EIX BX instance ofpropositional wff QED Basic Equivalence 5 Vx AX BX E VXAX Vx BX Proof Let I be an arbitrary interpretation with domain D Then Vx AX BX is true wrt I iffAd Bd is true wrt Ifor all d ED iffAd is true wrt Ifor all d ED and Bd is true wrt Ifor all d ED iff VXAX is true wrt I and in BX is true wrtl iff VXAX Vx BX is true wrt I Since I was arbitrary the wffs are equivalent QED Restricted Equivalences 6 Renaming Variables Ify does not occur in WX then I EIX Wx E Ely WXy and VX WX E Vy WXy Remember that WXy is obtainedfrom WX by replacing all free occurrences of X by y Example VX Ely pX y EIX qX y 5 V2 3y plz y 32 qlz y Example Let s replace the quantifier variables in the wff so that they are all distinct W 3V plxr v 9 3X qlxr v V W rlxr y Ans Replace Vx by V2 3v plzr v 9 3X qlxr v V W rlzr vil Replace Vy rz y by Vw rz w V2 3v plzr v 9 3X llxr v va rer wil Restricted Equivalences 7 lfx duesnut occur free m c then Simplification a VXCECa dEXCEC Dis an wamwm 2 cvaAm andix CVAX 2 cvax Ax emanation c VX C Ax 2 m vmm and 3XC Ax 2 C 3xAx a VX c Ax 2 c vmm 1 3XC9 Ax 2 9 3x Ax 2 Be careful with m VXWXH c 2 3mm 9 c swam 9 c 2 VXAX c 4142009 Example We know that x Vy pX y 9 Vy 3xpx y is valid but the converse is not valid So we can t interchange 3x and Vy But for predicates that take single arguments the two quantifiers can be interchanged For example we have the following equivalence 3X W W 9 qy E W 3X W 9 qy Proof 3X W W 9 qy 5 3X W 9 W qy 7d E W W 9 W qy 76 W W W 9 qy 7d 5 W 3X W 9 qy 7e Normal Forms lAwff in prenex normalform has all quantifiers at the left end 947 3X W W 9 qy Prenex Normal Form Algorithm a Rename variables ofW so that no quantifiers use the same variable name and such that the quantified variable names are distinct from the free variable names b Move quantifiers left using 1 7b 7C 7d and 7e Example Example qX 3X rX 9 9 3y pX y E qx Elz rz 9 Ely pz y rename E 32 MM M2 9 a Ely 72 y 7b 5 32 MM M2 9 Vya 72 y 1 E 32 MM W M2 9 a 72 y 7d 5 32 W qX M2 9 a 72 VD 7b Prenex CNFDNF Awff in prenex normal form is in prenex CNF or prenex DNF ifthe wffto the right of the quantifiers is in CNF or DNF where a literal is now eitheran atom or its negation Example px and a px are literals Example Elz Vy qx rz V a pz y is a prenex CNF Example 32 W W r2 V W W y is a prenex DNF Prenex CNFDNF Algorithm a b Put wff in prenex normal form Remove 9 c Move to the right to form literals d Distribute V over andor over V for desired form Example 7 X 7 y 31qX V rz X 9 p1 y preneX normalform E 7 X 7 y31qX V rz X lpz y remove 9 E 7 X 7 y 31 qX rz X y pz y move right preneX DNF E W W 31 W V plI y rlzi X V p1y distribute preneX CNF 4142009 Formalizing English Sentences Some rules that usually work for English sentences are 0 VX quantifies a conditiona 0 3X quantifies a conjunction 0 Use VX with conditionalfor all every and only 0 Use 3X with conjunction for llsome quotthere is and llnot ll 0 Use VX with conditional or 3X with conjunction for llno A is B 0 Use 3X with conjunction or VX with conditionalfor llnot allA s are B Example For a person X let CX mean X is a criminal and let sX mean X is sane Formalize the following sentences 1 All criminals are sane Solution VX cX 9 sX Example Contd 2 Every criminal is sane Solution VX cX 9 sX 3 Only criminals are sane Solution VX sX 9 cX Example Contd 4 Some criminals are sane Solution EIX cX sX 5 There is a criminal that is sane Solution EIX cX sX Example Contd 6 No criminal is sane Solution VX cX 9 sX E EIX cX sX 7 Not all criminals are sane Solution EIX cX sX E VX cX 9 sX 4142009 Formal proofs in predicate calculus Formal proofs All inference rules for propositional calculus 39 Blft we head additional inference rUles to reason extend to predicate calculus Wlth mOSt quantl ed Wffs39 For example suppose we want to prove that the following wff is valid Example l7 x px P 3x Vy px v 9 W 3x F er v 2 vx px 9 3x pm P We might start With the proof 1 Elx Vy px y P 339 3X plxl l 239 MP But what do we do forthe next line ofthe proof We re stuck if we want to use inference rules We need more inference rules Free to replace Universal Instantiation UI For a wff Wx and a term t we sayt is free to o ft is free to replace x in Wx replacex in Wx ifWt has the same bound VxWx occurrences of variables as Wx Example Wt Let Wx 3v pm W39Then If a property holds for everything then the WM By my v v is not free to replace X in Wx property holds for any particular thing Special cases that satisfy the restriction Wfx Ely pfx y fx is free to replace x in Wx Wc Ely pc y c is free to replace x in Wx vax vax Wx Ely px y x is free to replacex in Wx x C Existential Generalization E6 E6 contrapositive of UI EG Wt 3x Wx E a 3x Wx a Wt EVx a Wx a Wt U if t is free to replace x in Wx Wt 3xWx If a property holds for a particular thing then the property holds for something Special cases that satisfy the restriction Wx WC 3xWx 3xWx Example W pc v We can write Vy pc y Wc where Wx Vy px y Now since c is a constant we can use EG to In er 3X Vv px v For example over the domain of natural numbers let px y mean x y and let c0 Then Vy 0 g y we can use EG to infer 3x Vy x y 4142009 Existential Instantiation El ifc is a new constant in the proof and c does not occur in the statement to be proved then Elex Wc Example For example if the wff x pxb occurs in a proof then we can t say pbb holds Let pxb mean quotx is the parent of bquot Then pbb is false So we can39t pick a constant that is already in the wf f Universal Generalization UG if amongthe wffs used to infer Wx x is not free in any premise and x is not free in any constructed by El Wx We let x be any arbitrary but fixed element of the domain D Next we construct a proofthat Wx is true Then we say that since x was arbitrary it follows that Wx is true for all x in D So from a proof of Wx we have proved Vx Wx Example Vx Ely px y 9 Ely Vx px y is invalid Here is an attempted proof 1 Vx Ely px y P 2 Ely px y 1U 3 px c 2E 4 Vx px c 3 U6 NO x on line 3 is free in wff inferred by El 5 Ely Vx px y 4 EG NOT QED 1 4 CP Example Elx px 9 Vx px is invalid Here is an attempted proof 1 Elx px P 2 px 1 El NO x is not a new constant in the proof 3 Vx px 2 UG NOT QED 1 3 CP Example 3x px 3xqx 9 3x px Aqx is invalid Here is an attempted proof 4142009 Example px 9 Vx px is invalid Here is an attempted proof 1 px P 2 Vx px l UG NO x is free in a premise NOT QED 1 2 CP 1 3x px 2 3xqx P 3 pc 1 El 4 qc 2 El N0 c is not a new constant in the proof 5 pc Aqc 3 4 Con 6 3x px qx 5 EG NOT E 1 6 CP Example Vx Ely px y 9 Ely py y is invalid Here is an attempted proof 1 Vx Ely px y P 2 3v ply v 1 UI NO y is not free to replace x in Ely px y NOT QED 1 2 CP Example Vx px fx 9 Elx px x is invalid Here is an attempted proof Example Vx px fx 9 Ely Vx px y is invalid Here is an attempted proof 1 Vx px fx P 2 Ely Vx px y 1 EG NO x is not free to replace y in Vx px y NOT QED 1 2 CP l Vx px fx P 2 px fx 1 UI 3 Elx px x 2 EG NO px fx px xxt for any term t NOT QED 1 3 CP Example 3X PM 9 pc is invalid Here is an attempted proof 1 Elx px P 2 pc 1 El NO c occurs in statement to be proved NOT QED 1 2 CP 4142009 Example VX W per v 9 W plvr v isvalid Here is an attempted proof 1 VX vv plx v P 2 vv ply v 1 UI NO v isnot free to replace x in vv plx vll NOT QED 1 2 CP But here is a correct proof 1 VX vv plx v P 2 vv plx v 1 UI 3 pl xl 2 UI 4 VX plx x 3 U6 5 W plv v 4 T QED 1 5 CP Example Vx Ax 9 Bx 9 Vx Ax 9 Vx Bx is valid Find a proof Example Prove that the following wffisvalid us39ng IP VX 9 W X AVX W V2 W v A My 2 9 W 2 9 Vx W 9 W V A My 0 Proof39 1Vx9pl Proo 1 Vx Ax 9 Bx P 2 Vx Ax P 3 Ax 2 UI 4 Ax 9 Bx 1 UI 5 B x 34 MP 6 Vx Bx 5 7 Vx Ax 9 Vx Bx 2 6 CP QED 1 7 CP Example Find a CP proof ofthe statement VX W X AVX W V2 W V A My 2 9 W 2 9 Vx W a W v A My 0 Proof xxl ZVXWVlelxrleplv z9 plXZ P 33x 3vlplxrleplvX Pfor PT 4 pla blAplb a 3 El El 5 pla blAplb al9 pla a 2 UI Ul U a 4 5 79le a 1 UI 8pla alAepla a 6 7 Conj 9 false gyr 1 2 9 IP Example Prove that the following wff is valid W 3V plx 9 pm 1 px P 2 Elx px 1 EG 3 pc 2 El 4 px 9 pc l 2 CP 5 3v plx 9 FM 4 EG 6 Vx Ely px 9 py 5 U6 1 Vx px x P 2 VX W V2 per v A ply 2 9 per 2 P 3 per X 1 UI 4 pXypy x 9px x 2UUIU 5 per v A ply X 3 4 MT 6 VX Wper VlPer X 5 UGUG QED 1 2 6 CP Example Vx Ax 9 C 9 Elx Ax 9 C Proof 1 Vx Ax 9 C P 2 Elx Ax P 3 Ad 2 El 4 Ad 9 C 1 UI 5 C 3 4 MP 6 Elx Ax 9 C 2 5 CP QED 1 6 CP 3x Ax 9 C 9 Vx Ax 9 C Proof 1 Elx Ax 9 C 2 Ax 3 Elx Ax 4 C 5 Ax a c 6 Vx Ax 9 C QED 1 6 CP Example 4142009 Example Evencomputerscience major is a logical thinker John is a computerscience major Therefore there is some logical thinker Ans Let Cx mean 39x is a computerscience major l Lx mean quotx is a logical thinker l Let bJohn Vx Cx9 Lx Cb xLx Vx Cx 9 Lx Cb 9 Elx Lx Example Contd Vx Cx 9 Lx Cb 9 3x Lx Proof U PWEquot 1 UI 2 3 MP 4 E6 1 6 CP

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.