Chapter 3: Golden Years, Physical Symbol System Hypothesis

Question 1

Which period was said to be the golden years of AI? List 4 features that contributed to this designation

Answer 1

The golden years of AI were between 1955 and 1974. In that period there was:
- Lots of funding
- Many promises and optimism
- Symbolic AI the prevailing method
- Artificial General Intelligence was often the end goal.

Keywords: 1955, 1974, funding, optimism, symbolic AI, AGI.

Question 2

When is a physical system a physical symbol system?

Answer 2

When it:
- Contains a number of symbols
- Contains expressions consisting of symbols and their relations
- Contains processes/rules that manipulate these expressions, in particular create new expressions.

Keywords: symbols, expressions, rules, creation

Question 3

Define the Physical Symbol System Hypothesis. Explain the key terms of this definition.

Answer 3

A physical symbol system has the necessary and sufficient means for general intelligent action.

• Necessary means that all general intelligent beings are physical symbol systems
• Sufficient means that all physical symbol systems (of sufficient size) can be made in such a way to perform general intelligent actions.

E.g.
1. Humans brains are a physical symbol system
2. Modern computers can exhibit general intelligent action

Keywords: necessary, sufficient, criterion, intelligence

Question 4

Give an example of a computer program that is deemed a physical symbol system.

Answer 4

Logic theorist, created by Newell & Simon. Made to prove mathematical theorems.

(Other examples include: logical agents, SRHDLU, ELIZA)

Question 5

How is information encoded in logical agents?

Answer 5

Information is encoded into a knowledge base (KB) using first-order logic formulas. Logically, KB is a conjunction of formulas:
KB=φ1 ∧ φ2 ∧ · · · ∧ φn
Where y φi is a logical formula asserting some “knowledge”.

Keywords: knowledge, first-order logic, conjunction

Question 6

Provide the logical equivalence of the following formulas:

1. φ → ψ
2. ¬(φ ∧ ψ)
3. ∀X : φ
4. ∃X : φ

Answer 6

1. ¬φ ∨ ψ
2. ¬φ ∨ ¬ψ
3. ¬∃X : ¬φ
4. ¬∀X : ¬φ

Question 7

What would be a naive way to prove a logical theorem? Provide two requirements for this approach, and explain the caveat.

Answer 7

We could systematically apply first-order logical rules to the KB until we find ϕ or ¬ϕ. This approach essentially just enumerates all theorems that follow from the KB, and that it will only work if the inferences rules are complete (i.e. they can deduce all logically valid statements) and sound (i.e. they do not generate any false statements).

This is the best we can do, since first-order logic is only semi-decidable, meaning that there is no algorithm that can determine the truth or falsehood of all statements in first-order logic. (Undecidability of a statement does not depend on the specific KB that is being used, but rather on the properties of first-order logic itself)

Keywords: first-order logic, enumerate, completeness, soundness, semi-decidability.

Question 8

Explain refutation-based methods for proving logical theorems.

Answer 8

Refutation-based methods essentially use proof by contradiction:
- Add ¬ϕ to KB to get KB ∧ ¬ϕ
- Attempt to show that KB ∧ ¬ϕ is invalid

Question 9

Explain how truth values are assigned to (syntactical) formulas. Also explain satisfiability and validity.

Answer 9

A logical formula φ only has a truth value with respect to a given model M. A model provides an interpretation of the logical formula, and the truth value of the formula is assigned based on the evaluation of the formula under that interpretation.

• “Satisfiability” refers to the ability of a formula to be true for at least one model (existential).
• “Validity” refers to the ability of a formula to be true for all models (universal).

If a logical formula is unsatisfiable, it is also invalid.

Keywords: models, interpretation, truth, existential, universal

Question 10

What is the difference between an atom and a literal? Furthermore, define clauses and ‘clausal form’.

Answer 10

• An atom is a predicate, whereas a literal is an atom, or an negation of an atom.
• A clause is a disjunction of literals:
  ( C = L1 ∨ · · · ∨ Ln)
• A formula is in clausal form if it is in a conjunction of clauses:
  (C1 ∧ · · · ∧ Cn)

Question 11

Practice: are these formulas in clausal form?

1. (A ∨ B ∧ C) ∧ (¬A ∨ C)
2. (A(X) ∨ B(Y )) ∧ (¬A(Y ) ∨ B(X))
3. ∃X : ¬P(X) ∨ Q(X)

Hover over for tip 1
Hover over for tip 2

Answer 11

1. No, left conjunct is not a clause
2. Yes, both conjuncts are clauses
3. No, formula contains an existential quantifier

Question 12

Explain the goal and process of Skolemization.

Answer 12

Skolemization is a technique used in predicate logic to eliminate the existential quantifiers in a formula by introducing new function symbols, known as Skolem functions. The process of Skolemization is used to convert a formula in the prenex normal form, which is a formula that has all quantifiers at the front, into clausal form, which is a disjunctive normal form of a formula that is composed of clauses.

The process of Skolemization replaces every existentially quantified variable X with a function f (·) whose arguments are the universally quantified variables that have X in their scope, for example:
∃x (P(x) ∧ Q(x)) becomes P(f(x)) ∧ Q(f(x))
(or P(c) ∧ Q(c), if written as a Skolem constant, applicable when the skolem function has no arguments)

Two things to keep in mind;
- The names of the Skolem functions must be unique
- This process preserves satisfiability but not validity

Question 13

Practice: Skolemize the below formulas:
1. ∃X : ∀Y : P(X, Y )
2. ∀X : ∀Y : ∃Z : P(X, Y , Z)
3. ∃X : ∀Y : ∃Z : P(X, Y , Z)

Hover over for tip 1
Hover over for tip 2

Answer 13

1. ∀Y : P(c, Y )
2. ∀X : ∀Y : P(X, Y , f(X, Y))
3. ∀Y : P(c, Y , f(Y))

Question 14

Provide the 6 rules for rewriting a formula into clausal form.

Answer 14

1. Move all negations inward until only atoms are negated
2. Rename all variables so that they are unique per quantifier
3. Get rid of existential quantifiers by Skolemization
4. Make all quantifiers implicit
5. Convert to conjunctive normal form by distributing disjunctions and conjunctions
6. Write down the clauses in a list

Keywords: negations, rename, uniqueness, Skolemization, implicit, conjunctive normal form, list

Question 15

Describe the resolution inference rule.

Answer 15

The resolution inference rules takes two clauses and produces a new clause. The input clauses must contain a complementary literal. An example:
L1 ∨ · · · ∨ Ln ∨ S and M1 ∨ · · · ∨ Mm ∨ ¬S resolves to:
L1 ∨ · · · ∨ Ln ∨ M1 ∨ · · · ∨ Mm, which is called the resolvent of the inputs.

Question 16

Explain how you can determine if the list of initial clauses is satisfiable or not.

Answer 16

You can apply the resolution inference rule on the list of initial clauses. If any of the resolvents is equivalent to the empty clause, the list of initial clauses is by definition unsatisfiable. Example:

1. P (initial)
2. ¬P ∨ Q (initial)
3. ¬Q ∨ R (initial)
4. ¬R (initial)
5. Q (resolvent of 1 and 2)
6. R (resolvent of 3 and 5)
   7 {} (resolvent of 4 and 6)

Thus the list of initial clauses is unsatisfiable.

Question 17

Explain when substitution can be applied, and how it works.

Answer 17

Substitution can be applied to a term in a formula if it is a variable. If t is a term and X is a variable, we can define a substitution t/X. This substitution can be applied to a clause C, which is denoted by C[t/X]. This is purely a syntactic operation, and replaces all instances at once (parallelly).

Examples:
Clause: Human(X)
Substitutions θ: socrates/X
C[θ] : Human(Socrates)

Clause: ¬P(X) ∨ Q(X, Y )
Substitutions θ: c/X, f (Z)/Y
C[θ]: ¬P(c) ∨ Q(c, f (Z))

Question 18

Explain what is meant with composition in relation to substitutions.

Answer 18

Substitutions can be composed.
Suppose that:
θ1 = t1/X1, . . . ,tn/Xn
θ2 = t’1/Y1, . . . ,t’m/Ym

The composition θ = θ1 ◦ θ2 is obtained as follows
1. Apply θ2 to the terms in θ1 to get θ’1 = t1[θ2]/X1, . . . ,tn[θ2]/Xn
2. Concatenate θ’1 and θ2 to get:
t1[θ2]/X1, . . . ,tn[θ2]/Xn,t’1/Y1, . . . ,t’0m/Ym
3. Remove from this list all elements Xj/Xj, and t’i/Yi such that Yi ∈ {X1, . . . , Xn}.

Example:
Let θ1 = V/U, W /V and θ2 = U/V

1. θ’1 = V[U/V]/U, W [U/V]/V = U/U, W /V
2. θ’1, θ2 = U/U, W /V, U/V
3. θ = θ1 ◦ θ2 = W /V

Question 19

Unification is associated with composition of substitutions, explain what a unifier is and when a unifier qualifies as the most general unifier (MGU).

Answer 19

Suppose that we have two atoms A1 and A2.
- A substitution θ is called a unifier of A1 and A2 if A1[θ] = A2[θ] (syntactically)
- If there is a unifier for A1 and A2 we say that they can be unified
- A unifier θ is called a most general unifier (MGU) if for any other unifier ϑ there is a (list of) substitution(s) ω such that ϑ = θ ◦ ω

Question 20

How can the attention paradox be solved, so that it’s negation is not unsatisfiable?

Answer 20

We can rename the variables as long the variable names are consistent within clauses. Therefore if we have written a formula in clausal form and see that it leads to unsatisfiability, we can then rename the variables within each clause in order to apply resolution.

Question 21

Give an example of a Horn Clause, a Definite clause and a goal clause.

Answer 21

1. Horn clause has at most one positive literal:
   ¬P ∨ Q
2. A definite clause is a horn clause with exactly one positive literal: P
3. A goal clause is a horn clause without positive literals:
   ¬A_{1<\sub> ∨ · · · ∨ ¬An<\sub>}

Question 22

Give an example of a Horn Clause, a Definite clause and a goal clause.

Answer 22

1. Horn clause has at most one positive literal:
   ¬P ∨ Q
2. A definite clause is a horn clause with exactly one positive literal: P
3. A goal clause is a horn clause without positive literals:
   ¬A₁ ∨ · · · ∨ ¬A_n