Propositions, truth tables, and valid forms of inference

Definition 1   A proposition is a statement which has a definite truth value (either true or false).

We also use the term Proposition informally when distinguishing Propositions, Theorems, Corollaries, and Lemmata. A Theorem is usually a big result you have to work hard for. A Proposition is a little theorem which probably follows fairly quickly from definitions. A Lemma is a technical result mostly sued in proving other theorems. A Corollary is a result which follows quickly from a Theorem or Proposition. Since all of the statements of Theorems, Propositions, Lemata, and Corollaries are sentences with determinate truth value, all are propositions. In fact, they are all propositions which are true! In classical mathematics, unlike real life, all of our statements are propositions. Since they take on only the truth values T and F, we can define connectives by saying what they do to truth values:

Definition 2   The connectives and , written $\wedge$, or, written $\vee$, not, written $\lnot$, implies, written $\rightarrow$, and iff, written $\leftrightarrow$ are defined by the truth tables

p	q	$p\wedge q$	$p\vee q$	$\lnot p$	$p \rightarrow q$	$p \leftrightarrow q$
T	T	T	T	F	T	T
T	F	F	T	F	F	F
F	T	F	T	T	T	F
F	F	F	F	T	T	T

Proposition 1.1   Any truth function in two variables can be expressed using $\wedge$, $\vee$, and $\lnot$.

Proposition 1.2   Any truth function in two variables can be expressed using $\wedge$ and $\lnot$.

Proposition 1.3   Any truth function in two variables can be expressed using $\vee$ and $\lnot$.

Proposition 1.4   Any truth function in two variables can be expressed using $\rightarrow$ and $\lnot$.

Proposition 1.5   Any truth function in two variables can be expressed using only the connective p|q whose truth table is given by

p	q	p|q
T	T	F
T	F	T
F	T	T
F	F	T

Proposition 1.6   Any truth function in n variables can be written in either disjunctive normal form (as a disjunction ``or'' of terms which are ``ands'' of variables and negations of variables) or conjunctive normal form (an ``and'' of terms which are ``ors'' of variables and negations of variables).

These results collectively give what is called functional completeness of the connectives sufficient to express all possible truth functions. Switching theory modifies these results to design logic circuits which use a minimum of components or a minimum depth to the expression (for fast execution).

Looking at the truth tables we can derive some standard rules of inference. The premises are listed above the line and the conclusions below. Look at the truth tables to see that if all of the premises get a truth value of T then so do the conclusions. In logic this is called soundness of the rules of inference.

Proposition 1.7   The following rules of inference always transform true premises to true conclusions:

1.

Modus Ponens $${\frac{ p, p\rightarrow q}{q}}$$

2.

Contrapositive $${\frac{\lnot q \rightarrow \lnot p }{p\rightarrow q}}$$

3.

Argument from cases $${\frac{p\vee q, p\rightarrow r, q\rightarrow r }{r}}$$

4.

Indirect proof: $${\frac{\lnot\lnot p}{p}}$$ This tells us that we can prove a statement by showing that its negation is impossible.

The standard form of direct argument uses what is called the deduction theorem: to prove $p \rightarrow q$ it suffices to show that q follows from p. From truth tables the soundness of this form of argument can be seen from the fact that $p \rightarrow q$ is true if p is false or if both p and q are true. The deduction theorem in logic says that if we have a proof starting with a premise p and leading to a conclusion q then we can transform it into a proof from no premises leading to $p \rightarrow q$.