Logic 14: Language and Models for Predicate Logic Flashcards
QL Elements
1) all the resources from PL
2) infinitely many variables: x,y,z, etc
3) infinitely many names: a, b, c, etc
4) infinitely many predicate letters: F, G, H, etc
5) the existential (∃) and universal (∀) quantifiers
QL Grammar
1) If F is a predicate of adicity n and a1-an are names, then F(a1, . . ., an) is a wff
2) If A is a wff then ¬A is a wff
3) If A and B are wffs then (A∧B), (A∨B), (A→B) and (A↔B) are wffs
4) If A is a wff and a is a name and x a variable, then ∃xA(x/a) and ∀xA(x/a) are wffs, where A(x/a) is the result of replacing every occurrence of a in A with x.
QL Grammar explained
1) when we have a predicate, we can get a wff by putting a name in each of the slots the predicate has
- if it’s a monadic predicate, F, Fa is a wff, or Fb, or Fc
- if dyadic predicate G, then G(a,b) or G(b,c) or G(a,c)
4) we can take any of the wffs generated by the previous steps and replace every occurence of one name by the same variable, which is then bound by one of our two quantifiers
I know that Fa is a wff, and that G(a,c) is a wff.
Using old rules from PL I know that Fa→G(a,c) is a wff
So now I can replace every occurence of a name, let’s choose “a”, with a variable “x”
Fx→G(x,c)
Note that this is NOT a wff, but can make it a wff now by binding that variable with a quantifier like the existential quantifier
∃x(Fx→G(x,c))
Now this is a wff, and we could get rid of the other name, “c” and replace it with a new variable y
∃x(Fx→G(x,y))
which again, is NOT, a wff, but we can make it a wff by binding this variable with a quantifier, like the universal quantifier
∀y∃x(Fx→G(x,y))
now this is a wff
How to test for truth and falsity in QL
Need to know what a model of QL looks like and how to tell whether a wff is true or false on a given model
Elements of a Model for Predicate Logic (QL)
1) An assignment of truth-values to the simple sentence letters
2) A non-empty domain of subjects, D
3) An assignment that maps to each name an object from the domain, and maps at least one name onto every object from the domain
4) An assignment to each n-adic predicate, an extension of ordered n-tuples of objects from the domain
QL model explained, part i
1) everything our models for PL did, our models for QL also do,
For any simple sentence letters, we simple say whether they are true or false
2) our models needs to specify the things that we are talking about- the domain
- specially when we use our quantifiers
- ex. when we use the universal quantifier to say that everything is some way, what things are we talking about when we say everything?
- need to specify– “Everyone needs to take the final exam,” meaning everyone in the class.
- thus the class is the DOMAIN of our quantifier
- the domain can be any set of things we like, but it must have some things in it, it cannot be the empty set
- when we talk about everything, we must be talking about something
QL model explained, part ii
3) for each name we are using, we must use it to name some thing in the domain
- more than one name can name the same thing in the domain, but no name can name MORE than one one thing in the domain
- our language is designed to eliminate ambiguity, names must name a unique thing
- two things cannot have the same name (unlike people in the real world)
- but everything in the domain must get at least one name, nothing can go unnamed in a model
4) tells us to assign an EXTENSION to each predicate
- these are the things from the domain that the predicate applies to
ex1. monadic predicates- the extension will be the subset of the domain that is all the things that have the relevant property
- - suppose our domain is all the people, and we have a predicate M(x) for “x is a man”
- the extension for the predicate M will be the subset of people who have the property of being a man
ex2. dyadic predicates
- say the domain is all people
- L(x,y) for “x loves y”
- want to pick out the things in the domain that this predicate hold between, all the PAIRS of people such that the first loves the second
- if Romeo and Juliet are both people, and Romeo loves Juliet, we want our model to show that L holds between that pair of people, form the first to the second
– difficulty is preserving the ORDER, while Romeo loves Juliet, Juliet may not love Romeo
- thus we can’t simply put the set containing both Romeo and Juliet into the extension of L, because the ORDER of a set’s members does not matter
{Romeo, Juliet} = {Juliet, Romeo}
- we need an ORDERED PAIR
- like a set because it’s a collection of things, but unlike a set bc order of the elements matter
Ordered Pairs
Like sets in that they are collections of things, but order matters, noted using <a>
is different from</a>
Can also have ordered triples, ordered 4-tuple, etc for predicates of greater adicity
We assign a set of ordered n-tuples to every predicate of adicity n</a>
Model of QL
D: {Obama, Trump, Clinton}
“I(x)” means “the interpretation of x”
- in saying what the names name, and what the predicates apply, we are interpreting them
I(o): Obama
I(b): Trump
I(c): Clinton
I(p): Obama
“F” and “G” are monadic predicates, so they get assigned subsets of the domain
I(F): {Obama, Clinton}
- F gets both Obama and Clinton, so this model says that Obama and Clinton are both F, but that Trump is not
I(G): {Trump}
- says Trump is G but Obama and CLinton are not
I(H): {, }
- dyadic relation H, its extension consists of a set or ordered pairs of things from the domain
- Obama bears H to Trump, and Trump bears H to Clinton, and that’s it
- so Trump does not bear H to Obama, etc
Truth rules on QL model
1) The usual rules for propositional logic all still hold
2) F(a1, . . ., an) is true iff <i> ∈ I(F)
3) ∃xA is true iff there is some name, a, such that A(a/x) is true, where A(a/x) is the result of replacing every occurrence of x bound by the existential quantifier with a
4) ∀xA is true iff for every name, a, A(a/x) is true</i>
QL Truth rule #2: F(a1, …, an) is true iff <i> ∈ I(F)</i>
- where “∈” means “is a member of”
Given:
D: {Obama, Trump, Clinton}
I(o): Obama
I(b): Trump
I(c): Clinton
I(p): Obama
I(F): {Obama, Clinton}
I(G): {Trump}
I(H): {, }
ex. asked whether ‘F(c)’ is true
- it is true iff I(c) ∈ I(F)
I(c) = Clinton and I(f) = {Obama, Clinton}
Clinton ∈ {Obama, Clinton}
Thus, “F(c)” is true
QL Truth rule #3: ∃xA is true IFF there is some name, a, such that A(a/x) is true, where A(a/x) is the result of replacing EVERY occurence of x bound by the existential quantifier with a
- the first one is replacing the occurrences of the second one
D: {Obama, Trump, Clinton}
I(o): Obama
I(b): Trump
I(c): Clinton
I(p): Obama
I(F): {Obama, Clinton}
I(G): {Trump}
I(H): {, }
ex. asked whether ‘∃xFx’ is true
- this is true if there is some name we can substitue for “x” in “Fx” such that the resulting sentence is true
- for ‘∃xFx’ to be true, either “Fo” or “Fb” or Fc” or “Fp” have to be true
- Fo and Fc are true, so ‘∃xFx’ is true
ex2. ‘∃x∃yH(x,y)’ ?
- and
- this is true iff there is some name we can put in place of “x” such that ‘∃yH(x,y)’ is true
- will be true since both Obama and Trump occupy the first slot in an instance of H
- so let’s use a name for Obama,
that gives us ‘∃yH(o,y)’
- now we need to check if there’s a name we can put into y such that H(o, y) is true
– we can put the name for Trump, “b” which = H(o,b)
- is this true in our model? yes, because <i></i>
QL Truth rule #4: ∀xA is true IFF for every name, a, A(a/x) is true
- this is true iff every sentence that we can get by substituting a name for x in Fx is true
D: {Obama, Trump, Clinton}
I(o): Obama
I(b): Trump
I(c): Clinton
I(p): Obama
I(F): {Obama, Clinton}
I(G): {Trump}
I(H): {, }
ex. “∀xFx” ?
- this is true iff every sentence that we can get by substituting a name for x in Fx is true
- well, this is not the case
- we can substitute b for x to get Fb, and this is false on the model because I(b) ∉ I(F)
ex. 2 ‘∀x(Fx∨Gx)’?
- note that this says SOME name is replaced, does not mean the set includes everything
- true because whatever name we put in place of x in Fx v Gx, the result will be a true sentence
- Fo v Go is true because Fo is true
- Fb v Gb is true because Gb is true
- Fc v Gc is true because Fx is true
- we’re replacing all of x with ONE name
Validity in QL
- same as PL
- an argument is Semantically valid (double turn style) just in case every model that makes all the premises true also makes the conclusion true
- trying to see whether it is possible to construct a model that makes the premises true but the conclusion false (a counter-example), demonstrating semantic invalidity of the argument
- if there is no such model- no counter example, then the argument is semantically valid
QL Validity Example 1
1) Every president is a republican
2) There is a female president
C) There is a female republican
Can I construct a model on which 1 and 2 are true, but C is false?
To make 2 true, there has to be an element of the domain that is a member of the extensions of both the predicate “is female” and the predicate “is a president”
To make 1 true, that element of the domain has to be a member of the extension of the predicate “is a republican”, since I have put it into the extension of “is a president” and 1 says that every president is a republican
- but since this person is a member of the extension of the predicate “is female” already, this means I’ve done everything required to make it the case that they are in the extension of both “is female” and “is a republican”, which is all that takes to make C true
- in making a model on which 1 and 2 are both true, I have done what it takes to make C true on that model
- the argument is semantically valid
