Artificial Intelligence (Con esempi di domande)

Symbolic representation

Example: Quadratic equation

x² + a x + b = 0
x = ^{- a}⁄₂ ± √^a2 ⁄_{4 - b}

Start point: a (true) premise
End point: a 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)
Hence, All (Greeks) are (mortals)

The validity doesn’t depend on meaning.

Paralogisms (fallacies)

Example: All (humans) are (mortals)
All (Greeks) are (mortals)
Hence, 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.

Symbolic representation
Example: Quadratic equation
x² + a x + b = 0
x = -^a⁄₂ ± √^{a2 - 4b}⁄_-b

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)
Hence, All (Greeks) are (mortals)

The validity doesn't depend on meaning.

Paralogisms (fallacies)

Example: All (humans) are (mortals)
All (Greeks) are (mortals)
Hence, 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
Sentence 2 is false
Sentence 3 is true
Sentence 4 is false

Example: Set of possible worlds

Sentences:
1)
2)
3)

Boolean algebra

Any Boolean algebra is about a set (a collection of unique elements). We can start from a finite set of objects W and create a collection of all possible subsets of W and call it Σ. Σ is also called the power set of W (Σ = 2^W).

Def: Boolean algebra

Any non-empty collection of subsets Σ of a set W such that:

1. ∅ ∈ Σ
2. A, B ∈ Σ => A ∪ B ∈ Σ
3. A ∈ Σ => A^c ∈ Σ   A^c = W - A   the complement of A with respect to W

Corollaries

The set W belongs to any Boolean algebra generated on W. Σ is closed under intersection.

Two-valued algebra

Σ_i: Σ = W, {0, 1}

Functions: Having only two operators (arity of 2), we can explicitly define the functions of OR/union, AND/intersection and NOT/complement (Boolean functions).

Properties that can be proved for this algebra are also valid for the entire family of algebras.

Adequate Basis: With OR, AND and NOT we can define any function. Also with IMP and NOT or with just NOR or just NAND.

ABA IMP B   implication
001011100111
A IMP B = Ā OR B

An implication that holds in both ways is equivalence
ABA EQ B
001010100111

Formal semantics

Each possible world is a structure <{0,1}, Σ, V>.

{0,1} are truth values. Σ is the signature (alphabet) of the formal language which is a set of propositional symbols. Each symbol in Σ stands for an actual proposition (in natural language). Σ could be infinite but we usually limit to a universe of discourse. V is a function Σ→{0,1} which assigns truth values to the symbols in Σ. For each possible world, Σ and {0,1} are the same and V changes.

Formal language

L_P is a propositional language. It has:

• A set Σ of propositional symbols: Σ = {A, B, C, ...}
• Two primary logical connectives: ¬,→
• Three derived logical connectives