3.2: Propositional Logic
- Page ID
- 99063
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Propositional logic studies how the truth or falsehood of compound statements is determined by the truth or falsehood of the constituent statements. It gives us a way of reliably deriving true conclusions from true assumptions.
If \(P\) is a statement which is true, then \(P\) has truth value 1. If \(P\) is a statement which is false, \(P\) has truth value 0. We write \(T(P)\) for the truth value of \(P\).
Truth values can be thought of as a function \(T: S \rightarrow\ulcorner 2\urcorner\), where \(S\) is the set of all statements. When investigating the abstract principles of propositional logic, we consider possible assignments of truth values to variables representing statements. We are interested in claims that are independent of any particular assignment of truth values to the propositional variables. We use the integers 0 and 1 to represent truth values because it allows us to use arithmetic operations in propositional logic. Other authors prefer \(F\) and \(T\).
The symbols \(\wedge, \vee, \neg\) and \(\Rightarrow\) are propositional connectives. They are defined as follows for statements \(P\) and \(Q\).
| Connective | Name | Definition |
|---|---|---|
| \(\neg\) | negation | \(T(\neg P)=1-T(P)\) |
| \(\hat{\vee}\) | conjunction | \(T(P \wedge Q)=T(P) \cdot T(Q)\) |
| \(\Rightarrow\) | disjunction | \(T(P \vee Q)=T(P)+T(Q)-T(P) \cdot T(Q)\) |
| \(\Rightarrow\) | implication | \(T(P \Rightarrow Q)=1-T(P)+T(P) \cdot T(Q)\) |
In the expression " \(P \Rightarrow Q\) ", the statement \(P\) is called the antecedent or hypothesis and \(Q\) is called the consequence or conclusion.
Propositional connectives are formal equivalents of natural language connectives.
| Connective | Natural Language Equivalent |
|---|---|
| \(\neg\) | not |
| \(\wedge\) | and |
| \(\vee\) | or |
| \(\Rightarrow\) | implies |
Check that the formulas defining the propositional connectives give the meaning that you anticipate. For example, check that the definition of the truth value for \(P \wedge Q\) means that \(P \wedge Q\) is true if and only if both \(P\) and \(Q\) are true.
Propositional connectives approximate natural language connectives. Propositional connectives are formal and precise, while natural language connectives are imprecise and somewhat more expressive - consequently the approximation is imperfect. We saw an example of this when contrasting mathematicians’ use of the connective "or" with its use in everyday language. For precision in mathematics we interpret the connectives formally - even when using natural language expressions.
We can build very complicated compound statements by using logical connectives. Naturally, there are rules for building correct statements with connectives.
An atomic statement is a statement with no explicit propositional connectives.
An atomic statement is usually represented by a capital letter.
We define a well-formed propositional statement recursively as follows.
Atomic statements are well-formed.
If \(P\) and \(Q\) are well-formed statements, then the following are wellformed statements:
-
\((\neg P)\)
-
\((P \wedge Q)\)
-
\((P \vee Q)\)
-
\((P \Rightarrow Q)\). In practice the parentheses are dropped unless there is the potential for ambiguity. Additionally, "[" and "]" may be substituted for parentheses in the interests of readability. For any assignment of truth values to the atomic statements in a well-formed statement, the compound statement will have a well-defined truth value.
A compound statement is a well-formed statement composed of atomic statements and propositional connectives.
3.2.1. Propositional Equivalence.
One purpose of propositional logic is to give tools for assessing the truth of a compound statement without necessarily having to understand the specific meaning of the atomic statements. That is, some statements are demonstrably true or false by virtue of their form. Central to this understanding is the idea of propositional equivalence.
Let \(P\) and \(Q\) be well-formed statements built from atomic statements. We say that \(P\) and \(Q\) are propositionally equivalent provided that \(T(P)=T(Q)\) for any assignment of truth values to the constituent atomic statements.
If \(P\) and \(Q\) are propositionally equivalent, we may write \[P \equiv Q .\] EXAMPLE 3.1. \[[P \Rightarrow Q] \equiv[(\neg Q) \Rightarrow(\neg P)]\] This is a very important example of a propositional equivalence. We will show this by considering all possible assignments of truth values to \(P\) and \(Q\). Let’s set this up in what is popularly called a truth table. We consider all possible assignments of truth values to \(P\) and \(Q\), and compare the truth values of the compound statements under consideration:
\(\begin{array}{cccc}\frac{T(P)}{0} & \frac{T(Q)}{0} & \frac{T(P \Rightarrow Q)}{1} & \frac{T((\neg Q) \Rightarrow(\neg(P)))}{1} \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1\end{array}\)
Each row of the truth table represents a particular assignment of truth values to the atomic statements \(P\) and \(Q\). The four possible assignments are exhausted by the rows of the truth table. The truth values of the compound statements agree in each row of the truth table so the statements are equivalent.
\[\begin{aligned} &{[\neg(P \wedge Q)] \equiv[(\neg P) \vee(\neg Q)]} \\ &{[\neg(P \vee Q)] \equiv[(\neg P) \wedge(\neg Q)]} \end{aligned}\] Statements (3.3) and (3.4) are known as de Morgan’s laws. (How are they related to Exercise 1.2?)
With two possible exceptions, once you carefully study what these connectives mean, you should understand them intuitively. One exception is that the logical and mathematical "or", \(\vee\), is inclusive. We discussed this at the beginning of Chapter 2. The other exception is the logical connective " \(\Rightarrow\) ".
3.2.2. Implication.
Students often find it confusing that the implication \(P \Rightarrow Q\) can be true when the consequence, \(Q\), is false. This is understandable when we consider that implications are usually employed in argument in the following syllogism: \[\begin{gathered} P \\ P \Rightarrow Q \end{gathered}\] therefore, (i.e. if \(P\) is true, and \(P \Rightarrow Q\), then \(Q\) is true). This syllogism is the most important rule of logical deduction (called Modus Ponens). Logical implication is so often used to demonstrate the truth of the consequence that it is easy to understand why one might mistakenly think that the consequence must follow from the implication, rather than following from the antecedent. Consider the following statement:
If you are the king of France, then I am a monkey’s uncle.
Is this statement true? Presumably you are not the king of France, and I don’t believe that I am a monkey’s uncle. So both the antecedent and the consequence are false. However the statement is true. In fact, this statement is logically equivalent to the statement:
If I am not a monkey’s uncle, then you are not the king of France.
The definition of logical implication says that an implication in which the antecedent is false gives no information about the consequence. Hence, any logical implication with the antecedent "You are the king of France" will be true.
There is an additional concern with logical implication. In natural language (and intuitively in mathematics), the statement \[P \Rightarrow Q\] suggests a relationship between the statements \(P\) and \(Q\) - namely that the truth of \(P\) somehow forces the truth of \(Q\). As a propositional connective, this relationship between \(P\) and \(Q\) is not required for logical implication. The truth of \(P \Rightarrow Q\) is a function of the truth values of \(P\) and \(Q\), not their meanings. In mathematical writing, it is understood that not only is the implication logically true, but that \(P\) and \(Q\) are related and that the truth of \(P\) indeed forces the truth of \(Q\). For instance, consider the statement \[\mathbb{N} \subset \mathbb{Q} \Rightarrow 3>2 .\] This statement is true by the formal definition of \(\Rightarrow\). In fact, as a propositional statement, we could replace the antecedent with any other statement, true or false, and the conditional statement would be true. However, such a statement is mathematically unacceptable, since the antecedent and the consequence have nothing to do with each other. We are not concerned with the accidental truth values of atomic statements, but the mathematical connections between these statements, which comply with, yet go beyond, the formal definition of logical connectives.
3.2.3. Converse and Contrapositive.
Most mathematical claims have the form of an implication. Therefore you need to be familiar with the conventional nomenclature surrounding logical implication. Suppose we are interested in a particular logical implication, \[P \Rightarrow Q \text {. }\] There are two other logical implications which are naturally associated with \(P \Rightarrow Q\). One is the contrapositive, \[\neg Q \Rightarrow \neg P .\] An implication and its contrapositive are propositionally equivalent.
The statement,
"If this is an insect then it has six legs."
is propositionally equivalent to the statement
"If this does not have six legs, it is not an insect."
The contrapositive of
"A whale is a fish"
is
"If it is not a fish then it is not a whale".
The latter example illustrates that a statement need not be true in order to have a contrapositive (which is, of course, still propositionally equivalent to the original conditional statement). It also illustrates that conditional statements in natural language need not include the word "if" or "then", nor be written in a particular form, in order to be a conditional statement. The converse of a conditional statement, \[P \Rightarrow Q\] is the conditional statement, \[Q \Rightarrow P .\] A conditional statement and its converse are not propositionally equivalent. You can easily check that \(P \Rightarrow Q\) and \(Q \Rightarrow P\) have different truth values if \(T(P)=1\) and \(T(Q)=0\).
What is the converse to the statement
"All fish live in water"?
Since this is written in natural language, there is no unique answer.
An obvious converse is
"If something lives in water, then it is a fish".
If we put together an implication and its converse, we get the biconditional connective.
Let \(P\) and \(Q\) be statements. The biconditional, written \(\Longleftrightarrow\), is defined as follows.
| Connective | Name | Definition |
|---|---|---|
| \(\Longleftrightarrow\) | biconditional | \(T(P \Longleftrightarrow Q)=T(P \Rightarrow Q) \cdot T(Q \Rightarrow P)\) |
The biconditional connective is the formal interpretation of "if and only if". This phrase is so commonly used in mathematics that it has its own abbreviation: iff.
Other natural language words that can be translated into propositional connectives are "necessary" and "sufficient". The statement
"In order for \(P\) to hold, it is necessary that \(Q\) holds" is equivalent to \(P \Rightarrow Q\). The statement
"In order for \(P\) to hold, it is sufficient that \(Q\) holds"
is equivalent to \(Q \Rightarrow P\). Combining these two, we get that the statement "In order for \(P\) to hold, it is necessary and sufficient that \(Q\) holds" is equivalent to \(P \Longleftrightarrow Q\).