
Introduction to Logic

Tools for Thought

As we have seen, some sentences are true in some truth assignments and false in others. However, this is not always the case. There are sentences that are always true and sentences that are always false as well as sentences that are sometimes true and sometimes false.
As with Propositional Logic, this leads to a partition of sentences into three disjoint categories. A sentence is valid if and only if it is satisfied by every truth assignment. A sentence is unsatisfiable if and only if it is not satisfied by any truth assignment. A sentence is contingent if and only if there is some truth assignment that satisfies it and some truth assignment that falsifies it.
Alternatively, we can classify sentences into two overlapping categories. A sentence is satisfiable if and only if it is satisfied by at least one truth assignment, i.e. it is either valid or contingent. A sentence is falsifiable if and only if there is at least one truth assignment that makes it false, i.e. it is either contingent or unsatisfiable.

Note that these definitions are the same as in Propositional Logic. Moreover, some of our results are the same as well. If we think of ground relational sentences as propositions, we get similar results for the two logics  a ground sentence in Relational Logic is valid / contingent / unsatisfiable if and only if the corresponding sentence in Propositional Logic is valid / contingent / unsatisfiable.
Here, for example, are Relational Logic versions of common Propositional Logic validities  the Law of the Excluded Middle, Double Negation, and deMorgan's laws for distributing negation over conjunction and disjunction.
p(a) ∨ ¬p(a) 
p(a) ⇔ ¬¬p(a) 
¬(p(a) ∧ q(a,b)) ⇔ (¬p(a) ∨ ¬q(a,b)) 
¬(p(a) ∨ q(a,b)) ⇔ (¬p(a) ∧ ¬q(a,b)) 

Of course, not all sentences in Relational Logic are ground. There are valid sentences of Relational Logic for which there are no corresponding sentences in Propositional Logic.

The Common Quantifier Reversal tells us that reversing quantifiers of the same type has no effect on truth assignment.
∀x.∀y.q(x,y) ⇔ ∀y.∀x.q(x,y) 
∃x.∃y.q(x,y) ⇔ ∃y.∃x.q(x,y)) 

Existential Distribution tells us that it is okay to move an existential quantifier inside of a universal quantifier. (Note that the reverse is not valid, as we shall see later.)
∃y.∀x.q(x,y) ⇒ ∀x.∃y.q(x,y)

Finally, Negation Distribution tells us that it is okay to distribute negation over quantifiers of either type by flipping the quantifier and negating the scope of the quantified sentence.
¬∀x.p(x) ⇔ ∃x.¬p(x) 
¬∃x.p(x) ⇔ ∀x.¬p(x) 

Use the arrow keys to navigate.
