FO validity, FO consequence, FO equivalence
Another look at the central topics of the course. The general notions we want to capture are logical truth, logical consequence, and logical equivalence. Propositional logic gives us attempts to capture at least part of these general notions: tautology, tautological consequence, and tautological equivalence. These notions have the advantages of precision and mechanical testability, but they don't give us everything we want (there are logical truths that are not tautologies, logical consequences of a set of premises that are not tautological consequences of those premises, etc.).
Now that we have added quantifiers, we can get closer to the general notions. We now add the concepts of first-order validity (FO validity for short), FO consequence, and FO equivalence.
(Note: in Fitch, Taut Con tests for tautological consequence and FO Con tests for first-order consequence.)
|propositional logic||FO Logic||General Notion|
|P is a tautology iff P is true in every row of
its truth table (alternatively: iff P is not false in any row of its
example: Tet(a) v ~Tet(a)
|P is a FO validity iff P must be true
regardless of what the predicates mean and the names refer to
(alternatively: P cannot be false regardless of what the predicates mean
and the constants refer to)
example of a FO validity that is not a tautology: Ax (Tet(x) v ~Tet(x))
|P is a logical truth iff P must be true
(alternatively: iff P cannot be false)
example of a logical truth that is not a FO validity: Ax ~(Tet(x) & Cube(x))
|P is tautologically equivalent to Q iff P and Q have the same truth value in every row of a joint truth table (alternatively: iff P and Q do not have different truth values in any row of their joint truth table)||P is FO equivalent to Q iff P and Q must have the same truth value regardless of what the predicates mean and the names refer to (alternatively: iff P and Q cannot have different truth values regardless of what the predicates mean and the constants refer to)||P is logically equivalent to Q iff P and Q must have the same truth value (alternatively: iff P and Q cannot have different truth values)|
|C is a tautological consequence of P1 . . . Pn iff C is true in every row of a joint truth table in which P1 . . . Pn are all true (alternatively: iff there is no row of their joint truth table in which P1 . . . Pn are all true and C is false)||C is a FO consequence of P1 . . . Pn iff, if P1 . . . Pn are all true, then C must be true, regardless of what the predicates mean and the constants refer to (alternatively: iff it is not possible for P1 . . . Pn to all be true and C false, regardless of what the predicates mean and the constants refer to)||C is a logical consequence of P1 . . . Pn iff, if P1 . . . Pn are all true, then C must be true as well (alternatively: iff it is not possible for P1 . . . Pn to all be true and C false)|
Truth-functional form of quantifier sentences
The notion of a tautology is still applicable to first-order
logic, but is a little trickier to apply. We can no longer simply pull out the
atomic sentences in a compound sentence and use those to form the reference
columns of a truth table. But we can do something very similar. We first
determine the truth-functional form of the quantifier sentence(s) we want to
check, and then do a truth table for the truth-functional forms of the sentences
rather than the sentences themselves. See the text for details.
(including DeMorgan's, left over from last time) Why the DeMorgan's
equivalences for quantifiers are called "DeMorgan's equivalences for
quantifiers": the analogy between universal quantification and conjunction,
and between existential quantification and disjunction. Other equivalences.
Caution: some things that look similar to genuine equivalences aren't
Can be thought of as helping to take up the slack between first-order
consequence and the intuitive notion of logical consequence. Axioms specify
relations between predicates that depend on their meaning. (For instance, it
isn't part of logic proper to express the fact that for any objects x and y, x
is larger than y if and only if y is smaller than x. But we can formulate an
axiom that states this.) Occasionally axioms may express background assumptions
about a particular domain rather than purely logical relationships: for
instance, if we are discussing Tarski's World, we may want an axiom stating that
for all objects x, either x is a cube or x is a dodecahedron or x is a
tetrahedron. This clearly is not a purely logical truth -- there are many
counterexamples in the actual world! But it is true in Tarski's World, so as
long as we know we are dealing with Tarski's world, it can be useful to have it
as an axiom.
Sentences with multiple quantifiers
(Introduction only.) The amazing riches made possible by quantifiers.
Remarkable number (six, to be precise) of distinct propositions we can express
using only a single two-place predicate and two quantifiers.
To say, for example, that one object is larger than every other object, we need to explicitly express the "other" part by using the negation of an identity statement. Example: suppose we want to say that there is a cube that is larger than every other cube. The following sentence will not work: ∃x (Cube(x) ∧∀y (Cube(y) → Larger(x,y)). In fact, this sentence will never be true! The only way it could be true is if there were a cube that is larger than every cube, including itself. Since nothing can be larger than itself, this sentence cannot be true under any circumstances. Instead, we need to translate "other" by using x ≠ y, like this:
∃x (Cube(x) ∧∀y((Cube(y) ∧ x ≠ y) → Larger(x,y))