Propositional formulas
In algebra we distinguish between
expressions, like
$3x^2 - x^2 - 1$, and
equations, like
$3x^2 - x^2 - 1 = 0$. The
difference is in their
types. An expression like
$3x^2 - x^2 - 1$, when evaluated at a particular $x$ value,
results in a
number.
An equation like
$3x^2 - x^2 - 1 = 0$, when evaluated at a particular $x$ value,
results in a true/false value.
In propositional logic, there is no such distinction, and no
need for the equals sign. A propositional formula like
$a \wedge (\neg b \vee c)$ evalutes to a true/false value
already, so there is no need for equals signs, and no need
to distinguish between expressions and equations!
Propositional logic gets interesting when we combine multiple
logical operators to produce something more more complicated.
Such combinations are called
formulas. This really
works exactly like you'd expect given your experience in algebra
with combining arithmetic operators in expressions like
$x \cdot (-y + 2)$. For example, you probobly have an intuitive
understanding of what the formula $a \wedge (\neg b \vee c)$
means, in the sense that you could evaluate it if I told you
what values to give $a$, $b$ and $c$.
[If $a,b,c$ are true,true,false, what would the formula evaluate
to?]
However, we are going to want to prove things about
formulas (and maybe even give algorithms to compute with
formulas) and that requires formally defining the term.
Our previous definitions (boolean variable, boolean function and
propositional logic operators) hopefully just plain made sense.
They are very simple definitions. Formulas are more difficult
to define, because formulas are made up of formulas, which are
in turn made up of formulas, etc. To define this sort of thing
we need a recursive definition. We'll state it here,
and hopefully it'll make sense.
With this definition, we can prove that, for example, $(a)\wedge((\neg(b))\vee (c))$ is
a propositional formula. Let's see how that works.
$F := (a)\wedge\left((\neg(b))\vee (c)\right)$ is a propositional formula.
Since this is our first "real" proof, we will make the steps
explicit by putting them in a bulleted list.
- Since $\wedge$ is a propositional operator, and $F$ is $(a)\wedge\left((\neg(b))\vee (c)\right)$,
by Point 3 of the definition, we can deduce that $F$ is a
propositional formula if we can show that $a$ and $(\neg(b))\vee (c)$
are propositional formulas, which we do below.
- By Point 1 of the definition, $a$ is a propositional formula.
-
Since $\vee$ is a propositional operator, we can deduce
that $(\neg(b))\vee (c)$ is a propositional formula by
Point 3 of the definition if we can show that $\neg(b)$
and $c$ are propositional formulas, which we do below.
- By Point 2 of the definition, we can deduce that $\neg(b)$ is a
propositional formula if we can show that $b$ is a
propositional formula, which we do below.
- By Point 1 of the definition, $b$ is a propositional formula.
- By Point 1 of the definition, $c$ is a propositional formula.
That completes the proof, which we usually mark with ...
Note: If you want to prove that
something "is an X", the typical approach is to
got back to the definitions of "X" and show,
point by point, that the "something" you have meets those
requirements. That's precisely what we've done with the
above proof.
Importantly, to
prove that $F$ is a propositional formula required us to turn
around and prove that smaller pieces are propositional
formulas. This is the essence of a recursive definition:
$F$ is a propositional formula because something smaller is a
propositional formula, which is because something even smaller
is a propositional
formula ... it looks like it's
turtles all the way down.
However, if you look closely, you see that this process always
bottoms out at Point 1 of the definition (variables are
propositional formulas) which is not "recursive".
This is called the "base case" of the definition. We will have
more to say about recursive definitions in the future!
Expression Trees
Obviously, the proof from the previous section is ultra painful.
Let's never do that again. If you look at the structure of the
proof, you'll see that there's an obvious hierarchy to it. At
the top level is proving that $F$ is a propositional formula.
At the next level is proving $a$ is a formula, and proving
$(\neg(b))\vee (c)$ is a propositional formula, and so on.
We can represent this visually in what's called an expression
tree.
You should be able to match the six bullets in the proof with
the six nodes in the expression tree
(top-to-bottom, left-to-right).
So, in essence an
expression tree is a concise representation of the proof that a
given sequence of characters is a propositional formula. The
parentheses in the sequence of characters show you how to write
it as an expression tree.
Therefore, from now on we can prove that a given sequence of
characters is indeed a propositional formula simply by drawing
the expression tree.
Important: Remember, an expression tree is
a concise representation of the proof that a sequence of
characters is a propositional formula. So if you are asked to
prove that something like $\neg((a)\Rightarrow (b))$ is a
propositional formula ... just draw its expression tree.
ACTIVITY
- Draw the expression tree for $((\neg(a))\Rightarrow (b)) \Leftrightarrow ((a)\vee (b))$
-
Write down the formula represented by the expression tree:
-
Prove that $\neg(\neg((\neg(a))\vee (b)))$ is a
propositional formula.
- Why is $(a)\neg(b)$ not a propositional formula?
- Why is $(\wedge)\vee(a)$ not a propositional
formula?
- Is $x_1$ a propositional formula? Justify!
Note: For every propositional formula there is a unique
expression tree, and for every expression tree a unique
propositional formula.
Order of operations: enough of the parentheses already!
Would you write (36+(2*x))-(7*y)? No! You write 36 + 2*x - 7*y.
What allows us to do that and still be unambiguous?
Order of operations! We'll do the same thing with propositional logic.
This is the *language of propositional logic*, just like
we have a well-understood lanugage for algebra. The order
of operations and leaving out parentheses is just a convenient short-hand,
so we don't all go nuts! It is just like arithmetic and algebra.
It is also just a like a programming language!
So we will define precedence and associativity just as we would
for a programming language, with table!
Here are the precedence and associativity levels from highest to
lowest:
| level |
operator(s) |
associativity |
| 1 | $\neg$ | N/A |
| 2 | $\wedge$ | left-to-right |
| 3 | $\vee,\Rightarrow,\Leftrightarrow,\oplus$ | left-to-right |
Of course we use ( )s to get around the precedence/associativity
rules or even if we just want to be clearer. The goal here is
that we can write a formula without tons of parentheses and
still have a unique associated expression tree.
ACTIVITY
- Draw the expression tree for
$a \Rightarrow b \Rightarrow c$.
Note: you might want to put in the parentheses first!
- Draw the expression tree for
$a \Rightarrow b \wedge c \Rightarrow d$.
Note: you might want to put in the parentheses first!
- Draw the expression tree for $\neg a \Rightarrow b
\Leftrightarrow (a \vee b)$
-
Write down the formula represented by the expression tree
below without any unnecessary ( )s: