## Logical Discourse

In this section we discuss axiomatic systems and inference rules for quantified statements. To give example, we carry out a simple logical discourse for incidence geometry involving points, lines, and incidence.

## Axiomatic Systems

An axiomatic (or formal) system must contain a set of technical terms that are deliberately chosen as undefined, called ** undefined terms**, and are subject to the interpretation of the reader. All other technical terms of the system are ultimately defined by means of the undefined terms, and are called

**. An axiomatic system contains a set of statements, dealing with undefined terms and definitions, that are chosen to remain unproved, and are called axioms. Below is an example of a simple axiomatic system where the terms**

*definitions***,**

*point***, and**

*line***only have the meaning given by a small collection of axioms. We assume that we have a collection of points and a collection of lines. The only other assumptions we make about these points and lines, and their behavior, is given solely by the axioms.**

*incidence*The goal is not to say what a point is or what a line is, but rather to discover how they behave.

The axioms say a point is incident with a line.

Let point, line, and incidence be undefined terms. Collectively the following three axioms are called the ** Incidence Axioms**. A quick introduction to incidence geometry is found here.

$\qquad$ (A1) (

**) For every two distinct points $A$ and $B$ there exists a unique line $l$ incident with $A$ and $B$, and is denoted by $l(AB)$.**

*Line Uniqueness*$\qquad$ (A2) (

**) For every line $l$ there exist at least two distinct points incident with $l.$**

*Points On Line*$\qquad$ (A3) (

**) There exist three distinct points with the property that no line is incident with all three of them.**

*Noncollinear Points*We will use the following convention: uppercase letters denote points, i.e. $A$, $B, \ldots P$, $Q$, etc, and lowercase letters denote lines, i.e. $l, m, n$.

** Definition**. Three or more points are called collinear if there exists a line incident with all of them. Three or more lines are called

**if there exists a point incident with all of them.**

*concurrent*Notice the definitions of collinear and concurrent are dual notions, in the sense that they are defined the same way except that the roles of point and line are interchanged. We use the terms ** noncollinear** and

**to mean not collinear and not concurrent, respectively. Lines $l$ and $m$ are called**

*nonconcurrent***, denoted by $l=m$, if every point incident with $l$ is also incident with $m,$ and conversely. Lines $l$ and $m$ are called**

*equal lines***if $l=m$ or if no point is incident with both of them. The notation $l\parallel m$ means line $l$ is parallel to line $m$.**

*parallel lines*## Inference Rules for Quantified Statements

Before we begin proving theorems, we need to discuss the inference rules for quantified statements. However, before we do so, the reader is encourage to write out each incidence axiom in symbolic form and also write the negation of each one in both symbolic and English form. Suppose that $\exists x\in U$, $P(x)$ is true, where $U$ is the domain of discourse. Then we have $P(x)$ is true for some $x$ in $U$. Thus, there exists $c\in U$ such that $P(c)$ is true. Hence we have shown that the argument $$ \begin{array}{l} \exists x, P(x) \\ \hline \therefore \, \text{$P(c)$ for some element $c\in U$} \end{array} $$ is valid. Now suppose that $\forall x\in U$, $P(x)$ is true. Then we have, $P(x)$ is true for every $x$ in $U$. In particular, if $c\in U$, then $P(c)$ is true. Hence we have shown that the argument $$ \begin{array}{l} \forall x, P(x)\\ \hline \therefore \, \text{$P(c)$ if $c\in U$} \end{array} $$ is valid. The reader should write careful arguments to justify the other two inference rules. All four are listed below. \begin{alignat*}{2} & \text{Inference Rules for Universe $U$} &\qquad \qquad & \textbf{Name} \\ \hline & \begin{array}{l} \forall x, P(x) \\ \hline \therefore \, \text{$P(c)$ if $c\in U$} \end{array} && \text{Universal instantiation} \\ & \begin{array}{l} P(c) \text{ for an arbitrary $c\in U$} \\ \hline \therefore \, \forall x, P(x) \end{array} && \text{Universal generalization} \\ & \begin{array}{l} \exists x, P(x) \\ \hline \therefore \, \text{$P(c)$ for some element $c\in U$} \end{array} && \text{Existential instantiation} \\ & \begin{array}{l} P(c) \text{ for some element $c\in U$} \\ \hline \therefore \, \exists x, P(x) \end{array} && \text{Existential generalization} \end{alignat*}

## Theorems in Incidence Geometry

As examples on how to use these inference rules, we prove a few theorems in incidence geometry.

** Theorem**. If $l$ and $m$ are distinct lines that are not parallel, then $l$ and $m$ have a unique point in common.

** Proof**. We begin with a column proof.

Conclusions | Justifications | |

Lines $l$ and $m$ are distinct lines that are not parallel. | Hypothesis | 1 |

Exactly one must hold: $l$ and $m$ either have no points in common or not | Law of Excluded Middle | 2 |

There does not exists any points incident with both $l$ and $m$. | Case 1 | 3 |

Lines $l$ and $m$ are parallel. | Definition of parallel | 4 |

Contradiction | Steps 1, 4 | 5 |

Lines $l$ and $m$ have points in common. | Case 2 | 6 |

Exactly one must hold: lines $l$ and $m$ have exactly one point in common or more. | Law of Excluded Middle | 7 |

There exists distinct points $P$ and $Q$ that are both incident with both lines $l$ and $m$. | Case 2.1 | 8 |

$l=m$ | Axiom 1 | 9 |

Contradiction | Step 1 | 10 |

There exists exactly one point incident with lines $l$ and $m$. | Case 2.2 | 11 |

We end with a paragraph proof.

Assume $l$ and $m$ are distinct lines that are not parallel. By definition of parallel lines, these lines must have at least one point in common. If they have another point in common, then they are the same line by Axiom 1. Therefore, they have a unique point in common.

** Theorem**. There exist three distinct lines that are nonconcurrent.

** Proof**. We begin with a column proof.

Conclusions | Justifications | 1 |

$A$, $B$, and $C$ are distinct noncollinear points. | Axiom 3 | 2 |

There exists a line $\overleftrightarrow{AB}$ incident with $A$ and $B$. | Axiom 1 | 3 |

There exists a line $\overleftrightarrow{BC}$ incident with $B$ and $C$. | Axiom 1 | 4 |

There exists a line $\overleftrightarrow{AC}$ incident with $A$ and $C$. | Axiom 1 | 5 |

$\overleftrightarrow{AB}=\overleftrightarrow{BC}$ | RAA Hypothesis | 6 |

$A$ is incident with $\overleftrightarrow{BC}$ | Definition of equality | 7 |

$A$, $B$, and $C$ are collinear points. | Definition of collinear | 8 |

contradiction | Steps 1, 7 | 9 |

$\overleftrightarrow{AB}\neq\overleftrightarrow{BC}$ | RAA Conclusion | 10 |

$\overleftrightarrow{AB}=\overleftrightarrow{AC}$ | RAA Hypothesis | 11 |

$B$ is incident with $\overleftrightarrow{AC}$ | Definition of equality | 12 |

$A$, $B$, and $C$ are collinear points. | Definition of collinear | 13 |

contradiction | Steps 1, 12 | 14 |

$\overleftrightarrow{AB}\neq\overleftrightarrow{AC}$ | RAA Conclusion | 15 |

$\overleftrightarrow{AC}=\overleftrightarrow{BC}$ | RAA Hypothesis | 16 |

$A$ is incident with $\overleftrightarrow{BC}$ | Definition of equality | 17 |

$A$, $B$, and $C$ are collinear points. | Definition of collinear | 18 |

Contradiction | Steps 1, 17 | 19 |

$\overleftrightarrow{AC}\neq\overleftrightarrow{BC}$ | RAA Conclusion | 20 |

Lines $\overleftrightarrow{AB}$, $\overleftrightarrow{BC}$, $\overleftrightarrow{AC}$ are three distinct lines. | Steps 9, 14, 19 | 21 |

There exists a point $X$ incident with all three lines $\overleftrightarrow{AB}$, $\overleftrightarrow{BC}$, $\overleftrightarrow{AC}$. | RAA Hypothesis | 22 |

One and only one must hold: $X=A$ or $X\neq A$. | Law of Excluded Middle | 23 |

$X=A$ | Case 1 | 24 |

Point $A$ is incident with all three lines $\overleftrightarrow{AB}$, $\overleftrightarrow{BC}$, and $\overleftrightarrow{AC}$. | Steps 21, 23 | 25 |

$A$, $B$, $C$ are collinear points. | Definition of Collinear | 26 |

Contradiction | Steps 1, 25 | 27 |

$X\neq A$ | Case 2 | 28 |

Lines $\overleftrightarrow{AB}$ and $\overleftrightarrow{AC}$ are not parallel. | Def. of Parallel Lines | 29 |

$X=A$ | Theorem 2 | |

Contradiction | Steps 27, 29 | 30 |

There does not exist a point $X$ incident with all three lines $\overleftrightarrow{AB}$, $\overleftrightarrow{BC}$, $\overleftrightarrow{AC}$. | RAA Conclusion | 31 |

lines $\overleftrightarrow{AB}$, $\overleftrightarrow{BC}$, $\overleftrightarrow{AC}$ are nonconcurrent. | Def. of nonconcurrent | 32 |

We end with a paragraph proof.

By Axiom 3, there exists three distinct points $A$, $B$, and $C$ and by Axiom 1, we have lines $l(AB)$, $l(BC)$, and $l(AC)$. If $l(AB)=l(BC)$, then points $A$, $B$, and $C$ are collinear, contrary to hypothesis. Hence $l(AB)\neq l(BC)$. Similarly, it follows $l(BC)\neq l(AC)$ and $l(AB)\neq l(AC)$. Thus we have three distinct lines. Assume these lines are concurrent with point $X$. If $X=A$, then $A$ is on all three lines and again we contradict the hypothesis. Hence $X\neq A$, and so the nonparallel lines $l(AB)$ and $l(AC)$ have more than one point in common. This contradicts Theorem 2, and so $X$ can not exist. Whence these three distinct lines are nonconcurrent.

** Theorem**. For every point, there is at least one line not passing through it.

** Proof**. We begin with a column proof.

Conclusions | Justifications | |

$A$ is a point | Hypothesis | 1 |

$A$ is incident with every line. | RAA Hypothesis | 2 |

There exists 3 noncollinear points $E$, $D$, $F$. | Axiom 3 | 3 |

There exists a line $\overleftrightarrow{ED}$ incident with $E$ and $D.$ | Axiom 1 | 4 |

There exists a line $\overleftrightarrow{DF}$ incident with $D$ and $F$. | Axiom 1 | 5 |

One and only one must hold: $A=D$ or $A\neq D$. | Law of Excluded Middle | 6 |

$A\neq D$ | Case 1 | 7 |

$A$ and $D$ are incident with $\overleftrightarrow{ED}$ and $\overleftrightarrow{DF}.$ | Steps 2, 4, 5 | 8 |

$\overleftrightarrow{ED}$= $\overleftrightarrow{DF}$ | Axiom 1 | 9 |

$F$ is incident with $\overleftrightarrow{ED}$. | Definition of Equal Lines | 10 |

$E$, $D$, and $F$ are collinear points. | Definition of collinear | 11 |

Contradiction | Steps 3 and 11 | 12 |

$A=D$ | Case 2 | 13 |

$D$ is incident with every line. | Steps 2, 13 | 14 |

There exists a line $\overleftrightarrow{EF}$ incident with $E$ and $F$. | Axiom 1 | 15 |

$D$ is incident with $\overleftrightarrow{EF}$. | Step 1 | 16 |

$E$, $D$, and $F$ are collinear points. | Definition of Collinear | 17 |

Contradiction | Steps 3, 17 | 18 |

There exists a line not incident with $A$. | RAA conclusion | 19 |

We end with a paragraph proof.

Let $A$ be an arbitrary point. Assume every line is incident with $A$. By Axiom 3, there exists three distinct points, say $D$, $E$, and $F$. Point $A$ is not one of these points, say $D$. By Axiom 1, we have lines $l(ED)$ and $l(DF)$. Further, since $A$ and $D$ are distinct points and both are on $l(ED)$ and $l(DF)$ we have $l(ED)=l(DF)$, by Axiom 1. Hence $E, D$, and $F$ are collinear. Therefore, point $A$ is not incident with at least one line.

## Summary of Logical Discourse

The pattern of logical discourse goes as follows:

$\qquad $ (1) A set of primitive (undefined terms) is given.

$\qquad $ (2) A set of axioms (unproven statements) about the primitive terms is also given.

$\qquad $ (3) Then all of the terms of the discourse are defined by means of the primitive terms or by previously defined terms that were defined using primitive terms.

$\qquad $ (4) All other statements in the system are logically deduced from the axioms. These are the ** theorems** of the system.

In mathematical exposition, we often communicate by distinguishing different types of theorems. For example, a theorem is sometimes called a ** result**. There is an air of humility in calling a theorem merely a result. Other alternatives to

**are listed below.**

*theorem*$\qquad $

**. A very minor theorem, but important enough to number and refer to latter, i.e., the statement $1+1=2$ is a fact.**

*Fact*$\qquad $

**. Also a minor theorem, but more important (usually more general) than a fact –but not as prestigious as a theorem.**

*Proposition*$\qquad $

**. Often a technical theorem, which is used to help prove another more important theorem. Stating lemmas, before proving a difficult complicated theorem, is functional.**

*Lemma*$\qquad $

**. Similar to lemma but less formal. A claim will often be referred to only a small number of times, whereas a lemma may be referenced many times and is a useful result in itself. For example, stating a claim inside the proof theorem is a great way to help organize key steps in a proof.**

*Claim*

$\qquad $ ** Corollary**. An important enough result to state on its own whose proof requires a previously proved theorem as its main step.

## Exercises

** Exercise**. (a) Write each Incidence Axiom in symbolic form. (b) Write the negation of each Incidence Axiom in symbolic form. (c) Write the negation of each Incidence Axiom in words.

** Exercise**. Write careful arguments to explain why each inference rule for quantified statements is valid.

In the following exercises, first write a column proof and then write a paragraph proof.

** Exercise**. (a) For every line $l$, $l=l$. (b) For every line $l$ and every line $m$, if $l=m$ then $m=l$. (c) For every line $l$, $m$, and $n$, if $l=m$ and $m=n$, then $l=n$.

** Exercise**. There exists at least one line.

** Exercise**. There exists at least two lines.

** Exercise**. There exists at least three points.

** Exercise**. There exists at least three lines.

** Exercise**. Every point is on at least one line.

** Exercise**. For every line $l$, there is at least one point not lying on $l$.

** Exercise**. For every point $A$, there exist at least two distinct lines through $A.$

** Exercise**. If $C$ is on $l(AB)$ and distinct from $A$ and $B$, then $$l(CA)=l(BC)=l(AB) $$

** Exercise**. If $l(AB)=l(AC)$ and $B$ and $C$ are distinct, then $l(AB)=l(BC)$.

** Exercise**. If $l$ is any line, then there exists lines $m$ and $n$ such that $l$, $m$, and $n$ are distinct and both $m$ and $n$ have a point in common with $l$.

** Exercise**. If $A$ is any point, then there exist points $B$ and $C$ such that $A$, $B$, and $C$ are noncollinear.

** Exercise**. If $A$ and $B$ are two distinct points, then there exists a point $C$ such that $A$, $B$, and $C$ are noncollinear.

Let ** between** be another undefined term. The notation $A*B*C$ will be used to denote that point $B$ is

**points $A$ and $C.$ The following four axioms give meaning to the undefined term between and collectively are called the**

*between***.**

*Betweenness Axioms*$\qquad $ (B1) If $A*B*C$, then $A, B,$ and $C$ are three distinct collinear points and $C*B*A.$

$\qquad $ (B2) For any two distinct points $B$ and $C$, there exist a point $A$ incident with $l(BC)$ such that $A*B*C.$

$\qquad $ (B3) If $A, B,$ and $C$ are three distinct points on the same line, then one and only one of the points is between the other two.

$\qquad $ (B4) For any line $l$ and any three distinct points $A, B,$ and $C$ not incident with $l$,

$\qquad \qquad $ (a) if $A$ and $B$ are on the same side of $l$ and $B$ and $C$ are on the same side (see below) of $l$, then $A$ and $C$ are on the same side of $l$;

$\qquad \qquad $ (b) if $A$ and $B$ are on opposite sides of $l$ and $B$ and $C$ are on opposite sides of $l$, then $A$ and $C$ are on the same side of $l$.

The ** line segment** of two distinct points $A$ and $B$, denoted by $\overline{A B}$, consists of points $A$ and $B$, and all points incident with line $l(AB)$ that are between $A$ and $B.$ The two points $A$ and $B$ are called the

**of $\overline{A B}$.**

*endpoints*Let $l$ be any line and let $A$ and $B$ be any points not incident with $l.$ If $A$ and $B$ are the same point or if segment $\overline{A B}$ is not incident with $l$, we say $A$ and $B$ are on the ** same side** of $l$, whereas if $A$ and $B$ are distinct and segment $\overline{A B}$ is incident with $l$, we say that $A$ and $B$ are on opposite sides of $l.$

In the following exercises, prove the statement by writing a column proof and a paragraph proof.

** Exercise**. There exists at least three distinct line segments.

** Exercise**. If $A*B*C$ and $E$ is a point not incident with $l(AC)$, then $A$ and $B$ are on the same side of $l(EC).$

** Exercise**. If $A*B*C$ and $E$ is a point not incident with $l(AC),$ then $A$ and $C$ are on opposite sides of $l(EB)$.

** Exercise**. Every line bounds exactly two

**and these half-planes have no point in common.**

*half-planes*** Exercise**. If $A*B*C$ and $B*C*D$, then $A, B, C,$ and $D$ are distinct and collinear.

** Exercise**. If $A*B*C$ and $A*C*D$ then $A, B, C,$ and $D$ are distinct and collinear.

** Exercise**. If $A*B*C$ and $A*C*D,$ then $B*C*D.$

** Exercise**. If $A*B*C$ and $B*C*D$, then $A*C*D.$

In the following exercises, determine which of the following sentences or pairs of sentences are propositions. For those that are not, explain why not.

** Exercise**. A bird has two legs or an insect has six legs.

** Exercise**. The lake water is boiling hot.

** Exercise**. Does ice float?

** Exercise**. Do pigs tell lies?

** Exercise**. This sentence has four errors.

** Exercise**. The following sentence is false. The preceding sentence is true.

In the following exercises, write a truth table for each of the following propositional forms.

** Exercise**. $p\lor (q \land \neg p)$

** Exercise**. $p\land \neg(p\land p)$

** Exercise**. $(p\lor q)\land (p\land c)$

** Exercise**. $(\neg p\lor q)\land (r\lor \neg q)$

** Exercise**. $(p\lor \neg (r\land \neg q))\land \neg p$

** Exercise**. $(p \lor \neg q)\land (q\land \neg r)$

In the following exercises, determine whether the following given propositional forms is a tautology, a contradiction, or neither. Justify.

** Exercise**. $(p\land \neg q)\land (q\lor \neg p)$

** Exercise**. $(q\lor \neg p)\lor(r\land \neg q)$

** Exercise**. $(p\land \neg r)\lor (r\land \neg q)$

** Exercise**. $\neg(q\lor r\lor \neg p)\land (p\land r\land \neg q)$

** Exercise**. $(p\lor (q\land r))\lor (q\lor \neg r)$

In the following exercises, decide which of the following propositions that follow are true and which are false. If a proposition is false, provide a counterexample to it.

** Exercise**. $\forall x \in \mathbb{N}, x^2+3x+2\geq 0$

** Exercise**. $\forall x \in \mathbb{Z}, x^2+3x+2\geq 0$

** Exercise**. $\forall x \in \mathbb{Q}, x^2+3x+2\geq 0$

** Exercise**. $\forall x \in \mathbb{R}, x^2+3x+2\geq 0$

In the following exercises, write a working negation of each of the following statements. If the statement is in words, write the negation in words; if it is symbols, write the negation in symbols

** Exercise**. Every integer is even or odd.

** Exercise**. Every line segment has a unique midpoint.

** Exercise**. $\forall \epsilon>0, \exists \ K\in \mathbb{N}, \forall n,m\in \mathbb{N} \text{ s.t. } ((n>K \land m>K)\rightarrow |x_n -x_m|<\epsilon)$

** Exercise**. Every natural number has a prime divisor.

** Exercise**. There is no largest integer.

** Exercise**. $\forall n\in \mathbb{N}, \exists m\in \mathbb{N} \text{ s.t. } m>n$

** Exercise**. Let $x$ be a positive integer and define the following propositional functions: $$ p(x): \, x \text{ is prime,} \qquad q(x): \, x \text{ is even,} \qquad r(x): \, x>2. $$ Write out these statement in words.

$\qquad $ (a) $\exists x, p(x)$

$\qquad $ (b) $\exists x, [p(x)\land q(x)]$

$\qquad $ (c) $\forall x, r(x)$

$\qquad $ (d) $ \forall x, [r(x)\rightarrow (p(x)\lor q(x))]$

$\qquad $ (e) $\forall x, [(p(x)\land q(x))\rightarrow \neg r(x)]$

$\qquad $ (f) $\exists x, [p(x)\land (q(x)\lor r(x))]$

In the following exercises, find the working negation (negation in simplest form) of each formula.

** Exercise**. $\forall x, [p(x)\lor q(x)]$

** Exercise**. $\forall x, [\exists y, (p(x,y)\rightarrow q(x,y))]$

** Exercise**. $\exists x, [(\forall x, p(x,y)\rightarrow q(x,y))\land \exists z, r(x,z)]$

** Exercise**. $\forall x, \forall y, [p(x,y)\rightarrow q(x,y)]$

** Exercise**. Let $x$ be an integer and use the following propositional functions \begin{alignat*}{2} & p(x): \quad & & x \text{ is even} \\ & q(x): & & x \text{ is odd}\\ & r(x): & & x^2<0 \end{alignat*} to show that formulas $u$ and $v$ are not logically equivalent.

$\qquad $ (a) $u: \forall x, [p(x)\lor q(x)]$; \quad $v: [\forall x, p(x)] \lor [\forall x, q(x)]$

$\qquad $ (b) $u: \exists x, [p(x)\land q(x)]$; \quad $v: [\exists x, p(x)] \land [\exists x, q(x)]$

$\qquad $ (c) $u: \forall x, [p(x)\rightarrow q(x)]$; \quad $v: [\forall x, p(x)] \rightarrow [\forall x, q(x)]$

$\qquad $ (d) $u: \exists x, [p(x)\rightarrow r(x)]$; \quad $v: [\exists x, p(x)] \rightarrow [\exists x, r(x)]$

** Exercise**. Let $A$ be a set. Verify that

$\qquad $ (a) $\exists x\in A,[p(x)\lor q(x)]\equiv [\exists x\in A, p(x)]\lor [\exists x\in A, q(x)]$

$\qquad $ (b) $\forall x\in A,[p(x)\land q(x)]\equiv [\forall x\in A, p(x)]\land [\forall x\in A, q(x)]$

$\qquad $ (c) $\exists x\in A,[p(x)\rightarrow q(x)]\equiv [\exists x\in A, P(x)]\rightarrow [\exists x\in A, q(x)]$

In the following exercises, assume the domain of discourse is the set of integers and determine which of the following statements are true and which are false. Explain your answers.

** Exercise**. $\forall x, \forall y, x=y$

** Exercise**. $\forall x, \exists y, xy=1$

** Exercise**. $\exists x, \forall y, xy=y$

** Exercise**. $\forall x, \forall y, \exists z, xy=z$

** Exercise**. $\forall x, \forall y, xy=yx$

** Exercise**. $\forall x, \exists y , xy=x$

** Exercise**. $\forall x, \exists x, \forall z, xy=z$

In the following exercises, assume the domain of discourse is the set of integers and write the negation of the statement without using any negative words. Then explain if the statement is true or not.

** Exercise**. $\exists!\, n, n^2=4$

** Exercise**. $\exists! n, n \text{ has exactly two positive divisors}$

** Exercise**. $\exists ! n, n<100 \text{ and } n^2>50$

** Exercise**. (a) Verify the following argument is valid by constructing a truth table. (b) Write a column proof. (c) Write a paragraph proof. $$ \begin{array}{l} p \lor q \\ \neg \, q \rightarrow r \\ \neg \, p \lor \neg \, r \\ \hline \therefore \, p \end{array} $$

** Exercise**. Another logical connective is called the

**and is denoted by $\underline{\lor}$. It is defined by the following table: $$\begin{array}{c|c|c} p & q & p\underline{\lor} q \\ \hline T & T & F \\ T & F & T \\ F & T & T \\ F & F & F \end{array}$$**

*exclusive or*$\qquad $ (a) Prove that $\underline{\lor}$ obeys the commutative and associative properties.

$\qquad $ (b) Prove that $p\underline{\lor}q\equiv (p\land \neg q)\lor ((\neg q)\land y)$.

$\qquad $ (c) Prove that $p\underline{\lor}q\equiv (p\lor q)\land (\neg (q\land y))$.

$\qquad $ (d) Explain why (b) and (c) are important to know. Explain why $\underline{\lor}$ is called the

**.**

*exclusive or*** Exercise**. Use the method of contradiction to prove the following. (a) $\sqrt{3}$ is irrational, (b) $\sqrt[5]{3}$ is irrational.

** Exercise**. Let $x$ be a real number. Use the method of contradiction to prove: $$ \text{If $x^3+4x=0$, then $x=0$.} $$

** Exercise**. Use a counterexample to disprove the statement $$ \text{If $p$ is an odd prime, then $p^2+4$ is prime.} $$

** Exercise**. Let $q$, $q$, and $r$ denote the following statements: \begin{alignat*}{2} & p: & \quad & \text{Sam knows who to write proofs. } \\ & q: & & \text{Sam knows who to find counterexamples.} \\ & r: & & \text{Sam has taken Math 3300.} \end{alignat*} Express, as simple as possible, each formula in words.

$\qquad $ (a) $r\leftrightarrow (p\lor q)$,

$\qquad $ (b) $r\rightarrow \neg q$,

$\qquad $ (c) $r\land \neg p$,

$\qquad $ (d) $q\leftrightarrow (r\land \neg p)$,

$\qquad $ (e) $(p\land q)\lor \neg r$, and

$\qquad $ (f) $p\land (r\rightarrow q)$.

In the following exercises, find and simplify the negation of each formula.

** Exercise**. $p\land q \land r$

** Exercise**. $p\rightarrow (q\rightarrow r)$

** Exercise**. $p\rightarrow (q\lor r)$

** Exercise**. $p\land (p\rightarrow q)\land (q\rightarrow r)$

** Exercise**. $[p\land (q\rightarrow r)]\lor (\neg q\land p)$

** Exercise**. $ p\leftrightarrow q$

** Exercise**. $p\land (q\lor r)$

** Exercise**. $ \neg p \land (q\rightarrow p)$

In the following exercises, verify each of the following logical equivalencies.

** Exercise**. $[(p\land q)\rightarrow r]\equiv [p\rightarrow (q\rightarrow r)]$

** Exercise**. $[(p\lor q)\rightarrow r]\equiv[(p\rightarrow r)\land (q\rightarrow r)]$

** Exercise**. $[p\rightarrow (q\land r)]\equiv[(p \rightarrow q)\land (p\rightarrow r)]$

** Exercise**. $[p\rightarrow (q\lor r)]\equiv[(p\land \neg r)\rightarrow q]$