Solutions To Mathematics Textbooks/Proofs and Fundamentals/Chapter 1

Exercise 1.2.1

Statements: 4. "The U.S. has 49 States"

Non-statements: 1. "Today is a nice day" → Opinion 2. "Go to sleep" → Command, order 3. "Is it going to snow tomorrow?" → Question 5. I like to eat fruit, and you often think about traveling to Spain. 6. If we go tonight the babysitter will be unhappy. 7. "Call me on Thursday if you are home" → Command, order

Exercise 1.2.2

1

$4<3$ → This is a statement. It is asserting that 4 is less than 3. This is false, so this is a false statement.

2

If $x\geq 2$ then $x^{3}>1$ → Note that this is not a simple statement. It is a compound statement, so to say, where there is a premise, and a consequence. The premise is the statement $x\geq 2$: x is greater or equal to two. The consequence statement is $x^{3}>1$: x cubed is greater than one. The compound statement as a whole basically says that given the premise ($x\geq 2$) we will have the consequence ($x\geq 2$). This kind of statement is explained later in the book.

3

$y<7$ → This is a statement, but its truth or falsity depends upon the value of y. If y take a number smaller than 7, then the statement is true; if y takes a value greater or equal to 7, then the statement becomes false.

4

$x+y=z$ → This is a statement, but again, the truth or falsity of the statement depends upon the values of x, y and z. For example, x = 4, y = 3 and z = 7 make the statement true.

5

$(a+b)^{2}=a^{2}+2ab+b^{2}$ → This is a statement. You may have seen it before in an algebra course. We can actually show that this is true no matter what the values of a and b are, expanding the square $(a+b)^{2}$. This can be considered a proof, a concept that is shown later in the book.

6

$a^{2}+b^{2}=c^{2}$ → This is a statement, you may have seen it before as the pythagorean theorem, describing the relationships between the legs (a and b) and the hypothenuse (c) of a right triangle. It can be proven that this is always true for right triangles. In other contexts, its truth value depends on the values of a, b,

7

If $w=3$ then $z^{w}\neq 0$ → This is a compound statement like the one in (2), asserting that if w has a value of three, then rasing z to the wth power results in a value different to zero. Again, this depends on the value of z, but for some sets of numbers it can be shown that this is always true, but later in the book this is explained with greater care.

Exercise 1.2.3

1

$P\land Q$ → I like fruit and I don't like cereal.

2

$Q\lor R$ → I don't like cereal or I know how to cook an omelette (Note, this also implies "I don't like cereal and I know how to cook an omelette", an important mathematical distinction lost in the English language).

3

$\neg R$ → It is not the case that I know how to cook an omelette. (You can say I don't know how to cook an omelette, but depending on the context it is important to distinguish the negation from the statement).

4

$\neg (P\lor Q)$ → It is not the case that I like fruit or I don't like cereal (This can be confused with the statement $\neg P\lor Q$. This one can be distinguished using punctuation, like: It is not the case that I like fruit, or I don't like cereal. Here the coma separates the statement $\neg P$ from $Q$). Another option is "It is not the case that I like fruit and it is not the case that I don't like cereal," according to DeMorgan's Laws.

5

$\neg P\lor \neg Q$ → I don't like fruit or I like cereal (Here we directly incorporate the negation into the statement to make it shorter).

6

$\neg P\lor Q$ → I don't like fruit or I don't like cereal.

7

$(R\land P)\lor Q$ → I know how to cook an omelette and I like fruit, or I don't like cereal.

8

$R\land (P\lor Q)$ → I know how to cook an omelette, and I like fruit or I don't like cereal.

Exercise 1.2.4

In this exercise we use various forms of writing the conditional statements. Some of them might not be clear at first, so review those forms in the book. In common situations there are many ways of stating a conditional, and usually people are not rigorous about the language and rely on context to attain a good understanding of what is being said. In mathematics the language is very important, so you have to be very careful and try to eliminate any ambiguity.

1

$Z\rightarrow X$ → If I am eating spaghetti then I am happy.

2

$X\leftrightarrow Y$ → I am happy if and only if I am watching a movie.

3

$(Y\lor Z)\rightarrow X$ →if I am watching a movie or eating spaghetti then I am happy.

4

$Y\lor (Z\rightarrow X)$ → I am watching a movie, or if I am eating spaghetti I am happy.

5

$(Y\rightarrow \neg X)\land (Z\rightarrow \neg X)$ → I'm not happy provided that I am watching a movie, and assuming that I am eating spaghetti, then I'm not happy.

6

$(X\land \neg Y)\leftrightarrow (Y\lor Z)$ → I'm happy and I'm not watching a movie if and only if I'm watching a movie or eating spaghetti.

Exercise 1.2.5

1

Fred does not like to eat figs. → $\neg R$.

2

Fred has red hair, and does not have a big nose. → $X\land \neg Y$.

3

Fred has red hair or he likes to eat figs. → $X\lor R$.

4

Fred likes to eat figs, and he has red hair or he has a big nose. → $R\land (X\lor Y)$.

5

Fred likes to eat figs and he has read hair, or he has a big nose. → $(R\land X)\lor Y$.

6

It is not the case that Fred has a big nose or he has red hair. → $\neg (Y\lor X)$.

7

It is not the case that Fred has a big nose, or he has red hair. → $\neg Y\lor X$.

8

Fred has a big nose and red hair, or he has a big nose and likes to eat figs. → $(Y\land X)\lor (Y\land R)$.

Exercise 1.2.6

1

If the house is 30 years old, then it is ugly. → $F\rightarrow G$.

2

If the house is blue, then it is ugly or it is 30 years old. → $E\rightarrow (G\lor F)$.

3

If the house is blue then it is ugly, or it is 30 years old. → $(E\rightarrow G)\lor F$ (We put the consequence statement in parenthesis to clarify to leave out any ambiguities. Sometimes it is assumed that the implication takes precedence over other logic operators other than the biconditional, so that you can drop some parenthesis from statements. But it is better to use parenthesis to eliminate any ambiguity that can arise).

4

The house is not ugly if and only if it is 30 years old. → $\neg G\leftrightarrow F$.

5

The house is 30 years old if it is blue, and it is not ugly if it is 30 years old. → $(E\rightarrow F)\land (F\rightarrow \neg G)$.

6

For the house to be ugly, it is necessary and sufficient that it be ugly and 30 years old. → Remember that when we have the expression "necessary and sufficient" we are referring to a biconditional statement, hence: $G\leftrightarrow (G\land F)$.

Exercise 1.2.7

1

$A\lor C$ → Since A is true, then it doesn't matter the truth value of C, the disjunction (OR) statement is true.

2

$(C\land D)\lor B$ → C is false, then no matter the truth values of D, the conjunction (AND) statement will be false. And since the truth value of B is also false, then the OR statement will be false.

3

$\neg (A\land B)$ → B is false, so the AND statement is false. But then comes the negation of the AND statement, so the whole statement would be true.

4

$\neg D\lor \neg C$ → C is false, but with the negation it becomes true. That makes the whole OR statement true.

5

$(D\land A)\lor (B\land C)$ → A is true, so the left AND statement is also true. Therefore, the whole OR statement is true.

6

$C\lor [D\lor (A\land B)]$ → Since D is true, then (we don't need to worry about the AND statement) the inner OR statement is true and subsequently the outer OR statement is true.

Exercise 1.2.8

1

$Z\rightarrow Y$ → Since the antecedent (Z) is false, then the statement is true (a false antecedent means the conditional is true no matter what the truth value of the consequence is).

2

$X\leftrightarrow Z$ → The principle value of both statement X and Z is the same (false) so the statement is true.

3

$(Y\leftrightarrow W)\land X$ → X has truth value false, therefore the whole statement is false.

4

$W\rightarrow (X\rightarrow \neg W)$ → In the inner conditional, we have a false antecedent (X), so the conditional is true. Then the outer conditional is true because the antecedent (W) and the consequnce (the inner conditional) are both true.

5

$[(Y\rightarrow W)\leftrightarrow W]\land \neg X$ → The inner conditional in the left hand of the AND operator is true, because both Y and W are true. The equivalence then is also true, so the entire left hand side of the AND operator is true . As the X is negated, that makes the right hand side of the AND operator true, hence the whole statement is true.

6

$(W\rightarrow X)\leftrightarrow \neg (Z\lor Y)$. → The left hand side of the equivalence is false since W is a true antecedent and X is a false consequence. The right hand side of the equivalence is also false, because Y being true makes the OR part true, but the negation changes the truth value, so it is false. We have then: left hand side false and right hand side false, making the equivalence true.

Exercise 1.2.9

Let X = "Flora likes fruit", Y = "Flora doesn't like carrots", Z = "Flora likes nuts", W = "Flora doesn't like rutabags". We assume all this statements are true, and its negations are obviously false.

1

Flora likes fruit and carrots → $X\land \neg Y$. The negation of the Y statement is false, so the whole statement is false.

2

Flora likes nuts or rutabags, and she does not like carrots. → $(Z\lor \neg W)\land Y$. Z has a truth value of true, so the OR part is true. Now, Y is true, so the AND part is true.

3

Flora likes carrots, or she likes fruits and nuts. → $\neg Y\lor (X\land Z)$. Both X and Z are true, so the AND statement is true, and subsequently the OR statement is true.

4

Flora likes fruits or nuts, and she likes carrots or rutabags. → $(X\lor Z)\land (\neg Y\lor \neg W)$. Since Y and W are both negated, both are false and the right OR statement becomes false. That is enough to make the whole statement false.

5

Flora likes rutabags, or she likes fruit and either carrots or rutabags. → $\neg W\lor (X\land (\neg Y\lor \neg W))$. The inner OR is false, because both Y and W are negated, so they are both false. Therefore, the AND statement becomes false, and that makes the right hand side of the outer OR false. The left hand side of the OR is false (negation of W, a true statement). As both sides are false, the whole statement is false.

Exercise 1.2.10

Let X = "Hector likes beans", Y = "Hector doesn't like peas", Z = "Hector doesn't like lentils", W = "Hector likes sunflower seeds". It is assumed that all statements are true, so their negations are false.

1

If Hector likes beans, then he likes lentils. → $X\rightarrow \neg Z$. Since there is a true antecedent (X) with a false consequence (negation of Z), the statement is false.

2

Hector likes lentils if and only if he likes peas. → $\neg Z\leftrightarrow \neg Y$. Since both Z and Y have the same truth value (false), the equivalence statement is true.

3

Hector likes sunflower seeds, and if he likes lentils then he likes beans. → $W\land (\neg Z\rightarrow X)$. The consequence in the right hand side of AND is true, since it has a false antecedent (negation of Z). The left hand side is true, so the whole statement is true.

4

Hector likes peas and sunflower seeds if he likes beans. → $X\rightarrow (\neg Y\land W)$. The AND statement is false because Y is negated. Having a true antecedent (X) and a false consequence (the AND statement), this whole statement is false.

5

If Hector likes lentils then he likes sunflower seeds, or Hector likes lentils if and only if he likes peas. → $(\neg Z\rightarrow W)\lor (\neg Z\leftrightarrow \neg Y)$. In the right hand side, both Y and Z are negated, so both are false, and since their truth value is the same, the equivalence is true. Therefore, the OR statement is true.

6

For Hector to like beans and lentils it is necessary and sufficient for him to like peas or sunflower seeds. → $(X\land \neg Z)\leftrightarrow (\neg Y\lor W)$. The left hand side of the equivalence is false, because there is a false statement in AND (the negation of Z). In the right hand side, since there is a true statement (W) in the OR, then the right hand side is true. But the sides of the equivalence differ in truth values, so the whole statement is ultimately false.

Exercise 1.2.11

1

$P\land \neg Q$ → ${\begin{array}{c | c | c | c }P&Q&\neg Q&P\land \neg Q\\\hline T&T&F&F\\T&F&T&T\\F&T&F&F\\F&F&T&F\\\end{array}}$

2

$(R\lor S)\land \neg R$ → ${\begin{array}{c | c | c | c | c}R&S&\neg R&R\lor S&(R\lor S)\land \neg R\\\hline T&T&F&T&F\\T&F&F&T&F\\F&T&T&T&T\\F&F&T&F&F\\\end{array}}$

3

$X\lor (\neg Y\lor Z)$ → ${\begin{array}{c | c | c | c | c | c}X&Y&Z&\neg Y&\neg Y\lor Z&X\lor (\neg Y\lor Z)\\\hline T&T&T&F&T&T\\T&T&F&F&F&T\\T&F&T&T&T&T\\T&F&F&T&T&T\\F&T&T&F&T&T\\F&T&F&F&F&F\\F&F&T&T&T&T\\F&F&F&T&T&T\\\end{array}}$

4

$(A\lor B)\land (A\lor C)$ → ${\begin{array}{c | c | c | c | c | c}A&B&C&(A\lor B)&(A\lor C)&(A\lor B)\land (A\lor C)\\\hline T&T&T&T&T&T\\T&T&F&T&T&T\\T&F&T&T&T&T\\T&F&F&T&T&T\\F&T&T&T&T&T\\F&T&F&T&F&F\\F&F&T&F&T&F\\F&F&F&F&F&F\\\end{array}}$

5

$(P\land R)\lor \neg (Q\land S)$ → ${\begin{array}{c | c | c | c | c | c | c | c}P&Q&R&S&(P\land R)&(Q\land S)&\neg (Q\land S)&(P\land R)\lor \neg (Q\land S)\\\hline T&T&T&T&T&T&F&T\\T&T&T&F&T&F&T&T\\T&T&F&T&F&T&F&F\\T&T&F&F&F&F&T&T\\T&F&T&T&T&F&T&T\\T&F&T&F&T&F&T&T\\T&F&F&T&F&F&T&T\\T&F&F&F&F&F&T&T\\F&T&T&T&F&T&F&F\\F&T&T&F&F&F&T&T\\F&T&F&T&F&T&F&F\\F&T&F&F&F&F&T&T\\F&F&T&T&F&F&T&T\\F&F&T&F&F&F&T&T\\F&F&F&T&F&F&T&T\\F&F&F&F&F&F&T&T\\\end{array}}$

Exercise 1.2.12

1

$X\rightarrow \neg Y$ → ${\begin{array}{c | c | c | c}X&Y&\neg Y&X\rightarrow \neg Y\\\hline T&T&F&F\\T&F&T&T\\F&T&F&T\\F&F&T&T\\\end{array}}$

2

$(R\rightarrow S)\leftrightarrow R$ → ${\begin{array}{c | c | c | c}R&S&R\rightarrow S&(R\rightarrow S)\leftrightarrow R\\\hline T&T&T&T\\T&F&F&F\\F&T&T&F\\F&F&T&F\\\end{array}}$

3

$\neg M\rightarrow (N\land L)$ → ${\begin{array}{c | c | c | c | c | c}L&M&N&\neg M&N\land L&\neg M\rightarrow (N\land L)\\\hline T&T&T&F&T&T\\T&T&F&F&F&T\\T&F&T&T&T&T\\T&F&F&T&F&F\\F&T&T&F&F&T\\F&T&F&F&F&T\\F&F&T&T&F&F\\F&F&F&T&F&F\\\end{array}}$

4

$(E\leftrightarrow F)\rightarrow (E\leftrightarrow G)$ → ${\begin{array}{c | c | c | c | c | c}E&F&G&E\leftrightarrow F&E\leftrightarrow G&(E\leftrightarrow F)\rightarrow (E\leftrightarrow G)\\\hline T&T&T&T&T&T\\T&T&F&T&F&F\\T&F&T&F&T&T\\T&F&F&F&F&T\\F&T&T&F&F&T\\F&T&F&F&T&T\\F&F&T&T&F&F\\F&F&F&T&T&T\\\end{array}}$

5

$(P\rightarrow R)\lor \neg (Q\leftrightarrow S)$ → ${\begin{array}{c | c | c | c | c | c | c | c}P&Q&R&S&P\rightarrow R&Q\leftrightarrow S&\neg (Q\leftrightarrow S)&(P\rightarrow R)\lor \neg (Q\leftrightarrow S)\\\hline T&T&T&T&T&T&F&T\\T&T&T&F&T&F&T&T\\T&T&F&T&F&T&F&F\\T&T&F&F&F&F&T&T\\T&F&T&T&T&F&T&T\\T&F&T&F&T&T&F&T\\T&F&F&T&F&F&T&T\\T&F&F&F&F&T&F&F\\F&T&T&T&T&T&F&T\\F&T&T&F&T&F&T&T\\F&T&F&T&T&T&F&T\\F&T&F&F&T&F&T&T\\F&F&T&T&T&F&T&T\\F&F&T&F&T&T&F&T\\F&F&F&T&T&F&T&T\\F&F&F&F&T&T&F&T\\\end{array}}$

Exercise 1.2.13

A statement is a tautology if its truth table always gives true values. We have a contradiction when the truth table always gives false values.

1

$P\lor (\neg P\land Q)$ → ${\begin{array}{c | c | c | c | c}P&Q&\neg P&\neg P\land Q&P\lor (\neg P\land Q)\\\hline T&T&F&F&T\\T&F&F&F&T\\F&T&T&T&T\\F&F&T&F&F\end{array}}$
→ This statement is neither a tautology nor a contradiction.

2

$(X\lor Y)\leftrightarrow (\neg X\rightarrow Y)$ → ${\begin{array}{c | c | c | c | c | c}X&Y&\neg X&X\lor Y&\neg X\rightarrow Y&(X\lor Y)\leftrightarrow (\neg X\rightarrow Y)\\\hline T&T&F&T&T&T\\T&F&F&T&T&T\\F&T&T&T&T&T\\F&F&T&F&F&T\\\end{array}}$
→ This statement is a tautology, because as we see in the truth table, it is always true.

3

$(A\land \neg B)\land (\neg A\lor B)$ → ${\begin{array}{c | c | c | c | c | c | c}A&B&\neg A&\neg B&A\land \neg B&\neg A\lor B&(A\land \neg B)\land (\neg A\lor B)\\\hline T&T&F&F&F&T&F\\T&F&F&T&T&F&F\\F&T&T&F&F&T&F\\F&F&T&T&F&T&F\end{array}}$
→ This statement is a contradiction, given that it always is false.

4

$[Z\lor (\neg Z\lor W)]\land \neg (W\land U)$ → ${\begin{array}{c | c | c | c | c | c | c | c | c}U&W&Z&\neg Z&\neg Z\lor W&Z\lor (\neg Z\lor W)&W\land U&\neg (W\land U)&[Z\lor (\neg Z\lor W)]\land \neg (W\land U)\\\hline T&T&T&F&T&T&T&F&F\\T&T&F&T&T&T&T&F&F\\T&F&T&F&F&T&F&T&T\end{array}}$
→ We can stop at that row of the truth table, because now we know that the statement can't be a tautology or a contradiction.

5

$[L\rightarrow (M\rightarrow N)]\rightarrow [M\rightarrow (L\rightarrow N)]$ → ${\begin{array}{c | c | c | c | c | c | c | c}L&M&N&M\rightarrow N&L\rightarrow N&L\rightarrow (M\rightarrow N)&M\rightarrow (L\rightarrow N)&[L\rightarrow (M\rightarrow N)]\rightarrow [M\rightarrow (L\rightarrow N)]\\\hline T&T&T&T&T&T&T&T\\T&T&F&F&F&F&F&T\\T&F&T&T&T&T&T&T\\T&F&F&T&F&T&T&T\\F&T&T&T&T&T&T&T\\F&T&F&F&T&T&T&T\\F&F&T&T&T&T&T&T\\F&F&F&T&T&T&T&T\end{array}}$
→ This statement is a tautology.

6

$[(X\leftrightarrow Z)\land (X\leftrightarrow Y)]\land X$ → ${\begin{array}{c | c | c | c | c | c| c}X&Y&Z&X\leftrightarrow Z&X\leftrightarrow Y&(X\leftrightarrow Z)\land (X\leftrightarrow Y)&[(X\leftrightarrow Z)\land (X\leftrightarrow Y)]\land X\\\hline T&T&T&T&T&T&T\\T&T&F&F&T&F&F\end{array}}$
→ We see that this statement is neither a tautology nor a contradiction.

7

$[(P\leftrightarrow \neg Q)\land P]\land Q$ → ${\begin{array}{c | c | c | c | c | c}P&Q&\neg Q&P\leftrightarrow \neg Q&(P\leftrightarrow \neg Q)\land P&[(P\leftrightarrow \neg Q)\land P]\land Q\\\hline T&T&F&F&F&F\\T&F&T&T&T&F\\F&T&F&T&F&F\\F&F&T&F&F&F\\\end{array}}$
→ The statement is always false, therefore it is a contradiction.

Exercise 1.2.14

1

If John eats a blueberry pizza, then he either eats a blueberry pizza or he does not. → Let X = "John eats a blueberry pizza". Then we have the following statement: $X\rightarrow (X\lor \neg X)$ → We can already see that this is a tautology, because no matter the truth value of X, $(X\lor \neg X)$ is always true, and if the consequence in the conditional is always true, then so is the conditional. But let's see the truth table, just to be certain:
${\begin{array}{c | c | c | c}X&\neg X&X\lor \neg X&X\rightarrow (X\lor \neg X)\\\hline T&F&T&T\\F&T&T&T\end{array}}$

2

If John eats a blueberry pizza or he does not, then he eats a blueberry pizza. → Let X = "John eats a blueberry pizza". Then we have the following statement: $(X\lor \neg X)\rightarrow X$.
${\begin{array}{c | c | c | c}X&\neg X&X\lor \neg X&(X\lor \neg X)\rightarrow X\\\hline T&F&T&T\\F&T&T&F\end{array}}$
→ This statement is neither a tautology nor a contradiction.

3

If pigs have wings and pigs do not have wings, then the sun sets in the east. → Let X = "pigs have wings" and Y = "the sun sets in the east". We can write this statement as follows: $(X\land \neg X)\rightarrow Y$.
→ This statement is a tautology, since it always is false. The reason for this is that in the statement $X\land \neg X$ both truth values are always opposite, and because is and AND statement, it can't be true. And, since these false statement is the antecedent of the conditional, no matter what the value of Y is, the statement is always true. You can convince yourself of this by looking at the truth table:
${\begin{array}{c | c | c | c | c}X&Y&\neg X&X\land \neg X&(X\land \neg X)\rightarrow Y\\\hline T&T&F&F&T\\T&F&F&F&T\\F&T&T&F&T\\F&F&T&F&T\end{array}}$.

4

If Ethel goes to the movies then Agnes will eat a cake, and Agnes does not eat cake, and Ethel goes to the movies. → Let X = "Ether goes to the movies" and Y = "Agnes eats a cake". The statement can be written as follows: $((X\rightarrow Y)\land \neg Y)\land X$.
${\begin{array}{c | c | c | c | c | c}X&Y&\neg Y&X\rightarrow Y&(X\rightarrow Y)\land \neg Y&((X\rightarrow Y)\land \neg Y)\land X\\\hline T&T&F&T&F&F\\T&F&T&F&F&F\\F&T&F&T&F&F\\F&F&T&T&T&F\end{array}}$ According to the truth table, this statement is a contradiction, since it is always false.

5

Rabbits eat cake or pie, and if rabbits eat pie then eat cake. → Let X = "Rabbits eat cake" and Y = "Rabbits eat pie". So, we can write this statement like this: $(X\lor Y)\land (Y\rightarrow X)$.
${\begin{array}{c | c | c | c | c}X&Y&X\lor Y&X\rightarrow Y&(X\lor Y)\land (X\rightarrow Y)\\\hline T&T&T&T&T\\T&F&T&T&T\\F&T&T&F&F\\F&F&F&T&F\end{array}}$
→ This statement is neither a tautology nor a contradiction.

6

The cow is green or the cow is not green, if and only if the goat is blue and the goat is not blue. → Let X = "The cow is green" and Y = "The goat is blue". The we have the following statement: $(X\lor \neg X)\leftrightarrow (Y\land \neg Y)$.
→ This one is a clear contradiction. Note that $X\lor \neg X$ is always true, because always one of X and ¬X is true. But when we have $Y\land \neg Y$, it is always false because the truth values are always opposite. Therefore, the truth values of $X\lor \neg X$ and $Y\land \neg Y$ are never the same, so the whole statement is always false: a contradiction. Let's look at the truth table:
${\begin{array}{c | c | c | c | c | c | c}X&Y&\neg X&\neg Y&X\lor \neg X&Y\land \neg Y&(X\lor \neg X)\leftrightarrow (Y\land \neg Y)\\\hline T&T&F&F&T&F&F\\T&F&F&T&T&F&F\\F&T&T&F&T&F&F\\F&F&T&T&T&F&F\end{array}}$

Exercise 1.2.15

1

Show that $P\lor T$ is a tautology. → We already know that an OR statement is true when at least one of the two statements is true. Since we have a statement that is a tautology (always true), therefore the OR statement will be true no matter the truth value of P. We can put a truth table just to show how this works:
${\begin{array}{c | c | c}P&T&P\lor T\\\hline T&T&T\\F&T&T\end{array}}$

2

Show that $P\land C$ is a contradiction. → When we have an AND statement, we know that is only true if both statements are true. But since one of the statements is a contradiction (always false), then the AND statement can't be true. Hence is always false: a contradiction.
${\begin{array}{c | c | c}P&C&P\land C\\\hline T&F&F\\F&F&F\end{array}}$

Exercise 1.3.1

Let P, Q, R and S be statements. Show that the following are true.

1

$\neg (P\rightarrow Q)\rightarrow P$. We need to show that this is a tautology.
${\begin{array}{c | c | c | c | c}P&Q&P\rightarrow Q&\neg (P\rightarrow Q)&\neg (P\rightarrow Q)\rightarrow P\\\hline T&T&T&F&T\\T&F&F&T&T\\F&T&T&F&T\\F&F&T&F&T\end{array}}$
Therefore, this is true. Other way to see this is true is by using Fact 1.3.2 - 8. to yield $\neg (P\rightarrow Q)\Leftrightarrow \neg (\neg P\lor Q)$ and then Fact 1.3.2 - 13. to get $\neg (\neg P\lor Q)\Leftrightarrow P\land \neg Q$. Then, using Fact 1.3.1 - 3 (Simplification) gives us $P\land \neg Q\Rightarrow P$.

Exercise 1.4.1

For each of the following arguments, if it is valid, give a derivation, and if it is not valid, show why.

1

${\begin{array}{c l l}(1)&P\wedge Q&\\(2)&(P\vee Q)\rightarrow R&\\\hline (3)&P&,(1){\text{ Simplification}}\\(4)&P\vee Q&,(3){\text{ Addition}}\\(5)&R&,(2),(4){\text{ Modus Ponens}}\\\end{array}}$ Therefore, the argument is valid (we have shown a derivation).

2

Constructing the table of truth, it can be seen that it is not a tautology, therefore, it is not a valid reasoning.

3

${\begin{array}{c l l}(1)&E\rightarrow F&\\(2)&\neg G\rightarrow \neg F&\\(3)&H\rightarrow I&\\(4)&E\vee H&\\\hline (5)&F\rightarrow G&,(2){\text{ Contrapositive}}\\(6)&E\rightarrow G&,(1),(5){\text{ Hypothetical Syllogism}}\\(7)&G\vee I&,(6),(3),(4){\text{ Constructive Dilemma}}\\\end{array}}$ Therefore, the argument is valid (we have shown a derivation).

4

${\begin{array}{c l l}(1)&L\rightarrow M&\\(2)&(M\vee N)\rightarrow (L\rightarrow K)&\\(3)&\neg P\wedge L&\\\hline (4)&L&(3){\text{ Simplification}}\\(5)&M&(1),(4){\text{ Modus Ponens}}\\(6)&M\vee N&(5){\text{ Addition}}\\(7)&(L\rightarrow K)&(2),(6){\text{ Modus Ponens}}\\(8)&K&(7),(4){\text{ Modus Ponens}}\\\end{array}}$ Therefore, the argument is valid (we have shown a derivation).

5

Constructing a truth table, it can be seen that it is not a tautology, therefore, it is not a valid reasoning. Values that satisfy all premises as true but leave the conclusion as false are: Q is false, S is false, F is false, E is false, and H is false.

Exercise 1.5.3

1

${\begin{array}{c l l}(\exists y)P(y)&\\\end{array}}$

2

${\begin{array}{c l l}(\forall y)Q(y)&\\\end{array}}$

3

${\begin{array}{c l l}(\exists y)P(y)\wedge (\exists y)R(y)&\\\end{array}}$

4

${\begin{array}{c l l}(\forall y)Q(y)R(y)&\\\end{array}}$

5

${\begin{array}{c l l}(\exists y)(Q(y)\rightarrow \neg R(y))&\\\end{array}}$

6

${\begin{array}{c l l}(\forall y)(\neg Q(y)\rightarrow P(y)&\\\end{array}}$

7

${\begin{array}{c l l}(\forall y)(\neg P(y))&\\\end{array}}$

Exercise 1.5.11

1

${\begin{array}{c l l}(1)&(\forall x\in U)[R(x)\rightarrow C(x)]&\\(2)&(\forall x\in U)[T(x)\rightarrow R(x)]&\\\hline (3)&T(a)\rightarrow R(a)&,(2){\text{Universal Instantiation}}\\(4)&R(a)\rightarrow C(a)&,(1){\text{Universal Instantiation}}\\(5)&T(a)\rightarrow C(a)&,(3),(4){\text{Hypothetical Syllogism}}\\(6)&\neg C(a)\rightarrow \neg T(a)&,(5){\text{Contrapositive}}\\(7)&(\forall x\in U)[\neg C(x)\rightarrow \neg T(x)]&,(6){\text{Universal Generalitation}}\end{array}}$

2

${\begin{array}{c l l}(1)&(\forall a\in V)[N(a)\rightarrow B(a)]&\\(2)&(\exists b\in V)[N(b)\wedge D(b)]&\\\hline (3)&N(c)\wedge D(c)&,(2){\text{Existential Instantiation}}\\(4)&N(c)\rightarrow B(c)&,(1){\text{Universal Instantiation}}\\(5)&N(c)&,(3){\text{Simplification}}\\(6)&D(c)&,(3){\text{Simplification}}\\(7)&B(c)&,(4),(5){\text{Modus ponens}}\\(8)&B(c)\wedge D(c)&,(6),(7){\text{Adition}}\\(9)&(\exists x\in V)[B(x)\wedge D(x)]&,(8){\text{Existential Generalitation}}\end{array}}$ Note: remember always use the Existential Instantiation (EI) before the Universal Instantiation (UI).