1 Propositional Logic
Logic is the study of correct reasoning. It can be used to figure out whether an argument is valid, to find flaws in arguments, and to construct new arguments. In mathematics, logic is used to develop proofs – short, convincing arguments that something is true. A proof is like a puzzle: each piece (or step) fits together until the whole picture is complete.
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\),
- \(1+3=5\), and
- 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:
Every even integer greater than 2 is the sum of two primes.
In either case, Goldbach’s Conjecture is a mathematical statement.
Propositional logic is a system of reasoning that uses simple statements, called “propositions,” to draw conclusions. For example, consider the following argument:
All dogs are animals. Rover is a dog. Therefore, Rover is an animal.
This argument is valid because it follows the rules of propositional logic. The first two statements are called “premises,” and the last statement is called the “conclusion.”
1.1 Logical Connectives
We will define the following seven logical connectives: \[ \neg \quad \lor \quad \land \quad \rightarrow \quad \leftrightarrow \quad \downarrow \quad \uparrow \]
and in doing so, we will use these symbols to represent the follows words:
- \(\neg\) for not or negation,
- \(\lor\) for and/or or disjunction,
- \(\land\) for and or conjunction,
- \(\rightarrow\) for implies or if … then … ,
- \(\leftrightarrow\) for if and only if or equivalent,
- \(\downarrow\) for joint negation or not both, and
- \(\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:
- \(3+4=7\)
- Samuel is 46 years old.
- \(3+4=8\)
- The current month is December.
- It is raining.
- Right now it is 3 o’clock.
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.
Formally, compound statements are defined as follows.
- All simple statements are compound statements.
- If \(p\) and \(q\) are compound statements, then so are \[ \neg p \quad p \land q \quad p \lor q \quad p \rightarrow q \quad p \leftrightarrow q \]
- 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 (q \lor r)\) are \(p, q,\) and \(r\). 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.
\(p\) | \(\neg p\) | |
---|---|---|
T | F | |
F | T |
Definition 1.1 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.
Basically, the not connective converts true to false and false to true.
Definition 1.2 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.
\(p\) | \(q\) | \(p\land q\) |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
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.
Definition 1.3 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.
\(p\) | \(q\) | \(p\lor q\) |
---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Disjunction is used logically in the inclusive and/or sense. The word disjunction, as written in Latin, is 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.
Definition 1.4 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.
\(p\) | \(q\) | \(p\rightarrow q\) |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
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\).
- \(p\) implies \(q\)
- if \(p\) then \(q\)
- if \(p\), \(q\)
- \(q\), if \(p\)
- \(p\) only if \(q\)
- \(p\) is sufficient for \(q\)
- \(q\) is necessary for \(p\)
- whenever \(p\), \(q\)
- \(q\) whenever \(p\)
Definition 1.5 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.
\(p\) | \(q\) | \(p\leftrightarrow q\) |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
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\).
- \(p\) if and only if \(q\),
- \(p\) is necessary and sufficient for \(q\),
- \(p\) is equivalent to \(q\), and
- \(p\) and \(q\) are equivalent.
As a summary of the truth tables for the logical connectives see Table 1.6.
The connectives \(\downarrow\) and \(\uparrow\) will be explored in the exercises.
\(p\) | \(q\) | \(p\land q\) | \(p\lor q\) | \(p\rightarrow q\) | \(p\leftrightarrow q\) | \(p\uparrow q\) | \(p\downarrow q\) |
---|---|---|---|---|---|---|---|
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 |
1.2 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.
p | q | r |
---|---|---|
T | T | T |
T | T | F |
T | F | T |
T | F | F |
F | T | T |
F | T | F |
F | F | T |
F | F | F |
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. As examples of this convention see Table 1.6 and Table 1.7.
1.3 Tautologies, Contradictions, and Contingencies
We sometimes classify statements according to whether or not they are always true, always false, or otherwise.
Definition 1.6 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.
Example 1.1 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 Table 1.8 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.
\(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))\) |
---|---|---|---|---|---|
T | T | T | T | T | T |
T | F | F | F | T | T |
F | T | F | T | F | T |
F | F | F | T | T | T |
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 problem.
Is there a better way to solve the tautology problem than the brute force method of a truth table?
We now list several important tautologies, leaving their proofs for the reader as exercises. 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.
Theorem 1.1 (Tautologies Used in Proofs) The following statements are tautologies.
Statement | Name |
---|---|
\(p \lor \neg p\) | excluded middle |
\((p\land q) \rightarrow p\) | simplification |
\(p \rightarrow (p\lor q)\) | construction |
\(((p\lor q)\land \neg p ) \rightarrow q\) | syllogism |
\((p\land (p\rightarrow q))\rightarrow q\) | modus ponens |
\((\neg q\land (p\rightarrow q))\rightarrow \neg p\) | modus tollens |
\((p\rightarrow q) \leftrightarrow (\neg p \lor q)\) | conditional disjunction |
\((p \rightarrow q) \leftrightarrow (\neg q \rightarrow \neg p)\) | contrapositive |
\(((p\rightarrow r) \land (q\rightarrow r))\leftrightarrow ((p\lor q)\rightarrow r )\) | proof by cases |
\((p\rightarrow (q\land \neg q))\leftrightarrow \neg p\) | indirect proof |
Proof. The proof is left for the reader as Exercise 1.7.
Proof. The proof is left for the reader as Exercise 1.10.
1.4 Contrapositive, Converse, and Inverse
Three important statements are associated with any implication \(p\rightarrow q\), namely
- the statement \(\neg q\rightarrow \neg p\) is called the contrapositive of \(p\rightarrow q\),
- the statement \(q\rightarrow p\) is called the converse of \(p\rightarrow q\), and
- 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.
\(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \(\neg p\rightarrow \neg q\) | \(q\rightarrow p\) |
---|---|---|---|---|---|
T | T | F | F | T | T |
T | F | F | T | T | T |
F | T | T | F | F | F |
F | F | T | T | T | T |
Further, an implication is not necessarily equivalent to its converse (inverse).
1.5 Modus Ponens and Substitution
In propositional logic, modus ponendo ponens (or ), which is Latin for the way that affirms by affirming, is a valid, simple argument form and rule of inference.
Theorem 1.3 (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 1.4 (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 Exercise 1.22.
Example 1.2 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, by Theorem 1.4, it suffices to verify that \(\eqref{tauex2}\) is in fact a tautology. We leave this verification to the reader.
Example 1.3 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 by Theorem 1.4, we see that \(\eqref{scsex2}\) is also a tautology.
1.6 Inference Rules
By a mathematical proof (or proof) we shall mean the assertion that a certain statement (the conclusion) follows from other statements (the premises). A proof will be said to be (logically) valid, if and only if the conjunction of the premises implies the conclusion, that is, if the premises are all true, the conclusion must also be true. In order to determine whether a mathematical proof is valid we need to be able to accomplish two goals: a valid logically argument and justifications for each statement.
It’s important to realize that a logically argument depends upon its form in that it does not matter what the components of the argument are. For example, is the following argument valid?
\[\begin{equation} \label{argument} \text{If $ p\rightarrow q$ and $q\rightarrow r$, then $p\rightarrow r$.} \end{equation}\]
Since the implication \((p\rightarrow q)\land (q\rightarrow r)\rightarrow (p\rightarrow r)\) is a tautology, \(\eqref{argument}\) is a valid argument, as can be proven by constructing a truth table. Indeed \(\eqref{argument}\) is valid as an argument regardless of the meaning of \(p\), \(q\) and \(r\). A proof demonstrates that the conclusion must happen and is a consequence of the premises.
Theorem 1.5 Suppose the statement \(r\) is a consequence of the premises \(p_1, p_2, ... p_k\) and also suppose another statement \(q\) is a consequence of the same premises \(p_1, p_2, ..., p_k\) and \(r\). Then \(q\) is a consequence of just \(p_1, p_2, ..., p_k\).
Proof. Let \(P_k\) denote \(p_1 \land \cdots \land p_k\). For a rigorous proof we need to show that \[\begin{equation} \label{tautproof} \left( (P_k \rightarrow r) \land (P_k \land r \rightarrow q) \right) \rightarrow \left( P_k \rightarrow q \right) \end{equation}\]
is a tautology. To understand why \(\eqref{tautproof}\) is a tautology, let \(p\) be the variable for \(p_1\land p_2\land \cdots \land p_k\) and consider the truth table for \(p\rightarrow q\). In any row where \(p\) is false, \(p\rightarrow q\) is true by definition of \(\rightarrow\). In any row where \(p\) is true, \(r\) must also be true, since \(p\rightarrow r\) is a tautology. But since \((p\land r)\rightarrow q\) is always true, this guarantees that in every row where \(p\) is true, \(q\) must also be true. Therefore, \(p\rightarrow q\) is a tautology, as desired.
Before we begin writing proofs, let’s review the following tautologies.
Inference Rule | Tautology | Name |
---|---|---|
\(\begin{array}{l} p \\ \hline \therefore \, p\lor q \end{array}\) | \(p\rightarrow (p\lor q)\) | Addition |
\(\begin{array}{l} p\land q\\ \hline \therefore \, p \end{array}\) | \((p\land q)\rightarrow p\) | Simplification |
\(\begin{array}{l} p \\ q \\ \hline \therefore \, p\land q \end{array}\) | \(((p)\land (q))\rightarrow (p\land q)\) | Conjunction |
\(\begin{array}{l} p \\ p\rightarrow q \\ \hline \therefore \, q \end{array}\) | \([p\land (p\rightarrow q)]\rightarrow q\) | Modus ponens |
\(\begin{array}{l} \neg q \\ p\rightarrow q \\ \hline \therefore \, \neg p \end{array}\) | \([\neg q \land (p\rightarrow q)]\rightarrow \neg p\) | Modus tollens |
\(\begin{array}{l} p\rightarrow q \\ q\rightarrow r \\ \hline \therefore \, p\rightarrow r \end{array}\) | \([(p\rightarrow q)\land (q\rightarrow r)]\rightarrow (p\rightarrow r)\) | Hypothetical syllogism |
\(\begin{array}{l} p\lor q \\ \neg p \\ \hline \therefore \, q \end{array}\) | \([(p\lor q)\land \neg p]\rightarrow q\) | Disjunctive syllogism |
1.7 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 1.7 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 1.4 Verify the following are logical equivalencies:
- \(p\rightarrow q \equiv \neg p \lor q\)
- \(\neg (p\rightarrow q) \equiv p\land \neg q\)
Solution. The following truth table clearly demonstrates that \(p\rightarrow q\) and \(\neg p\lor q\) are logically equivalent (columns 5 & 6).
\(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \(p\rightarrow q\) | \(\neg p\lor q\) | \(\neg(p\rightarrow q )\) | \(p\land \neg q\) |
---|---|---|---|---|---|---|---|
T | T | F | F | T | T | F | F |
T | F | F | T | F | F | T | T |
F | T | T | F | T | T | F | F |
F | F | T | T | T | T | F | F |
It also shows that \(\neg(p\rightarrow q )\) and \(p\land \neg q\) are logically equivalent (columns 7 & 8).
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 1.6 (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 1.7 (Properties of Logical Equivalence) Let \(p\) and \(q\) be statements.
- The commutative properties:
- \((p\land q)\equiv (q\land p)\)
- \((p\lor q)\equiv (q\lor p)\)
- The associative properties:
- \(((p\land q)\land r) \equiv (p\land (q\land r))\)
- \(((p\lor q)\lor r) \equiv (p\lor (q\lor r))\)
- The distributive properties:
- \((p\land (q\lor r)) \equiv ((p\land q)\lor (p\land r))\)
- \((p\lor (q\land r)) \equiv ((p\lor q)\land (p\lor r))\)
- The idempotent properties:
- \(p\lor p \equiv p\)
- \(p\land p \equiv p\)
- De Morgan laws:
- \(\neg (p\land q)\equiv \neg p \lor \neg q\)
- \(\neg (p\lor q)\equiv \neg p \land \neg q\)
- Law of excluded middle:
- \(p\lor \neg p\) is a tautology
- \(p\land \neg p\) is a contradiction
Proof. The proof is left for the reader as Exercise 1.8.
Theorem 1.8 (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
- \(p\lor T \equiv T\)
- \(p\land T \equiv p\)
- \(p\lor F\equiv p\)
- \(p\land F \equiv F\)
Proof. The proof is left for the reader as Exercise 1.9.
Theorem 1.9 (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. By Theorem 1.6, \(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, also by Theorem 1.6. Therefore, by Theorem 1.4} we see that \(P'\leftrightarrow Q'\) is a tautology as needed.
Example 1.5 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) ] \\ & \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*}\]
1.8 Exercises
Exercise 1.1 Consider the following statement: \[ \text{If $x=0$, then $x^2=0$ and if $x^2=0$, then $x=0$.} \]
- Express this statement in symbolic form using only conjunction and conditional.
- Express this statement in symbolic form using only biconditional.
Exercise 1.2 Rewrite each statement in the form If …, then ….
- A nessary condition for two triangles to be congruent is that three sides of one be equal respectively to the three sides of the other.
- 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.
- The base angles of an isosceles triangle are equal.
Exercise 1.3 Construct a truth table and identify whether the proposition is either a tautology, contradiction, or a contingency.
- \((p\land q)\rightarrow (p\lor q)\)
- \((p\lor q)\lor (p\rightarrow q)\)
- \((p\rightarrow q)\lor (p\land \neg q)\)
- \((\neg p\land q) \land \neg (p\rightarrow \neg q)\)
- \(\neg (p\lor q)\land \neg (p\rightarrow q)\)
- \((p\land q)\land \neg (p\lor \neg q)\)
- \(((p\land q)\lor r) \rightarrow \neg q\)
- \(((r\land q)\lor p) \rightarrow \neg q\)
Exercise 1.4 Show the following statements are contingencies.
- \((p\land q)\land (p\rightarrow q)\)
- \(((p\land q)\rightarrow (p\lor q))\rightarrow p\land q\)
Exercise 1.5 Find a tautology that contains the statement \(p\land (q\rightarrow \neg p)\). Find a contingency that contains the statement \((p\land q)\land (p\lor \neg q)\). Find a contradiction that contains the statement \(p\land (p\land \neg q)\).
Exercise 1.6 Construct truth tables for each of the following and arrange them so that each compound statement implies all the following ones.
- \(\neg \, p\leftrightarrow q\)
- \(p \rightarrow (\neg \, p\rightarrow q )\)
- \(\neg \, ( p\rightarrow (q\rightarrow p ) )\)
- \(p\lor q\)
- \(\neg \, p \land q\)
Exercise 1.7 Prove Theorem 1.1.
Exercise 1.8 Prove Theorem 1.7.
Exercise 1.9 Prove Theorem 1.8.
Exercise 1.11 First 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\). Now do the following:
- Explain why all propositional forms with two variables are logically equivalent with 1 of 16 possibilities.
- 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.
- 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.
- Explain how to rewrite all of the possibilities in part (c), using only \(\lor\) and \(\neg\). Repeat using only \(\land\) and \(\neg\).
Exercise 1.12 Write the converse, contrapositive, and inverse of each statement. Further, determine whether the given statement and/or its converse is true.
- If \(x\neq 0\), then \(x^2\neq 0\).
- If \(xy=0\), then \(x=0\)
- If \(x\) is a real number, then \(x\) is a rational number.
- If \(x\) is positive and \(x^2=4\), then \(x=2\).
- If \(x\neq 2\) and \(x^2+3x+1=0\), then \(x=1\).
- 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 1.13 Show that \(\neg\), \(\lor\), and \(\land\) form a functionally complete collection of logical connectives.
Exercise 1.14 Show that \(\neg\) and \(\lor\) form a functionally complete collection of logical connectives.
Exercise 1.15 Show that \(\neg\) and \(\land\) form a functionally complete collection of logical connectives.
Exercise 1.16 In this exercise we will show that \(\uparrow\) forms a functionally complete collection of logical connectives.
- Show that \(p\downarrow p\) is logically equivalent to \(\neg p\).
- Show that \((p\downarrow q)\downarrow (p\downarrow q)\) is logically equivalent to \(p\lor q\).
- Explain how Exercise 1.14 applies.
Exercise 1.17 Show that \(\neg\) and \(\rightarrow\) form a functionally complete collection of logical connectives.
Exercise 1.18 Show that the five connectives \(\neg\), \(\land\), \(\lor\), \(\rightarrow\), \(\leftrightarrow\) can each be defined in terms of only \(\uparrow\). Do the same as (a) with \(\downarrow\).
Exercise 1.19 Prove that if \(P\) is logically equivalent to \(Q\), and \(Q\) is logically equivalent to \(R\), then \(P\) is logically equivalent to \(R\).
Exercise 1.20 Use Exercise 1.19, to prove that any two of the following three statements are logically equivalent.
- \(p\rightarrow q\)
- \((p\land \neg q)\rightarrow \neg p\)
- \((p\land \neg q)\rightarrow q\)
Exercise 1.21 Use Theorem 1.9 to prove the logical equivalences.
- \(\neg[(p\leftrightarrow q)\lor (p\land \neg q)]\equiv \neg(p\leftrightarrow q)\land \neg(p\land \neg q)\)
- \((p\lor q)\rightarrow (p\land q)\equiv [((p\lor q)\land \neg(p\land q))\rightarrow \neg(p\lor q)]\)
- \((r\land \neg p)\land ((r\land \neg p)\lor (p\land \neg q))\equiv r\land \neg p\)
- \((p\land r)\land ((p\rightarrow q)\lor r)\equiv [(p\land r)\land (p\rightarrow q)]\lor [(p\land r)\land r]\)
Exercise 1.22 Prove Theorem 1.4.