Propositional Logic (Truth Tables and Their Usage)

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.

By a mathematical statement (or statement, or proposition) we mean  a declarative sentence that can be classified as either true or false, but not both. For example, the sentences $$1+3=4, \quad 1+3=5, \quad \text{July is not a month}$$ can be accepted as statements. The first one is true, and the second two are false. It is currently unknown whether or not the following statement (known as Goldbach’s Conjecture) is true or false: $$\text{Every even integer greater than 2 is the sum of two primes. }$$

Logical Connectives

We will define seven logical connectives; and in doing so, we will use the symbols, $\neg$, $\lor$, $\land$, $\rightarrow$, $\leftrightarrow$, $\downarrow$, and $\uparrow$ to represent the follows words: 

$\qquad \neg$ for “not” or “negation”,   

$\qquad \lor$ for “and/or” or “disjunction”,  

$\qquad \land$ for “and”  or “conjunction”, 

$\qquad \rightarrow$ for “implies” or “if … then … “,  

$\qquad \leftrightarrow$ for “if and only if” or “equivalent”,   

$\qquad \downarrow$ for “joint negation” or “not both”, and

$\qquad \uparrow$ for “alternative negation” or “neither nor”.

Informally, we say a statement is simple whenever it does not use one of the seven connectives.  Examples of simple statements are: \begin{alignat*}{2} & 3+4=7 & \qquad \qquad &\text{Samuel is 46 years old.} \\ & 3+4=8 &   & \text{The current month is December.} \\ & \text{It is raining.} &  & \text{Right now it is 3 o’clock. } \end{alignat*}

Statements that are made up of one or more simple statements using logical connectives are called compound statements. 

The convention used here is that $p$ or $P$ may denote a statement.  We use $P$ sometimes to emphasis that $P$ may be a compound statement. 

More formally, compound statements are defined as follows.

$\qquad (1) $ All simple statements are compound statements. 

$\qquad (2) $ If $p$ and $q$ are compound statements, then so are  $$\neg p, \qquad p \land q, \qquad p \lor q, \qquad p \rightarrow q, \qquad p \leftrightarrow q. $$
$\qquad (3) $ Nothing else is a compound statement unless it can be obtained by a finite number of applications of statement (1) and (2) above. 

For instance, the propositional variables for the statement $p\land \lor q$ are $p$ and $q$. 

Using this definition one can prove that every statement can be decomposed into a finite number of simple statements in a unique way.  For a given statement $P$, it’s corresponding simple statements are called the statement variables (or propositional variables) of $P$.

We now consider each one of these connectives in turn, starting with the simplest first.  As we do so, we illustrate truth values of statements, using “T” for true and “F” for false. 

Definition. The statement $\neg p$, read “not $p$” and called the negation of statement $p$, is defined to be the denial of statement $p$. That is, $\neg p$ is false if $p$ is true, and $\neg p$ is true if $p$ is false.

$$\begin{array}{c|c} p & \neg p \\ \hline  T & F\\  F & T\\  \end{array}$$ Basically, the not connective converts true to false and false to true.

Definition. The statement $p\land q$, read “$p$ and $q$” and called the conjunction of $p$ and $q$, is true when both $p$ and $q$ are true and is false otherwise. 

Conjunction has the usually meaning of “and”, except that the two statements need not be related. Thus we state $$1+4=5 \quad \text{ and}\quad \text{ July is a month}$$ as being a true conjunction.   If we associate “$1+4=5$” with the propositional variable $p$ and “July is a month” with $q$, then we have the conjunction $p\land q$ which is easily seen to be true. 

$$\begin{array}{c|c|c} p & q & p\land q \\ \hline  T & T & T \\  T & F & F \\  F & T & F \\  F & F & F \\  \end{array}$$

Definition. The statement $p\lor q$, read “$p$ or $q$” and called the disjunction of $p$ and $q$, is false when both $p$ and $q$ are false and is true otherwise. 

Disjunction is used logically in the inclusive “and/or” sense.  The word disjunction, as written in Latin, is vel. and so we see that the symbol for disjunction, namely $\lor$, looks like its first letter in its Latin form.  Now we see that  $$ 1+4=5 \quad \text{ or} \quad \text{ July is a month}$$ is a true disjunction; and that $$ 0+4=5 \quad \text{ or} \quad \text{ July is a month} $$ is also a true disjunction. 

$$\begin{array}{c|c|c} p & q & p\lor p \\ \hline  T & T & T \\  T & F & T \\  F & T & T \\  F & F & F \\  \end{array}$$

Definition. The statement $p\rightarrow q$, read “$p$ implies $q$” and called the implication (or conditional) of $p$ and $q$, is false when $p$ is true and $q$ is false, and is true otherwise.

$$\begin{array}{c|c|c} p & q & p\rightarrow q \\ \hline  T & T & T \\  T & F & F \\ F & T & T \\  F & F & T \\  \end{array}$$

In any implication $p\rightarrow q$, $p$ is called the hypothesis (or antecedent or premise) and $q$ is called the consequence (or conclusion). Notice that an implication $p\rightarrow q$ is true when both $p$ and $q$ are true, and is false only in the case that $p$ is true and $q$ is false, and when $p$ is false (no matter what truth value $q$ has) the implication is true.  This way of defining implication is more general than the meaning used in everyday English.  For example, the implication $$\text{If it is cloudy today, then we will not go back to the beach.}$$ is an implication used in normal language, since there is a relationship between the hypotheses and the conclusion. On the other hand, the implication  $$ \text{If today is Monday, then $1+4=6$.} $$ is true every day except Monday, from the definition of implication. Using words and symbols is the usual approach the everyday mathematics.  Here are some common ways to express the conditional $p\rightarrow q$. 

$\qquad $ $p$ implies $q$

$\qquad $ if $p$ then $q$ 

$\qquad $ if $p$, $q$

$\qquad $ $q$, if $p$ 

$\qquad $ $p$ only if $q$

$\qquad $ $p$ is sufficient for $q$

$\qquad $ $q$ is necessary for $p$

$\qquad $ whenever $p$, $q$

$\qquad $ $q$ whenever $p$

Definition. The statement $p\leftrightarrow q$, read “$p$ if and only if $q$” and called the equivalence (or biconditional) of $p$ and $q$, is true if and only if $p$ and $q$ are true or both are false. 

$$\begin{array}{c|c|c} p & q & p\leftrightarrow q \\ \hline  T & T & T \\ T & F & F \\  F & T & F \\  F & F & T \\ \end{array}$$

Note that the biconditional $p\leftrightarrow q$ is true precisely when both implications $q\rightarrow p$ and $p\rightarrow q$ are true.  Here are some common ways to express the biconditional $p\leftrightarrow q.$

$\qquad $ $p$ if and only if  $q$, 

$\qquad $ $p$ is necessary and sufficient for $q$, 

$\qquad $ $p$ is equivalent to $q$, and 

$\qquad $ $p$ and $q$ are equivalent.

As a summary of the truth tables for the logical connectives. The connectives $\downarrow$ and $\uparrow$ will be explored during the exercises. 

$$\begin{array}{c|c|c|c|c|c|c|c} p & q & p\land q & p\lor q & p\rightarrow q & p\leftrightarrow q & p\uparrow q & p\downarrow q  \\ \hline  T & T & T & T & T & T & F & F \\  T & F & F & T & F & F & T &  F \\ F & T & F & T & T & F & T &  F \\  F & F & F & F & T & T & T &  T \end{array}$$

Propositional Logic: Truth Tables and Their Usage

Constructing Truth Tables

From the point of view of logic, it is the structure of a compound statement that makes it important. When constructing the truth table of a statement we will take into account this structure by parsing a statement into simpler statements. 

$$\begin{array}{c|c|c|c} p & q & r & \\ \hline T & T & T & \\T & T & F & \\T & F & T & \\T & F & F & \\F & T & T & \\F & T & F & \\F & F & T & \\F & F & F &\end{array}$$

When constructing compound statements, parentheses are used to specify the order in which the various logical connectives in a compound statement are applied. In particular, the logical connectives in the innermost parentheses are applied first. For example, $(p\land q)\lor (\neg r)$ is the disjunction of $(p\land q)$ and $\neg r$. To cut down on the number of parentheses used, we specify that the negation connective is applied before all other connectives. For instance, $\neg p\lor q$ is the disjunction of $\neg p$ and $q$, namely $(\neg p)\lor q$, not the negation of the conjunction of $p$ and $q$. Further, when working with compound propositions the order from highest priority to lowest is $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$. We agree that, in any truth table, the symbols for the propositional variables $p, q, r, \ldots  $ are in alphabetical order, and to make the rightmost column $T, F, T, F, \ldots, $ the next column leftward $T, T, F, F, \ldots $, and so forth. 

Tautologies, Contradictions, and Contingencies

We can classify statements according to whether or not they are always true, always false, or otherwise. 

Definition. A proposition that is always true, regardless of what truth values are assigned to its statement variables, is called a tautology; a proposition that is always false, regardless of what truth values are assigned to its statement variables, is called a contradiction; and otherwise a proposition is called a contingency.

Notice this truth table has four rows. 

Example. Determine whether or not the statement $$(p\rightarrow (q\land p))\lor (q\rightarrow (p\land q))$$ is a tautology.

Solution. We begin by parsing the statement $(p\rightarrow (q\land p))\lor (q\rightarrow (p\land q))$ into simpler forms, namely, $q\land p$, $p\rightarrow (q\land p)$, and $q\rightarrow (p\land q)$. We place these simpler forms into three columns in the table to aid in the computation of the values in the final column. The following truth table $$ \begin{array}{c<{\, \,\,}|>{\, \,\,}c<{\,\,}|>{\,\,}c|c<{\,\,}|>{\,\,}c|c}  p & q & q\land p & p\rightarrow (q\land p) & q\rightarrow (p\land q) & (p\rightarrow (q\land p))\lor (q\rightarrow (p\land q)) \\ \hline T & T & T & T & T & T  \\ \hline T & F & F & F & T & T  \\ \hline F & T & F & T & F & T  \\ \hline F & F & F & T & T & T \end{array}$$ shows that the statement  $(p\rightarrow (q\land p))\lor (q\rightarrow (p\land q))$  is a tautology because every entry in the last column is true.  More precisely, regardless of what truth values are assigned to its statement variables, $(p\rightarrow (q\land p))\lor (q\rightarrow (p\land q))$ has a true truth value.

Can you write an argument, explaining this? In general if a proposition contains $n$ variables then it takes $2^n$ rows to determine whether a proposition is a tautology or not.  The problem of determining whether any given proposition is a tautology is called the tautology problemIs there a better way to solve the tautology problem than the brute force method of a truth table? Each of the names of the tautologies are listed also.  It is important to know their names as well, as tautologies are usually  referred to by name. We now list several important tautologies, leaving their proofs for the reader as exercises.  

Theorem. (Tautologies Used in Proofs) The following statements are tautologies.
$\qquad (1)$ $p \lor \neg p$ (excluded middle)
$\qquad (2)$ $(p\land q) \rightarrow p$ (simplification)
$\qquad (3)$ $p \rightarrow (p\lor q)$ (construction)
$\qquad (4)$ $((p\lor q)\land \neg p ) \rightarrow q$ (syllogism)
$\qquad (5)$ $(p\land (p\rightarrow q))\rightarrow q$ (modus ponens)
$\qquad (6)$ $(\neg q\land (p\rightarrow q))\rightarrow \neg p$ (modus tollens)
$\qquad (7)$ $(p\rightarrow q) \leftrightarrow (\neg p \lor q)$ (conditional disjunction
$\qquad (8)$ $(p \rightarrow q) \leftrightarrow (\neg q \rightarrow \neg p)$ (contrapositive)
$\qquad (9)$ $((p\rightarrow r) \land (q\rightarrow r))\leftrightarrow ((p\lor q)\rightarrow r )$ (proof by cases)
$\qquad (10)$ $(p\rightarrow (q\land \neg q))\leftrightarrow \neg p$ (indirect proof

Proof. The proof is left for the reader as an exercise.

Theorem. (Order Related Tautologies) The following statements are tautologies.
$\qquad (1)$ $p \rightarrow p$ (reflexive)
$\qquad (2)$ $((p\rightarrow q)\land (q \rightarrow r))\rightarrow(p\rightarrow r)$  (transitivity)
$\qquad (3)$ $((p\leftrightarrow q)\land (q \leftrightarrow r))\rightarrow(p\leftrightarrow r)$ (transitivity)

Proof. The proof is left for the reader as an exercise.

Contrapositive, Converse, and Inverse

Three important statements are associated with any implication $p\rightarrow q$, namely 

$\qquad $ the statement $\neg q\rightarrow \neg p$ is called the contrapositive

$\qquad $ the statement $q\rightarrow p$ is called the converse, and

$\qquad $ the statement $\neg p\rightarrow \neg q$ is called the inverse

of the implication $p\rightarrow q$. It is easy to show that every implication is logically equivalent to its contrapositive. Try it. 

Notice that the inverse and converse of $p\rightarrow q$ are logically equivalent. $$ \begin{array}{c|c|c|c|c|c}  p & q & \neg p & \neg q & \neg p\rightarrow \neg q & q\rightarrow p \\ \hline T & T & F & F & T & T \\ \hline T & F & F & T & T & T \\ \hline F & T & T & F & F & F \\ \hline F & F & T & T & T & T  \end{array} $$ Further, an implication is not necessarily equivalent to its converse (inverse). 

Modus Ponens and Substitution

In propositional logic, modus ponendo ponens (or modus ponens), which is Latin for “the way that affirms by affirming”, is a valid, simple argument form and rule of inference.

Theorem. (Modus Ponens) Let $P$ and $Q$ be statements. If the statements $P$ and $P\rightarrow Q$ are tautologies, then so is the statement $Q$.

Proof. Suppose the statements $P$ and $P\rightarrow Q$ are tautologies. Assume for a contradiction that $Q$ is not a tautology.  Then it must be possible to have a truth assignment to the statement variables of $Q$ which yields false.  However, since $P$ is a tautology and $P\rightarrow Q$ is a tautology, we now have a truth assignment of $P\rightarrow Q$ which yields false. Yet all truth assignments for $P\rightarrow Q$ yield true.  This contradiction shows that the hypothesis that $Q$ is not a tautology can not hold. Therefore $Q$ must be a tautology.

Theorem. (Substitution Rule) Let $P$ be a tautology, and suppose that $P$ contains the distinct statement variables $p_1, p_2, \ldots, p_n$ (and perhaps others as well).  Suppose further that $Q_1, Q_2, \ldots, Q_n$ are statements. Then, if in the tautology $P$, we replace $p_1$ by $Q_1$, replace $p_2$ by $Q_2$, and so on, then the resulting statement is also a tautology.

Proof. This proof is left as an exercise.

Example. Show that the statement  \begin{equation} \label{scsex} (p\land \neg q)\rightarrow [(\neg p\lor \neg q)\rightarrow (p\land \neg q)] \end{equation} is a tautology.

Solution. Notice the compound statement in \eqref{scsex} has the form \begin{equation} \label{tauex2} P\rightarrow (Q\rightarrow P) \end{equation} where $P:=p\land \neg q$ and $Q:=\neg p\lor \neg q$. Therefore, it suffices to verify that \eqref{tauex2} is in fact a tautology. We leave this verification to the reader.

Example. Show that the statement  \begin{equation} \label{scsex2} (p\rightarrow \neg q)\lor \neg (p\rightarrow \neg q) \end{equation} is a tautology.

Solution. It is easy to see that the statement $P\lor \neg P$ is a tautology; and thus we see that \eqref{scsex2} is also a tautology.

Logical Equivalence

In propositional logic, statements $p$ and $q$ are logically equivalent if they have the same semantic meaning.  In other words, two statements are equivalent if they have the same truth value for every possible assignment. Another way to say this is the following: for each assignment of truth values to the simple statements which make up $P$ and $Q$, the statements $P$ and $Q$ have identical truth values. We will see that, from a practical point of view, we can replace a variable in a tautology by any logically equivalent statement and still have a tautology.

Definition. Let $P$ and $Q$ be statements. We say that $P$ is logically equivalent to $Q$, denoted by $P\equiv Q$, provided that $P$ and $Q$ have the same truth-value for every possible choice of truth values of the propositional variables involved in $P$ and $Q$. 

Example. Verify the following are logical equivalencies: \begin{equation} \label{exlogeq} p\rightarrow q \equiv \neg p \lor q \qquad \qquad \neg (p\rightarrow q) \equiv p\land \neg q \end{equation}

Solution. The following truth table clearly demonstrates that $p\rightarrow q$ and $ \neg p\lor q$ are logically equivalent (columns 5 \& 6).  It also shows that $\neg(p\rightarrow q )$ and $ p\land \neg q$ are logically equivalent (columns 7 \& 8).  \begin{equation*} \begin{array}{c|c|c|c||c|c||c|c} p & q & \neg p & \neg q & p\rightarrow q & \neg p\lor q & \neg(p\rightarrow q ) & p\land \neg q  \\ \hline T & T & F & F & \textbf{T} & \textbf{T} & \textbf{F} & \textbf{F} \\  T & F & F & T & \textbf{F} & \textbf{F} & \textbf{T} & \textbf{T} \\  F & T & T & F & \textbf{T} & \textbf{T} & \textbf{F} & \textbf{F} \\  F & F & T & T & \textbf{T} & \textbf{T} & \textbf{F} & \textbf{F} \end{array} \end{equation*}

There are, of course, an infinite number of tautologies and logical equivalences.  However, as we have seen, the method of truth tables is exponential in the number of variables.  Thus we need practical methods of determining whether a given statement is a tautology or whether two given statements are logical equivalent or not. 

Theorem. (Logical Equivalence) Two compound statements $P$ and $Q$ are logically equivalent if and only if the compound statement $P\leftrightarrow Q$ is a tautology. 

Proof. If $P\leftrightarrow Q$ is a tautology, then any assignment of truth values to the statement variables makes the statement $P\leftrightarrow Q$  true, that is, it gives the same truth values to both $P$ and $Q$. Therefore, $P$ and $Q$ are logically equivalent. Conversely, if $P$ and $Q$ are logically equivalent, then any assignment of truth values to the statement variables of $P$ and $Q$ gives the same truth value to both $P$ and $Q$.  Whence $P\leftrightarrow Q$ is a tautology.

Theorem. (Properties of Logical Equivalence) Let $p$ and $q$ be statements. 

The commutative properties
$\qquad $ $(p\land q)\equiv  (q\land p)$
$\qquad $ $(p\lor q)\equiv (q\lor p)$

The associative properties
$\qquad $ $((p\land q)\land r) \equiv (p\land (q\land r))$
$\qquad $ $((p\lor q)\lor r) \equiv (p\lor (q\lor r))$

The distributive properties
$\qquad $ $(p\land (q\lor r)) \equiv ((p\land q)\lor (p\land r))$
$\qquad $ $(p\lor (q\land r)) \equiv ((p\lor q)\land (p\lor r))$

The idempotent properties
$\qquad $ $p\lor p \equiv p$
$\qquad $ $p\land p \equiv p$

De Morgan laws
$\qquad $ $\neg (p\land q)\equiv \neg p \lor \neg q $
$\qquad $ $\neg (p\lor q)\equiv \neg p \land \neg q$

Law of excluded middle:
$\qquad $ $p\lor \neg p$ is a tautology 
$\qquad $ $p\land \neg p$ is a contradiction

Proof. The proof is left for the reader as an exercise.

Theorem. (Properties of Logical Equivalence II) Let $p$ and $q$ be statements. 
An implication and contrapositive are logically equivalent: $$ p\rightarrow q \equiv \neg p \rightarrow \neg q. $$
The converse and inverse of the implication $p\rightarrow q$ are logically equivalent: $$ q\rightarrow p \equiv \neg q \rightarrow \neg p. $$
Let $T$ denote a tautology and $F$ denote a contradiction. Then 
$\qquad $ $p\lor T \equiv T$
$\qquad $ $p\land T \equiv p$
$\qquad $ $p\lor F\equiv p$
$\qquad $ $p\land F \equiv F$

Proof. The proof is left for the reader as an exercise.

Theorem. (Logical Equivalence/Substituton) Let $P$ and $Q$ be logically equivalent statements, and suppose that $P$ and $Q$ contain the statement variables $p_1, p_2, \ldots, p_n$ (and possible others). Suppose further that $Q_1, Q_2, \ldots, Q_n$ are statements. Then, if we replace $p_1$ by $Q_1$, replace $p_2$ by $Q_2$, and so on, in both $P$ and $Q$, then the resulting statements are still logically equivalent.

Proof. Denote the statements obtained by replacing $p_1$ by $Q_1$, $p_2$ by $Q_2$, and so on, in $P$ and $Q$ by $P’$ and $Q’$, respectively.  We will show that $P’$ and $Q’$ are logically equivalent.  Since, $P’$ and $Q’$ are logically equivalent if and only if the statement $P’\leftrightarrow Q’$ is a tautology.  Now since our hypothesis is that $P$ and $Q$ are logically equivalent we know that $P\leftrightarrow Q$ is a tautology. Therefore, we see that $P’\leftrightarrow Q’$ is a tautology as needed.  We summarize the proof as follows: \begin{align*} & P, Q \text{ are logically equivalent } \\ & \Longleftrightarrow P\leftrightarrow Q \text{ is a tautology} \\ & \implies P’\leftrightarrow Q’ \text{ is a tautology}  \\ & \Longleftrightarrow P’, Q’ \text{ are logically equivalent } \end{align*}

Example. Use properties of logical equivalence to show that  \begin{equation} \neg (p\leftrightarrow q)\equiv \neg q\leftrightarrow p \end{equation} is a tautology.

Solution. We apply the properties of logical equivalence as follows: \begin{align*} \neg (p\leftrightarrow q) & \equiv \neg [(p\rightarrow q)\land (q\rightarrow p)] \\ & \equiv \neg (p\rightarrow q)\lor \neg (q\rightarrow p) \\ &  \equiv (p\land \neg q) \lor (q\land \neg p) \\ &  \equiv [(p\land \neg q)\lor q]\land [(p\land \neg q)\lor \neg p] \\ &  \equiv [(p\lor q)\land (\neg q\lor q)] \land [(p\lor \neg p) \land (\neg q \lor \neg p) ] \qquad   \\ &  \equiv [(p\lor q) \land T] \land [T\land (\neg q \lor \neg p)] \\ &  \equiv (p\lor q) \land (\neg q \lor \neg p)  \\ &  \equiv (q\lor p) \land (\neg p \lor \neg q)  \\ &  \equiv (\neg q\rightarrow p)\land (p\rightarrow \neg q) \\ &  \equiv \neg q \leftrightarrow p \end{align*}


Exercise. Consider the following statement: $$ \text{If $x=0$, then $x^2=0$ and if $x^2=0$, then $x=0$.} $$ (a) Express this statement in symbolic form using only conjunction and conditional.  (b) Express this statement in symbolic form using only biconditional.

In the following exercises, rewrite each statement in the form “If …, then …”.

Exercise. A neccessary condition for two triangles to be congruent is that three sides of one be equal respectively to the three sides of the other. 

Exercise. A sufficient condition for two triangles to be congruent is that the three sides of one be equal respectively to the three sides of the other.

Exercise. The base angles of an isosceles triangle are equal.

In the following exercises, construct a truth table and identify whether the proposition is either a tautology, contradiction, or a contingency.  

Exercise. $(p\land q)\rightarrow (p\lor q)$

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

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

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

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

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

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

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

In the following exercises, show the following statements are contingencies.

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

Exercise. $((p\land q)\rightarrow (p\lor q))\rightarrow p\land q$

Exercise. (a) Find a tautology that contains the statement  $p\land (q\rightarrow \neg p)$. (b) Find a contingency that contains the statement  $(p\land q)\land (p\lor \neg q)$. (c) Find a contradiction that contains the statement $p\land (p\land \neg q)$.

Exercise. Construct truth tables for each of the following and arrange them so that each compound statement implies all the following ones. (a) $\neg \, p\leftrightarrow q$ (b) $p \rightarrow (\neg \, p\rightarrow q )$ (c) $\neg \, ( p\rightarrow (q\rightarrow p ) )$ (d) $p\lor q$ (e) $\neg \, p \land q$

Exercise. Write working negations of the following propositions and propositional forms.  (a) $X\lor (Y\land Z)$ (b) $Y\land (\neg Z\land \neg X)$ (c) $(X\lor \neg Y)\land \neg(Z\land \neg X)$ (d) $Z\land ((X\lor \neg Y)\land W)$.

Exercise. (a) Explain why all propositional forms with just one variable are logically equivalent with one of the following four: $P$ or $\neg P$ or $P\lor \neg P$ or $P\land \neg P$ (b) Explain why all propositional forms with two variables are logically equivalent with 1 of 16 possibilities.  (c) Using only $\lor$ and $\land$, together with the variables $P$ and $Q$, give examples of all 16 possibilities in part (b), using the fewest number of symbols. (d) Find a formula for the number of logically nonequivalent types of propositional forms of three variables.  Repeat with $n$ variables.  Explain why your formulas are correct.  (e) Explain how to rewrite all of the possibilities in part (c), using only $\lor$ and $\neg$. Repeat using only $\land$ and $\neg$.

In the following exercises, write the converse, contrapositive, and inverse of each statement.  Further, determine whether the given statement and/or its converse is true. 

Exercise. If $x\neq 0$, then $x^2\neq 0$.

Exercise. If $xy=0$, then $x=0$

Exercise. If $x$ is a real number, then $x$ is a rational number.

Exercise. If $x$ is positive and $x^2=4$, then $x=2$.

Exercise. If $x\neq 2$ and $x^2+3x+1=0$, then $x=1$.

Exercise. If $n$ is an even integer or a prime number, then $n$ is not an even nonnegative integer.

A collection of logical connectives is called functionally complete if every compound statement is logically equivalent to a compound statement involving only these logical connectives. 

Exercise. Show that $\neg$, $\lor$, and $\land$ form a functionally complete collection of logical connectives.

Exercise. Show that $\neg$ and $\lor$ form a functionally complete collection of logical connectives.

Exercise. Show that $\neg$ and $\land$ form a functionally complete collection of logical connectives.

Exercise. In this exercise we will show that $\uparrow$ forms a functionally complete collection of logical connectives. (a) Show that $p\downarrow p$ is logically equivalent to $\neg p$. (b) Show that $(p\downarrow q)\downarrow (p\downarrow q)$ is logically equivalent to $p\lor q$. 

Exercise. Show that $\neg$ and $\rightarrow$ form a functionally complete collection of logical connectives.

Exercise. (a) Show that the five connectives  $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$ can each be defined in terms of only $\uparrow$.  (b) Do the same as (a) with $\downarrow$.

Exercise. Prove that if $P$ is logically equivalent to $Q$, and $Q$ is logically equivalent to $R$, then $P$ is logically equivalent to $R$.

Exercise. Prove that any two of the following three statements are logically equivalent.  (1) $p\rightarrow q$, (2) $(p\land \neg q)\rightarrow \neg p$, and (3) $(p\land \neg q)\rightarrow q$.

In the following exercises, prove the logical equivalencies.

Exercise. $\neg[(p\leftrightarrow q)\lor (p\land \neg q)]\equiv \neg(p\leftrightarrow q)\land \neg(p\land \neg q)$

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

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

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