# CS代考计算机代写 PowerPoint Presentation

PowerPoint Presentation

Logic

Planning

Logic

Planning

Lesson Preview

Formal notation

Conjunctions, disjunctions, negations, implications

Truth tables

Rules of inference

Resolution theorem proving

Why do we need formal logic?

Soundness: Only valid conclusions can be proven.

Completeness: All valid conclusions can be proven.

If an animal has feathers, then it is a bird

If an animal lays eggs and it flies, then it is a bird

Vertebrate

Bird

Bluebird

Penguin

Eagle

Brick

Block

Block

A Foo

Brick

¬touches

¬touches

supports

supports

supports

supports

Mark the sufficient conditions:

If…

□ A brick supports two bricks

□ A brick supports two blocks

□ Those two blocks touch

□ Those two blocks do not touch

□ Those two blocks support a block

□ Those two blocks support a brick

…then the object is a foo

Predicate:

A function that maps object arguments to true or false values

Feathers(bluebird)

Predicate:

A function that maps object arguments to true or false values

If an animal has feathers, then it is a bird

Feathers(animal)

If Feathers(animal):

Then Bird(animal)

If an animal lays eggs and it flies, then it is a bird

Lays-eggs(animal)

∧

Flies(animal)

If Lays-eggs(animal) ∧

Flies(animal):

Then Bird(animal)

If an animal lays eggs or it flies, then it is a bird

Lays-eggs(animal)

∨

Flies(animal)

If Lays-eggs(animal) ∨

Flies(animal):

Then Bird(animal)

Flies(animal)

∧

¬Bird(animal)

If Flies(animal) ∧ ¬Bird(animal):

Then Bat(Animal)

If an animal flies and is not a bird, it is a bat.

If Lays-eggs(animal) ∧ Flies(animal):

Then Bird(animal)

Lays-eggs(animal) ∧ Flies(animal) ⇒ Bird(animal)

Operator Symbol Accepted Symbol

AND A ∧ B A & B

A && B

OR A ∨ B A | B

A || B

NOT ¬A !A

~A

IMPLIES A ⇒ B A = B

A == B

A => B

If an animal lays eggs and does not have feathers, it is a reptile.

Lays-eggs(animal) ∧ ¬Feathers(animal) ⇒ Reptile(animal)

If an animal has feathers or has talons, it is a bird.

Feathers(animal) ∨ Talons(animal) ⇒ Bird(animal)

If an animal lays eggs, has a beak, and flies, it is a duck.

Lays-eggs(animal) ∧ Beak(animal) ∧ Flies(animal) ⇒ Duck(animal)

If an animal lays eggs, has a beak, and do not fly, it is a platypus.

Lays-eggs(animal) ∧ Beak(animal) ∧ ¬Flies(animal) ⇒ Platypus(animal)

A B A ∨ B

True True True

True False True

False True True

False False False

A B A ∨ ¬B

True True True

True False True

False True False

False False True

A B ¬A ∧ ¬B

True True False

True False False

False True False

False False True

A B C A ∨ (B ∧ ¬C)

True True True True

True True False True

True False True True

True False False True

False True True False

False True False True

False False True False

False False False False

A B A ∧ B B ∧ A

True True True True

True False False False

False True False False

False False False False

Commutative Property

Distributive Property

A B C A ∧ (B ∨ C) (A ∧ B) ∨ (A ∧ C)

True True True True True

True True False True True

True False True True True

True False False False False

False True True False False

False True False False False

False False True False False

False False False False False

Associative Property

A B C A ∨ (B ∨ C) (A ∨ B) ∨ C

True True True True True

True True False True True

True False True True True

True False False True True

False True True True True

False True False True True

False False True True True

False False False False False

de Morgan’s Law

A B ¬(A ∧ B) ¬A ∨ ¬B

True True False False

True False True True

False True True True

False False True True

Truth of Implications

A B A ⇒ B

True True True

True False False

False True True

False False True

Implication Elimination

Given:

a ⇒ b

Rewrite as:

¬a ∨ b

Given:

Feathers ⇒ Bird

Rewrite as:

¬Feathers ∨ Bird

Modus Ponens

Sentence 1: p ⇒ q

Sentence 2: p

∴ Sentence 3: q

Feathers ⇒ Bird

Feathers

∴ Bird

Modus Tollens

Sentence 1: p ⇒ q

Sentence 2: ¬q

∴ Sentence 3: ¬p

Feathers ⇒ Bird

¬Bird

∴ ¬Feathers

Rules of Inference: Instantiate general rules to prove specific claims.

Prove: Harry is a bird

By Modus Ponens

S1: Feathers(animal) ⇒ Bird(animal)

S2: Feathers(Harry)

S3: Bird(Harry)

Prove: Harry is a bird

S1: Feathers(animal) ⇒ Bird(animal)

S2: Feathers(Harry)

S3: Bird(Harry)

✓

Prove: Buzz does not have feathers

S1: Feathers(animal) ⇒ Bird(animal)

S2: ¬Bird(Buzz)

S3: ¬Feathers(Buzz)

By Modus Tollens

Prove: Buzz does not have feathers

S1: Feathers(animal) ⇒ Bird(animal)

S2: ¬Bird(Buzz)

S3: ¬Feathers(Buzz)

✓

For one animal:

Lays-eggs(animal) ∧ Flies(animal) ⇒ Bird(animal)

For all animals:

∀x[Lays-eggs(x) ∧ Flies(x) ⇒ Bird(x)]

“Universal Quantifier”

For one animal:

Lays-eggs(animal) ∧ Flies(animal) ⇒ Bird(animal)

For at least one animal:

∃y[Lays-eggs(y) ∧ Flies(y) ⇒ Bird(y)]

“Existential Quantifier”

We know:

S1: ¬can-move ⇒ ¬liftable

We find:

S2: ¬can-move

How do we prove the box is not liftable?

We know:

S1: ¬can-move ⇒ ¬liftable

By implication elimination:

S1: can-move ∨ ¬liftable

We find:

S2: ¬can-move

We assume:

S3: liftable

How do we prove the box is not liftable?

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable

S2: ¬can-move

S3: liftable

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable

S2: ¬can-move

S3: liftable

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable

S2: ¬can-move

S3: liftable

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable

S2: ¬can-move

S3: liftable

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable

S2: ¬can-move

S3: liftable

We know:

S1: ¬can-move ∧ battery-full ⇒ ¬liftable

We find:

S2: ¬can-move

S3: battery-full

How do we prove the box is not liftable?

We know:

S1: ¬can-move ∧ battery-full ⇒ ¬liftable

By implication elimination:

S1: ¬(¬can-move ∧ battery-full) ∨ ¬liftable

We find:

S2: ¬can-move

S3: battery-full

How do we prove the box is not liftable?

We know:

S1: ¬can-move ∧ battery-full ⇒ ¬liftable

By implication elimination:

S1: ¬(¬can-move ∧ battery-full) ∨ ¬liftable

By deMorgan’s Law:

S1: can-move ∨ ¬battery-full ∨ ¬liftable

We find:

S2: ¬can-move

S3: battery-full

How do we prove the box is not liftable?

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable ∨ ¬battery-full

S2: ¬can-move

S3: battery-full

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable ∨ ¬battery-full

S2: ¬can-move

S3: battery-full

S4: liftable

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable ∨ ¬battery-full

S2: ¬can-move

S3: battery-full

S4: liftable

How do we prove the box is not liftable?

S1: can-move ∨ ¬liftable ∨ ¬battery-full

S2: ¬can-move

S3: battery-full

S4: liftable

S1: can-move ∨ ¬liftable ∨ ¬battery-full

S2: ¬can-move

S3: battery-full

S4: liftable

S1: can-move ∨ ¬liftable ∨ ¬battery-full

S2: ¬can-move

S3: battery-full

S4: liftable

S1: can-move ∨ ¬liftable ∨ ¬battery-full

S2: ¬can-move

S3: battery-full

S4: liftable

S1: can-move ∨ ¬liftable ∨ ¬battery-full

S2: ¬can-move

S3: battery-full

S4: liftable

How do we prove this is a bird?

If an animal has wings and does not have fur, it is a bird.

Write in formal logic:

has-wings ∧ ¬has-fur ⇒ bird

(Use the predicates has-wings, has-fur, and bird)

Carl Chapman, http://www.flickr.com/photos/12138336@N02/1997128094/

49

How do we prove this is a bird?

has-wings ∧ ¬has-fur ⇒ bird

Use implication elimination to rewrite as a conditional:

¬(has-wings ∧ ¬has-fur) ∨ bird

(Use the predicates has-wings, has-fur, and bird)

Carl Chapman, http://www.flickr.com/photos/12138336@N02/1997128094/

50

How do we prove this is a bird?

¬(has-wings ∧ ¬has-fur) ∨ bird

Use de Morgan’s Law to rewrite in conjunctive normal form:

¬has-wings ∨ has-fur ∨ bird

(Use the predicates has-wings, has-fur, and bird)

Carl Chapman, http://www.flickr.com/photos/12138336@N02/1997128094/

51

How do we prove this is a bird?

S1:

¬has-wings ∨ has-fur ∨ bird

S2: has-wings

S3: ¬has-fur

What sentence would be assumed to facilitate the proof?

S4: ¬bird

Carl Chapman, http://www.flickr.com/photos/12138336@N02/1997128094/

52

How do we prove this is a bird?

S1:

¬has-wings ∨ has-fur ∨ bird

S2: has-wings

S3: ¬has-fur

S4: ¬bird

What part of S1 would we eliminate first?

ο ¬has-wings

ο has-fur

ο bird

Carl Chapman, http://www.flickr.com/photos/12138336@N02/1997128094/

53

How do we prove this is a bird?

S1:

¬has-wings ∨ has-fur ∨ bird

S2: has-wings

S3: ¬has-fur

S4: ¬bird

What part of S1 would we eliminate first?

ο ¬has-wings

ο has-fur

ο bird

Carl Chapman, http://www.flickr.com/photos/12138336@N02/1997128094/

54

How do we prove this is a bird?

S1:

¬has-wings ∨ has-fur ∨ bird

S2: has-wings

S3: ¬has-fur

S4: ¬bird

What do we do next?

ο Resolve on S2 and ¬has-wings from S1

ο Resolve on S2 and has-fur from S1

ο Resolve on S3 and ¬has-wings from S1

ο Resolve on S3 and has-fur from S1

Carl Chapman, http://www.flickr.com/photos/12138336@N02/1997128094/

55

Assignment

How would you represent Raven’s progressive matrices using formal logic?

To recap…

Formal notation

Properties of truth values

Rules of inference

Proof by refutation

/docProps/thumbnail.jpeg