Solution Manual for Introduction to Mathematical Thinking: Algebra and Number Systems, 1st Edition

Preview (16 of 450 Pages)

100%

Purchase to unlock

Loading page image...

Chapter 1 SolutionsAn Introduction to Mathematical Thinking:Algebra and Number SystemsWilliam J. Gilbert and Scott A. Vanstone, Prentice Hall, 2005Solutions prepared by William J. Gilbert and Alejandro MoralesExercise 1-1:Determine which of the following sentences are statements. What are the truthvalues of those that are statements?7>5Solution:It is a statement and it is true.Exercise 1-2:Determine which of the following sentences are statements. What are the truthvalues of those that are statements?5>7Solution:It is a statement and its truth value is FALSE.Exercise 1-3:Determine which of the following sentences are statements. What are the truthvalues of those that are statements?Is 5>7?Solution:It is not a statement because it is a question.Exercise 1-4:Determine which of the following sentences are statements. What are the truthvalues of those that are statements?√2 is an integer.Solution:This is a statement. It is false as there is no integer whose square is 2.Exercise 1-5:Determine which of the following sentences are statements. What are the truthvalues of those that are statements?1.1

Loading page image...

Show that√2 is not an integer.Solution:It is not a statement because the sentence does not have a truth value, it isa command.Exercise 1-6:Determine which of the following sentences are statements. What are the truthvalues of those that are statements?If 5 is even then 6 = 7.Solution:It is a statement and its truth value is TRUE.Exercise 1-7:Write down the truth tables for each expression. NOT(NOTP).Solution:PNOTPNOT(NOTP)TFTFTFExercise 1-8:Write down the truth tables for each expression. NOT(PORQ)Solution:PQPORQNOT (PORQ)TTTFTFTFFTTFFFFTExercise 1-9:Write down the truth tables for each expression.P=⇒(QORR)Solution:PQRQORRP=⇒(QORR)TTTTTTTFTTTFTTTTFFFFFTTTTFTFTTFFTTTFFFFT1.2

Loading page image...

Exercise 1-10:Write down the truth tables for each expression. (PANDQ) =⇒RSolution:PQRPANDQ(PANDQ) =⇒RTTTTTTTFTFTFTFTTFFFTFTTFTFTFFTFFTFTFFFFTExercise 1-11:Write down the truth tables for each expression. (POR NOTQ) =⇒R.Solution:PQRNOTQPOR (NOTQ)(POR NOTQ) =⇒RTTTFTTTTFFTFTFTTTTTFFTTFFTTFFTFTFFFTFFTTTTFFFTTFExercise 1-12:Write down the truth tables for each expression. NOTP=⇒(Q⇐⇒R).Solution:PQRQ⇐⇒RNOTP=⇒(Q⇐⇒R)TTTTTTTFFTTFTFTTFFTTFTTTTFTFFFFFTFFFFFTT1.3

Loading page image...

Exercise 1-13:PUNLESSQis defined as (NOTQ) =⇒P. Show that this statement has thesame truth table asPORQ. Give an example in common English showing theequivalence ofPUNLESSQandPORQ.Solution:DefiningPUNLESSQas (NOTQ) =⇒P, thenPQNOTQPUNLESSQPORQTTFTTTFTTTFTFTTFFTFFSince the last two columns are the same the statementPUNLESSQdefinedas (NOTQ) =⇒Pis equivalent toPORQ.“I will go unless I forget” and “I will go or I forget”.Exercise 1-14:Write down the truth table for theexclusive orconnective XOR, where thestatementPXORQmeans (PORQ) AND NOT (PANDQ). Show that thisis equivalent to NOT(P⇐⇒Q).Solution:PQPORQPANDQPXORQNOT(P⇐⇒Q)TTTTFFTFTFTTFTTFTTFFFFFFSince the last two columns are the same, the statements are equivalent.Exercise 1-15:Write down the truth table for thenot orconnective NOR, where the statementPNORQmeans NOT(PORQ).Solution:DefiningPNORQas NOT(PORQ), then the truth table for theN ORconnective isPQPORQPNORQTTTFTFTFFTTFFFFT1.4

Loading page image...

Exercise 1-16:Write down the truth table for thenot andconnective NAND, where the state-mentPNANDQmeans NOT(PANDQ).Solution:PQPANDQPNANDQTTTFTFFTFTFTFFFTExercise 1-17:Write each statement usingP,Q, and connectives.PwheneverQ.Solution:Q=⇒P.Exercise 1-18:Write each statement usingP,Q, and connectives.Pis necessary forQSolution:Q=⇒P.Exercise 1-19:Write each statement usingP,Q, and connectives.Pis sufficient forQ.Solution:P=⇒Q.Exercise 1-20:Write each statement usingP,Q, and connectives.Ponly ifQSolution:P=⇒Q.Exercise 1-21:Write each statement usingP,Q, and connectives.Pis necessary and sufficient forQ.Solution:P⇐⇒Q. Another equivalent answer isQ⇐⇒P.Exercise 1-22:Show that the statements NOT (PORQ) and (NOTP) AND (NOTQ) havethe same truth tables and give an example of the equivalence of these statementsin everyday language.Solution:1.5

Loading page image...

PQPORQNOT (PORQ)TTTFTFTFFTTFFFFTPQNOTPNOTQ(NOTP) AND (NOTQ)TTFFFTFFTFFTTFFFFTTTThe final columns of each table are the same, so the two statements havethe same truth tables.This equivalence can be illustrated in everyday language. Consider the state-ment “I do not want cabbage or broccoli”.This means that “I do not wantcabbage” and “I do not want broccoli”.Exercise 1-23:Show that the statementsPAND (QANDR) and (PANDQ) ANDRhavethe same truth tables. This is theassociative lawfor AND.Solution:PQRQANDRPAND (QANDR)TTTTTTTFFFTFTFFTFFFFFTTTFFTFFFFFTFFFFFFFPQRPANDQ(PANDQ) ANDRTTTTTTTFTFTFTFFTFFFFFTTFFFTFFFFFTFFFFFFFThe final columns of each table are equal, so the two statements have thesame truth tables.1.6

Loading page image...

Exercise 1-24:Show that the statementsPAND (QORR) and (PANDQ) OR (PANDR)have the same truth tables. This is adistributive law.Solution:PQRQORRPAND (QORR)TTTTTTTFTTTFTTTTFFFFFTTTFFTFTFFFTTFFFFFFPQRPANDQPANDR(PANDQ) OR (PANDR)TTTTTTTTFTFTTFTFTTTFFFFFFTTFFFFTFFFFFFTFFFFFFFFFThe final columns of each table are the same, so the two statements havethe same truth tables.Exercise 1-25:Is (PANDQ) =⇒Requivalent toP=⇒(Q=⇒R) ? Give reasons.Solution 1:Suppose (PANDQ) =⇒Ris false. ThenPANDQis true andRis false.Because bothPandQare true thenQ=⇒Ris false, and thusP=⇒(Q=⇒R)is also false.Now suppose thatP=⇒(Q=⇒R) is false. ThenPis true and (Q=⇒R)is false.This last statement implies thatQis true andRis false.ThereforePANDQis true, and (PANDQ) =⇒Ris false.We have shown that whenever one statement is false, then the other one isalso false. It follows that the statements are equivalent.Solution 2:1.7

Loading page image...

PQRPANDQ(PANDQ) =⇒RTTTTTTTFTFTFTFTTFFFTFTTFTFTFFTFFTFTFFFFTPQRQ=⇒RP=⇒(Q=⇒R)TTTTTTTFFFTFTTTTFFTTFTTTTFTFFTFFTTTFFFTTThe final columns of each table are the same, so the two statements havethe same truth tables, and the statements are equivalent.Exercise 1-26:LetPbe the statement ‘It is snowing’ and letQbe the statement ‘It is freezing.’Write each statement usingP,Q, and connectives.It is snowing, then it is freezingSolution:P=⇒Q.Exercise 1-27:LetPbe the statement ‘It is snowing’ and letQbe the statement ‘It is freezing.’Write each statement usingP,Q, and connectives.It is freezing but not snowing,Solution:QAND (NOTP).Exercise 1-28:LetPbe the statement ‘It is snowing’ and letQbe the statement ‘It is freezing.’Write each statement usingP,Q, and connectives.When it is not freezing, it is not snowing.Solution:NOTQ=⇒NOTP.1.8

Loading page image...

Exercise 1-29:LetPbe the statement ‘I can walk,’Qbe the statement ‘I have broken my leg’andRbe the statement ‘I take the bus.’ Express each statement as an Englishsentence.Q=⇒NOTP.Solution:It can be “If I have broken my leg then I cannot walk”.Exercise 1-30:LetPbe the statement ‘I can walk,’Qbe the statement ‘I have broken my leg’andRbe the statement ‘I take the bus.’ Express each statement as an Englishsentence.P⇐⇒NOTQSolution:It can be “I can walk if and only if I have not broken my leg”.Exercise 1-31:LetPbe the statement ‘I can walk’Qbe the statement ‘I have broken my leg’andRbe the statement ‘I take the bus.’ Express each statement as an Englishsentence.R=⇒(QOR NOTP)Solution:It can be “If I take the bus then I have broken my leg or I cannot walk”.Exercise 1-32:LetPbe the statement ‘I can walk,’Qbe the statement ‘I have broken my leg’andRbe the statement ‘I take the bus.’ Express each statement as an Englishsentence.R=⇒(Q⇐⇒NOTP)Solution:It can be “I take the bus only if I have broken my leg is equivalent to Icannot walk”.Exercise 1-33:Express each statement as a logical expression using quantifiers.State theuniverse of discourse.There is a smallest positive integer.Solution:If we assume that the universe of discourse is the set of integers, we canexpress the statement as∃x∀y,(0< x≤y).1.9

Loading page image...

Exercise 1-34:Express each statement as a logical expression using quantifiers.State theuniverse of discourse.There is no smallest positive real number.Solution:The universe of discourse is the set of all positive real numbers. The state-ment “there is no smallest positive real number” is equivalent to∀r∃x,(x < r).Exercise 1-35:Express each statement as a logical expression using quantifiers.State theuniverse of discourse.Every integer is the product of two integers.Solution:If we assume that the universe of discourse is the set of integers, we canexpress the statement as∀x∃y∃z(x=yz).Exercise 1-36:Express each statement as a logical expression using quantifiers.State theuniverse of discourse.Every pair of integers has a common divisor.Solution:The universe of discourse is the set of integers. The given statement is∀x∀y∃z,(zdividesxANDzdividesy).1.10

Loading page image...

Exercise 1-37:Express each statement as a logical expression using quantifiers.State theuniverse of discourse.There is a real numberxsuch that, for every real numbery,x3+x=y.Solution:If we assume that the universe of discourse is the set of real numbers, wecan express the statement as∃x∀y,(x3+x=y).Exercise 1-38:Express each statement as a logical expression using quantifiers.State theuniverse of discourse.For every real numbery, there is a real numberxsuch thatx3+x=y.Solution:If we assume that the universe of discourse is the set of real numbers, wecan express the statement as∀y∃x,(x3+x=y).Exercise 1-39:Express each statement as a logical expression using quantifiers.State theuniverse of discourse.The equationx2−2y2= 3 has an integer solution.Solution:If we assume that the universe of discourse is the set of integers, we canexpress the statement as∃x∃y,(x2−2y2= 3).Exercise 1-40:Express the following quote due to Abraham Lincoln as a logical expressionusing quantifiers: “You can fool some of the people all of the time, and all ofthe people some of the time, but you can not fool all of the people all of thetime.”Solution:Letxandtbe variables. Let the universe of discourse ofxto be the set ofall people, and the universe of discourse oftto be the set of all times. And LetF(x, t) stand for fooling a personxat timet.The quote from Abraham Lincoln can be expressed as∃x∀t, F(x, t) AND∀x∃t, F(x, t) AND NOT (∀x∀t, F(x, t)).1.11

Loading page image...

Exercise 1-41:Negate each expression, and simplify your answer.∀x,(P(x) ORQ(x))Solution:NOT [∀x,(P(x) ORQ(x))]∃x,NOT (P(x) ORQ(x))∃x,(NOTP(x)ANDNOTQ(x)).Exercise 1-42:Negate each expression, and simplify your answer.∀x,((P(x) ANDQ(x)) =⇒R(x)).Solution:UsingExample 1.23.,NOT (A=⇒B) is equivalent toAAND NOTB,we haveNOT∀x,[(P(x) ANDQ(x)) =⇒R(x)]∃x,NOT [(P(x) ANDQ(x)) =⇒R(x)]∃x,[(P(x) ANDQ(x)) AND NOTR(x)]Exercise 1-43:Negate each expression, and simplify your answer.∃x,(P(x) =⇒Q(x)).Solution:UsingExample 1.23.,NOT (A=⇒B) is equivalent toAAND NOTB,we haveNOT∃x(P(x) =⇒Q(x))∀x,NOT (P(x) =⇒Q(x))∀x,(P(x)ANDNOTQ(x)).Exercise 1-44:Negate each expression, and simplify your answer.∃x∀y,(P(x) ANDQ(y)).Solution:NOT∃x∀y,(P(x) ANDQ(y))]∀xNOT∀y,(P(x) ANDQ(y))∀x∃y,NOT (P(x) ANDQ(y))∀x∃y,(NOTP(x)) OR (NOTQ(y))Exercise 1-45:If the universe of discourse is the real numbers, what does each statement meanin English? Are they true or false?∀x∀y,(x≥y).Solution:Every real number is as large as any real number. This statement is false, ifyou letx= 1 andy= 2 then 1<2.1.12

Loading page image...

Exercise 1-46:If the universe of discourse is the real numbers, what does each statement meanin English? Are they true or false?∃x∃y,(x≥y).Solution:For some real number there is a real number that is less than or equal to it.This statement is always true because we can always takey=x/2Exercise 1-47:If the universe of discourse is the real numbers, what does each statement meanin English? Are they true or false?∃y∀x,(x≥y).Solution:There is a smallest real number. This statement is false, ifyis the smallestreal number and you letx=y−1 theny−1< y.Exercise 1-48:If the universe of discourse is the real numbers, what does each statement meanin English? Are they true or false?∀x∃y,(x≥y).Solution:For every real number there is a smaller or equal real number.This statement is true, if you lety=x/2 thenx≥x/2.Exercise 1-49:If the universe of discourse is the real numbers, what does each statement meanin English? Are they true or false?∀x∃y,(x2+y2= 1).Solution:For all real numbersxthere exists a real numberysuch thatx2+y2= 1.This statement is false, if you let|x|>1 then 1−x2<0 and for all realy,y2≥0, so there is no real numberysatisfying the equation.Exercise 1-50:If the universe of discourse is the real numbers, what does each statement meanin English? Are they true or false?∃y∀x,(x2+y2= 1).Solution:There exists a real numberysuch that for all real numbersx,x2+y2= 1.This statement is false, for everyylet|x|>1 thenx2>1 and becausey2>0 thenx2+y2>1.1.13

Loading page image...

Exercise 1-51:Determine whether each pair of statements is equivalent. Give reasons.∃x,(P(x) ORQ(x)).(∃x, P(x)) OR (∃x, Q(x)).Solution:These statements are equivalent.Suppose∃x,(P(x) ORQ(x)) is true.Hence∃x,,P(x) is true orQ(x) is true. We can assume that there exists anxsuch thatP(x) is true, therefore for that particularx, (∃x, P(x)) OR (∃x, Q(x))is true regardless of the value of∃x, Q(x). This also holds if∃x, Q(x) is true.Now suppose that (∃x, P(x)) OR (∃x, Q(x)) is true. Hence at least one of(∃x P(x)) or (∃x Q(x)) is true. Assume that there exists anxsuch thatP(x)is true, therefore for that particularx,P(x) ORQ(x) is true regardless of thevalue ofQ(x). So∃x,(P(x) ORQ(x)) is true. This also holds if (∃x, Q(x)) istrue.We have shown that whenever one of the statements is true, then the otherone is also true. Hence they are equivalent.Exercise 1-52:Determine whether each pair of statements is equivalent. Give reasons.∃x,(P(x) ANDQ(x)).(∃x P(x)) AND (∃x, Q(x)).Solution:These statements are not equivalent. Assume the universe of discourse is theset of real numbers. LetP(x) be the statementx >0 andQ(x) the statementx≤0. Then∃x,(P(x) ANDQ(x)) is false while (∃x, P(x)) AND (∃x, Q(x))is true. (It may not be the samexin both parts of the second statement!)Exercise 1-53:Determine whether each pair of statements is equivalent. Give reasons.∀x,(P(x) =⇒Q(x)).(∀x, P(x)) =⇒(∀x, Q(x)).Solution:These statements are not always equivalent. We can give a particular exam-ple in which they do not have the same meaning.Let the universe of discourse be the set of real numbers.LetP(x) be theexpressionx <0 andQ(x) be the expressionx2<0. Then for all real numbersx, ifx <0 thenx2>0 soP(x) =⇒Q(x) is false. However, (∀x, P(x)) is nottrue, and (∀x, Q(x)) is not true so (∀x, P(x)) =⇒(∀x, Q(x)) is true.Exercise 1-54:Determine whether each pair of statements is equivalent. Give reasons.∀x,(P(x) ORQ(y)).(∀x, P(x)) ORQ(y).Solution:These statements are equivalent. Because the variablexdoes not occur inQ(y), this statement does not depend on the quantifiers ofx, it depends onlyon the particular choice ofy.1.14

Loading page image...

Therefore, the statement∀x,(P(x) ORQ(y)) is true when∀x, P(x) is trueor whenQ(y) is true. This is exactly the second statement.Exercise 1-55:Write the contrapositive, and the converse of each statement.If Tom goes to the party then I will go to the party.Solution:Contrapositive:If I don’t go to the party the Tom will not go to the party.Converse:If I go to the party then Tom will go to the party.Exercise 1-56:Write the contrapositive, and the converse of each statement.If I do my assignments then I get a good mark in the course.Solution:Contrapositive:If I do not get a good mark in the course then I do not do myassignments.Converse:If I get a good mark in the course then I do my assignments.Exercise 1-57:Write the contrapositive, and the converse of each statement.Ifx >3 thenx2>9.Solution:Contrapositive:Ifx2≤9 thenx≤3.Converse:Ifx2>9 thenx >3.Exercise 1-58:Write the contrapositive, and the converse of each statement.Ifx <−3 thenx2>9.Solution:Contrapositive:Ifx2≤9 thenx≥ −3.Converse:Ifx2>9 thenx <−3.Exercise 1-59:Write the contrapositive, and the converse of each statement.If an integer is divisible by 2 then it is not prime.Solution:Contrapositive:If an integer is a prime then it is not divisible by 2.Converse:If an integer is not prime then it is divisible by 2.Exercise 1-60:Write the contrapositive, and the converse of each statement.Ifx≥0 andy≥0 thenxy≥0.Solution:Contrapositive:Ifxy <0 thenx <0 ory <0.Converse:Ifxy≥0 thenx≥0 andy≥0.Exercise 1-61:Write the contrapositive, and the converse of each statement.Ifx2+y2= 9 then−3≤x≤3.Solution:1.15

Preview Mode

This document has 450 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

AP Calculus AB Scoring Guide Unit 6 Progress Check

Clinical Psychologist

Module 4 Matrices

MATH 1324 Homework 5 Answers

Ap progress 1 5 all 5

The Fundamental Theorem of Calculus and Definite I

AP Calculus AB Scoring Guide

Investigating the Rising Cost of MTA Transit Fare

Module 11 Geometry

AP Calculus AB Unit 5 Progress Check Scoring Guide

Company

Explore

Study Tools