Logic

Donovan D Chang

9 Logic

Smith [14] says in the preface of his introductory textbook to advanced mathematics, “mathematics is concerned with the formation of a theory (collection of true statements) that describes patterns or relationships among quantities and structures.” To formulate a theory, we need logic, preferably a sound one, and among two lines of thoughts to build – deduction and induction. Let us begin with the definitions of a few key terms.

A proposition is a sentence that has one and only truth value, either true or false, usually denoted by T or F, respectively. The negation of a proposition $P$ , denoted by $\sim P$ , is the proposition “not $P$ .”

Note that, colloquially, the negation and the denial of a proposition $P$ are essentially the same. However, in terms of logic, there is only one negation, $\sim P$ , yet there can be many denials, so long as it is equivalent to the negation $\sim P$ (e.g. $\sim\sim\sim P$ ).

Continuing to introduce important terms, the conjunction of two propositions, denoted $P \wedge Q$ , means $P$ and $Q$ , whereas the disjunction of two propositions, denoted $P \vee Q$ , means $P$ or $Q$ . A tautology is a propositional form that is true, irrespective of the truth values of the propositions involved, and a contradiction, the opposite of a tautology, is a propositional form that is false, irrespective of the truth values of the propositions involved. In other words, tautology is always true and contradiction is always false.

Suppose there are $n$ propositions. Then, there can be $2^n$ possible cases in total, since each proposition can be assigned either T or F, but not T and F. It would be convenient for us to list and examine all these possible cases in a structured way – it is a truth table. Looking at an example would make it easier to understand.

Example. Show that $(P \vee Q)\wedge(\sim P \wedge ~Q)$ is a contradiction using a truth table.

$\begin{array}{ccc|ccc|c} P & Q & P \vee Q & \sim P & \sim Q & \sim P \, \wedge \sim Q & \left(P \vee Q\right)\wedge\left(\sim P \, \wedge \sim Q\right) \\ \hline T & T & T & F & F & F & F \\ F & T & T & T & F & F & F \\ T & F & T & F & T & F & F \\ F & F & F & T & T & T & F \end{array}$

The truth table above has 4 input rows, either T or F assigned to each proposition $P$ or $Q$ . The proposition of interest, $(P \vee Q)\wedge(\sim P \wedge ~Q)$ , is shown in the rightmost column. The columns in between reflect the steps we go through to evaluate the truth value of $(P \vee Q)\wedge(\sim P \wedge ~Q)$ , as the proposition is not in a form readily assessable.

In the first three columns, we assessed the truth value of the first half, $(P \vee Q)$ , and in the three columns in the middle, the latter half, $(\sim P \wedge ~Q)$ , then comparing the truth values of $(P \vee Q)$ and $(\sim P \wedge ~Q)$ , we finally assign values to $(P \vee Q)\wedge(\sim P \wedge ~Q)$ in the last column. We can see, the values are all F, for all possible cases of $P$ and $Q$ . Therefore, $(P \vee Q)\wedge(\sim P \wedge ~Q)$ is a contradiction.

Definition. (The Equivalence of Propositional Forms)
The propositional forms having the same truth tables are equivalent.

What about conditional clauses? We all have heard of expressions in the form of, for example, “if $P$ , then $Q$ .” How do we deal with this? Let us define terms and introduce notations, first.

The conditional, denoted $P\Rightarrow Q$ , means if $P$ , then $Q$ . The conditional in reverse order, $Q\Rightarrow P$ , is called the converse and $\sim Q \Rightarrow \,\sim P$ is called the contrapositive of $P\Rightarrow Q$ . The biconditional, denoted $P\Leftrightarrow Q$ and read “ $P$ if and only if (iff) $Q$ “, means the truth value of $P$ and $Q$ are always the same.

Utilizing the conditionals, here we introduce a famous theorem:

Theorem.
For propositions $P$ and $Q$ ,

$P\Rightarrow Q$ is equivalent to $\sim Q \Rightarrow \,\sim P$
$P\Rightarrow Q$ is not equivalent to $Q\Rightarrow P$

Proof.
The proof is straightforward with a truth table. Note the truth value of $P\Rightarrow Q$ is identical with $\sim Q \Rightarrow \sim P$ , but not with $Q \Rightarrow P$ .

$\begin{array}{ccc|ccc|c} P & Q & P \Rightarrow Q & \sim Q & \sim P & \sim Q \Rightarrow \,\sim P & Q \Rightarrow P \\ \hline T & T & T & F & F & T & T \\ F & T & T & F & T & T & F \\ T & F & F & T & F & F & T \\ F & F & T & T & T & T & T \end{array}$

Note that, by the Hierarchy of Connectives, the connectives are always applied in the order of $\sim$ , $\wedge$ , $\vee$ , $\Rightarrow$ , and $\Leftrightarrow$ .

DeMorgan’s Laws

Now we introduce famous DeMorgan’s Laws. On hearing DeMorgan’s Laws, Some might recall a set theory. However, originally DeMorgan’s Laws were established in propositional logic and Boolean algebra.

Theorem. (DeMorgan’s Laws)
For propositions $P$ and $Q$ ,

$\sim(P \wedge Q)$ is equivalent to $\sim P\, \vee \sim Q$
$\sim(P \vee Q)$ is equivalent to $\sim P \, \wedge \sim Q$

Proof of DeMorgan’s Laws.
Following are the truth tables of cases of DeMorgan’s Laws.

$\begin{array}{ccc|c|ccc} P & Q & P \wedge Q & \sim(P \wedge Q) & \sim P & \sim Q & \sim P \, \vee \sim Q \\ \hline T & T & T & F & F & F & F \\ T & F & F & T & F & T & T \\ F & T & F & T & T & F & T \\ F & F & F & T & T & T & T \\ \end{array}$

We can see the equivalence of $\sim(P \wedge Q)$ and $\sim P\, \vee \sim Q$ .

$\begin{array}{ccc|c|ccc} P & Q & P \vee Q & \sim(P \vee Q) & \sim P & \sim Q & \sim P \, \wedge \sim 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 \\ \end{array}$

We can see the equivalence of $\sim(P \vee Q)$ and $\sim P \, \wedge \sim Q$ .

We see a pattern, when removing a parenthesis, $\sim$ is applied to and flips each element inside, converting $P$ to $\sim P$ , $\wedge$ to $\vee$ , and vice versa.

9 Logic

DeMorgan’s Laws

License

Share This Book