PHIL 12A Syntax and Semantics Philosophy Problems Set 8 and 9 Please complete all questions in problem set 9. You may also need problem set 8, lecture slides, and the textbook called Logic in Action. I will provide all of them in attachments. PHIL 12A Spring 2019

Problem Set 9

100 points

1

Syntax and Semantics of Monadic Predicate Logic

1.1

1.1.1

Identity and Substitution

The Identity Predicate

1. 4 points Exercise 4.36 of Logic in Action. Write out your formula with no abbreviations.

2. 4 points Exercise 4.38(2) of Logic in Action. Demonstrate the difference in meaning

by providing a model in which the two formulas have different truth values.

1.1.2

Substitution

3. 10 points total; 2.5 points each part Give a recursive definition of the set of

terms t that are substitutable for a variable x in a formula ?. That is, fill in the question

marks in the following template (note that we do not assume that the metavariables

x and y refer to distinct variables, so you need to analyze the case where x = y and

the case where x 6= y in part (d)):

(a) t is always substitutable for x in an atomic formula P (u) or s =

? t (because there

are no quantifiers in an atomic formula to capture a variable in t);

(b) t is substitutable for x in ¬? iff ?

(c) for # ? {?, ?, ?, ?}, t is substitutable for x in (? # ?) iff ?

(d) for Q ? {?, ?}, t is substitutable for x in Qy? iff ?

2

Syntax and Semantics of Predicate Logic

4. These problems concern translating English sentences into the language of predicate

logic:

(a) 3 points Assume the domain of discourse is all dogs. Translate the following

sentences into predicate logic: (Use f for Fido, r for Rover, and L for loves)

Fido is loved by everyone.

Rover loves everyone who loves Fido.

Fido and Rover love each other.

1

(b) 5 points For each of the following, specify an appropriate domain of discourse,

specify a translation key, and translate into predicate logic. (Note: you do not

have to understand what a sentence means before you can attempt to translate

it.)

Cats that love dogs dont taunt dogs.

There is a greatest natural number.

Friends of Fidos friends are Rovers friends.

There is no largest even number.

Every apple is tastier than every orange.

(c) 4 points Translate the following sentences into predicate logical formulas. Assume the domain of discourse is cats and dogs.

Some cat doesnt love all dogs.

Every dog who loves all cats doesnt love every dog.

Every cat who loves a dog is purred at by some cat.

No cat loves a cat who loves a dog, except for the cats who dont love dogs.

5. These problems concern describing situations using the language of predicate logic:

(a) 4 points Exercise 4.18 of Logic in Action.

(b) 5 points Exercise 4.22 of Logic in Action.

6. These problems concern describing binary relations:

(a) 3 points The formula ?x?y?z((R(x, y)?R(y, z)) ? R(x, z)) expresses the transitivity of the relation R. Which of the following relations are transitive?

Being a cousin of … on the set of human beings.

Being a sibling of … on the set of human beings.

The divides relation on the set of natural numbers. (Recall that a natural

number n divides a natural number m if there is some natural k such that

n × k = m)

(b) 5 points Exercise 4.24 of Logic in Action.

(c) 5 points Exercise 4.25 of Logic in Action.

7. 12 points The following natural language sentences are ambiguous: they can be

interpreted in at least two different ways. For each one of them, provide two predicate

logic formulas that correspond to two different readings (i.e., four formulas in total).

(a) There is a dog who likes only cats who like only dogs.

(b) Fido and Rover are liked by some cat.

Decide for each of the four predicate logic formulas that you have given whether they

are true or false in the model in Figure 1. Explain your answers.

2

: dog

: cat

? : likes

f :Fido, r:Rover, t:Tibbles

r

f

t

Figure 1: Model for Problem 7.

Figure 2: Model for Problem 8.

8. 10 points Consider the model in Figure 2. Let the set of solid dots be the interpretation of the unary predicate symbol P . Let the edge relation of the graph be the

interpretation of the binary predicate symbol R. What does

?x(P (x) ? (?y(¬P (y) ? ?z(R(y, z) ? P (z)))))

mean? Is this true in the model?

9. 8 points Consider the four models in Figure 3. Let R be the binary predicate

interpreted by the arrow in the diagram. Give for each model a predicate logic formula

that is true in that model but not in the other three.

3

Figure 3: Models for Problem 9.

10. These problems concern validity and consequence in predicate logic:

(a) 8 points Which of the following statements are true?

(i) ?xF (x) ? ?x¬F (x)

(ii) ?xF (x) ? ?x¬F (x)

(iii) ?xF (x) ? ?x¬¬F (x)

(iv) ?x?y?z((R(x, y) ? R(y, z)) ? R(x, z))

(v) ?x?yR(x, y) ? ?xR(x, x)

(vi) ?x?yR(x, y) ? ?zR(z, z)

(vii) ?xR(x, x) ? ?x?yR(y, x)

(viii) ?xR(x, x) ? ?x?yR(y, y)

(b) 6 points Which of the following statements are true? If the statement is false,

provide a counterexample.

(i) ?x?yR(y, x) ?y?xR(y, x)

(ii) ?xR(x, x) ?x?yR(x, y)

(iii) ?x?yR(x, y) ?xR(x, x)

(iv) ?x?yR(x, y) ?xR(x, x)

(v) ?x?yR(y, x) ?x?yR(x, y)

(vi) ?xR(x, x) ?x?yR(y, y)

(c) 4 points Which of the following statements are true? If the statement is false,

provide a counterexample.

(i) {?x?y(R(x, y) ? R(y, x)), R(a, b)} R(a, a)

(ii) {?x?y(R(x, y) ? R(y, x)), R(a, b)} R(b, b)

(iii) {?x?y(R(x, y) ? R(y, x)), ¬R(b, a)} ¬R(a, b)

(iv) {?x?y(R(x, y) ? R(y, x)), R(b, c), ¬R(a, c)} ¬R(a, b)

11. 10 points Extra Credit In an extra credit problem for Problem Set 8, we showed

that if a formula of pure monadic predicate logic is satisfiable, then it is satisfiable in a

4

model of size at most 2k where k is the number of predicates occurring in the formula.

(We stated this in terms of falsifiable, but ? is satisfiable iff ¬? is falsifiable, so we

can state it either way.)

Let us now consider a sentence with a binary predicate symbol:

?x?yR(x, y) ? ?x¬R(x, x) ? ?x?y?z((R(x, y) ? R(y, z)) ? R(x, z)).

Is this sentence satisfiable? If so, are there any finite models that make the sentence

true? If so, give an example. If not, explain why not.

12. 8 points Extra Credit A formula of predicate logic is in prenex normal form iff it

is of the form

Q1 x1 . . . Qn xn ?

where Qi ? {?, ?} and ? does not contain quantifiers. The following is an important

fact about predicate logic.

Proposition 1. Every formula ? of predicate logic is equivalent to a formula in prenex

normal form.

To get a feel for this, find prenex equivalents of the following formulas:

(a) ?x(P (x) ? ?yR(x, y));

(b) ?x(?yR(y, x) ? P (x));

(c) ?x(P (x) ? ?yR(x, y));

(d) ?x(?yR(y, x) ? P (x)).

5

PHIL 12A Spring 2019

Problem Set 8

60 points

1

Syntax and Semantics of Monadic Predicate Logic

1.1

1.1.1

Pure Monadic Predicate Logic

Pure Monadic Predicate Logic I

1. 2 points Exercise 4.6 in Logic in Action.

2. 2 points Exercise 4.7 in Logic in Action.

3. 10 points total; each part 2.5 points Give a recursive definition of the set of

free variables of a formula ?, i.e., those variables with at least one free occurrence

in ?, as described in the slides. To do so, fill in the question marks in the following

template (note that we do not assume that the metavariables x and y refer to

distinct variables, so you need to analyze the case where x = y and the case where

x 6= y):

(a) x is a free variable of P (y) iff ?

(b) x is a free variable of ¬? iff ?

(c) for # ? {?, ?, ?, ?}, x is a free variable of (? # ?) iff ?

(d) for Q ? {?, ?}, x is a free variable of Qy? iff ?

4. 10 points Given a model M = (D, I), a subset A ? D is said to be definable in the

language of pure monadic predicate logic iff there is a pure monadic formula ? with

exactly one free variable x such that for some variable assignment g,

A = {d ? D | M g[x:=d] ?},

i.e., A is exactly the set of objects d such that ? is true under the variable assignment

that maps x to d.

For example, in the model in Figure 1, the set {2, 4} is defined by the formula

¬Sophomore(x). For every subset of the domain of that model, say whether it

is definable by a formula or not. If it is definable, give a formula that defines it.

1.1.2

Pure Monadic Predicate Logic II

5. 3 points Exercise 4.14 of Logic in Action.

6. 3 points Exercise 4.15 of Logic in Action.

1

Language:

Sophomore

Student

Faculty

I

I

Invitee

I

1

I

3

Model:

2

4

Figure 1: Model for Problem 4.

7. 12 points Determine whether each of the following formulas are true in the model

in Figure 2, where R stands for red, G stands for green, B stands for blue, P stands

for purple, S stands for square, and C stands for circle:

(a) practice ?x(R(x) ? C(x));

(b) practice ?x(C(x) ? S(x));

(c) ?xG(x) ? ?xC(x);

(d) ?xR(x) ? ?xC(x);

(e) ?xC(x) ? ?xS(x);

(f) ?x(G(x) ? C(x));

(g) ?x(¬P (x) ? S(x));

(h) ?x(S(x) ? (P (x) ? R(x))).

Figure 2:

8. practice Exercise 4.17 of Logic in Action.

9. 8 points For each of the following sentences, say whether or not it is valid. If it is

not valid, present a model in which it is false.

(a) practice ?x(P (x) ? Q(x)) ? (?xP (x) ? ?xQ(x));

(b) ?x(P (x) ? Q(x)) ? (?xP (x) ? ?xQ(x));

(c) ?xP (x) ? ?xP (x);

2

(d) ?x?y(P (x) ? Q(y)) ? ?z(P (z) ? Q(z));

(e) ?x(P (x) ? ?xP (x)).

10. 5 points An important fact about pure monadic predicate logic is the following.

Proposition 1. Each sentence ? of pure monadic predicate logic is equivalent to a

sentence ?? containing the same predicate symbols as ? and only one variable.

To get a feel for this, explain the following equivalences by appealing to the semantics

of monadic predicate logic:

(a) ?x?y(P (x) ? Q(y)) is equivalent to ?xP (x) ? ?yQ(y);

(b) ?xP (x) ? ?yQ(y) is equivalent to ?zP (z) ? ?zQ(z).

11. 5 points Extra Credit. In the slides, we mentioned the important lemma that if a

formula ? of pure monadic predicate logic is not valid, then it is falsified in a model on

the domain D = {1, . . . , 2k } where k is the number of predicate symbols appearing in

?. In this extra credit problem, we will show that if ? is not valid, then it is falsified

in a model where D has at most 2k elements (from which the lemma easily follows).

Suppose M = (D, I) is a model and g an assignment such that M 2g ?. We will

shrink M to a model with no more than 2k elements that also falsifies ?.

Let P red(?) be the set of all unary predicates that occur in ?. For example, if ? is

?x(P1 (x) ? P3 (x)), then P red(?) = {P1 , P3 }.

We assume that P red(?) has k elements. It follows that P red(?) has 2k subsets.

For each d ? D, let

db = {d0 ? D | for all P ? P red(?) : d ? I(P ) iff d0 ? I(P )}.

That is, db is the set of all objects that are indistinguishable from d in M using

predicates that appear in ?. The idea behind the proof is that such indistinguishable

b (For example, in the model in

objects should be collapsed into a single object d.

Figure 4, the objects 1 and 3 cannot be distinguished from each other by any of the

four predicates, so they can be collapsed into a single object b

1=b

3.) There can be at

k

most 2 distinct sets db because each distinct db defines a distinct subset of P red(?),

namely the subset {P ? P red(?) | d ? I(P )}, and there are only 2k subsets of

c = (D,

b I):

b

P red(?). This leads us to the definition of our collapsed model M

b = {db | d ? D};

D

b ) iff d ? I(P );

for each predicate P ? P red(?), db ? I(P

b ) = ?.

for each predicate P 6? P red(?), I(P

c by

Given any variable assignment g for M, define the variable assignment gb for M

[

gb(xi ) = g(x

i ).

3

It follows that for any variable x and d ? D,

b

g[x

:= d] = gb[x := d].

It also follows that for any subformula ? of ? and variable assignment g,

c gb ? iff M g ?.

M

Prove this iff by induction on ?. Give only the base case where ? is an atomic

formula of the form P (x) and the inductive step where ? is of the form ?x?. Use the

equations given above (plus the inductive hypothesis for the ? case).

c 2gb ?,

From what you proved and our initial assumption that M 2g ?, it follows that M

which shows that ? is indeed falsified in a model with at most 2k elements!

1.2

1.2.1

Constants and Functions

Constants

12. 5 points Let ? be a formula in which the constant c appears but the variable x does

not appear. Prove that if ? is valid, then ?x?cx is valid, where ?cx is the formula

obtained from ? by replacing all occurrences of c with x. Intuitively: if ? holds of

an arbitrary element, then it holds of everything. In your argument you may assume

(without proof) the fact that for any model M = (D, I) and variable assignment g for

M:

M g ? iff M g[x:=JcKgI ] ?cx .

You may also assume that if two models M and N differ only on the interpretation

of a constant that does not appear in a formula ?, then M g ? iff N g ?.

1.2.2

Function Symbols

13. 5 points Extra Credit In the slides, we mentioned the fact that there is an algorithm

that converts any formula ? of monadic predicate logic with unary function symbols

into a formula ?0 of monadic predicate logic without function symbols such that ? is

valid iff ?0 is valid.

To give you a feel for how this could be true, let ? be a formula of monadic predicate

logic, P a unary predicate, and f a unary function symbol not occurring in ?. Prove

that the formula

?z(?(z) ? P (f (z)))

is valid if and only if the formula

?x?y(P (y) ? Q(x)) ? ?z(?(z) ? Q(z))

is valid, where Q is a new predicate symbol that does not appear in ?.

Suggestion: suppose ?z(?(z) ? P (f (z))) is not valid, so it is falsified in some model

4

M. Then define a model M0 that differs from M at most in the interpretation of

0

the predicate Q (i.e., just define I M (Q) for us), such that M0 falsifies ?x?y(P (y) ?

Q(x)) ? ?z(?(z) ? Q(z)) (prove it). In the other direction, suppose ?x?y(P (y) ?

Q(x)) ? ?z(?(z) ? Q(z)) is not valid, so it is falsified in some model N . Then define

a model N 0 that differs from N at most in the interpretation of the function symbol

0

f (i.e., just define I N (f ) for us) such that N 0 falsifies ?z(?(z) ? P (f (z))) (prove it).

5

Logic in Action

New Edition, November 23, 2016

Johan van Benthem, Hans van Ditmarsch, Jan van Eijck, Jan Jaspars

0-2

Contents

1

General Introduction

1-1

1.1

Inference, Observation, Communication . . . . . . . . . . . . . . . . . . 1-1

1.2

The Origins of Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-3

1.3

Uses of Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-5

1.4

Logic and Other Disciplines . . . . . . . . . . . . . . . . . . . . . . . . 1-9

1.5

Overview of the Course . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-11

Classical Systems

2-1

2

2-1

Propositional Logic

2.1

Reasoning in Daily Life . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-1

2.2

Inference Patterns, Validity, and Invalidity . . . . . . . . . . . . . . . . . 2-3

2.3

Classification, Consequence, and Update . . . . . . . . . . . . . . . . . . 2-5

2.4

The Language of Propositional Logic . . . . . . . . . . . . . . . . . . . 2-8

2.5

Semantic Situations, Truth Tables, Binary Arithmetic . . . . . . . . . . . 2-13

2.6

Valid Consequence and Consistency . . . . . . . . . . . . . . . . . . . . 2-18

2.7

Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-22

2.8

Information Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-24

2.9

Expressiveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-26

2.10 Outlook Logic, Mathematics, Computation . . . . . . . . . . . . . . . 2-28

2.11 Outlook Logic and Practice . . . . . . . . . . . . . . . . . . . . . . . 2-32

2.12 Outlook Logic and Cognition . . . . . . . . . . . . . . . . . . . . . . 2-34

0-3

0-4

3

4

CONTENTS

Syllogistic Reasoning

3-1

3.1

Reasoning About Predicates and Classes . . . . . . . . . . . . . . . . . . 3-1

3.2

The Language of Syllogistics . . . . . . . . . . . . . . . . . . . . . . . . 3-4

3.3

Sets and Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . 3-5

3.4

Syllogistic Situations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-10

3.5

Validity Checking for Syllogistic Forms . . . . . . . . . . . . . . . . . . 3-12

3.6

Outlook Satisfiability and Complexity . . . . . . . . . . . . . . . . . 3-18

3.7

Outlook The Syllogistic and Actual Reasoning . . . . . . . . . . . . . 3-21

The World According to Predicate Logic

4-1

4.1

Learning the Language by Doing . . . . . . . . . . . . . . . . . . . . . . 4-2

4.2

Practising Translations . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-8

4.3

Reasoning Patterns with Quantifiers . . . . . . . . . . . . . . . . . . . . 4-13

4.4

Formulas, Situations and Pictures . . . . . . . . . . . . . . . . . . . . . . 4-17

4.5

Syntax of Predicate Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 4-25

4.6

Semantics of Predicate Logic . . . . . . . . . . . . . . . . . . . . . . . . 4-30

4.7

Valid Laws and Valid Consequence . . . . . . . . . . . . . . . . . . . . . 4-35

4.8

Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-38

4.9

Identity, Function Symbols, Algebraic Reasoning . . . . . . . . . . . . . 4-41

4.10 Outlook Mathematical Background . . . . . . . . . . . . . . . . . . . 4-46

4.11 Outlook Computational Connection . . . . . . . . . . . . . . . . . . . 4-49

4.12 Outlook Predicate Logic and Philosophy . . . . . . . . . . . . . . . . 4-51

Knowledge, Action, Interaction

5

Logic, Information and Knowledge

4-57

5-1

5.1

Logic and Information Flow . . . . . . . . . . . . . . . . . . . . . . . . 5-1

5.2

Information versus Uncertainty . . . . . . . . . . . . . . . . . . . . . . . 5-3

5.3

Modeling Information Change . . . . . . . . . . . . . . . . . . . . . . . 5-10

5.4

The Language of Epistemic Logic . . . . . . . . . . . . . . . . . . . . . 5-12

5.5

Models and Semantics for Epistemic Logic . . . . . . . . . . . . . . . . 5-15

CONTENTS

0-5

5.6

Valid Consequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-21

5.7

Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-25

5.8

Information Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-30

5.9

The Logic of Public Announcement . . . . . . . . . . . . . . . . . . . . 5-37

5.10 Outlook Information, Knowledge, and Belief . . . . . . . . . . . . . . 5-42

5.11 Outlook Social Knowledge . . . . . . . . . . . . . . . . . . . . . . . . 5-44

5.12 Outlook Secrecy and Security . . . . . . . . . . . . . . . . . . . . . . 5-47

6

Logic and Action

6-1

6.1

Actions in General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-1

6.2

Sequence, Choice, Repetition, Test . . . . . . . . . . . . . . . . . . . . . 6-6

6.3

Viewing Actions as Relations . . . . . . . . . . . . . . . . . . . . . . . . 6-10

6.4

Operations on Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-13

6.5

Combining Propositional Logic and Actions: PDL

6.6

Transition Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-20

6.7

Semantics of PDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-23

6.8

Axiomatisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-26

6.9

Expressive power: defining programming constructs . . . . . . . . . . . . 6-30

. . . . . . . . . . . . 6-17

6.10 Outlook Programs and Computation . . . . . . . . . . . . . . . . . . 6-31

6.11 Outlook Equivalence of Programs and Bisimulation . . …

Purchase answer to see full

attachment

Don't use plagiarized sources. Get Your Custom Essay on

PHIL 12A Syntax and Semantics Philosophy Problems Set 8 and 9 Please complete all questions in problem set 9. You may also need problem set 8, lecture slid

Just from $13/Page

Why should I choose Homework Writings Pro as my essay writing service?

We Follow Instructions and Give Quality Papers

We are strict in following paper instructions. You are welcome to provide directions to your writer, who will follow it as a law in customizing your paper. Quality is guaranteed! Every paper is carefully checked before delivery. Our writers are professionals and always deliver the highest quality work.

Professional and Experienced Academic Writers

We have a team of professional writers with experience in academic and business writing. Many are native speakers and able to perform any task for which you need help.

Reasonable Prices and Free Unlimited Revisions

Typical student budget? No problem. Affordable rates, generous discounts - the more you order, the more you save. We reward loyalty and welcome new customers. Furthermore, if you think we missed something, please send your order for a free review. You can do this yourself by logging into your personal account or by contacting our support..

Essay Delivered On Time and 100% Money-Back-Guarantee

Your essay will arrive on time, or even before your deadline – even if you request your paper within hours. You won’t be kept waiting, so relax and work on other tasks.We also guatantee a refund in case you decide to cancel your order.

100% Original Essay and Confidentiality

Anti-plagiarism policy. The authenticity of each essay is carefully checked, resulting in truly unique works. Our collaboration is a secret kept safe with us. We only need your email address to send you a unique username and password. We never share personal customer information.

24/7 Customer Support

We recognize that people around the world use our services in different time zones, so we have a support team that is happy to help you use our service. Our writing service has a 24/7 support policy. Contact us and discover all the details that may interest you!

Try it now!

How it works?

Follow these simple steps to get your paper done

Place your order

Fill in the order form and provide all details of your assignment.

Proceed with the payment

Choose the payment system that suits you most.

Receive the final file

Once your paper is ready, we will email it to you.

Our Services

Our reputation for excellence in providing professional tailor-made essay writing services to students of different academic levels is the best proof of our reliability and quality of service we offer.

Essays

When using our academic writing services, you can get help with different types of work including college essays, research articles, writing, essay writing, various academic reports, book reports and so on. Whatever your task, homeworkwritingspro.com has experienced specialists qualified enough to handle it professionally.

Admissions

Admission Essays & Business Writing Help

An admission essay is an essay or other written statement by a candidate, often a potential student enrolling in a college, university, or graduate school. You can be rest assurred that through our service we will write the best admission essay for you.

Reviews

Editing Support

Our professional editor will check your grammar to make sure it is free from errors. You can rest assured that we will do our best to provide you with a piece of dignified academic writing. Homeworkwritingpro experts can manage any assignment in any academic field.

Reviews

Revision Support

If you think your paper could be improved, you can request a review. In this case, your paper will be checked by the writer or assigned to an editor. You can use this option as many times as you see fit. This is free because we want you to be completely satisfied with the service offered.