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

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.

Login

Accessing this textbook requires a login. Please enter your credentials below!