Is ⇒ associative? In other words, is a ⇒ (b ⇒ c) always equivalent to a ⇒ b ⇒ c? What is a methodical way of answering questions of this type? We can make a truth table (Definition: "truth table", p. 19) with two output columns, one for each formula in question, and then just check whether those two columns are the same.
Exercise 2.2.1.1
Use truth tables to show that a ⇒ (b ⇒ c) and (a ⇒ b) ⇒ c aren't equivalent.
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 (Using Truth Tables), we could have
made a truth table for the single formula 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), one for ψ =(a ⇒ b) ⇒ c, and one for φ ⇔ ψ; filling out the first two helper columns makes it easier to fll out the last column.
Tip
When making a truth table for a large complicated WFF by hand, it's helpful to make columns for sub-WFFs; as you fll in a row, you can use the results of one column to help you calculate the entry for a later column.
Exercise 2.2.1.2
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 c onditional?
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.
So, how would do we use truth tables to reason about WaterWorld? Suppose you wanted to show that G − safe was true on some particular board. Clearly a truth table with the single column G − 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 (Propositional axioms for 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. (Notice
how this formula effectively ignores all the rows of 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 is true.)
- 2384 reads