conditional statements and equivalence assignment quizlet

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

2.5: Logical Equivalences

• Last updated
• Save as PDF
• Page ID 23239

• Harris Kwong
• State University of New York at Fredonia via OpenSUNY

Tautology & Contradiction

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

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.

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.

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.

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

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]

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.

• \(p \Rightarrow q \equiv \overline{q} \Rightarrow \overline{p}\)
• \(p \vee p \equiv p\)
• \(p \wedge q \equiv \overline{\overline{p} \vee \overline{q}}\)
• \(p \Leftrightarrow q \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)\)

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 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\).

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

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}\)

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}\)

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

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}\)

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}\)

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

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

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

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

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,

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.

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.

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.

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\).

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).

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.

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.

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.

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.

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}\).

\(\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?

• \((\overline{p} \vee q)\Rightarrow p\)
• \((p\Rightarrow q) \vee (p\Rightarrow \overline{q})\)
• \((p\Rightarrow q) \Rightarrow r\)

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.

• \((p\wedge q)\Leftrightarrow p \equiv p\Rightarrow q\)
• \((p\wedge q)\Rightarrow r \equiv p\Rightarrow(\overline{q}\vee r)\)
• \((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.

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).

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

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

• If triangle \(ABC\) is isosceles and contains an angle of 45 degrees, then \(ABC\) is a right triangle.
• If quadrilateral \(ABCD\) is a square, then it is both a rectangle and a rhombus.
• If quadrilateral \(ABCD\) has two sides of equal length, then it is either a rectangle or a rhombus.

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

Negate the following implications:

• \(x^2>0 \Rightarrow x>0\).
• If \(PQRS\) is a square, then \(PQRS\) is a parallelogram.
• If \(n>1\) is prime, then \(n+1\) is composite.
• 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:

• \(\overline{p\Leftrightarrow q} \equiv \overline{p} \Leftrightarrow \overline{q}\)
• \((p\Rightarrow q) \wedge (p\Rightarrow\overline{q}) \equiv \overline{p}\)
• \(p\Rightarrow q \equiv q\Rightarrow p\)

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

Exercise \(\PageIndex{10}\label{ex:logiceq-10}\)

• \((p\Rightarrow q)\Rightarrow r \equiv p\Rightarrow (q\Rightarrow r)\)
• \(p\Rightarrow (q\vee r) \equiv (p\Rightarrow q) \vee (p\Rightarrow r)\)
• \(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\)”?

• If \(x>0\), then \(x^2>0\).
• If \(x\leq0\), then \(x^2\leq0\).
• If \(x^2\leq0\), then \(x\leq0\).
• If \(x^2\not>0\), then \(x\not>0\).

Exercise \(\PageIndex{12}\label{ex:logiceq-12}\)

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

• \((p\Rightarrow q) \wedge \overline{p}\)
• \((p\Rightarrow\overline{q}) \wedge (p\wedge q)\)
• \((p\Rightarrow\overline{q}) \wedge q\)

Exercise \(\PageIndex{13}\label{ex:logiceq-13}\)

Simplify the following formulas:

• \(p\wedge(p\wedge q)\)
• \(\overline{\overline{p}\vee q}\)
• \(\overline{p\Rightarrow\overline{q}}\)

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

Exercise \(\PageIndex{14}\label{ex:logiceq-14}\)

• \((p\Rightarrow\overline{q}) \wedge (\overline{q}\Rightarrow p)\)
• \(\overline{p\wedge\overline{q}}\)
• \(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\)

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

Exercise \(\PageIndex{16}\)

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\)

Have an account?

Conditional Statements Quiz

9th - 10th grade, mathematics.

36 questions

Introducing new   Paper mode

No student devices needed.   Know more

• 1. Multiple Choice Edit 5 minutes 1 pt Which of the following statements is the converse of "If the moon is full, then the vampires are prowling." ? If the vampires are prowling, then the moon is full. If the moon is not full, then the vampires are prowling. If the vampires are not prowling, then the moon is not full.
• 2. Multiple Choice Edit 5 minutes 1 pt Which of the following statements is the inverse of  "If you do not understand geometry, then you do not know how to reason deductively." ? If you reason deductively, then you understand geometry. If you understand geometry, then you reason deductively. If you do not reason deductively, then you understand geometry.
• 3. Multiple Choice Edit 5 minutes 1 pt Which of the following statements is the converse of  "You cannot skateboard if you do not have a sense of balance." ? If you cannot skateboard, then you do not have a sense of balance. If you do not have a sense of balance, then you cannot skateboard. If you skateboard, then you have a sense of balance.
• 4. Multiple Choice Edit 5 minutes 1 pt Which of the following statements is the inverse of  "If it rains, then I do not go fishing." ? If I go fishing, then it does not rain. If I do not go fishing, then it rains. If it does not rain, then I go fishing.
• 5. Multiple Choice Edit 3 minutes 1 pt Which of the following statements is the inverse of  "Our pond floods whenever there is a thunderstorm." ? If there is a thunderstorm, then our pond floods. If we do not get a thunderstorm, then our pond does not flood. If you pond does not flood, then we did not get a thunderstorm.
• 6. Multiple Choice Edit 3 minutes 1 pt Given, "If I have a Siberian Husky, then I have a dog." Identify the converse. If I do not have a Siberian Husky, then I do not have a dog. If I have a dog, then I have a Siberian Husky. If I do not have a dog, then I do not have a Siberian Husky. If I do not have a Siberian Husky, then I have a dog. 
• 7. Multiple Choice Edit 3 minutes 1 pt Given, "If I have a Siberian Husky, then I have a dog." Identify the inverse . If I do not have a Siberian Husky, then I do not have a dog. If I have a dog, then I have a Siberian Husky. If I do not have a dog, then I do not have a Siberian Husky. If I do not have a Siberian Husky, then I have a dog. 
• 8. Multiple Choice Edit 3 minutes 1 pt Given, "If I have a Siberian Husky, then I have a dog." Identify the contrapositive . If I do not have a Siberian Husky, then I do not have a dog. If I have a dog, then I have a Siberian Husky. If I do not have a dog, then I do not have a Siberian Husky. If I do not have a Siberian Husky, then I have a dog. 
• 9. Multiple Choice Edit 3 minutes 1 pt Given, "If I have a Siberian Husky, then I have a dog." Identify the hypothesis. If I have a Siberian Husky. I have a Siberian Husky. Then I have a dog. I have a dog.
• 10. Multiple Choice Edit 3 minutes 1 pt Given, "If I have a Siberian Husky, then I have a dog." Identify the conclusion. If I have a Siberian Husky. I have a Siberian Husky. Then I have a dog. I have a dog.
• 11. Multiple Choice Edit 3 minutes 1 pt Given, "If angles are congruent, then the measures of the angles are equal." Identify the converse. If the measures of the angles are equal, then the angles are congruent. "If angles are not congruent, then the measures of the angles are not equal." If the measures of the angles are not equal, then the angles are not congruent. If the angles are not congruent, then the measure of the angles are equal.
• 12. Multiple Choice Edit 3 minutes 1 pt Given, "If angles are congruent, then the measures of the angles are equal." Identify the inverse. If the measures of the angles are equal, then the angles are congruent. "If angles are not congruent, then the measures of the angles are not equal." If the measures of the angles are not equal, then the angles are not congruent. If the angles are not congruent, then the measure of the angles are equal.
• 13. Multiple Choice Edit 3 minutes 1 pt Given, "If angles are congruent, then the measures of the angles are equal." Identify the contrapositive. If the measures of the angles are equal, then the angles are congruent. If angles are not congruent, then the measures of the angles are not equal. If the measures of the angles are not equal, then the angles are not congruent. If the angles are not congruent, then the measure of the angles are equal.
• 14. Multiple Choice Edit 3 minutes 1 pt Given, "If angles are congruent, then the measures of the angles are equal." Identify the hypothesis. If angles are congruent. Angles are congruent. Then the measures of the angles are equal. The measures of the angles are equal.
• 15. Multiple Choice Edit 3 minutes 1 pt Given, "If angles are congruent, then the measures of the angles are equal." Identify the conclusion. If the angles are congruent. The angles are congruent. Then the measures of the angles are equal. The measures of the angles are equal.
• 17. Multiple Choice Edit 3 minutes 1 pt What is the hypothesis of the following statement: "If Johnny is late to school, then his mom will have to drive him." His mom will have to drive him If Johnny is late to school Johnny is late to school Then his mom will have to drive him
• 18. Multiple Choice Edit 3 minutes 1 pt What is the conclusion of the following statement: "The angles are supplementary, if they add up to 180 degrees." if they add up to 180 degrees the angles are supplementary they add up to 180 degrees there is no conclusion
• 19. Multiple Choice Edit 3 minutes 1 pt Conditional: If it does not rain today, then we will have practice. What is this statement called: If it rains today, then we will not have practice. Converse Inverse Contrapositive Negation
• 20. Multiple Choice Edit 5 minutes 1 pt Conditional: If Maria gets married, then the reception will be at the country club. What is this statement: If the reception is at the country club, then Maria will be getting married. Converse Inverse Contrapositive Negation
• 21. Multiple Choice Edit 3 minutes 1 pt Original: If Emily is not late to class, then she will not be marked tardy. What is this? If Emily is late to class, then she will be marked tardy. Converse Inverse Contrapositive Negation
• 22. Multiple Choice Edit 3 minutes 1 pt Original: If Jenny buys a guitar, then she will not buy a keyboard. What is this? If Jenny does buy a keyboard, then she will not buy a guitar. Converse Inverse Contrapositive Negation

Explore all questions with a free account

Continue with email

Continue with phone

Equivalent Translations

As we saw in section 2.4 ), two logical statements are said to be logically equivalent if and only if they have the same truth value for every truth assignment.

We can extend this idea to our propositional logic translations – two (English) statements are said to be equivalent iff they have the same underlying meaning, and iff their translations to propositional logic are logically equivalent.

Common equivalences, revisited

We previously identified the following common logical equivalences:

• Double negative: ¬ ¬ p and p
• Contrapositive: p → q and ¬ q → ¬ p
• Expressing an implies using an OR: p → q and ¬ p ∨ q
• One of DeMorgan’s laws: ¬ (p ∧ q) and ( ¬ p ∨ ¬ q)
• Another of DeMorgan’s laws: ¬ (p ∨ q) and ( ¬ p ∧ ¬ q)

Equivalence example 1

Suppose we have the following propositional atoms:

Consider the following three statements:

I get cold except possibly if it is summer.

If it’s not summer, then I get cold.

I get cold or it is summer.

We translate each sentence to propositional logic:

• Meaning: I promise that if I get cold, then it must not be summer…because I am always cold when it’s not summer.
• Meaning: I promise that anytime it isn’t summer, then I will get cold.
• Meaning: I’m either cold or it’s summer…because my being cold is true every time it isn’t summer.

As we can see, each of these statements is expressing the same idea.

Equivalence example 2

Consider the following two statements:

I don’t eat both chips and fries.

I don’t eat chips and/or I don’t eat fries.

These statements are clearly expressing the same idea – if it’s not the case that I eat both, then it’s also true that there is at least one of the foods that I don’t eat. This is an application of one of DeMorgan’s laws: that ¬ (p ∧ q) is equivalent to ( ¬ p ∨ ¬ q) .

If we were to create truth tables for both ¬(p ∧ q) and ¬p V ¬q , we would see that they are logically equivalent (that the same truth assignments make each statement true).

Equivalence example 3

Using the same propositional atoms as example 2, we consider two more statements:

I don’t eat chips or fries.

I don’t eat chips and I don’t eat fries.

These propositions are clearly expressing the same idea – I have two foods (chips and fries), and I don’t eat either one. This demonstrates another of DeMorgan’s laws: that ¬ (p ∨ q) is equivalent to ( ¬ p ∧ ¬ q) . If we were to create truth tables for each proposition, we would see that they are logically equivalent as well.

Last modified by: Julie Thornton May 31, 2022

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

AP®︎/College Computer Science Principles

Course: ap®︎/college computer science principles   >   unit 3.

• Introducing logical equivalence

Equivalent simple Booleans

• Equivalent compound Booleans
• Equivalence between conditionals and Booleans
• Combining equivalence rules

Equivalences with NOT

• when is_hot_out is NOT true, I wear a sweater
• when is_hot_out is false, I wear a sweater

Two NOT 's

• (Choice A)   NOT false A NOT false
• (Choice B)   NOT true B NOT true
• (Choice C)   A ≠ A C A ≠ A
• (Choice D)   NOT (NOT false) D NOT (NOT false)
• (Choice E)   NOT (A = A) E NOT (A = A)

NOT <, NOT >

If it's not ‘less than’, it must be ‘greater than or equal to’.

If it's not ‘greater than’, it must be ‘less than or equal to’.

Equivalences with ≤ and ≥

• (Choice A)   (days > 365) OR (days < 365) A (days > 365) OR (days < 365)
• (Choice B)   NOT (days < 365) B NOT (days < 365)
• (Choice C)   NOT (days > 365) C NOT (days > 365)
• (Choice D)   (days > 365) AND (days = 365) D (days > 365) AND (days = 365)

Want to join the conversation?

• Upvote Button navigates to signup page
• Downvote Button navigates to signup page
• Flag Button navigates to signup page