Solved: a) Describe what is meant by a direct proof, a

a) Define the negation of a proposition. b) What is the negation of "This is a boring course"?

a) Define (using truth tables) the disjunction, conjunction, exclusive or, conditional, and biconditional of the propositions p and q. b) What are the disjunction, conjunction, exclusive or, conditional, and biconditional ofthe propositions "I'll go to the movies tonight" and "I'll finish my discrete mathematics homework"?

a) Describe at least five different ways to write the conditional statement p q in English. b) Define the converse and contrapositive of a conditional statement. c) State the converse and the contrapositive of the conditional statement "If it is sunny tomorrow, then I will go for a walk in the woods."

a) What does it mean for two propositions to be logically equivalent? b) Describe the different ways to show that two compound propositions are logically equivalent. c) Show in at least two different ways that the compound propositions P v (r -+ q) and P v q V r are equivalent.

(Depends on the Exercise Set in Section 1.2) a) Given a truth table, explain how to use disjunctive normal form to construct a compound proposition with this truth table. b) Explain why part (a) shows that the operators /\, v, and are functionally complete. c) Is there an operator such that the set containing just this operator is functionally complete?

What are the universal and existential quantifications of a predicate P(x)? What are their negations?

a) What is the difference between the quantification 3xVyP(x , y) and Vy3xP(x , y), where P(x , y) is a predicate? b) Give an example of a predicate P (x, y) such that 3xVyP(x, y) and Vy3xP (x, y) have different truth values.

Describe what is meant by a valid argument in propositional logic and show that the argument "If the earth is flat, then you can sail off the edge of the earth," "You cannot sail off the edge of the earth," therefore, "The earth is not flat" is a valid argument.

Use rules of inference to show that if the premises "All zebras have stripes" and "Mark is a zebra" are true, then the conclusion "Mark has stripes" is true.

a) Describe what is meant by a direct proof, a proof by contraposition, and a proof by contradiction of a conditional statement P -+ q. b) Give a direct proof, a proof by contraposition and a proof by contradiction of the statement: "If n is even, then n + 4 is even."

a) Describe a way to prove the biconditional P # q. b) Prove the statement: "The integer 3n + 2 is odd if and only if the integer 9n + 5 is even, where n is an integer."

To prove that the statements PI , P2, P3, and P4 are equivalent, is it sufficient to show that the conditional statements P4 -+ P2, P3 -+ PI , and PI -+ P2 are valid? If not, provide another set of conditional statements that can be used to show that the four statements are equivalent.

a) Suppose that a statement ofthe form VxP(x) is false. How can this be proved? b) Show that the statement "For every positive integer n, n 2 ::: 2n" is false.

What is the difference between a constructive and nonconstructive existence proof? Give an example of each.

What are the elements of a proof that there is a unique element x such that P(x), where P(x) is a propositional function?

Explain how a proof by cases can be used to prove a result about absolute values, such as the fact that Ixyl = Ix l lyl for all real numbers x and y.

Let P be the proposition "I will do every exercise in this book" and q be the proposition "I will get an ''I>:' in this course." Express each of these as a combination of P and q. a) I will get an "Pl' in this course only if ! do every exercise in this book. b) I will get an "Pl' in this course and I will do every exercise in this book: c) Either I will not get an "Pl' 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.

Find the truth table of the compound proposition (p v q) -+ (p /\ r).

Show that these compound propositions are tautologies. a) (q /\ (p -+ q -+ P b) p v q)/\p) -+ q

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 lx l = x, then x ::: O. c) If n is greater than 3, then n 2 is greater than 9.

Given a conditional statement P -+ q, find the converse of its inverse, the converse of its converse, and the converse of its contrapositive.

Given a conditional statement p -+ q, find the inverse of its inverse, the inverse of its converse, and the inverse of its contrapositive.

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.

Show that these statements are inconsistent: "If Sergei takes the job offer then he will get a signing bonus." "If Sergei takes the job offer, then he will receive a higher salary." "If Sergei gets a signing bonus, then he will not receive a higher salary." "Sergei takes the job offer."

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 you meet three people, A, B, and C, on the island of knights and knaves described in Example 18 in Section 1.1. What are A, B, and C if A says "I am a knave and B is a knight" and B says "Exactly one of the three of us is a knight"?

(Adapted from [Sm78]) Suppose that on an island there are three types of people, knights, knaves, and normals. 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 ofthe three committed the crime, but not which one. They also knew that the criminal was a knight, and that the other two were not. 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?

Show that if S is a proposition, where 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 Lob s paradox.)

Show that the argument with premises "The tooth fairy is a real person" and "The truth 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?

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 ofthese 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 knows calculus. d) Every student in every class knows calculus. e) There is at least one class with no students who know calculus.

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 = km for some integer k.) Determine the truth values of each of these statements. a) P(4, 5) c) "1m "In P(m , n) e) 3n "1m P(m , n) b) P(2, 4) d) 3m "In P (m, n) 1) Vn P(I , n)

Find a domain for the quantifiers in 3x3y(x =1= y 1\ Vzz =1= x) 1\ (z =1= y such that this statement is true.

Find a domain for the quantifiers in 3x3y(x =1= y 1\ Vz z = x) V (z = y ) such that this statement is false

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."

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 3n denotes "there exists exactly n ," so that 3nx P (x) means there exist exactly n values in the domain such that P (x) is true. Determine the true value of these statement where the domain consists of all real numbers. a) 30x(x z = -1) c) 3zx(x z = 2) b) 3\x(lx l = 0) d) 3 3 x(x = Ix I)

Express each of these statements using existential and universal quantifiers and propositional logic where 3n is defined in Exercise 20. a) 30xP(x) b) 3\xP(x) c) 3zxP(x) d) 3 3 XP (X)

Let P (x, y) be a propositional function. Show that 3x Vy P (x , y) --+ Vy 3x P (x , y) is a tautology.

Let P (x) and Q(x) be propositional functions. Show that 3x (P(x) --+ Q(x and "Ix P (x) --+ 3x Q(x) always have the same truth value.

If Vy 3x P (x , y) is true, does it necessarily follow that 3x Vy P (x , y) is true?

If "Ix 3y P (x , y) is true, does it necessarily follow that 3x Vy P(x , y) is true?

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.

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

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."

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.

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.

Use rules of inference to show that if the premises Vx(P(x) --+ Q(x , Vx(Q(x) --+ R(x , and -.R(a), where a is in the domain, are true, then the conclusion -'P (a) is true.

Prove that if x3 is irrational, then x is irrational.

Prove that if x is irrational and x 0, then .jX is irrational.

Prove that given a nonnegative integer n, there is a unique nonnegative integer m such that m2 n < (m + 1) 2

Prove that there exists an integer m such that m 2 > 10 1 000 . Is your proof constructive or nonconstructive?

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.)

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

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

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

Assuming the truth of the theorem that states that ...;n is irrational whenever n is a positive integer that is not a perfect square, prove that ..fi + .../3 is irrational

Given the truth values of the propositions p and q, find the truth values of the conjunction, disjunction, exclusive or, conditional statement, and biconditional of these propositions.

Given two bit strings of length n, find the bitwise AND, bitwise OR, and bitwise XOR of these strings

Given the truth values of the propositions p and q in fuzzy logic, find the truth value of the disjunction and the conjunction of p and q (see Exercises 40 and 41 of Section 1 . 1 ).

Given positive integers m and n, interactively play the game of Chomp.

Given a portion of a checkerboard, look for tilings of this checkerboard with various types of pol yomi noes, including dominoes, the two types oftriominoes, and larger polyominoes.

Look for positive integers that are not the sum of the cubes of nine different positive integers.

Look for positive integers greater than 79 that are not the sum of the fourth powers of 18 positive integers.

Find as many positive integers as you can that can be written as the sum of cubes of positive integers, in two different ways, sharing this property with 1 729.

Try to find winning strategies for the game of Chomp for different initial configurations of cookies.

Look for tilings of checkerboards and parts of checkerboards with polynominoes.

Discuss logical paradoxes, including the paradox of Epimenides the Cretan, Jourdain's card paradox, and the barber paradox, and how they are resolved.

Describe how fuzzy logic is being applied to practical applications. Consult one or more of the recent books on fuzzy logic written for general audiences.

Describe the basic rules of WFF'N PROOF, The Game of Modern Logic, developed by Layman Allen. Give examples of some of the games included in WFF'N PROOF.

Read some of the writings of Lewis Carroll on symbolic logic. Describe in detail some of the models he used to represent logical arguments and the rules of inference he used in these arguments.

Extend the discussion of Prolog given in Section 1 .3, explaining in more depth how Prolog employs resolution.

Discuss some of the techniques used in computational logic, including Skolem's rule.

Automated theorem proving" is the task of using computers to mechanically prove theorems. Discuss the goals and applications of automated theorem proving and the progress made in developing automated theorem provers.

Describe how DNA computing has been used to solve instances of the satisfiability problem.

Discuss what is known about winning strategies in the game of Chomp.

Describe various aspects of proof strategy discussed by George P6lya in his writings on reasoning, including [P062], [P07 1], and [P090].

Describe a few problems and results about tilings with polyominoes, as described in [G094] and [Ma91], for example.