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

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 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)