Friday, September 2, 2011

Introduction to propositional logic

Read Loveys' notes posted on WebCT - the other notes and the textbook are optional.

1Propositional logic¶

1.1Symbols¶

• $\top$, $\bot$ ("top" and "bottom" or "true" and "false", although Loveys doesn't like the latter) - propositional constants, or truth values (but don't call them that)
• Propositional variables: $p, q, r, q', q_1, ...$ etc
• Connectives:

1.2Rules for making propositional formulas¶

1. $\top, \bot, p, q ...$ are all formulas
2. If $\Phi$ is a formula, so is $\neg \Phi$ (the sole unary connective)
3. If $a$ and $b$ are formulas, so are $a \land b$, $a \lor b$, etc

Make sure there are enough parentheses (which Loveys calls brackets¹) that precedence is forced, i.e. there is only one way to interpret any formula. Note that technically there should be parentheses around $a$ and $b$ when joined with a binary connective, but if the expression is still unambiguous then it's fine, we can drop them for brevity by convention. We could also have used square brackets ([, ]) or curly braces ({, }).

As an example, to check that $\neg ((((p) \land (\neg (q))) \lor (\neg(p))) \land \bot))$ is a formula, we can use a tree diagram and split at each connective. (I'm not going to do it here because it would take too long but it should be pretty obvious how it works). The valuation of this formula w

1.3Valuation¶

There are only two propositional constants in this classical logic system - the "truth values" $\top$ and $\bot$. The process of assigning a truth value to a formula is called valuation, defined as follows:

A valuation, $V$, is a function from $\{ p, q, ... \} \to \{\top, \bot\}$. The domain is the countably infinite set of variables, and thus formulas. We have the following rules:

1. $V(\top) = \top$, $V(\bot) = \bot$
2. $V(\neg \Phi) \neq V(\Phi)$
3. $V(a \land b) = \top$ if and only if $V(a) = V(b) = \top$
   $V(a \lor b) = \bot$ if and only if $V(a) = V(b) = \bot$ (i.e. the $\lor$ connective behaves like inclusive or)
   $V(a \to b) = \bot$ if and only if $V(a) = \top$ and $V(b) = \bot$ (material implication²)
   $V(a \iff b) = \top$ only if $V(a) = V(b)$

In other words, the connectives behave pretty much as we would expect them to. No need to memorise any rules.

1.4Truth tables¶

Given a formula $\Phi$ with $n$ different propositional variables ($p_1, p_2 ... p_n$), we can summarise the possible values of $V(\Phi)$ using a truth table with $2^n$ lines³. Each line in the truth table should represent a different combination of valuations for each of $p_1, p_2 ... p_n$, and the last column will always contain the valuation of the formula as a whole. For example, the truth table for $p \to q$ can be represented as follows:

With more complex formulas, we can get much longer and more complicated truth tables, but writing one out never becomes truly difficult, merely time-consuming. As an example, the truth table for a slightly more complicated formula, $(p \to q) \to (q \to p)$, is shown below:

Although this formula is longer, it still uses only two different variables, and so the truth table only needs to have four lines to cover all of the cases.

1.5Tautologies¶

A tautology is a formula $\Phi$ for which $V(\Phi) = \top$ for every valuation $V$. In other words, every line in the truth table comes out $\top$. This is not the same as saying that it is "always true", and Loveys will be on your case if you do not recognise that, so be careful. A formula has no inherent truth in it; it is only when interpreted that a truth value can be assigned. Furthermore, tautologies are only so due to the role of the connectives in the formula^clarify?. This is just semantics, though, so don't worry about it too much.

Here's an example of a tautology, one that you'll see again once we start doing predicate logic (I won't write out the truth table because, well, it's a tautology):

$(p \land (p \to q)) \to q$ (If $p$ is true, and $p$ implies $q$, then $q$ is true)

See List of tautologies for more. Note that the formula used in the above section ($(p \to q) \to (q \to p)$) is not a tautology - an implication does not imply its converse.

An anti-tautology always comes out $\bot$.