Maggie Johnson Handout #17

CS103A

The Logic of Quantifiers

Key Topics

· Tautologies with Quantifiers

· First-Order Validity, Equivalence & Consequence

· DeMorgan’s & Other Equivalences for Quantifiers

What quantified sentences are logical truths?

What arguments involving quantifiers are valid?

Tautologies with Quantifiers

Can we ignore quantifiers in determining truth value?

1. "x (Professor(x) ® Smart(x))

"x Professor(x)

---

"x Smart(x)

2. "x Professor(x)

"x Smart(x)

---

"x Professor(x) ^ Smart(x)

3. $x (Professor(x) ® Smart(x))

$x Professor(x)

---

$x Smart(x)

4. $x Professor(x)

$x Smart(x)

---

$x Professor(x) ^ Smart(x)

One way of arriving at tautologies is to substitute complex, quantified sentences into a known tautology from prepositional logic. Here is a known tautology:

P v ~P

The following is also a tautology:

("x (Professor(x) ® Smart(x))) v ~("x (Professor(x) ® Smart(x)))

Truth-Functional Form: All quantified sentences and atomic sentences have been replaced by variables, and the truth-functional connectives outside the scope of the quantifiers or connecting atomic sentences have been maintained.

A quantified sentence in FOL is a tautology iff its truth-functional form is a tautology.

$x (Professor(x) ® Smart(x)) $x Professor(x) ® $x Smart(x)

$x Professor(x) $x Professor(x)

--- ---

$x Smart(x) $x Smart(x)

First-Order Validity, Equivalence and Consequence

Propositional Logic	First-Order Logic	General Notion
Tautology	FO Validity	Logical Truth
Tautological Consequence	FO Consequence	Logical Consequence
Tautological Equivalence	FO Equivalence	Logical Equivalence

A sentence of FOL is FO valid if it is a logical truth when you ignore the meanings of the names, function symbols and predicates (other than the identity symbol).

A sentence of FOL is an FO consequence of premises P1,…,Pn if it is a logical consequence of these premises truth when you ignore the meanings of the names, function symbols and predicates (other than the identity symbol).

Two wff’s are FO equivalent if, in any possible circumstance, they are satisfied by the same objects. That is, if, when you replace the free variables in the wff’s with new names, the resulting sentences are logically equivalent.

DeMorgan’s & Other Equivalences for Quantifiers

~"x P(x) ó $x ~P(x)

~$x P(x) ó "x ~P(x)

"x (P(x) ^ Q(x)) ó "x P(x) ^ "x Q(x))

$x (P(x) v Q(x)) ó $x P(x) v $x Q(x)

For any wff P in which x is not free:

"x P ó P

$x P ó P

"x (P v Q(x)) ó P v "x Q(x)

$x (P ^ Q(x)) ó P ^ $x Q(x)

For any wff P(x) and variable y that does not occur in P(x):

"x P(x) ó"y P(y)

$x P(x) ó$y P(y)