Are we done with propositional logic, now that we can test for equivalence and tautologies, using truth tables? Possibly. Truth tables can answer any question about propositional logic, but not always conveniently.
Consider the following code:
bool do_something(int value)
{
bool a = …;
bool b = …;
if (a && !b)
return true;
else if (!a && !b)
return false;
else if (a)
return a;
else if (b)
return false;
else
return true;
}
Clearly, this is very ugly and should be simplified. But to what? We could build a truth table for the corresponding WFF, but so far we don't have any better way of finding a simpler equivalent formula than testing equivalence with whatever comes to mind. We need some way to generate formulas, given either an equivalent formula or a truth table.
There is another practical difficulty with truth table: they can get unwieldy.
Exercise 1
How many rows are there in a truth table with 2 input variables?
3 variables? 5 variables? 10 variables?
Solution
- 2 variables: As we're seen, 4 rows.
- 3 variables: 8 rows.
- 5 variables: 32 rows.
- 10 variables: 1024 rows.
-
Exercise 2
(Optional)
Now, how many such boolean
functions are possible, with 2 inputs? With 3?
For fun, sit down and name all the possible two-input functions.
You'll find that some of them are rather boring, such as the
constant function
Solution
- With 2 variables, we have 4 rows.
How many different ways can we assign
- With 3 variables, we have 8 rows and a total of 256 different functions.
- With
When discussing a circuit with 100 wires (each corresponding to a single proposition), truth tables are clearly infeasible. Modern processors have millions of wires and transistors. It is still an area of active research to cope with such a huge number of possibilities. (The key idea is to break things down into small sections, prove things about the small sections, and hopefully have a small set of sentences formally capturing the interface between sections.)
So truth tables are intractable for analyzing circuits of more than
a few wires.
But will they suffice for answering WaterWorld questions?
Image a (large) table with all the neighbor propositions:
Aside:
Also, this method of playing WaterWorld via huge truth tables would be unsatisfying for another reason: it doesn't actually reflect our own reasoning. As a general principle of programming, your program should always reflect how you conceive of the problem. The same applies to logic.
Aside:
So, no: we're not yet finished with propositional logic. We want to look for (hopefully) more feasible ways to determine whether a formula is a tautology (or, whether two formulas are equivalent). As a clue, we'll try to discover methods which are based on the way we naively approach this. We'll look first at equivalences, and then at inference rules.
