John Beverley

View Original

Logic Notes 11/11 - 11/15

Quantifiers, Interpretations, and Expansions

Recall in our logic with just sentence letters and connectives, we defined validity as:

An argument in is truth-functionally valid iff: if all of its premises are true then its conclusion is true

We need something more for quantificational logic.  We need the notion of truth on an interpretation:

An argument is quantificationally-valid iff: there is no interpretation on which all of its premises are true and its conclusion is false.

Consider the following sentences of our logic with predicates, relations, and quantifiers:

Mb
Wm

These sentences will have different truth values on different interpretations.  Consider the following two interpretations.

D: People
M:   is male.
W:   lives in the White House
b: Barack Obama
m: Michelle Obama

D:  Animals
M:   is a manatee
W:   is a wombat
b: Bruce Willis
m: Minnesota

Mb
Wm

On the first interpretation, both of the sentences are true, because Barack Obama is (in fact) male, and Michelle Obama lives in the White House and is not male.  On the second interpretation, both sentences are false, because Bruce Willis is not a manatee and Minnesota is not a wombat.

If you didn’t know anything about Barack, Michelle, Bruce, and Minnesota, you wouldn’t be able to tell whether these sentences are true on these interpretations.  But there are ways of providing interpretations so that anyone can tell whether the sentences are true or false in the interpretation.  Consider the following interpretation.

-------------------------------------

|           W                    MW     |

|             ☺                  ☺        |

-------------------------------------

D: The figures above
M:   has an “M” above it
W:   has a “W” above it
b: the first figure above.
m: The second figure above.

The first sentence is false on this interpretation, and the second one is true.

That said, there are some sentences that are true in absolutely all interpretations, such as:

Mb v ~Mb

No matter what object ‘b’ refers to in this interpretation, and no matter what ‘M’ means in that interpretation, that object either has the property meant by ‘W’ in that interpretation or it does not.

Consider the following argument. Mb & Wm  |= Mb

If the premise is true on an interpretation, then so is the conclusion.  There is no interpretation on which the premise is true and the conclusion is false.  Therefore, the argument is valid.

The following argument is invalid. Mb  |= Wm

We can see this by producing an interpretation on which the premise is true and the conclusion is false.

-------------------------------------

|            M                                |

|             ☺                  ☺        |

-------------------------------------

D: The figures above
M:   has an “M” above it
W:   has a “W” above it
b: the first figure above
m: The second figure above.

Consider the following small interpretation.

-------------------------------------

|           F                      FG       |

|           ☺                    ☺        |

|                                               |

------------------------------------

D: the smiley faces above
F:  has an “F” above it.
G:   has a “G” above it.

Let’s now determine whether the following sentence is true in this small domain.

VxFx

I think it is obvious that this sentence is true in this interpretation:

A sentence of the form Vvφ is true in an interpretation iff: every object in the domain of the interpretation satisfies φ.

So the above sentence will be true in this interpretation iff every object in the domain satisfies “Fx”.  We can see whether every object in the domain satisfies this open sentence by giving the stick figures names, ‘a’ and ‘b’ respectively, and then deciding whether the resulting sentences are true.

Similarly, let’s determine whether the following sentence is true in the above interpretation.

ExGx

I hope that it is obvious that it is true in the above interpretation.  Here is an official rule.

A sentence of the form Evφ is true in an interpretation iff: there is an object in the domain of the interpretation that satisfies φ.

We can see whether ‘ExGx’ is true in this interpretation by seeing whether there is a stick figure in the domain that satisfies ‘Gx’. 

You might notice that the universal is true iff both instantiations are true, while the existential is true iff either one or the other is true. When the domain of an interpretation is finite, then a universal generalization is true in that interpretation if and only if a certain conjunction is true.  And existential generalizations are true iff a certain disjunction is true.  Consider the following sentences.

VxFx.

EyFy

---------------------------

|           F                      |

|           ☺        ☺        |

-----------------------------

D: The smiley faces
F: has an “F” above it.
a: The first smiley face.
b: The second smiley face.

Notice that the first and second smiley faces are the only objects in the domain of quantification ‘a’ and ‘b’ name these objects in this interpretation.  Therefore:

“ExFx” is true in this interpretation iff  “Fa v Fb” is.

“VyFy” is true in this interpretation iff  “Fa & Fb” is.

This conjunction and disjunction are the expansions of the universal and existential in the above interpretation.  You can now use truth-table rules to discover that that the disjunction is true in this interpretation and the conjunction is false in this interpretation.  So, you can infer that the universal is false in this interpretation and the existential is true in this interpretation.

1.  To find the expansion of some quantified sentences in a finite domain, first name everything in the domain.

2.  Next, start with the leftmost quantifier.  Replace universals with conjunctions using every name to replace the variable.  Replace existentials with disjunctions.

3.  After that, work your way into further quantifiers.  Be sure to keep parentheses.

Notice that the expansion of a sentence will be different with different interpretations. Suppose that we have three objects in the domain, as in the following interpretation.

------------------------------------

|           F          G          F         |

|           ☺        ☺        ☺        |

------------------------------------

D: The smiley faces
F:  has an “F” above it.
G:  has a “G” above it.

Then:

VxFx               expands to       (Fa & Fb) & Fc
ExFx                expands to       (Fa v Fb) v Fc

The placement of parentheses makes no difference.

Now, let’s move on to checking whether arguments are valid using interpretations. Consider:

Fa \= VxFx.

Check whether we can construct an interpretation that uses a domain with just one object (We can’t; we need a domain with at least two objects).

---------------------------

|           F                      |

|           ☺        ☺        |

----------------------------

D: The smiley face above
F:   has an “F” above it
a: The smiley face above.

The premise is true in this model, but the conclusion is false.  So this argument is invalid.   We can use an expansion to check this. Here is a numerical interpretation that is structurally analogous.

D: {1, 2}
F:   is in .
a: 1