Introduction to Symbolic Logic

June 29, 2005

v Mini-Review

Ø Recall the study of SL – Syntax/translations, Semantics, Derivations

Ø Predicate Logic is an extension of SL

§ So far, we have established the syntax of PL in order to do translations

§ In order to talk about the meaning of a PL sentence, we now have to establish a semantics for PL

v PL Semantics

Ø The semantics of SL was relatively straightforward.

§ We began by defining the basic truth tables for each of the truth-functional connectives

§ We then showed that truth tables give us a decision procedure for deciding the truth of a sentence or other properties about sentences or arguments

· Even though it can be tedious, it is always possible to construct a complete truth table (that is, even if a sentence has a larger number of sentence letters than we would want to deal with, a computer program could work out the truth values for each line of the table)

§ Unfortunately, the semantics of PL is more complex because even an atomic PL sentence is made up of distinct parts: a predicate and some number of singular terms

· This means that we cannot simply do a truth table to determine the truth of a PL sentence; instead, we have to give an interpretation

Ø Interpretations

§ We have already seen what an interpretation looks like whenever we have seen or constructed a symbolization key

§ Essentially, an interpretation gives us a way to interpret a PL sentence

§ Technically, an interpretation is a function that takes a piece of PL as input and outputs its meaning

· Remember the analogy of a “real world” and a “symbolic world” from when we first began studying SL.

· The interpretation establishes how the symbolic world connects to the real world.

· An interpretation consists of the specification of a UD and the assignment of a truth-value to each sentence letter of PL, a member of the UD to each individual constant of PL, and a set of n-tuples of members of the UD to each n-place predicate of PL.

§ We can provide interpretations that show certain facts about sentences or arguments, in the same way we could use truth tables to show semantic properties of SL

· The interpretation method is not a decision procedure, however, so it is not possible to use it for every sentence of PL.

· Fortunately, it can be used reliably when all of the predicates are one-place and we will use a method that makes it easier to deal with 2-place predicates

Ø Quantificational Properties

§ The truth-functional properties that SL has are called quantificational properties in PL

· There are counterparts for each property, but we will focus on consistency and validity because they’re the most interesting

§ Briefly, the Properties of Sentences

· A PL sentence can either be quantificationally true, false or indeterminate

· Just as with truth-functional truth, falsehood, and indeterminacy, it is the form of the sentence that determines whether it holds one of these properties

· Quantificational Truth (for example) – true on every interpretation

¨ No matter what you assign as your interpretation, this kind of sentence will be true

¨ Ex. ($x)(Gx Ú ~Gx)

Ø No matter what G is in the interpretation, we know that this has to be true

Ø We can’t possibly go through every possible interpretation to show that this is quantificationally true, but we can reason that it is and looking at a diagram of a possible interpretation can help us do that

§ DIAGRAM METHOD 1 – any one-place predicate is represented as a circle. Anything that falls in that circle has the property (G in this case); anything that falls outside the circle does not have the property

Ø Recall that a UD must be non-empty. The diagram shows us that a singular term must be either in the G circle or out of it, so this sentence is true, regardless of what UD we choose and what we assign to G.

¨ It is not always so easy to reason why a sentence is a quantificational truth, but we can show that it is not one more easily by showing that there is at least one interpretation on which the sentence is false.

Ø Ex. (Ga & ($x)Bx) É ("x)Bx

§ In order to make this sentence false, we need to make the antecedent true and the consequent false

· DIAGRAM METHOD 2 – any individual constant is represented as a point in the diagram

§ Note that an interpretation doesn’t have to be exactly like the ones we have already seen.

· The formal definition of an interpretation tells us that each predicate is a set of n-tuples. A one-place predicate can be defined by the set that lists each member of the UD that has that property

· This allows us to make very simple interpretations based on the diagrams that can show, at least, that a sentence does not hold a particular property

· DIAGRAM METHOD 3 – we can read an interpretation off the diagram in the following way:

¨ Any individual constants that are named in the diagram are made part of the UD.

¨ Each one-place predicate is assigned a set that lists the members of the UD that are in the predicate’s circle

¨ Each individual constant is named as it is in the diagram

· The resulting interpretation may look a little unnatural, but it suffices to show that a sentence is NOT quantificationally true

¨ When a sentence includes two-place predicates, these describe relations between singular terms rather than properties of them

Ø DIAGRAM METHOD 4 – two-place predicates are represented with an arrow. These relational predicates are then written in the interpretation as a set of ordered pairs

§ We’ll see an example of this soon.

· A similar method can be used to show that a sentence is not quantificationally false or that it is indeterminate (by providing 2 interpretations)

· We can also show that two sentences are quantificationally equivalent, but the fun really starts when we talk about consistency

Ø Quantificational Consistency

§ A set of sentences is quantificationally consistent iff there is at least one interpretation on which all members of the set are true.

§ To show this all we need to do is draw one diagram in which all sentences of the set are true and then read that interpretation off the diagram

· DIAGRAM METHOD 5 – It is a good idea to always start with a UD of about 4 terms. When there are less than 4 terms, the interpretation sometimes won’t behave the way you want it to. While it doesn’t matter so much with consistency since all we care about is finding one interpretation, when we do validity it will be important to use at least more than 2 elements in your diagram.

§ Ex. {("x)Gax, ~Gba Ú ($x)~Gax}

§ Ex. {("x)(Fx É Gx), ("x)(Fx É ~Gx)

· We can make this set consistent by making F be the empty set. That is, no singular term in the UD has that property so both of these conditionals are vacuously true.

Ø Quantificational Validity

§ An argument of PL is quantificationally valid iff there is no interpretation on which every premise is true and conclusion is false.

§ To show that an argument is quantificationally invalid, we need to design an interpretation on which the premises are true but the conclusion is false

§ To show that an argument is quantificationally valid, we need to show that in any interpretation on which the premises are true, the conclusion must also be true

· This is like trying to show that a sentence is quantificationally true by going through every interpretation to make sure that it is true

· Fortunately, if we use a large enough UD in our interpretation, we can generally show that, if an argument is valid, it is not possible to construct an interpretation on which the premises are true and the conclusion is false

§ Ex. {($x)(Fx Ú Gx), ("x)~Fx} |= ($x)Gx is valid

§ Ex. {($x)[($y)Fy É Hx], ($y)~Fy} |≠ ~($x)Fx

v Homework 6

Ø 7.7(5b, 5d, 5p, 5r) --

Ø 8.3(4) – 4 problems

Ø 8.4(1) – 4 problems

v Extra Material – Identity and Functions

Ø PLE is an extension of PL that introduces two new ideas: the identity predicate and functions

Ø The Identity Predicate

§ The identity predicate allows us to say that two singular terms are identical

§ We could do this in PL by introducing Ixy: x is identical to y in each interpretation, but it is useful to be able to use the ‘=’ sign instead

§ ‘=’ is a two place predicate, so it takes two singular terms. We could write ‘=ab’, but since we are more used to seeing ‘=’ between terms, we can write ‘a=b’ in a PLE sentence

§ Note that just like any other predicate, ‘=’ can only be used on singular terms, not sentences. So it is illegal to say that ‘a=Pa’

§ The identity predicate allows us to talk about exact numbers of things

· Symbolization Key: p. 351

· Ex. The only pear in the basket is rotten.

¨ ($x)[((Px & Nxb) & Rx) & ("y)[(Py & Nyb) É y=x]]

Ø Functions

§ A function is an operation that takes one or more element of a set as arguments and returns a single value

§ Addition, subtraction, etc. are examples of functions in math. For example, the addition function takes two numbers as input and outputs their sum

§ We can use function in PLE to talk about specific singular terms without giving them a name

§ A function is represented by a lowercase letter followed by parentheses that surround its argument

· Only singular terms can be arguments for a function. It is illegal to write ‘f(Pa)’

§ Example: Sarah is Jess’ sister.

· UD: people

s(x): the sister of x

Cx: x is in college

j: Jess

s: Sarah

· s=s(j)

· Notice that the interpretation given for s(x) is not a complete sentence. It only names a thing.

§ A function behaves the same as any other singular term in PLE

· This means they can be used to fill in predicates

· Ex. Jess’ sister is in college

· Cs(j)

6