Is ⇒⇒ associative? In other words, is
a⇒(b⇒c)
a
b c
always equivalent to
a⇒b⇒c
a b
c
?
What is a methodical
way of answering questions of this type?
We can make a
truth table
with two output columns,
one for each formula in question,
and then just check whether those two columns are the same.
Use truth tables to show that
a⇒
b⇒c
a
b c
and
a⇒b
⇒c
a b
c
aren't equivalent.
Table 1: Truth table to check associativity of implication| aa | bb | cc | (a⇒(b⇒c))(a⇒(b⇒c)) | ((a⇒b)⇒c)((a⇒b)⇒c) |
|---|
| false | false | false | true | false |
| false | false | true | true | true |
| false | true | false | true | false |
| false | true | true | true | true |
| true | false | false | true | true |
| true | false | true | true | true |
| true | true | false | false | false |
| true | true | true | true | true |
By inspecting the two right-most columns,
we see that the formulas are indeed not equivalent.
They have different values for two truth-settings,
those with
a=falsea and
c=falsec .
Thus we see that truth tables are a method for answering
questions of the form
“Is formula φφ equivalent to formula ψψ?”
We make a truth table, with a column for each of φφ and ψψ,
and just inspect whether the two columns always agree.
A bit of a brute-force solution, but certainly correct.
What about the related question,
“Is formula θθ a tautology?”.
Well, obviously truth tables can handle this as well:
make a truth table for the formula, and inspect whether all
entries are true.
For example, in the
above problem,
we could have made a truth table for the single formula
a⇒
b⇒c
⇔
a⇒b
⇒c⇔
a
b c
a b
c
.
The original question of equivalence becomes,
is this new formula a tautology?
The first approach is probably a tad easier to do by hand,
though clearly the two approaches are equivalent.
Another handy trick is to have three output columns
you're computing:
one for
φ=a⇒
b⇒c
φ
a
b c
,
one for
ψ=
a⇒b
⇒c
ψ
a b
c
,
and one for
φ⇔ψ⇔ φ ψ;
filling out the first two helper columns
makes it easier to fill out the last column.
When making a truth table for a large complicated WFF by hand,
it's helpful to make columns for sub-WFFs;
as you fill in a row, you can use the results of one column
to help you calculate the entry for a later column.
Is it valid to replace the conditional
int do_something(int value1, int value2)
{
bool a = …;
bool b = …;
if (a && b)
return value1;
else if (a || b)
return value2;
else
return value1;
}
with this conditional?
int do_something(int value1, int value2)
{
bool a = …;
bool b = …;
if ((a && !b) || (!a && b))
return value2;
else
return value1;
}
After all, the latter seems easier to understand, since it
has only two cases, instead of three.
In the original code, we return value2
when the first case is false, but the second case is true.
Using a WFF, when
¬(a∧b)∧(a∨b)
a b
a b
.
Is this equivalent to the WFF
a∧¬b∨¬a∧b
a b
a b
?
Here is a truth table:
Table 2: Truth table for comparing conditionals' equivalence| aa | bb | ¬(a∧b)¬(a∧b) | (a∨b)(a∨b) | (¬(a∧b)∧(a∨b))(¬(a∧b)∧(a∨b)) | (a∧¬b)(a∧¬b) | (¬a∧b)(¬a∧b) | ((a∧¬b)∨(¬a∧b))((a∧¬b)∨(¬a∧b)) |
|---|
| false | false | true | false | false | false | false | false |
| false | true | true | true | true | false | true | true |
| true | false | true | true | true | true | false | true |
| true | true | false | true | false | false | false | false |
Yes, looking at the appropriate two columns we see they are equivalent.
So, how would do we use truth tables to reason about WaterWorld?
Suppose you wanted to show that G-safeG-safe was true on some particular
board. Clearly a truth table with the single column G-safeG-safe
alone isn't enough (it would have only two rows — false and
true — and just sit there and stare at you).
We need some way to incorporate both
the rules of WaterWorld
and the parts of the board that we could see.
We can do that by
starting with a huge formula
that was the conjunction of all
the WaterWorld domain axioms; call it ρρ.
We would encode the board's observed state with another formula, ψψ.
Using these, we can create the (rather unwieldy) formula that
we're interested in:
ρ∧ψ⇒G-safe
ρ ψ
G-safe
.
(Notice how this formula effectively ignores
all the rows of the the truth-table
that don't satisfy the rules ρρ,
and the rows that don't correspond to the board we see ψψ:
because of the semantics of ⇒⇒, whenever
ρ∧ψρ ψ is false, the overall formula
ρ∧ψ⇒G-safe
ρ ψ
G-safe
is true.)
