What about MPL? In the last topic, you used translation schemes to interpret MPL wffs. Here is an example of a translation scheme:

Domain: the set of all animals
Cx: x is a cat
Mx: x is a mammal

Here is a second translation scheme:

Domain: animals
Cx: x is a clock
Mx: x is a mammal

So, depending on how it is interpreted, "∀x(Cx→Mx)" formula may be taken to mean something true or false. In short, an MPL formula is true or false under an interpretation.

More formally, an interpretation of an MPL formula (or group of formulas) consists of (1) a non-empty domain of discourse, (2) a mapping from each constant in the formula(s) to an element of the domain, and (3) a mapping from each predicate letter in the formula(s) to a predicate.

For example, the two translation schemes above are both interpretations of the formula "∀x(Cx→Mx)".

For each of the following, find an interpretation under which the MPL formula is true.

Then find an interpretation under which the MPL formula is false.

1. ∀xHx

   Domain: the set of all cats
   Hx : x is a cat
   

   The formula is false under this interpretation:

   Domain: the set of all fish
   Hx : x is a cat
   

   '); ?>
2. ∃x(Px&Rx) Domain: the set of all pigs
   Px: x is a pig
   Rx: x is an animal
   

Domain: the set of all pigs
Px: x is a pig
Rx: x is a book

One can now define some logical properties of MPL formulas.

An MPL formula is consistent just in case it is true under at least one interpretation.

An MPL formula is inconsistent just in case it is true under no interpretations.

An MPL formula is valid just in case it is true under every interpretation.

In the exercises above, we have just seen examples of formulas which are consistent but not valid. (Can you think of other examples?)

"∃x(Ax & ~Ax)" is an example of an inconsistent formula. (Try to think of an interpretation which makes it true.)

"(Pa→∃xPx)" is an example of a valid formula. To see why, notice that this formula is false under an interpretation only if that interpretation makes "Pa" true and "∃xPx" false. But if an interpretation makes "Pa" true, then it makes "∃xPx" true too. So no interpretation makes "(Pa→∃xPx)" false; in other words, "(Pa→∃xPx)" is true under every interpretation.

(Don't be confused by the use of the word "valid" here. Earlier you learned about valid and invalid arguments. This is a different use of the technical term "valid" here. A valid MPL formula is not the same as a valid argument.)

The definitions of consistent and inconsistent MPL formulas can be extended to groups of MPL formulas:

A set of MPL formulas is consistent just in case there is at least one interpretation under which all the members of the set are true.

A set of MPL formulas is inconsistent just in case there is no interpretation under which all the members of the set are true.

For example, the following set of MPL formulas is consistent:

∃x Hx
∃x ~Hx


To see this, consider this interpretation:

domain: the set of all pigeons
Hx: x is male


Under this interpretation, "∃x Hx" means that at least one pigeon is male (which is true) and "∃x ~Hx" means that at least one pigeon is not male (which is also true). Since the formulas are both true under some interpretation, the set of formulas is consistent.

It is often easier to show consistency of a set of MPL formulas than to show inconsistency. Consistency can be shown with just one example; consistency can be shown by giving a single example of an interpretation under which all the formulas are true. However, one interpretation is not enough to show inconsistency; to show inconsistency one needs to show that there is NO interpretation under which all the formulas are true.

Still, it is sometimes clear that a set of MPL formulas is inconsistent:

∀x Hx
∃x ~Hx


Suppose that "∀x Hx" is true under some interpretation. Then the predicate which interprets "H" applies to every element of the domain of that interpretation. But, if so, then "∃x ~Hx" will not be true under that interpretation. For "∃x ~Hx" is only true if there is some element of the domain to which the predicate which interprets "H" does not apply. So there is NO interpretation under which both of these two formulas are true; this set of formulas is inconsistent. (Be aware that this is a rough argument, not a rigorous formal proof that these these two formulas are inconsistent.)

Which of the following sets of formulas are consistent?

1. ∃xHx

   Ha

   ~Hb

2. ∀x(Fx→Gx)

   ∃xFx

   ~∃xGx

3. ∀x(Fx & Gx)

   Fa

   Gb

In MPL01, it was noted that one cannot show that the following argument is valid using SL:

All hackers are nerds.
Mitch is a hacker.
So Mitch is a nerd.


At this point, we need just a few more definitions to be ready to work on this argument and see whether Mitch is really a nerd.

We need to define what it is for MPL formulas to imply or entail another formula:

An MPL formula &phi entails an MPL formula &psi just in case there is no interpretation under which &phi is true and &psi false.

Notice that there is a close connection between entailment and inconsistency:

&phi entails &psi if and only if &phi and ~&psi are inconsistent.

Stop and think to make sure you can see why entailment and inconsistency are connected in this way.

Now let us extend to definition of entailment to apply to groups of MPL formulas:

An set of MPL formulas S entails an MPL formula &psi just in case there is no interpretation under which all the members of S are true and &psi false.

This all sounds familiar. Remember the definition of "valid argument"? A valid argument is an argument where it is impossible for the premises to be true while the conclusion is false.

We have now formalized, in MPL, the notion of a valid argument. At last we are ready to think about Mitch.

All hackers are nerds.
Mitch is a hacker.
So Mitch is a nerd.


Consider the following formalization of this argument:

∀x(Hx → Nx), Hm Nm

What we want to know is whether or not "∀x(Hx → Nx)" and "Hm" entail "Nm". To show this, we need to show that there is no interpretation that makes "∀x(Hx → Nx)" and "Hm" true and "Nm" false. But we certainly cannot check every interpretation to show this. There are too many interpretations--- indeed, infinitely many. How can we do it?

For a hint, click here:

Here is some progress then: to decide whether or not an argument is valid, first formalize it. Then determine whether or not the set of premises entails the conclusion. (Or, equivalently, determine whether or not the formalized premises, together with the negation of the formalized conclusion, form a consistent set.) This completes the predicate logic topic for elementary logic.

There is much more to learn about predicate logic.

For example, it turns out that there are methods to determine whether or not a set of MPL formulas is consistent. In a word, MPL is decidable.

However, just as SL is not strong enough to show that the Mitch the hacker argument is valid, MPL is not strong enough to show validity in other cases. Full predicate logic (PL) is suitable for some of these other cases. Curiously (although perhaps unfortunately) PL is undecidable; there is no method to determine whether or not a set of PL formulas is consistent.

However, we must stop here. This is only a 3-credit course after all.

We hope you have enjoyed this course!