Bài giảng Trí tuệ nhân tạo - Chapter 7: Structured knowledge

Structured Knowledge

Chapter 7

Logic Notations

Does logic represent well knowledge in structures?

2

Logic Notations

Frege’s Begriffsschrift (concept writing) - 1879:

assert P

P

not P

Q

P

if P then Q

for every x, P(x)

P(x)

x

3

Logic Notations

Frege’s Begriffsschrift (concept writing) - 1879:

red(x)

“Every ball is red”

“Some ball is red”

x

ball(x)

red(x)

x

ball(x)

4

Logic Notations

Algebraic notation - Peirce, 1883:

Universal quantifier: Π P

x x

Existential quantifier: ∑ P

x x

5

Logic Notations

Algebraic notation - Peirce, 1883:

“Every ball is red”: ∏ (ball —< red )

x

“Some ball is red”: ∑ (ball • red )

x

6

Logic Notations

Peano’s and later notation:

“Every ball is red”: (∀x)(ball(x) ⊃ red(x))

“Some ball is red”: (∃x)(ball(x) ∧ red(x))

7

Logic Notations

Existential graphs - Peirce, 1897:

Existential quantifier: a link structure of bars, called line of

identity, represents ∃

Conjunction: the juxtaposition of two graphs represents ∧

Negation: an oval enclosure represents ¬

8

Logic Notations

“If a farmer owns a donkey, then he beats it”:

farmer

owns

beats

donkey

9

Logic Notations

((p

→

r)

∧

(q

→

s)) → ((p q) → (r s))

p

q

s

r

p q r s

10

Existential Graphs

EG’s rules of inferences:

Erasure: in a positive context, any graph may be erased.

Insertion: in a negative context, any graph may be inserted.

Iteration: a copy of a graph may be written in the same

context or any nested context.

Deiteration: any graph may be erased if a copy of its occurs

in the same context or a containing context.

Double negation: two negations with nothing between them

may be erased or inserted.

11

Existential Graphs

Prove: ((p

→ r) ∧ (q → s)) → ((p q) → (r s)) is valid

12

Existential Graphs

Prove: ((p

→

r)

∧

(q

→

s)) → ((p q) → (r s)) is valid

p

q

s

r

p q r s

13

Existential Graphs

Prove: ((p

→ r) ∧ (q → s)) → ((p q) → (r s))

Erasure: in a positive context,

any graph may be erased.

Insertion: in a negative context,

any graph may be inserted.

Iteration: a copy of a graph may

be written in the same context or

any nested context.

Deiteration: any graph may be

erased if a copy of its occurs in

the same context or a containing

context.

Double negation: two negations

with nothing between them may

be erased or inserted.

14

Existential Graphs

Prove: ((p

→

r)

∧

(q

→

s))

→

((p q)

→ (r s))

Erasure: in a positive context,

any graph may be erased.

Insertion: in a negative context,

any graph may be inserted.

Iteration: a copy of a graph may

be written in the same context or

any nested context.

Deiteration: any graph may be

erased if a copy of its occurs in

the same context or a containing

context.

p

q

s

r

Double negation: two negations

with nothing between them may

be erased or inserted.

15

Existential Graphs

Prove: ((p

→

r)

∧

(q

→

s))

→

((p q)

→

(r s))

Erasure: in a positive context,

any graph may be erased.

p

q

r

s

Insertion: in a negative context,

any graph may be inserted.

Iteration: a copy of a graph may

be written in the same context or

any nested context.

Deiteration: any graph may be

erased if a copy of its occurs in

the same context or a containing

context.

p

q

s

r

Double negation: two negations

with nothing between them may

be erased or inserted.

p

r

16

Existential Graphs

Prove: ((p

→

r)

∧

(q

→

s))

→

((p q)

→ (r s))

Erasure: in a positive context,

any graph may be erased.

p

q

r

s

Insertion: in a negative context,

any graph may be inserted.

p

r

Iteration: a copy of a graph may

be written in the same context or

any nested context.

Deiteration: any graph may be

erased if a copy of its occurs in

the same context or a containing

context.

p

q

s

r

Double negation: two negations

with nothing between them may

be erased or inserted.

r

p q

17

Existential Graphs

→

Prove: ((p

r)

∧

(q

→

s))

→

((p q)

→

(r s))

Erasure: in a positive context,

any graph may be erased.

p

q

s

r

Insertion: in a negative context,

any graph may be inserted.

r

p q

Iteration: a copy of a graph may

be written in the same context or

any nested context.

Deiteration: any graph may be

erased if a copy of its occurs in

the same context or a containing

context.

p

q

s

r

Double negation: two negations

with nothing between them may

be erased or inserted.

r

s

q

p q

18

Existential Graphs

→

Prove: ((p

r)

∧

(q

→

s)) → ((p q) → (r s))

Erasure: in a positive context,

any graph may be erased.

p

q

s

r

Insertion: in a negative context,

any graph may be inserted.

Iteration: a copy of a graph may

be written in the same context or

any nested context.

r

s

q

p q

Deiteration: any graph may be

erased if a copy of its occurs in

the same context or a containing

context.

p

q

s

r

Double negation: two negations

with nothing between them may

be erased or inserted.

p q r s

19

Existential Graphs

→

Prove: ((p

r)

∧

(q

→

s))

→ ((p q) → (r s))

p

q

r

s

p

q

r

s

p

r

p

q

s

r

p

q

s

r

p q r s

r

p q

r

s

q

p q

20