EF Propositional calculus

Section 2.2 Propositional calculus

Logical equivalence gives us something like an “equals sign” that we can use to perform logical “calculations” and manipulations, similar to algebraic calculations and manipulations. To enable us to do such calculations, we first need a “tool chest” of basic logical equivalences to use therein.

Proposition 2.2.1. Rules of Propositional Calculus.

Suppose \(A,B,C,E,U\) are logical statements, where \(E\) is a contradiction and \(U\) is a tautology. Then the following equivalences always hold.

Rules involving tautologies.
1. \(\displaystyle A \lgcor U \lgcequiv U\)
2. \(\displaystyle A \lgcand U \lgcequiv A\)
Rules involving contradictions.
1. \(\displaystyle A \lgcor E \lgcequiv A\)
2. \(\displaystyle A \lgcand E \lgcequiv E\)
Duality of tautologies and contradictions.
1. \(\displaystyle \lgcnot U \lgcequiv E\)
2. \(\displaystyle \lgcnot E \lgcequiv U\)
Double negation.
\(\displaystyle \lgcnot \lgcnot A \lgcequiv A\)
Idempotence.
1. \(\displaystyle A \lgcor A \lgcequiv A\)
2. \(\displaystyle A \lgcand A \lgcequiv A\)
Commutativity.
1. \(\displaystyle A \lgcor B \lgcequiv B \lgcor A\)
2. \(\displaystyle A \lgcand B \lgcequiv B \lgcand A\)
Associativity.
1. \(\displaystyle (A \lgcor B) \lgcor C \lgcequiv A \lgcor (B \lgcor C)\)
2. \(\displaystyle (A \lgcand B) \lgcand C \lgcequiv A \lgcand (B \lgcand C)\)
Distributivity.
1. \(\displaystyle A \lgcand (B \lgcor C) \lgcequiv (A \lgcand B) \lgcor (A \lgcand C)\)
2. \(\displaystyle A \lgcor (B \lgcand C) \lgcequiv (A \lgcor B) \lgcand (A \lgcor C)\)
3. \(\displaystyle (A \lgcor B) \lgcand C \lgcequiv (A \lgcand C) \lgcor (B \lgcand C)\)
4. \(\displaystyle (A \lgcand B) \lgcor C \lgcequiv (A \lgcor C) \lgcand (B \lgcor C)\)
DeMorgan’s Laws.
1. \(\displaystyle \lgcnot (A \lgcor B) \lgcequiv \lgcnot A \lgcand \lgcnot B\)
2. \(\displaystyle \lgcnot (A \lgcand B) \lgcequiv \lgcnot A \lgcor \lgcnot B\)
Constructing the conditional and biconditional.
1. \(\displaystyle A \lgccond B \lgcequiv \lgcnot A \lgcor B\)
2. \(\displaystyle A \lgcbicond B \lgcequiv (A \lgccond B) \lgcand (B \lgccond A)\)

Remark 2.2.2.

Each of these basic equivalences can be established with a truth table. See Exercise 2.5.4.

Example 2.2.3. DeMorgan.

Using Rule 9.b of Proposition 2.2.1, the following are equivalent statements.

The triangle can’t be both right and equilateral.
The triangle is not right or it is not equilateral.

To see how the rule applies, let \(p\) represent the statement “the triangle is right” and let \(q\) represent the statement “the triangle is equilateral.” Then the first statement above is \(\lgcnot (p \lgcand q)\text{,}\) while the second statement above is \(\lgcnot p \lgcor \lgcnot q\text{.}\)

Now we need some new substitution rules to enable us to use the rules of Proposition 2.2.1 in logical calculations.

Theorem 2.2.4. Substitution Rules.

Replacing a substatement by an equivalent one.
Suppose \(A\) is a logical statement and \(X\) is a substatement of \(A\text{.}\) If statement \(Y\) is equivalent to \(X\text{,}\) then the new statement \(A'\) obtained from \(A\) by replacing substatement \(X\) by \(Y\) is equivalent to \(A\text{.}\) That is, if \(Y \lgcequiv X\) then \(A' \lgcequiv A\text{.}\)
Substituting into a known equivalence.
Suppose \(A\) and \(B\) are logical statements, each of which involves substatement variables \(p_1, p_2, \dotsc, p_m\text{.}\) If \(A\) and \(B\) are equivalent, then so are new statements \(A'\) and \(B'\) obtained by applying substitution \(p_i = C_i\) to both \(A\) and \(B\text{,}\) for every collection of statements \(C_1, C_2, \dotsc, C_m\text{.}\)

Proof idea.

Think of \(X\) as an intermediate column in the calculation of the truth table of \(A\text{.}\) Replacing \(X\) by \(Y\) does not change this column, as the truth tables of \(X\) and \(Y\) are the same.
We leave this statement for you, the reader, to consider. (Again, think of the \(C_i\) as intermediate columns in the calculations of the truth tables of \(A'\) and \(B'\text{.}\))

Example 2.2.5.

One of DeMorgan’s Laws (Rule 9.a of Proposition 2.2.1) says that \(\lgcnot (p \lgcor q) \lgcequiv \lgcnot p \lgcand \lgcnot q\text{.}\) Therefore,

\begin{equation*} \lgcnot \bbrac{ (r \lgccond t) \lgcor (t \lgccond r) } \lgcequiv \lgcnot (r \lgccond t) \lgcand \lgcnot (t \lgccond r), \end{equation*}

using Rule 2 of our new Substitution Rules, with substitutions \(p = r \lgccond t\text{,}\) \(q = t \lgccond r\text{.}\)

Here is an example of a string of logical manipulations. It also demonstrates the use of Rule 10.a of Proposition 2.2.1 to manipulate an expression involving a conditional.

Example 2.2.6. DeMorgan with a conditional.

Consider the statement \((p_1 \lgcor p_2) \lgccond q\text{.}\) We may read it as “if either \(p_1\) or \(p_2\) is true, then \(q\) will be true as well.” So it seems that each of \(p_1\) and \(p_2\) must imply \(q\) on its own. Let’s see what propositional calculus says about this:

\begin{align*} (p_1 \lgcor p_2) \lgccond q \amp \lgcequiv \lgcnot (p_1 \lgcor p_2) \lgcor q \amp \amp \text{(i)}\\ \amp \lgcequiv (\lgcnot p_1 \lgcand \lgcnot p_2) \lgcor q \amp \amp \text{(ii)}\\ \amp \lgcequiv (\lgcnot p_1 \lgcor q ) \lgcand (\lgcnot p_2 \lgcor q) \amp \amp \text{(iii)}\\ \amp \lgcequiv (p_1 \lgccond q) \lgcand (p_2 \lgccond q) \amp \amp \text{(iv)}, \end{align*}

with justifications

Rule 2 of our new Substitution Rules, where we substitute \(A = p_1 \lgcor p_2\) into both sides of the construction of the conditional (Rule 10.a of Proposition 2.2.1);
Rule 1 of our new Substitution Rules, using DeMorgan (Rule 9.a of Proposition 2.2.1) on the substatement \(\lgcnot (p_1 \lgcor p_2)\text{;}\)
distributivity (Rule 8.d of Proposition 2.2.1); and
Rule 1 of our new Substitution Rules, using the construction of the conditional (Rule 10.a of Proposition 2.2.1) on each of the two “factors” of the conjunction.

So our intuition about the logic of a disjunction in a conditional in this way was correct.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: