Artificial Intelligence (Con esempi di domande)

1

Symbolic representation

Example: quadratic equation

x² + ax + b = 0

x = -a/2 ± √(a²/4 - b)

START POINT: a (true) premise

END POINT: conclusion (that's also true)

It's a sequence of steps where at each step a transformation rule is applied.

Symbolic reasoning

Syllogisms

Many valid arguments obey an abstract schema:

Example:

• All (humans) are (mortals)
• All (Greeks) are (humans)
• All (Greeks) are (mortals)

The validity doesn't depend on meaning.

Paralogisms (fallacies)

Example:

• All (humans) are (mortals)
• All (Greeks) are (mortals)
• All (Greeks) are (humans)

There can be paralogisms due to wrong sequences, due to ambiguities, or due to subtleties.

Symbolic logic can be used to distinguish correct reasoning from incorrect reasoning, regardless of the actual meaning: it uses the formal, symbolic structure alone.

Possible worlds

Sentences can restrict the set of possible worlds that can exist.

They can be true or false and generalized or not generalized.

Considering many sentences at the same time means taking the intersection of their sets of possible worlds.

Example: possible world

sentence 1 is true

... 2 is false

... 3 is true

... 4 is false

Example: set of possible worlds

Sentences:

1. sentence 1 is true
2. sentence 2 is true
3. sentence 3 is true

Entailment

Σφ_n ⊧ ψ

There is an entailment when all the possible worlds that satisfy Σφ_n satisfy ψ as well.

There is entailment iff every world that satisfies Γ also satisfies ψ.

Example:

Σ{A, A → B, B} ⊧ B?

Σ{A, B, A → B} ⊧ ψ

Σ{A → B, B} ⊧ A?

There is no entailment in this case.

Rule of inference (inference schema)

Σ{φ, φ → ψ} ⊧ ψ

There is entailment for any φ, ψ.

Equivalence (symmetric entailment)

φ ⊧ ψ ⇔ ψ ⊧ φ

φ and ψ are logically equivalent: φ ≡ ψ

A wff can be replaced by an equivalent one.

Required properties:

• Termination = All the rules are needed to arrive at a point where only literals remain, therefore completing the algorithm.
• Soundness (correctness) = ⊨_Γ φ ⇒ ⊨Γ⊢φ (the answer found is right) from tableaux, symbolic derivation
• Completeness = ⊨⊢φ ⇒ ⊨Γ⊢φ (if there's an answer, this method will find it)

Resolution by refutation

The only rule that is required to achieve soundness and completeness is the rule of resolution;

• φ ∨ χ
• ¬χ ∨ ψ

φ ∨ ψ _resolvent

This works if the problem is preprocessed and transformed in this specific format.

How to apply the method:

1. Γ⊨φ
2. Γ ∪ { ¬φ } _{refutation set}
3. Pre-process Γ ∪ { ¬φ } (into CNF and then CF)
4. Apply the resolution rule exhaustively.

Valuation function

A VF assigns a value to all variables at once.

<U, Σ, ν>[s] ⊨ P(x) ?

S(x) ∈ ν(P/1) ?

<U, Σ, ν>[s] ∀x P(x) :

iff FORALL d∈U we have <U, Σ, ν>[s(x:d)] ⊨ P(x)

The condition that needs to be true is ν(P/1) ≡ U.

<U, Σ, ν>[s] ⊨ ∃x P(x) ?

iff IT EXISTS d∈U such that <U, Σ, ν>[s(x:d)] ⊨ P(x)

The condition is ν(P/1) ≠ ∅.

∃G(a), G(x)→H(a) ⊨ ⊭ H(a)

<U, Σ, ν>[s] ⊭ ∀x (G(x)→H(x))

ν(G/1) ⊈ ν(H/1)

-

∃G(a), ∀x (G(x)→H(x)) ⊨ H(a) ?

This can't be checked with a truth table.

<U, Σ, ν>[s] ⊨ ∀x (∃y L(x,y))

iff FORALL d_x∈U <U, Σ, ν>[s](x:d_x) ⊨ ∃y L(x,y)

; iff IT EXISTS d_y∈U <U, Σ, ν>[s](x:d_x)(y:d_y) ⊨ L(x,y)

The order of the quantifiers matters (the meaning of the sentence changes).

Negation and quantifiers

¬(∀x P(x)) ≡ ∃x ¬P(x)

¬(∃x P(x)) ≡ ∀x ¬P(x)

Example:

∃_Σ∀x(G(x)→H(x)), ∀x(H(x)→M(x)) ⊢ ∀x(¬G(x)→M(x))

∃_Σ→G(x), H(x), Σ →H(x), M(x), Σ G(k), Σ M(k)

(Easy solution)

Standardization of variables:

∃_Σ∀x₀(G(x₀