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 $\small\mbox{ op}$ is said to have the commutative property
if for all operands $a$ and $b$, it holds that
$a {\small\mbox{ op }} b = b {\small\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 $\small\mbox{op}$ is said to have the associative property
if for all operands $a$, $b$ and $c$, it holds that
$(a {\small\mbox{ op }} b) {\small\mbox{ op }} c = a {\small\mbox{ op }} (b {\small\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 appearing 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 proves 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.)
In other words, we proved the following two theorems:
In propositional logic, operators ∧, ∨, ⇔ and ⊕ are
commutative, and operator ⇒ is not.
Proved in class by checking truth tables.
For example, we checked that the truth table for
$$
a \Rightarrow b \Leftrightarrow b \Rightarrow a
$$
...does not have all true's in the output column, which shows that
"$\Rightarrow$" is not commutative.
In propositional logic, operators ∧, ∨, ⇔ and ⊕ are
associative, and operator ⇒ is not.
Proved in class by checking truth tables.
For example, we checked that the truth table for
$$
(a \vee b) \vee c \Leftrightarrow a \vee (b \vee c)
$$
... has all true's in the output column, which shows that
"$\vee$" is associative.