Let P(x) be the statement "Student x knows calculus" and

Problem 2E Find the truth table of the compound proposition (p ?q)?(p?¬r).

Problem 3E Show that these compound propositions are tautologies.

Problem 1E Let p be the proposition "I will do every exercise in this book" and q be the proposition "I will get an "A" in this course." Express each of these as a combination of P and q. a) I will get an "A" in this course only if I do every exercise in this book. ________________ b) I will get an "A" in this course and I will do every exercise in this book. ________________ c) Either I will not gel an "A" in this course or I will not do every exercise in this book. ________________ d) For me to get an "A" in this course it is necessary and sufficient that I do every exercise in this book.

Problem 4E Give the converse, the contrapositive, and the inverse of these conditional statements. a) If it rains today, then I will drive to work. ________________ b) If |x|=x, then x ? 0. ________________ c) If n is greater than 3, then n2 is greater than 9.

Problem 5E Given a conditional statement p ? q, find the converse of its inverse, the converse of its converse, and the converse of its contrapositive.

Problem 6E Given a conditional statement p? q, find the inverse of its inverse, the inverse of its converse, and the inverse of its contrapositive.

Problem 7E Find a compound proposition involving the propositional variables p,q,r, and s that is true when exactly three of these propositional variables are true and is false otherwise.

Problem 8E Show that these statements are inconsistent: "If Sergei lakes the job offer then be will get a signing bonus." "If Sergei takes the job offer, then he will receive a higher salary." "If Sergei gels a signing bonus, then he will not receive a higher salary." "Sergei takes the job offer."

Problem 10E Suppose that in a three-round obligato game, the teacher first gives the student the proposition p ?q. then the proposition ¬( p ? r) ? q, and finally the proposition q. For which of the eight possible sequences of three answers will the student pass the test?

Problem 9E Show that these statements are inconsistent: "If Miranda does not take a course in discrete mathematics, then she will not graduate." " If Miranda does not graduate, then she is not qualified for the job." "If Miranda reads this book, then she is qualified for the job." "Miranda does not take a course in discrete mathematics but she reads this book."

Suppose that in a four-round obligato game, the teacher first gives the student the proposition \(\neg(p \rightarrow(q \wedge r))\), then the proposition \(p \vee \neg q\), then the proposition \(\neg r\), and finally, the proposition \((p \wedge r) \vee(q \rightarrow p)\). For which of the 16 possible sequences of four answers will the student pass the test? Equation Transcription: Text Transcription: Neg (p right arrow (q wedge r)) P vee neg q Neg r (p wedge r) vee (q right arrow p)

Problem 13E Suppose that you meet three people Aaron, Bohan, and Crystal. Can you determine what Aaron, Bohan, and Crystal are if Aaron says "All of us are knaves" and Bohan says "Exactly one of us is a knave."?

Problem 15E (Adapted from [Sm78]) Suppose that on an island there are three types of people, knights, knaves, and normals (also known as spies). Knights always tell the truth, knaves always lie, and normals sometimes lie and sometimes tell the truth. Detectives questioned three inhabitants of the island—Amy, Brenda. and Claire—as part of the investigation of a crime. The detectives knew that one of the three committed the crime, but not which one. They also knew that the criminal was a knight, and that the other two were nol. Additionally, the detectives recorded these statements: Amy: "I am innocent." Brenda: "What Amy says is true." Claire: " Brenda is not a normal." After analyzing their information, the detectives positively identified the guilty party. Who was it?

Problem 14E Suppose that you meet three people, Anita, Boris, and Carmen. What are Anila, Boris, and Carmen if Anila says "I am a knave and Boris is a knight" and Boris says "Exactly one of the three of us is a knight"?

Problem 16E Show that if S is a proposition, w here S is the conditional statement "If S is true. then unicorns live," then "Unicorns live' is true. Show that it follows that S cannot be a proposition. (This paradox is known as LÖb's paradox.)

Let \(P(m, n)\) be the statement " \(m\) divides \(n\)," where the domain for both variables consists of all positive integers. (By " \(m\) divides \(n\) " we mean that \(n=k m\) for some integer k.) Determine the truth values of each of these statements. a) \(P(4,5)\) b) \(P(2,4)\) c) \(\forall m \forall n P(m, n)\) d) \(\exists m \forall n P(m, n)\) e) \(\exists n \forall m P(m, n)\) f) \(\forall n P(1, n)\) Equation Transcription: Text Transcription: P(m,n) m n n=km P(4,5) P(2,4) Forall m forall nP(m,n) Exists m forall nP(m,n) Exists n forall mP(m,n) forall nP(1,n)

Problem 20E Let P(x) be the statement "Student x knows calculus" and let Q(y) be the statement "Class y contains a student who knows calculus." Express each of these as quantifications of P(x) and Q(y). a) Some students know calculus. ________________ b) Not every student knows calculus. ________________ c) Every class has a student in it who know s calculus. ________________ d) Every student in every class knows calculus. ________________ e) There is at least one class with no students who know calculus.

Problem 17E Show that the argument with premises "The tooth fairy is a real person" and "The tooth fairy is not a real person" and conclusion "You can find. gold at the end of the rainbow" is a valid argument. Does this show that the conclusion is true?

Problem 25E Use existential and universal quantifiers to express the statement '"Everyone has exactly two biological parents" using the propositional function P(x,y), which represents "x is the biological parent of y."

The quantifier \(\exists_{n}\) denotes "there exists exactly \(n\)," so that \(\exists_{n} x P(x)\) means there exist exactly \(n\) values in the domain such that \(P(x)\) is true. Determine the true value of these statements where the domain consists of all real numbers. a) \(\exists_{0} x\left(x^{2}=-1\right)\) b) \(\exists_{1} x(|x|=0)\) c) \(\exists_{2} x\left(x^{2}=2\right)\) d) \(\exists_{3} x(x=|x|)\) Equation Transcription: Text Transcription: Exists n n Exists_n x P(x) P(x) exists_0x (x^2 = -1) exists_1x (|x| = 0) Exists_2 x (x^2 = 2) Exists_3 x (x =|x|)

Problem 27E Express each of these statements using existential and universal quantifiers and propositional logic where ?n is defined in Exercise 26.

Problem 28E Let P(x, y) be a propositional function. Show that is a tautology.

Let \(P(x)\) and \(Q(x)\) be propositional functions. Show that \(\exists x(P(x) \rightarrow Q(x))\) and \(\forall x P(x) \rightarrow \exists x Q(x)\) always have the same truth value. Equation Transcription: i Text Transcription: P(x) Q(x) Exists x (P(x) right arrow Q(x)) x P(x) right arrow Exists x Q(x)

Problem 32E Find the negations of these statements. a) If it snows today, then I will go skiing tomorrow. ________________ b) Every person in this class understands mathematical induction. ________________ c) Some students in this class do not like discrete mathematics. ________________ d) In every mathematics class there is some student who falls asleep during lectures.

Problem 33E Express this Statement using quantifiers: "Every student in this class has taken some course in every department in the school of mathematical sciences."

Problem 34E Express this statement using quantifiers: 'There is a building on the campus of some college in the United States in which every room is painted white."

Problem 35E Express the Statement "There is exactly one student in this class who has taken exactly one mathematics class at this school" using the uniqueness quantifier. Then express this statement using quantifiers, without using the uniqueness quantifier.

Problem 41E Prove that there exists an integer m such that m2 > 101000 .Is your proof constructive or nonconstructive?

Problem 40E Prove that given a nonnegative integer", there is a unique nonnegative integer m such that

Problem 42E Prove that there is a positive integer that can be written as the sum of squares of positive integers in two different ways. (Use a computer or calculator to speed up your work.)

Problem 43E Disprove the statement that every positive integer is the sum of the cubes of eight nonnegative integers.

Problem 44E Disprove the statement that every positive integer is the sum of at most two squares and a cube of nonnegative integers.

Problem 45E Disprove the statement that every positive integer is the sum of 36 fifth powers of nonnegative integers.

Suppose that the truth value of the proposition \(p_{i}\) is \(\mathbf{T}\) whenever \(i\) is an odd positive integer and is \(\mathbf{F}\) whenever \(i\) is an even positive integer. Find the truth values of \(\bigvee_{i=1}^{100}\left(p_{i} \wedge p_{i+1}\right)\) and \(\bigwedge_{i=1}^{100}\left(p_{i} \vee p_{i+1}\right)\). Equation Transcription: Text Transcription: pi i bigvee_i=1^100(pi wedge pi+1) Bigwedge i=1^100(pi vee pi+1)

Problem 46E Assuming the truth of the theorem that stales that is irrational whenever n is a positive integer that is not a perfect square, prove that is irrational.

Problem 12E Explain why every obligato game has a winning strategy.Exercises 13 and 14 are set on the island of knights and knaves described in Example ? in Section 1.2.

Problem 19E Model 16 ×16 Sudoku puzzles (with 4×4 blocks) as satisfiability problems.

Find a domain for the quantifiers in \(\exists x \exists y(x \neq y \wedge\) \(\forall z((z=x) \vee(z=y)))\) such that this statement is false. Equation Transcription: Text Transcription: Neg (p right arrow (q wedge r)) P vee q Neg r (p wedge r) vee (q right arrow p)

Find a domain for the quantifiers in \(\exists x \exists y(x \neq y \wedge\) \(\forall z((z=x) \vee(z=y)))\) such that this statement is true. Equation Transcription: Text Transcription: Exists x exists y(x not = y wedge Forall z((z=x) vee (z=y)))

Problem 24E Use existential and universal quantifiers to express the statement "No one has more than three grandmothers" using the propositional function G(x,y). which represents "x is the grandmother of y."

Problem 30E If is true, does it necessarily follow that is true?

Problem 31E If is true, docs it necessarily follow that is true?

Problem 38E Prove that if x2 is irrational, then x is irrational.

Prove that if \(x\) is irrational and \(x \geq 0\), then \(\sqrt{x}\) is irrational. Equation Transcription: Text Transcription: x X > or = 0 Sqrt x

Problem 36E Describe a rule of inference that can be used to prove that there are exactly two elements x and y in a domain such that P(x) and P(y) are true. Express this rule of inference as a statement in English.

Problem 37E Use rules of inference lo show that if the premises and ¬R(a), where a is in the domain, are true, then the conclusion ¬P(a) is true.