WIXLIB

WUCT121Discrete MathematicsLogicTutorial Exercises Solutions1.Logic2.Predicate Logic3.Proofs4.Set Theory5.Relations and FunctionsWUCT121Logic Tutorial Exercises Solutions1

Section 1: LogicQuestion1(i) If x 3 , then x 2 .(a)Statement(b)False(c)x 3 x 2(ii)If x 0 or x 1 , then x 2 x .(a)Statement(b)True(c)( x 0 x 1) x 2 x(iii) There exists a natural number x for which x 2 2 x .(a)Statement(b)False(iv)If x and x 0 , then if(a)Statement(b)True(c)x 1 then x 1 .( x x 0) ( x 1 x 1)xy 5 implies that either x 1 and y 5 or x 5 and y 1 .(v)(a)(b)StatementFalse. Consider x 1 and y 5 or x 5 and y 1 .(c)xy 5 (( x 1 y 5) ( x 5 y 1))xy 0 implies x 0 or y 0 .(vi)(a)(b)(c)StatementTruexy 0 x 0 y 0(vii) xy yx .(a)Statement(b)True(viii) There is a unique even prime number.(a)Statement(b)True, x 2.WUCT121Logic Tutorial Exercises Solutions2

Question2(a) If x is odd and y is odd then x y is even.p: x is odd. q: y is odd. r: x y is even.Form: p q r .(b)It is not both raining and hot.p: It is raining. q: It is hotForm: ( p q ) , alternatively p q(c)It is neither raining nor hot.p: It is raining. q: It is hotForm: p q , alternatively ( p q ) .(d)It is raining but it is hot.p: It is raining. q: It is hot.Form: p q .(e) 1 x 2 .p : 1 x , q : 1 x , r : x 2, s : x 2 .Form: ( p q ) ( r s ) .Question3:(a) P Q :Mathematics is easy or I do not need to study.(b)P Q :(c) Q:(d)(e)(f) Q:I do not need to study. P: P Q:Mathematics is not easy.Mathematics is not easy and I do not need to study.(g)P Q:If Mathematics is easy, then I do not need to studyMathematics is easy and I do not need to studyI need to study.Question4(a) The truth tables for ( p q ) q and ( p q ) q .p q ( p T T FTT F FFF T TTF F TTStep:12The tables are the same(b)q) q ( pFTFFTTTF13* FFTF2q) TFTF3*qThe truth tables for ( p q ) p and ( p q ) p .p q ( p q) p ( p q) pT T FTFFTTT F FFFFFTF T TTTTFTF F TTTFFFStep: 12123*3*The tables are not the same. The student’s guess is falseWUCT121Logic Tutorial Exercises Solutions3

Question5(a) The truth tables for p p and p p .p pTF p p pT FF TT TF F2* 12* 1(b) p p is a tautology i.e. always true; p p is a contradiction, i.e. always false(c) Use truth tables.p q (pT TT FF TF FStep:Notice that “true p) q (p p) qTFFFTFTFFFTFTTFTTFTTFTTF21 3*21 3*anything” is true and “false anything” is falseConclusion: If you have a compound statement R of the form “ T P ”, where Tstands for a tautology (and P is any compound statement), then R is also atautology. Similarly, if you have a compound statement, S, of the form “ F P ”,where F stands for a contradiction, then S is also a contradiction.Question6(a) The truth tables for the statements ( p p ) (q r ) and q r .q r (p p) (q r) q rT TTFTTTT FTFTTTF TTFTTTF FTFFFFT TTTTTTT FTTTTTF TTTTTTF FTTFFFStep:21 4*31*Notice that the two statements are logically equivalent.In fact, the truth value of the first is dependent entirely on the secondpTTTTFFFFWUCT121Logic Tutorial Exercises Solutions4

(b) The truth tables for the statements ( p p ) (q r ) and q r .q r (p p) (q r) q rT TFFTTTT FFFFFFF TFFFFFF FFFFFFT TFTTTTT FFTFFFF TFTFFFF FFTFFFStep:21 4*31*Notice that the two statements are logically equivalent.In fact, the truth value of the first is again dependent entirely on the second.pTTTTFFFFConclusion: If you have a compound statement R of the form “ T P ”, where T standsfor a tautology (and P is any compound statement), then the truth-value of R dependsentirely on the truth-value of P. Similarly, if you have a compound statement, S, ofthe form “ F P ”, where F stands for a contradiction, then the truth-value of Sdepends entirely on the truth-value of P.Question7(a) ( p q ) ( p q )(p 1q) (p 3 2q)(q 3p)Step4*Place F under main connectiveFFF must be FstTFT1 , p must be T and q must be F.F2nd , p must be T and q must be Fq must be TTq cannot be both T and F , thus ( p q ) ( p q ) can only ever be true and is a tautology(b) ( p q ) (q p )StepPlace F under main connective must be F and must be F1st must be T. 2nd , q must be Tand p must be F1st p can be F and q can be T, (2p 1q) 4*FFFTFTFTno conflictThere is no contradiction, thus the statement is not a tautologyWUCT121Logic Tutorial Exercises Solutions5

(c) ( p q ) ( r ( p q ))(pStepPlace F under main connective must be T and must be F p must be T and q must be T r must be F and must be F q)1 ( r 5*F24T(p q)3FTTFFT p must be T and q must be Fq cannot be both T and F , thus ( p q ) ( r ( p q )) can only ever be true and is atautologyFQuestion8(a)( p q ) r ( p q ) r ( p q ) r p q r(b)p ( p q ) p ( p q ) p p q T q TImplication LawDe Morgan' s LawAssociativityImplication LawAssociativityNegation LawDominance LawQuestion9(a)LHS ( p q ) ( p q )Implication Law p q p qDe Morgan' sDouble Negation RHS(b)LHS ( p q ) r ( p q ) r ( p q ) rWUCT121Implication LawDe Morgan' s ( p q ) r p (q r )Double NegationAssociativity p (q r ) RHSImplicationLogic Tutorial Exercises Solutions6

Question10(a) If x is a positive integer and x 2 3 then x 1 .The proposition is True.If x is a positive integer, then x 2 3 x 3 .Now 3 1.7 and so x 1 .(b) ( ( x 1) ( y 0 )) (( x 1) ( y 0 )) .The proposition is false. (You should have tried proving it using De Morgan’s Laws andfailed.)Now find values of x and y that make the statement false.Let x 0 and y 1 . ( x 1) ( y 0 ) is True( x 1) ( y 0) is also TrueThus, (( x 1) ( y 0 )) is Falseand the proposition is False.Question11(a) ( x 1) ( y 0)(b) ( ( x 1)) ( y 0) ( x 1) ( y 0)Implication LawDouble Negation ( x 1) ( y 0)Negation of ( y 0) ( x 1) ( y 0 ) ( x 1) ( y 0 ) ( x 1)Implication Law .Negation of Question12 ( ( p q ) q ) ( p q ) q ( p q) q p q q p qWUCT121De Morgan' sDouble NegationAssociativityIdempotent LawLogic Tutorial Exercises Solutions7

Section 2 :Predicate LogicQuestion1(a)Every real number that is not zero is either positive or negative.The statement is true.(b)The square root of every natural number is also a natural number.The statement is false (consider n 2 ).(c)Every student in WUCT121 can correctly solve at least one assigned problem.Lecturers are yet to work out if this is true or false!Question2(a) x , y , ( xy 0 ( x 0 y 0 ))The statement is false (consider x 1 and y 0 ). x , y , x yThe statement is true.(c) student s in WUCT121, lecturer’s jokes j, s hasn’t laughed at j.True or false ?(b)Question3(a)Let H be the set of all people (human beings).P : p H, q H, p loves q . P : ( p H , q H , p loves q ) p H , ( q H , p loves q ) p H , q H , p doesn' t love qIn a nice world, P is true!.(b)P : p H , q H , p loves q . P : ( p H , q H , p loves q ) p H , ( q H , p loves q ) p H , q H , p doesn' t love qIn a perfect world, P is true!(c)P : p H , q H , p loves q . P : ( p H , q H , p loves q ) p H , ( q H , p loves q ) p H , q H , p doesn' t love qP is definitely true!(d)P : p H , q H , p loves q . P : ( p H , q H , p loves q ) p H , ( q H , p loves q ) p H , q H , p doesn' t love qIn our world, P is probably true!WUCT121Logic Tutorial Exercises Solutions8

P : x , x . P : ( x , x )(e) x , x P is true.(f)P : ( n , p , n 2 p ) n , ( p , n 2 p ) n , p , n 2 p P : ( n , p , n 2 p ) n , p , n 2 pP is true.(g)P : n , n is not prime . P : ( n , n is not prime) n , n is primeP is true.(h)P : triangle T , T is a right triangle . P : ( triangle T , T is a right triangle) triangle T , T is not a right triangle P is true.Question4(a) x , ( x 1 x 0 )This statement is true. Clearly, 0 1 x, so x 0(b) x , ( x 1 x 2 )This statement is false. Let x 1.5 . Then x 1 but x 2 .(c) x , x 1 x 2 x()This statement is true. Let x 2 . Then x 1 and x 2 4 2 x .(d)x1 x , x 1 2x 1 3 This statement is true. Let x 3 . Then x 1 and(e)x3 1 .x 1 10 32 x , y , x 2 y 2 9This statement is false. Let x 1 and y 1 . Then x 2 y 2 2 9 .(f) x , y , x 2 y 1This statement is true. For x , let y x 2 . Then clearly x 2 y 1 .(g) x , y , x 2 y 2 0This statement is true. Let x 0 . For each y , y 2 0 , and we havex2 y2 y2 0 .WUCT121Logic Tutorial Exercises Solutions9

( x , y , x y x 2 y 2(h))This statement is true. Let x 0 and y 1 . Then x y and x 2 0 1 y 2 .Question5(i)For each of the following statements, ( ξ 0, x 0, x ξ ) ξ 0, ( x 0, x ξ ) ξ 0, x 0, x ξThe negation of the statement is false.For any ξ 0 , we can take x (ii)( y , x ,, y x 2() y , x ,, y x 2ξ2and we have x 0 but x ξ .) y , x ,, y x 2The negation of the statement is false.Let y 1 . We know x 2 0 for all x , i.e. x 2 y .(iii)x y y y , x , x y x 2 x y y , x , x y x y 2 x y y , x , x y x y 2 x y x y y , x , x y x 2 2 y , x , ( x y ( y x x y ))The negation of the statement is false.Clearly, x y ( y x x y ) is equivalent toimpossible. y x y x y , which isQuestion6(a) P : ( x , x 2 2) x , ( x 2 2) x , x 2 2(b) Q : ( x , x 2 1 2 x ) x , ( x 2 1 2 x ) x , x 2 1 2 xWUCT121Logic Tutorial Exercises Solutions10

Question7(a)P : ( x , y , y x ) P : ( x , y , y x ) ( x , ( y , y x )) ( x , y , ( y x )) ( x , y , y x )The true statement is P because for a real number x, x – 1 is a smaller realnumber.(b)Q : ( x , ( x 0 x 0 )) Q : ( x , ( x 0 x 0)) ( x , ( x 0 x 0)) x , ( x 0) ( x 0) x , x 0 x 0 x , x 0The true statement is Q because x 0 is neither positive nor negative.Question8(a) ( x , x 0 ) x , ( x 0 ) x , x 0The negation is true.(b) ( z , (z is odd z is even)) z , (z is odd z is even) z , (z is not odd z is not even ) (De Morgan' s)The original statement is true(c)(( n , n is even n is prime()))n is not prime) (De Morgan' s) n , n is even n is prime( n , n is odd The original statement is true.WUCT121Logic Tutorial Exercises Solutions11

(d) y 1 y , y 0 1 y y 1 y , y 0 1 y y 1 y , y 0 1 y y 1 y , y 0 1 y The negation is true.(e) ( x , y , xy 1) x , ( y , xy 1) x , y , ( xy 1) x , y , xy 1The negation is true.(f) ( n , p , n 2 p ) n , ( p , n 2 p ) n , p , (n 2 p ) n , p , n 2 pThe negation is true.(g) ( ε , x , y , (ε 0 x y ε )) ε , ( x , y , (ε 0 x y ε )) ε , x , ( y , (ε 0 x y ε )) ε , x , y , (ε 0 x y ε ) ε , x , y , (ε 0 ( x y ε )) (Thm. 1.4.2 pt 6) ε , x , y , (ε 0 x y ε )The statement is true.Question9(a)(()) y , y 1 y 2 1() y , (y 1 (y 2 1)) y , (y 1 y 2 1) y , y 1 y 2 1The original statement is false. Take y 0, then y 0 1 y 2 0 1)WUCT121Logic Tutorial Exercises Solutions12

(b)( x , x 2 1 0() x , x 2 1 0) x , x 2 1 0The original statement is false. For any real number, x, x 2 0 , so x 2 1 1 .Thus, x 2 1 0 .(c)(d) ( x, y , z , x ( y z ) ( x y ) z ) x, y , z , ( x ( y z ) ( x y ) z ) x, y , z , x ( y z ) ( x y ) zThe original statement is false. Let x y 1 and z 0 .Then 1 (1 0 ) 1 1 0 and (1 1) 0 0 0 0 . ( x , y , x y 0 ) x , ( y , x y 0 ) x , y , ( x y 0 ) x , y , x y 0The negation is false. For any real number x, x x 0 , so let y x .Question10 Write the following statements using quantifiers. Find their negations anddetermine in each case whether the statement or its negation is false, giving briefreason where possible.(a)P : n , m , n m P : ( n , m , n m) n , ( m , n m ) n , m , (n m ) n , m , n mThe statement P is false. Let n 1 . All natural numbers m are greater than n.P : x , x 2 0(b)( P : x , x 2 0( x , x 2 0)) x , x 2 0The statement P is false. For any real number x, x 2 is not less than 0.(c)Let D be the set of all dogs.P : d D , d is vegetarian. . P : ( d D , d is vegetarian ) d D , (d is vegetarian ) d D , d is not vegetarianThe statement P is probably false.WUCT121Logic Tutorial Exercises Solutions13

(d)(e)P : x , x is rational . P : ( x , x is rational) x , ( x is rational) x , x is not rationalThe statement P is false. The number 2 is real and rational.Let S be the set of all students and let M be the set of all mathematics subjects.P : s S , m M , s likes m . P : ( s S , m M , s likes m ) s S , ( m M , s likes m ) s S , m M , (s likes m) s S , m M , s dislikes mUnfortunately, P is more likely to be false

WUCT121 Logic Tutorial Exercises Solutions 2 Section 1: Logic Question1 (i) If x 3, then x 2. (a) Statement (b) False (c) x 3 x 2 (ii) If x 0 or x 1, then x2 x. (a) Statement (b) True (c) (x 0 x 1) x2 x (iii) There exists a natural number x for which 2 2x. (a) Statement (b) False (iv) and If x x 0, then if x 1 then x 1.