Section Progress:

24.1 DeMorgan’s for Quantifiers (DeMQ)

We just saw of 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.

25.1 DeMorgan’s for Quantifiers (DeMQ)