A Propositional logic formula analysis tool
Truth tables and expression trees are wonderful tools for
understanding formulas in propositional logic. However, they
are tedious to do by hand. And whenever anything is tedious to
do by hand we should ... have a computer do it for us!
To that end, check out ...
The SI242 Propositional logic
formula analysis tool
ACTIVITY: Use the above tool to explore and discover with a partner
-
What's the easiest way you can find to determine whether two formulas
are equivalent? For example:
- Are a⊕b⇒b∧¬c and a⇔b∨¬(b⊕c) equivalent?
- Are a⊕b⇒b∧¬c and a⇔b∨¬(b⇒c) equivalent?
-
A binary operator $\mbox{op}$ is said to have commutative property
if for all operands $a$ and $b$, it holds that
$a \mbox{ op } b = b \mbox{ op } a$.
Of our propositional operators
$\wedge,\vee,\Rightarrow,\Leftrightarrow,\oplus$, which are
commutative and which are not? How can you prove
that an operator is commutative? How can you prove
that an operator is not commutative?
-
A binary operator $\mbox{op}$ is said to have the associative property
if for all operands $a$, $b$ and $c$, it holds that
$(a \mbox{ op } b) \mbox{ op } c = a \mbox{ op } (b \mbox{
op } c)$.
Of our propositional operators
$\wedge,\vee,\Rightarrow,\Leftrightarrow,\oplus$, which are
associative and which are not? How can you prove
that an operator is associative? How can you prove
that an operator is not associative?
-
What is the simplest formula you can find that is equivalent
to ite(a,b,c)? ["Simplest" is not precise, so use your own
judgement on what constitutes "simple".]
Use the tool to check that the truth table for your formula
matches that of the ite function!
Properties of propositional operators
It's worth taking some time to review what we learned from the
in-class activity. For more detail, consult your personal
notes.
-
From activity (1), we learned that that we can test whether two
formulas are equivalent by constructing their truth tables and
checking that their outputs are the same. Note: To do this you
will really want the variables to appear in the same order in
the truth table, i.e. the columns are in the same order. If you
check the "Sort Vars T.T." option in the SI242 Formula Analysis Tool,
it will ensure that the columns are sorted by variable name.
There is an easier way, however, that only uses one table.
Suppose you want to check whether formulas $F$ and $G$ are
equivalent. You are really asking whether
$(F) \Leftrightarrow (G)$ is true under all possible
interpretations of the variables in $F$ and $G$. This we can
check by constructing a truth table for $(F) \Leftrightarrow (G)$.
If all values in the output column are true, then $A$ and $B$
are equivalent. Otherwise, they are not. Moreover, if there
is a row with a false output, the interpretation designated by
that row is a "counterexample" that prove that $F$ and $G$ are
not equivalent.
-
From activity (2), we learned that
-
Important!
The commutative operators are: ∧, ∨, ⇔ and ⊕. (Only ⇒ is
not commutative.)
-
From activity (3), we learned that
-
Important!
The associative operators are: ∧, ∨, ⇔ and ⊕. (Only ⇒ is
not associative.)
These properties of propositional operators are a start in
building an "algebra of true/false values". We can now rewrite
formulas to put them in more useful forms just like we rewrite
algebraic expressions and equations. In
activity (4), we did
exactly that. We originally defined ite(a,b,c) by a truth
table. Using the algorithm from last class, we constructed a
propositional formula for ite(a,b,c), but it was a big, ugly
formula. To simplify it, we needed to do something in the same
spirit as algebra - we needed commutativity and other properties
of operators. We arrived at ¬a∧c ∨ a∧b as our simple equivalent formula.
Please refer to your own notes from class for details.