Logical Discourse Using Rules of Inference

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

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 definitions. 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 point, line, and incidence 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. 

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) (Line Uniqueness) 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)$.

$\qquad$ (A2) (Points On Line) For every line $l$ there exist at least two distinct points incident with $l.$

$\qquad$ (A3) (Noncollinear Points) There exist three distinct points with the property that no line is incident with all three of them.

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 concurrent if there exists a point incident with all of them.

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 nonconcurrent to mean not collinear and not concurrent, respectively. Lines $l$ and $m$ are called equal lines, denoted by $l=m$,  if every point incident with $l$ is also incident with $m,$ and conversely. Lines $l$ and $m$ are called parallel 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$.

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.

A unique point in common: Logical Discourse Using Rules of Inference
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. 

ConclusionsJustifications
Lines $l$ and $m$ are distinct lines that are not parallel.Hypothesis1
Exactly one must hold: $l$ and $m$ either have no points in common or notLaw of Excluded Middle2
There does not exists any points incident with both $l$ and $m$.Case 13
Lines $l$ and $m$ are parallel.Definition of parallel4
ContradictionSteps 1, 45
Lines $l$ and $m$ have points in common.Case 26
Exactly one must hold: lines $l$ and $m$ have exactly one point in common or more.Law of Excluded Middle7
There exists distinct points $P$ and $Q$ that are both incident with both lines $l$ and $m$.Case 2.18
$l=m$Axiom 19
ContradictionStep 110
There exists exactly one point incident with lines $l$ and $m$.Case 2.211

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.

There exist three distinct lines that are nonconcurrent: Logical Discourse Using Rules of Inference
There exist three distinct lines that are nonconcurrent.

Proof. We begin with a column proof. 

ConclusionsJustifications1
$A$, $B$, and $C$ are distinct noncollinear points.Axiom 32
There exists a line $\overleftrightarrow{AB}$ incident with $A$ and $B$.Axiom 13
There exists a line $\overleftrightarrow{BC}$ incident with $B$ and $C$.Axiom 14
There exists a line $\overleftrightarrow{AC}$ incident with $A$ and $C$.Axiom 15
$\overleftrightarrow{AB}=\overleftrightarrow{BC}$RAA Hypothesis6
$A$ is incident with $\overleftrightarrow{BC}$Definition of equality7
$A$, $B$, and $C$ are collinear points.Definition of collinear8
contradictionSteps 1, 79
$\overleftrightarrow{AB}\neq\overleftrightarrow{BC}$RAA Conclusion10
$\overleftrightarrow{AB}=\overleftrightarrow{AC}$RAA Hypothesis11
$B$ is incident with $\overleftrightarrow{AC}$Definition of equality12
$A$, $B$, and $C$ are collinear points.Definition of collinear13
contradictionSteps 1, 1214
$\overleftrightarrow{AB}\neq\overleftrightarrow{AC}$RAA Conclusion15
$\overleftrightarrow{AC}=\overleftrightarrow{BC}$RAA Hypothesis16
$A$ is incident with $\overleftrightarrow{BC}$Definition of equality17
$A$, $B$, and $C$ are collinear points.Definition of collinear18
ContradictionSteps 1, 1719
$\overleftrightarrow{AC}\neq\overleftrightarrow{BC}$RAA Conclusion20
Lines  $\overleftrightarrow{AB}$,  $\overleftrightarrow{BC}$,  $\overleftrightarrow{AC}$ are three distinct lines.Steps 9, 14, 1921
There exists a point $X$ incident with all three lines  $\overleftrightarrow{AB}$,  $\overleftrightarrow{BC}$,  $\overleftrightarrow{AC}$.RAA Hypothesis22
One and only one must hold: $X=A$ or $X\neq A$.Law of Excluded Middle23
$X=A$Case 124
Point $A$ is incident with all three lines  $\overleftrightarrow{AB}$,  $\overleftrightarrow{BC}$, and $\overleftrightarrow{AC}$.Steps 21, 2325
$A$, $B$, $C$ are collinear points.Definition of Collinear26
ContradictionSteps 1, 2527
$X\neq A$Case 228
Lines $\overleftrightarrow{AB}$ and $\overleftrightarrow{AC}$ are not parallel.Def. of Parallel Lines29
$X=A$Theorem 2
ContradictionSteps 27, 2930
There does not exist a point $X$ incident with all three lines $\overleftrightarrow{AB}$,  $\overleftrightarrow{BC}$, $\overleftrightarrow{AC}$.RAA Conclusion31
lines $\overleftrightarrow{AB}$, $\overleftrightarrow{BC}$, $\overleftrightarrow{AC}$ are nonconcurrent.Def. of nonconcurrent32

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.

One line not passing through it: Logical Discourse Using Rules of Inference
For every point, there is at least one line not passing through it.

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

Proof. We begin with a column proof. 

ConclusionsJustifications
$A$ is a pointHypothesis1
$A$ is incident with every line.RAA Hypothesis2
There exists 3 noncollinear points $E$, $D$, $F$.Axiom 33
There exists a line $\overleftrightarrow{ED}$ incident with $E$ and $D.$Axiom 14
There exists a line $\overleftrightarrow{DF}$ incident with $D$ and $F$.Axiom 15
One and only one must hold: $A=D$ or $A\neq D$.Law of Excluded Middle6
$A\neq D$Case 17
$A$ and $D$ are incident with  $\overleftrightarrow{ED}$ and  $\overleftrightarrow{DF}.$Steps 2, 4, 58
$\overleftrightarrow{ED}$= $\overleftrightarrow{DF}$Axiom 19
$F$ is incident with  $\overleftrightarrow{ED}$.Definition of Equal Lines10
$E$, $D$, and $F$ are collinear points.Definition of collinear11
ContradictionSteps 3 and 1112
$A=D$Case 213
$D$ is incident with every line.Steps 2, 1314
There exists a line $\overleftrightarrow{EF}$ incident with $E$ and $F$.Axiom 115
$D$ is incident with $\overleftrightarrow{EF}$.Step 116
$E$, $D$, and $F$ are collinear points.Definition of Collinear17
ContradictionSteps 3, 1718
There exists a line not incident with $A$.RAA conclusion19

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 theorem are listed below.

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

$\qquad $ Proposition. Also a minor theorem, but more important (usually more general) than a fact –but not as prestigious as a theorem. 

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

$\qquad $ Claim. 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. 



$\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 between points $A$ and $C.$ The following four axioms give meaning to the undefined term between and collectively are called the 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  endpoints of $\overline{A B}$.

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 half-planes and these half-planes have no point in common.

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 exclusive or 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}$$
$\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]$