2 of 2

25.1 DeMorgan’s for Quantifiers (DeMQ)

We just saw the Aristotelian pairs of contradictories generate some equivalences in FOL.

FO Equivalences: sentences that co-vary in truth value in FOL

FO Equivalences are sentences that are equivalent in FOL. They always have the same truth value.

FOL includes the truth-functional connectives. So all the equivalences of BOOL and PROP still hold here.

For example,

~(PvQ) ⇔ ~P&~Q (DeM)

is an FOL equivalence.

Tautological Equivalence: equivalence that depends just on the truth-functional connectives.

Since it is an equivalence that depends just on the truth-functional connectives, we can call it a tautological equivalence.

But FOL also includes the quantifiers and identity.

Any equivalence that depends on them will be an FO equivalence but not a taut-equivalence.

The most important FO equivalence concerns the interaction of the quantifiers and negation:

~AxP(x) ⇔ Ex~P(x)

~ExP(x) ⇔ Ax~P(x)

DeMorgan’s for Quantifiers (DeMQ)
~AxP(x) ⇔ Ex~P(x)
~ExP(x) ⇔ Ax~P(x)

These are called DeMorgan’s for Quantifiers (DeMQ). Sort of like the original DeMorgan’s, when you push in the negation you flip from one quantifier to the other.