2.5: Logical Equivalences

Tautology & Contradiction

Definition

A tautology is a proposition that is always true, regardless of the truth values of the propositional variables it contains.

Definition

A proposition that is always false is called a contradiction.

 A proposition that is neither a tautology nor a contradiction is called a contingency. The term contingency is not as widely used as the terms tautology and contradiction.

Example $\PageIndex{1}\label{eg:logiceq-01}$

From the following truth table $$\begin{array}{|c|c|c|c|} \hline p & \overline{p} & p \vee \overline{p} & p \wedge \overline{p} \\ \hline \text{T} & \text{F} & \text{T} & \text{F} \\ \text{F} & \text{T} & \text{T} & \text{F} \\ \hline \end{array}$$ we gather that $p\vee\overline{p}$ is a tautology, and $p\wedge\overline{p}$ is a contradiction.

In words, $p\vee\overline{p}$ says that either the statement $p$ is true, or the statement $\overline{p}$ is true (that is, $p$ is false). This claim is always true.

The compound statement $p\wedge\overline{p}$ claims that $p$ is true, and at the same time, $\overline{p}$ is also true (which means $p$ is false). This is clearly impossible. Hence, $p\wedge \overline{p}$ must be false.

 

Example $\PageIndex{2}\label{eg:logiceq-02}$

Show that $(p \Rightarrow q) \Leftrightarrow (\overline{q} \Rightarrow \overline{p})$ is a tautology.

Answer

We can use a truth table to verify the claim. $$\begin{array}{|*{7}{c|}} \hline p & q & p\Rightarrow q & \overline{q} & \overline{p} & \overline{q}\Rightarrow\overline{p} & (p \Rightarrow q) \Leftrightarrow (\overline{q} \Rightarrow \overline{p}) \\ \hline \text{T} & \text{T} & \text{T} & \text{T} &  \text{T} & \text{F} & \text{T} \\ \text{T} & \text{F} & \text{F} & \text{T} & \text{F} & \text{F} & \text{T} \\ \text{F} & \text{T} & \text{T} & \text{F} & \text{T} & \text{T} & \text{T} \\ \text{F} & \text{F} & \text{T} & \text{T} & \text{T} & \text{T} & \text{T} \\ \hline \end{array}$$ Note how we work on each component of the compound statement separately before putting them together to obtain the final answer.

Example $\PageIndex{3}\label{eg:logiceq-03}$

Show that the argument

“If $p$ and $q$, then $r$. Therefore, if not $r$, then not $p$ or not $q$.”

is valid. In other words, show that the logic used in the argument is correct.

Answer

Symbolically, the argument says $$[(p \wedge q) \Rightarrow r] \Rightarrow [\overline{r} \Rightarrow (\overline{p} \vee \overline{q})]. \label{eqn:tautology}$$ We want to show that it is a tautology. It is easy to verify with a truth table. We can also argue that this compound statement is always true by showing that it can never be false.

Suppose, on the contrary, that ([eqn:tautology]) is false for some choices of $p$, $q$, and $r$. Then $$(p \wedge q) \Rightarrow r \quad \mbox{must be true}, \qquad\mbox{and}\qquad \overline{r} \Rightarrow (\overline{p} \vee \overline{q}) \quad \mbox{must be false}.$$ For the second implication to be false, we need $$\overline{r} \quad\mbox{to be true}, \qquad\mbox{and}\qquad \overline{p} \vee \overline{q} \quad\mbox{to be false}.$$ They in turn imply that $r$ is false, and both $\overline{p}$ and $\overline{q}$ are false; hence both $p$ and $q$ are true. This would make $(p \wedge q) \Rightarrow r$ false, contradicting the assumption that it is true. Thus, ([eqn:tautology]) cannot be false, it must be a tautology.

hands-on exercise $\PageIndex{1}\label{he:logiceq-01}$

Use a truth table to show that $$[(p \wedge q) \Rightarrow r] \Rightarrow [\overline{r} \Rightarrow (\overline{p} \vee \overline{q})]$$ is a tautology.

 

Answer

We need eight combinations of truth values in $p$, $q$, and $r$. We list the truth values according to the following convention. In the first column for the truth values of $p$, fill the upper half with T and the lower half with F. In the next column for the truth values of $q$, repeat the same pattern, separately, with the upper half and the lower half. So we split the upper half of the second column into two halves, fill the top half with T and the lower half with F. Likewise, split the lower half of the second column into two halves, fill the top half with T and the lower half with F. Repeat the same pattern with the third column for the truth values of $r$, and so on if we have more propositional variables.

Complete the following table: $$\begin{array}{|*{11}{c|}} \hline p & q & r & p\wedge q & (p\wedge q)\Rightarrow r & \overline{r} & \overline{p} & \overline{q} & \overline{p}\vee\overline{q} & \overline{r} \Rightarrow (\overline{p}\vee\overline{q}) & [(p \wedge q) \Rightarrow r] \Rightarrow [\overline{r}\Rightarrow(\overline{p} \vee \overline{q})] \\ \hline \text{T} & \text{T} & \text{T} &&&&&&&& \\ \text{T} & \text{T} & \text{F} &&&&&&&& \\ \text{T} & \text{F} & \text{T} &&&&&&&& \\ \text{T} & \text{F} & \text{F} &&&&&&&& \\ \text{F} & \text{T} & \text{T} &&&&&&&& \\ \text{F} & \text{T} & \text{F} &&&&&&&& \\ \text{F} & \text{F} & \text{T} &&&&&&&& \\ \text{F} & \text{F} & \text{F} &&&&&&&& \\ \hline \end{array}$$ Question: If there are four propositional variables in a proposition, how many rows are there in the truth table?

 

Biconditional and Equivalence

Note

Two logical formulas $p$ and $q$ are logically equivalent, denoted $p\equiv q,$ (defined in section 2.2) if and only if  $p \Leftrightarrow q$ is a tautology.

We are not saying that $p$ is equal to $q$. Since $p$ and $q$ represent two different statements, they cannot be the same. What we are saying is, they always produce the same truth value, regardless of the truth values of the underlying propositional variables. That is why we write $p\equiv q$ instead of $p=q$.

Example $\PageIndex{4}\label{eg:logiceq-04}$

We have learned that $$p\Leftrightarrow q \equiv (p\Rightarrow q) \wedge (q\Rightarrow p),$$ which is the reason why we call $p\Leftrightarrow q$ a biconditional statement.

Example $\PageIndex{5}\label{eg:logiceq-05}$

 

Use truth tables to verify the following equivalent statements.

• $p \Rightarrow q \equiv \overline{p} \vee q$. [equiv1]
• $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$. [equiv2]

Answer

The truth tables for (a) and (b) are depicted below. $$\begin{array}{|*{5}{c|}} \hline p & q & p\Rightarrow q & \overline{p} & \overline{p}\vee q \\ \hline \text{T} & \text{T} & \text{T} & \text{F} & \text{T} \\ \text{T} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{T} & \text{T} & \text{T} & \text{T} \\ \text{F} & \text{F} & \text{T} & \text{T} & \text{T} \\ \hline \end{array}$$ $$% \arraygap{1.25} \begin{array}{|*{8}{c|}} \hline p & q & r & q\vee r & p\wedge (q\vee r) & p\wedge q & q\wedge r & (p\wedge q)\vee(p\wedge r) \\ \hline \text{T} & \text{T} & \text{T} & \text{T} & \text{T}\phantom{(q\vee{})} & \text{T} & \text{T} & \text{T} \\ \text{T} & \text{T} & \text{F} & \text{T} & \text{T}\phantom{(q\vee{})} & \text{T} & \text{F} & \text{T} \\ \text{T} & \text{F} & \text{T} & \text{T} & \text{T}\phantom{(q\vee{})} & \text{F} & \text{T} & \text{T} \\ \text{T} & \text{F} & \text{F} & \text{F} & \text{F}\phantom{(q\vee{})} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{T} & \text{T} & \text{T} & \text{F}\phantom{(q\vee{})} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{T} & \text{F} & \text{T} & \text{F}\phantom{(q\vee{})} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{T} & \text{T} & \text{F}\phantom{(q\vee{})} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{F} & \text{T} & \text{F}\phantom{(q\vee{})} & \text{F} & \text{F} & \text{F} \\ \hline \end{array}$$ Example ([equiv1]) is an important result. It says that $p \Rightarrow q$ is true when one of these two things happen: (i) when $p$ is false, (ii) otherwise (when $p$ is true) $q$ must be true.

hands-on exercise $\PageIndex{2}\label{he:logiceq-02}$

Use truth tables to establish these logical equivalences.

1. $p \Rightarrow q \equiv \overline{q} \Rightarrow \overline{p}$
2. $p \vee p \equiv p$
3. $p \wedge q \equiv \overline{\overline{p} \vee \overline{q}}$
4. $p \Leftrightarrow q \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)$

 

Answer

We have set up the table for (a), and leave the rest to you.

$$\begin{array}[t]{|c|c|c|c|c|c|} \hline p & q & p\Rightarrow q & \overline{q} & \overline{p} & \overline{q}\Rightarrow\overline{p} \\ \hline \text{T} & \text{T} &&&& \\ \text{T} & \text{F} &&&& \\ \text{F} & \text{T} &&&& \\ \text{F} & \text{F} &&&& \\ \hline \end{array}$$

hands-on exercise $\PageIndex{3}\label{he:logiceq-03}$

 

The logical connective exclusive or, denoted $p\veebar q$, means either $p$ or $q$ but not both. Consequently, $$p\veebar q \equiv (p\vee q) \wedge \overline{(p\wedge q)} \equiv (p\wedge\overline{q}) \vee (\overline{p}\wedge q).$$ Construct a truth table to verify this claim

 

Properties

Properties of Logical Equivalence. Denote by $T$ and $F$ a tautology and a contradiction, respectively. We have the following properties for any propositional variables $p$, $q$, and $r$.

1. Commutative properties: $\begin{array}[t]{l} p \vee q \equiv q \vee p, \\ p \wedge q \equiv q \wedge p. \end{array}$

2. Associative properties: $\begin{array}[t]{l} (p \vee q) \vee r \equiv p \vee (q \vee r), \\ (p \wedge q) \wedge r \equiv p \wedge (q \wedge r). \end{array}$

3. Distributive laws: $\begin{array}[t]{l} p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r), \\ p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r). \end{array}$

4. Idempotent laws: $\begin{array}[t]{l} p \vee p \equiv p, \\ p \wedge p \equiv p. \end{array}$

5. De Morgan’s laws: $\begin{array}[t]{l} \overline{p\vee q} \equiv \overline{p}\wedge\overline{q}, \\ \overline{p\wedge q} \equiv \overline{p}\vee \overline{q}. \end{array}$

6. Laws of the excluded middle, or inverse laws: $\begin{array}[t]{l} p \vee \overline{p} \equiv T, \\ p \wedge \overline{p} \equiv F. \end{array}$

7. Identity laws: $\begin{array}[t]{l} p \vee F \equiv p, \\ p \wedge T \equiv p. \end{array}$

8. Domination laws: $\begin{array}[t]{l} p \vee T \equiv T, \\ p \wedge F \equiv F. \end{array}$

9. Equivalence of an implication and its contrapositive: $p \Rightarrow q \equiv \overline{q} \Rightarrow \overline{p}$.

10. Writing an implication as a disjunction: $p \Rightarrow q \equiv \overline{p} \vee q$.

11. The negation of an implication: $\overline{p \Rightarrow q} \equiv p \wedge \overline{q}$

Be sure you understand and memorize the last three equivalences, because we will use them frequently in the rest of the course.

It may not be easy to memorize the names of all these properties; however, they should all make sense to you.  The important name is De Morgan's laws.  Let us explain them in words, and compare them to similar operations on the real numbers,

1. Commutative properties: In short, they say that “the order of operation does not matter.” It does not matter which of the two logical statements comes first, the result from conjunction and disjunction always produces the same truth value. Compare this to addition of real numbers: $x+y=y+x$. Subtraction is not commutative, because it is not always true that $x-y=y-x$. This explains why we have to make sure that an operation is commutative.

2. Associative properties: Roughly speaking, these properties also say that “the order of operation does not matter.” However, there is a key difference between them and the commutative properties.

   • Commutative properties apply to operations on two logical statements, but associative properties involves three logical statements. Since $\wedge$ and $\vee$ are binary operations, we can only work on a pair of statements at a time. Given the three statements $p$, $q$, and $r$, appearing in that order, which pair of statements should we operate on first? The answer is: it does not matter. It is the order of grouping (hence the term associative) that does not matter in associative properties.

   • The important consequence of the associative property is: since it does not matter on which pair of statements we should carry out the operation first, we can eliminate the parentheses and write, for example, $$p\vee q\vee r$$ without worrying about any confusion.

   • Not all operations are associative. Subtraction is not associative. Given three numbers 5, 7, and 4, in that order, how should we carry out two subtractions? Which interpretation should we use: $$(5-7)-4, \qquad\mbox{or}\qquad 5-(7-4)?$$ Since they lead to different results, we have to be careful where to place the parentheses.

3. Distributive laws: When we mix two different operations on three logical statements, one of them has to work on a pair of statements first, forming an “inner” operation. This is followed by the “outer” operation to complete the compound statement. Distributive laws say that we can distribute the “outer” operation over the inner one.

4. Idempotent laws: When an operation is applied to a pair of identical logical statements, the result is the same logical statement. Compare this to the equation $x^2=x$, where $x$ is a real number. It is true only when $x=0$ or $x=1$. But the logical equivalences $p\vee p\equiv p$ and $p\wedge p\equiv p$ are true for all $p$.

5. De Morgan’s laws: When we negate a disjunction (respectively, a conjunction), we have to negate the two logical statements, and change the operation from disjunction to conjunction (respectively, from conjunction to a disjunction).

6. Laws of the excluded middle, or inverse laws: Any statement is either true or false, hence $p\vee\overline{p}$ is always true. Likewise, a statement cannot be both true and false at the same time, hence $p\wedge\overline{p}$ is always false.

7. Identity laws: Compare them to the equation $x\cdot1=x$: the value of $x$ is unchanged after multiplying by 1. We call the number 1 the multiplicative identity. For logical operations, the identity for disjunction is F, and the identity for conjunction is T.

8. Domination laws: Compare them to the equation $x\cdot0=0$ for real numbers: the result is always 0, regardless of the value $x$. The “zero” for disjunction is T, and the “zero” for conjunction is F.

Example $\PageIndex{6}\label{eg:logiceq-07}$

What is the negation of $2\leq x\leq 3$? Give a logical explanation as well as a graphical explanation.

Answer

The inequality $2\leq x\leq 3$ means $$(x\geq 2) \wedge (x\leq 3).$$ Its negation, according to De Morgan’s laws, is $$(x<2) \vee (x>3).$$ The inequality $2\leq x\leq 3$ yields a closed interval. Its negation yields two open intervals. Their graphical representations on the real number line are depicted below.

(130,60)(-20,-45) (-20,0)(1,0)130 (30, 0)(30,0)2 (20,-25)(20,20)$2$ (50,-25)(20,20)$3$ ( 0,-50)(90,20)$(x\geq 2)\wedge(x\leq 3)$ (30, 0)(1,0)30

(130,60)(-20,-45) (-20,0)(1,0)130 (30, 0)(30,0)2 (20,-25)(20,20)$2$ (50,-25)(20,20)$3$ ( 0,-50)(90,20)$(x<2)\vee(x>3)$ (-20, 0)(1,0)48 ( 62, 0)(1,0)48

Take note of the two endpoints 2 and 3. They change from inclusion to exclusion when we take negation.

hands-on exercise $\PageIndex{4}\label{he:logiceq-04}$

Since $0\leq x\leq 1$ means “$x\geq 0$ and $x\leq 1$,” its negation should be “$x<0$ or $x>1$”.  Explain why it is inappropriate, and indeed incorrect, to write “$0>x>1$.”

hands-on exercise $\PageIndex{5}\label{he:logiceq-05}$

Expand $(p\vee q) \wedge (r\vee s)$.

Example $\PageIndex{7}\label{eg:logiceq-09}$

 

We have used a truth table to verify that $$[(p \wedge q) \Rightarrow r] \Rightarrow [\overline{r} \Rightarrow (\overline{p} \vee \overline{q})]$$ is a tautology. We can use the properties of logical equivalence to show that this compound statement is logically equivalent to $T$. This kind of proof is usually more difficult to follow, so it is a good idea to supply the explanation in each step. Here is a complete proof: $$% \arraygap{1.2} \begin{array}{lcl@{\quad}l} [(p \wedge q) \Rightarrow r] \Rightarrow [\overline{r} \Rightarrow (\overline{p} \vee \overline{q})] &\equiv& \overline{(p \wedge q) \Rightarrow r} \vee [\overline{r} \Rightarrow (\overline{p} \vee \overline{q})] & \mbox{(implication as disjunction)} \\ &\equiv& \overline{(p \wedge q) \Rightarrow r} \vee [\overline{\overline{p} \vee \overline{q}} \Rightarrow r] & \mbox{(implication as disjunction)} \\ &\equiv& \overline{(p \wedge q) \Rightarrow r} \vee [(p \wedge q) \Rightarrow r] & \mbox{(De Morgan's law)} \\ &\equiv& T & \mbox{(inverse law)} \end{array}$$ This is precisely what we called the left-to-right method for proving an identity (in this case, a logical equivalence).

Example $\PageIndex{8}\label{eg:logiceq-10}$

Write $\overline{p \Rightarrow q}$ as a conjunction.

 

Answer

It is important to remember that $$\overline{p\Rightarrow q} \not\equiv q\Rightarrow p,$$ and $$\overline{p\Rightarrow q} \not\equiv \overline{p}\Rightarrow\overline{q}$$ either. Instead, since $p\Rightarrow q \equiv \overline{p}\vee q$, it follows from De Morgan’s law that $$\overline{p \Rightarrow q} \equiv \overline{\overline{p} \vee q} \equiv p \wedge \overline{q}.$$ Alternatively, we can argue as follows. Interpret $\overline{p \Rightarrow q}$ as saying $p \Rightarrow q$ is false. This requires $p$ to be true and $q$ to be false, which translates into $p \wedge \overline{q}$. Thus, $\overline{p\Rightarrow q} \equiv p\wedge \overline{q}$.

 

Summary and Review

• Two logical statements are logically equivalent if they always produce the same truth value.
• Consequently, $p\equiv q$ is same as saying $p\Leftrightarrow q$ is a tautology.
• Beside distributive and De Morgan’s laws, remember these two equivalences as well; they are very helpful when dealing with implications. $$p \Rightarrow q \equiv \overline{q} \Rightarrow \overline{p} \qquad\mbox{and}\qquad p \Rightarrow q \equiv \overline{p} \vee q.$$

Exercises $\PageIndex{}$    

Exercise $\PageIndex{1}\label{ex:logiceq-01}$

Use a truth table to verify the De Morgan’s law $\overline{p\vee q} \equiv \overline{p}\wedge\overline{q}$.

Answer

$\begin{array}[t]{ {|c | c | c | c | c | c |}} \hline p & q & p\vee q & \overline{p\vee q} & \overline{p} & \overline{q} & \overline{p}\wedge\overline{q} \\ \hline T & T & T & F & F & F & F \\ T & F & T & F & F & T & F \\ F & T & T & F & T & F & F \\ F & F &F & T & T & T & T \\ \hline \end{array}$

Exercise $\PageIndex{2}\label{ex:logiceq-02}$

Use truth tables to verify the two associative properties.

Exercise $\PageIndex{3}\label{ex:logiceq-03}$

Construct a truth table for each formula below. Which ones are tautologies?

1. $(\overline{p} \vee q)\Rightarrow p$
2. $(p\Rightarrow q) \vee (p\Rightarrow \overline{q})$
3. $(p\Rightarrow q) \Rightarrow r$

Answer

Only (b) is a tautology, as indicated in the truth tables below.

(a) $\begin{array}[t]{|*{5}{c|}} \hline p & q & \overline{p} & \overline{p}\vee q & (\overline{p}\vee q)\Rightarrow p \\ \hline T & T & F &  T & \qquad\;T \\ T & F & F & F & \qquad\;T \\ F & T & T & T & \qquad\; F \\ F & F & T & T & \qquad\; F \\ \hline \end{array}$

(b) $\begin{array}[t]{|*{6}{c|}} \hline p & q & p\Rightarrow q & \overline{q} & p\Rightarrow\overline{q} & (p\Rightarrow q)\vee(p\Rightarrow\overline{q}) \\ \hline T &T &T & F & F &T \\ T &F &F & T & T &T \\ F &T &T & F & T &T \\ F &F &T & T & T &T \\ \hline \end{array}$

(c) $\begin{array}[t]{|*{5}{c|}} \hline p & q & r & p\Rightarrow q & (p\Rightarrow q)\Rightarrow r \\ \hline T &T &T & T & \qquad\quad T \\ T & T & F & T & \qquad\quad F \\ T &F &T & F & \qquad\quad T \\ T &F &F & F & \qquad\quad T \\ F &T &T & T & \qquad\quad T \\ F &T &F & T & \qquad\quad F \\ F &F &T & T & \qquad\quad T \\ F &F &F & T & \qquad\quad F \\ \hline \end{array}$

Exercise $\PageIndex{4}\label{ex:logiceq-04}$

Use truth tables to verify these logical equivalences.

1. $(p\wedge q)\Leftrightarrow p \equiv p\Rightarrow q$
2. $(p\wedge q)\Rightarrow r \equiv p\Rightarrow(\overline{q}\vee r)$
3. $(p\Rightarrow\overline{q}) \wedge (p\Rightarrow\overline{r}) \equiv \overline{p\wedge(q\vee r)}$

 

Exercise $\PageIndex{5}\label{ex:logiceq-05}$

Use only the properties of logical equivalences to verify (b) and (c) in Problem 4.

Answer

The proofs are displayed below without explanations. Be sure to fill them in.

(b) $\begin{array}[t]{lcl@{\quad(\hskip1.5in)}} (p\wedge q)\Rightarrow r &\equiv& \overline{p\wedge q}\vee r \\ &\equiv& (\overline{p}\vee\overline{q})\vee r \\ &\equiv& \overline{p}\vee(\overline{q}\vee r) \\ &\equiv& p\Rightarrow(\overline{q}\vee r) \end{array}$

(c) $\begin{array}[t]{lcl@{\quad(\hskip1.5in)}} (p\Rightarrow\overline{q}) \wedge (p\Rightarrow\overline{r}) &\equiv& (\overline{p}\vee\overline{q}) \wedge (\overline{p}\vee\overline{r}) \\ &\equiv& \overline{p}\vee(\overline{q}\wedge\overline{r}) \\ &\equiv& \overline{p}\vee\overline{q\vee r} \\ &\equiv& \overline{p\wedge(q\vee r)} \end{array}$

Exercise $\PageIndex{6}\label{ex:logiceq-06}$

 

Determine whether formulas $u$ and $v$ are logically equivalent (you may use truth tables or properties of logical equivalences).

$u:\;(p\Rightarrow q)\wedge (p\Rightarrow\overline{q})$

$v:\;\overline{p}$

$u:\;p\Rightarrow q$

$v:\;q\Rightarrow p$

$u:\;p\Leftrightarrow q$

$v:\;q\Leftrightarrow p$

$u:\;(p\Rightarrow q)\Rightarrow r$

$v:\;p\Rightarrow(q\Rightarrow r)$

Exercise $\PageIndex{7}\label{ex:logiceq-07}$

Find the converse, inverse, and contrapositive of these implications.

1. If triangle $ABC$ is isosceles and contains an angle of 45 degrees, then $ABC$ is a right triangle.
2. If quadrilateral $ABCD$ is a square, then it is both a rectangle and a rhombus.
3. If quadrilateral $ABCD$ has two sides of equal length, then it is either a rectangle or a rhombus.

Answer

(a)

Converse:	If triangle $ABC$ is a right triangle, then $ABC$ is isosceles
	and contains an angle of 45 degrees.
Inverse:	If triangle $ABC$ is not isosceles or does not contain an angle
	of 45 degrees, then $ABC$ is not a right triangle.
Contrapositive:	If triangle $ABC$ is not a right triangle, then $ABC$ is not isosceles
	or does not contain an angle of 45 degrees.

(b)

Converse:	If quadrilateral $ABCD$ is both a rectangle and a rhombus,
	then $ABCD$ is a square.
Inverse:	If quadrilateral $ABCD$ is not a square,
	then it is not a rectangle or not a rhombus.
Contrapositive:	If quadrilateral $ABCD$ is not a rectangle or not a rhombus,
	then $ABCD$ is not a square.

 

(c)

Converse:	If quadrilateral $ABCD$ is either a rectangle or a rhombus,
	then $ABCD$ has two sides of equal length.
Inverse:	If quadrilateral $ABCD$ is does not have two sides of equal length,
	then it is not a rectangle and it is not a rhombus.
Contrapositive:	If quadrilateral $ABCD$ is not a rectangle and it is not a rhombus,
	then $ABCD$ is does not have two sides of equal length.

 

Exercise $\PageIndex{8}\label{ex:logiceq-08}$

Negate the following implications:

1. $x^2>0 \Rightarrow x>0$.
2. If $PQRS$ is a square, then $PQRS$ is a parallelogram.
3. If $n>1$ is prime, then $n+1$ is composite.
4. If $x$ and $y$ are integers such that $xy\geq1$, then either $x\geq1$ or $y\geq1$.

Exercise $\PageIndex{9}\label{ex:logiceq-09}$

Determine whether the following formulas are true or false:

1. $\overline{p\Leftrightarrow q} \equiv \overline{p} \Leftrightarrow \overline{q}$
2. $(p\Rightarrow q) \wedge (p\Rightarrow\overline{q}) \equiv \overline{p}$
3. $p\Rightarrow q \equiv q\Rightarrow p$

Answer

(a) false (b) true (c) false

Exercise $\PageIndex{10}\label{ex:logiceq-10}$

Determine whether the following formulas are true or false:

1. $(p\Rightarrow q)\Rightarrow r \equiv p\Rightarrow (q\Rightarrow r)$
2. $p\Rightarrow (q\vee r) \equiv (p\Rightarrow q) \vee (p\Rightarrow r)$
3. $p\Rightarrow (q\wedge r) \equiv (p\Rightarrow q) \wedge (p\Rightarrow r)$

Exercise $\PageIndex{11}\label{ex:logiceq-11}$

Which of the following statements are equivalent to the statement “if $x^2>0$, then $x>0$”?

1. If $x>0$, then $x^2>0$.
2. If $x\leq0$, then $x^2\leq0$.
3. If $x^2\leq0$, then $x\leq0$.
4. If $x^2\not>0$, then $x\not>0$.

Answer

Only (b).

Exercise $\PageIndex{12}\label{ex:logiceq-12}$

Determine whether the following formulas are tautologies, contradictions, or neither:

1. $(p\Rightarrow q) \wedge \overline{p}$
2. $(p\Rightarrow\overline{q}) \wedge (p\wedge q)$
3. $(p\Rightarrow\overline{q}) \wedge q$

Exercise $\PageIndex{13}\label{ex:logiceq-13}$

Simplify the following formulas:

1. $p\wedge(p\wedge q)$
2. $\overline{\overline{p}\vee q}$
3. $\overline{p\Rightarrow\overline{q}}$

Answer

(a) $p\wedge q$
(b) $p\wedge\overline{q}$
(c) $p\wedge q$

Exercise $\PageIndex{14}\label{ex:logiceq-14}$

Simplify the following formulas:

1. $(p\Rightarrow\overline{q}) \wedge (\overline{q}\Rightarrow p)$
2. $\overline{p\wedge\overline{q}}$
3. $p\wedge(\overline{p}\vee q)$

 

Exercise $\PageIndex{15}$

T stands for a tautology & F stands for a contradiction. 

True or False?

a. $F\rightarrow\overline{q}$

b. $p\vee T$

c.  $F \wedge p$

d. $\overline{T}\vee F$

Answer

(a) true (b) true (c) false (d) false

 

Exercise $\PageIndex{16}$

T stands for a tautology & F stands for a contradiction. 

Simplify to an equivalent expression that is a single letter (T, F, p or ~p )

a. $\overline{T} \vee F \equiv$

b.  $T \wedge p \equiv$

c.  $F \wedge\overline{p} \equiv$

d. $F \vee \overline{p}\equiv$

e. $(F \vee T) \vee F\equiv$

f. $(F \vee T) \wedge T\equiv$