Using Truth Tables 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 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 and a b c aren't equivalent. Truth table to check associativity of implication abc(a⇒(b⇒c))((a⇒b)⇒c)

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 and c . 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 . For example, in the above problem, 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 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 . Is this equivalent to the WFF a b a b ? Here is a truth table: Truth table for comparing conditionals' equivalence ab¬(a∧b)(a∨b)(¬(a∧b)∧(a∨b))(a∧¬b)(¬a∧b)((a∧¬b)∨(¬a∧b))

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-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 — and — 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 . (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 is true.)