25.3 Truth-Functional Form Algorithm (TFFA)
If we have a sentence with a combination of connectives and quantifiers, it can be difficult to tell whether it is a tautology or FO validity.
For example, compare these two sentences:
They are both necessarily true, and they both involve connectives and quantifiers. Since they involve quantifiers, does that mean they are FO validities and not tautologies?
The mere presence of the quantifier does not disqualify these from being tautologies.
The key question is: what is guaranteeing that they are necessarily true? If the truth-functional connectives alone guarantee it is true, then it is also a tautology, regardless of whether quantifiers are in the sentence.
Basically, if the quantifiers aren’t doing the work to make it necessarily true, just the connectives are, then it is a tautology.
What we need is a tool for telling what is doing the work in a sentence. That is what the Truth-Functional Form Algorithm (TFFA) is.
Basically, whenever something is inside the scope of a quantifier, then that quantifier is doing work. If some connectives appear outside the scope of any quantifier, then they are doing truth-functional work.
Here’s how it works.
Work from left to right through a formula following these steps.
Step 1: Start underlining when you get to a quantifier (or a sentence with identity), and continue underlining until you get to the end of its scope.
Each underlined part of the sentence is now its own chunk.
Step 2: Replace the first underlined part with P, and replace any other chunks that are identical with P too. Replace the next underlined chunk with Q, etc.
A chunk counts as identical only if it is literally identical: the exact same string of symbols in the exact same order. Different variables, for example, would not count as identical.
The result is called the truth-functional form of the original sentence. Let’s see if you can do it.
Even though these sentences are similar, they don’t have the same truth-functional form (TFF).
Since the form of ∃xP(x)→∃xP(x) is P→P, and that is a tautology, that tells us the original sentence is a tautology too.
Basically, the quantifiers aren’t doing the work that guarantees that it is true.
But the TFF of ∃xP(x)→∃x~~P(x) is P→Q, which is not a tautology. So the original sentence is not a tautology.
You can hopefully tell that it is still an FO validity. But since the double negation is inside the scope of the quantifier, the quantifier is doing work here.
Since identity, =, is part of FOL but not part of truth-functional logic (BOOL and PROP), we need to ignore it too. That is why = is included in step 1.