4
$\begingroup$

How are quantifiers ($\forall$ and $\exists$) managed in truth tables?

I'm not actually sure it would make sense to include them in truth tables, but I can't exactly say why either.

For example, is there a valid truth table for the following formula?

$\exists x \ \phi \rightarrow \forall x \ (\psi \ \vee \ \sigma)$

Thanks

$\endgroup$
  • 7
    $\begingroup$ I wouldn't put them in a truth table. Truth tables are generally for propositional logic, not first order logic with quantifiers. $\endgroup$ – Adrian Keister Aug 19 '18 at 1:23
  • $\begingroup$ @AdrianKeister So a truth table for such a formula is not defined, or it is/could be defined, but we don't bother with it as it isn't very useful? $\endgroup$ – Stephen Aug 19 '18 at 1:29
  • $\begingroup$ I find the way the notion of truth tables is presented endlessly frustrating. I've collected my thoughts (complaints) in this blog post. Your question reminds me of the hypothetical student I describe in this section encountering predicate logic and finding truth tables aren't adequate. You may find other sections useful to make it clear how narrowly focused most texts/courses on logic are. $\endgroup$ – Derek Elkins left SE Aug 19 '18 at 3:19
9
$\begingroup$

They aren't.

Truth tables do not work well in predicate logic. Intuitively a $\forall$ behaves like an infinitary conjunction and $\exists$ like an infinitary disjunction, but that would make the truth table infinitely wide. Or one could try to handle the choice of value for the variables analogously to truth assignments for propositional variables, but that would lead to infinitely many rows in the table.

Semantic tableaux can be viewed as an attempt to adapt truth tables to work with quantifiers, by creating the infinitely rows lazily, that is, only when we discover they would tell us something new. But the resemblance is not obvious, and they do not behave nearly as nicely as truth tables in propositional logic do.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

To echo Henning: They aren't.

But just to add some detailed clarification as to why not:

Remember that in logic we ask questions like: Does this claim follow from these other claims? Is this claim always (necessarily) true? Are these sentences consistent with each other? Now, all these questions can be boiled down to exploring logical possibilities:

Does this claim (conclusion) follow from these other claims (premises)? -> Is it possible for the premises to be true and the conclusion false?

Is this claim always (necessarily) true? -> Is it possible for this claim to be false?

Are these sentences consistent with each other? -> Is it possible for all of these sentences to be true?

What truth-tables do, is to effectively explore all possibilities by exploring all possible worlds: all different scenarios where the statements involved could be true or false. Each row represents such a world or scenario. And so, when we are asked to see if it is possible for a statement to be false, using a truth-table we would see if there is a row where it is false.

Now, this works beautifully for truth-functional (propositional/sententional) logic, since the level of analysis does not go any deeper than the level of atomic sentences, which themselves are true or false. This is why for a finite number of sentences, there are only a finite number of classes of possible worlds: one where all the atomic claims are all true, one where the are all false, one where ... well, you know the drill: with $n$ statements, you get $2^n$ possible classes of worlds to explore, i.e. $2^n$ rows in your truth-table

OK, but with predicate logic, this all changes. Here we go deeper, and analyze statements at the level of predicates and subjects, the latter being the objects that the quantifiers quantify over. Moreover, it turns out that the truth of these statements can easily depend on how many objects there are. So, if we are asked to consider all possible worlds, we immediately have to recognize that we would need to consider infinitely many worlds: one where there is 1 object, one where there are 2, etc. And that's not even considering all the ways in which those different objects have or not have certain properties, and how they may or may not be related to each other. So, a truth-table approach of trying to exhaustively go through all possible worlds can't work here.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.