Tautology

Recall that an easy way to verify that, for example, $a \Rightarrow b$ is equivalent to $\neg b \Rightarrow \neg a$ is to construct the truth table for $(a \Rightarrow b) \Leftrightarrow (\neg b \Rightarrow \neg a)$ and check that all entries in the rightmost column are "true" (proof by exhaustion!):

This means that the formula $(a \Rightarrow b) \Leftrightarrow (\neg b \Rightarrow \neg a)$ is true under all possible interpretations. You might think that makes it boring (variety is the spice of life, right?), but in fact such formulas are really important - important enough to get a name ...
A propositional formula that is true under all possible interpretations is called a tautology. (A formula that is false under all possible interpretations is called a contradiction.)
Tautologies play a very important role in logic - far greater than you might guess at first. As we will see, they provide the building blocks for rewriting formulas and making deductions without having to resort to truth tables or SAT solvers or other such proof-by-exhaustion techniques. We can see this in an example. You can check that $\neg \neg a \Leftrightarrow a$ is a tautology. But can't I deduce from that fact that $\neg \neg (x \Rightarrow y \wedge z) \Leftrightarrow (x \Rightarrow y \wedge z)$? In other words, doesn't the simple tautology give me the general rule that I can always drop double negatives?

Let's explore this idea with the somewhat more complicated example of our initial tautology. Suppose you are given the formula: $$ F := u \wedge v \Rightarrow (v \oplus w) $$ This has the same form as $a\Rightarrow b$ with $u \wedge v$ as "$a$" and $(v \oplus w)$ as $b$. Therefore, can't I deduce that $$ \neg (v \oplus w) \Rightarrow \neg(u \wedge v) $$ is equivalent to $F$? The answer is decidedly "yes you can!" But how do we know that's OK? The answer is the following theorem, which we will state, and discuss, but which we won't formally prove here - mostly because it's pretty clear that it is true and why it is true, and a formal proof would take too much time.

Let $G$ be a formula in variables $x_1,\ldots,x_m$, and let $H_1,\ldots,H_m$ be formulas in the variables $y_1,\ldots,y_n$. Let $F$ be the formula resulting from replacing each $x_i$ variable in $G$ with the formula $H_i$. If $G$ is a tautology, then $F$ is a tautology.

Hopefully going back to our example will make this a bit clearer. In that case:

... and the claim is that because $G$ is a tautology, $F$ is a tautology too.

$G$$H_1$$H_2$$F$

The intuition behind how we know that this is true is this: when you evaluate $F$ for a particular assignment of true/false values to $u,v,w$, you evaluate from the bottom of the expression tree up. When you've moved up to a certain point, the subtrees corresponding to $H_1$ and $H_2$ have been evaluated (perhaps multiple times, because copies appear in several places) and the resulting true/false values appear at the nodes corresponding to the nodes for variables $a$ and $b$ in the expression tree for $G$. So at this point, continuing to evaluate $F$ is the same as evaluating $G$ with variable $a$ getting whatever value $H_1$ evaluated to, and variable $b$ getting whatever value $H_2$ evaluated to. But $G$ is a tautology, so the final result must be "true", regardless of what $H_1$ and $H_2$ evaluated to.

We do this instinctively with algebra. For example, $(x-1)(x+1) = x^2 - 1$, so $(2a - 3b - 1)(2a - 3b + 1) = (2a - 3b)^2 - 1$. What holds for variable $x$ continues holds when we substitute a complicated subformula for $x$. In propositional logic, we might say, for example, $(x\Rightarrow \neg x) \Leftrightarrow \neg x$ is a tautology, therefore $(u \oplus \neg v\Rightarrow \neg (u \oplus \neg v)) \Leftrightarrow \neg (u \oplus \neg v)$ is a tautology, so $(u \oplus \neg v\Rightarrow \neg (u \oplus \neg v))$ is equivalent to $\neg (u \oplus \neg v)$.

ACTIVITY

  1. Suppose formula $F$ is a contradiction. What can you tell me about $\neg F$?
  2. Suppose $F$ is a big formula with lots of variables (say 60 or 70). How could we check whether or not $F$ is a tautology?
  3. True or false: every formula is either a tautology or a contradiction. Prove your answer to this!
  4. (x => ~y & z) | ~(x => ~y & z) is an example of substituting complicated formulas into the variables of a tautology. What is the underlying tautology and what is the substitution in this case?

Rewriting & simplification

Technically, we should justify that rewriting "works", i.e. that replacing a subformula $F$ with equivalent formula $F'$ within a larger formula doesn't change the truth table for the larger formula. However, the analogy with what you've been doing for years in algebra is so strong, that you probably don't need much convincing, so I'm not going to spend time/space on it (given that we are short on both!).
Tautologies with $\Leftrightarrow$ at the top level are statements that two things are equivalent. We can use these to rewrite (usually to simplify) propositional formulas just as we use equalities like $a(b+c) = (ab + ac)$ to simplify algebraic expressions. So, for example, you can verify that $$\neg(a \Leftrightarrow b) \Leftrightarrow (a \Leftrightarrow \neg b)$$ is a tautology. Having done that, you have a new rule for rewriting/simplifying propositional formulas. We might call this something like the "negation-of-equivalence" rule.

Here's an example of how to simplify the formula $\neg(u \oplus v \Leftrightarrow \neg w)$ using some of the tautologies we know:

$$ \begin{array}{rcll} F & = & \neg(u \oplus v \Leftrightarrow \neg w) &\\ & = & u \oplus v \Leftrightarrow \neg \neg w & \mbox{by applying tautology $\neg(a\Leftrightarrow b) \Leftrightarrow (a \Leftrightarrow \neg b)$ with $a = u \oplus v$ and $b = \neg w$}\\ & = & u \oplus v \Leftrightarrow w & \mbox{by applying tautology $\neg \neg a \Leftrightarrow a$ with $a = w$} \end{array} $$

We actually have a collection of tautological equivalences (i.e. formulas of the form $X \Leftrightarrow Y$ that are tautologies) that we can use for simplification and rewriting:

ACTIVITY
  1. Below is a sequence of simplifications of a formula with no justification for each step. Provide the justification by stating for each line (after the first) what tautology is being used and what the subformulas associated with the variables in the tautology are $$ \begin{array}{rcll} F_1 & = & (u | v) | u &\\ & = & (v|u)|u &\mbox{__________________}\\ & = & v | (u|u)&\mbox{__________________}\\ & = & v|u &\mbox{__________________}\\ \end{array} $$
  2. Below is an invalid simplification. [Warning! the below is invalid!] Identify the step that corresponds to a "simplification" that is not actually a tautology, and thus is not valid. $$ \begin{array}{rcll} F_2 & = & (y \Rightarrow x) \wedge x&\\ & = & x \wedge (y \Rightarrow x) &\\ & = & x\wedge y \Rightarrow x \wedge x &\\ & = & x \wedge y \Rightarrow x &\\ \end{array} $$
  3. Find a simple right-hand-side to the following equivalence that doesn't use parentheses and that gives a tautology: $\neg(a\wedge b) \Leftrightarrow\ \mbox{____________}$
  4. Find a simple right-hand-side to the following equivalence that doesn't use parentheses and that gives a tautology: $\neg(a\vee b) \Leftrightarrow\ \mbox{____________}$
  5. In the previous homework, one answer was "constraint d is $\neg(bh \wedge \neg cs)$". Using your answer to problem (3) and one of the above simplification rules, show how to simplify "constraint d". Please write it down step-by-step like in problem (1).
  6. The Class 4 Theorem shows that every boolean function has a defining propositional formula. The proof actually shows how to build a defining formula from the truth table, and the formula it builds uses only $\wedge$, $\vee$ and $\neg$. That means any of the boolean operators can be defined using just those three operators.
    1. Find a simple equivalent to $a \Rightarrow b$ using only $\wedge$, $\vee$ and $\neg$.
    2. Find a simple(ish) equivalent to $a \oplus b$ using only $\wedge$, $\vee$ and $\neg$.
  7. Our definition of Propositional Formula does not allow the constants true or false. Let's define an Extended Propositional Formula to extend the definition of Propositional Formula by allowing the constants true and false. Thus, something like $a \vee (true \oplus b)$. Prove that for any Extended Propositional Formula $F$, there is a Propositional Formula that is equivalent to $F$.
  8. With Extended Propositional Formulas, there are a few simplifcation rules we can express nicely.
    1. Complete the tautology to make a nice simplification rule (check it!): $\text{false}\oplus b \Leftrightarrow$ ______________
    2. Complete the tautology to make a nice simplification rule (check it!): $\text{true}\oplus b \Leftrightarrow$ ______________
    3. Based on your results, we two new rules:

      If formula $F$ is a tautology, we can simplify $(F) \oplus a$ to _______________.

      If formula $F$ is a contradiction, we can simplify $(F) \oplus a$ to _______________.

Note: Problems 3 and 4 are super important. These rules are known as De Morgan's Laws. Problem 5a is also super important. So here they are:

  1. De Morgan's Laws: $\neg(a\vee b) \Leftrightarrow \neg a \wedge \neg b$ is a tautology, as is $\neg(a\wedge b) \Leftrightarrow \neg a \vee \neg b$.
  2. Implication rewriting: $(a \Rightarrow b) \Leftrightarrow (\neg a \vee b)$ is a tautology.

Here's a challenge: Prove $(\neg a \vee \neg b \vee c) \Leftrightarrow (a\wedge b \Rightarrow c)$ is a tautology by showing how to rewrite the right-hand side, step-by-step, until it is identical to the left-hand side.
Christopher W Brown