07. First Order Logic

Question 1

4 advantages of propositional logic:

Answer 1

it is declarative: pieces of syntax correspond to facts, unlike many programming languages which are procedural.

it allows for disjunctive/negated/partial information, unlike most data structures and databases.

it is compositional: meaning of P^Q is derived from meaning of P and of Q

it is context-independent, unlike natural language where meaning depends on context

Question 2

1 dis-advantage of propositional logic:

Answer 2

Propositional logic has very limited expressive power
(unlike natural language);
e.g., cannot say “pits cause breezes in adjacent squares” except by writing one sentence for each square

Question 3

First-Order Logic (FOL)
Whereas propositional logic assumes the world contains facts, first-order logic (like natural language) assumes the world contains
Objects: corresponds to nouns in natural language.
Examples: people, houses, numbers, theories, Angela Merkel, colors, football games, . . .
Relations: corresponds to verbs and adjectives. Relations can be unary or n-ary.
Unary examples: red, round, bogus, prime, multi-storied, . . . N-ary examples: brother of, bigger than, inside, part of, occurred after, owns, comes between, . . .
Functions: relations where each input is related to exactly one output.
Examples: father of, best friend, third inning of, one more than, end of, …

Answer 3

“One plus two equals three.”
Objects: one, two, three, one plus two Relations: equals
Functions: plus

“Squares neighboring the Wumpus are smelly.“
Objects: squares, Wumpus
Relations: smelly (unary), neighboring (n-ary) Functions: -

”Evil King John ruled England in 1200.”
Objects: King John, England, 1200 Relations: evil (unary), ruled (n-ary) Functions: -

Question 4

De Morgan rules for quantified sentences

Answer 4

∀x P≡ ¬∃x ¬P
∃x P≡ ¬∀x ¬P

Question 5

Assertions and Queries in First-Order Logic
We add sentences to a knowledge base using Tell, called assertions:
John is a king: Tell(KB, King(John)) Richard is a person: Tell(KB, Person(Richard))
All kings are persons: Tell(KB, ∀x King(x) ⇒ Person(x)) We ask questions of the knowledge base using Ask, called queries:
Ask(KB, King(John)) returns true. For some queries a yes/no answer is undesirable: …

Answer 5

Ask(KB, ∃x Person(x)).
With AskVars we obtain a stream of answers: AskVars(KB, ∃x Person(x)),
which returns {x/John} and {x/Richard}.

Question 6

Knowledge Engineering Process (1)
We describe the general process of knowledge-base construction, which we exemplify for the Wumpus world:
1 Identify the task
Example: does the knowledge base need to …
2 Assemble the relevant knowledge from experts in their domain. Example: …
3 Decide on vocabulary of predicates, functions, and constants. The resulting vocabulary is also known as the …. Example: Should pits be represented by …?
4 Encode general knowledge about the domain. This often …
Example: ∀s,t At(Agent,s,t)∧Breeze(t)⇒Breezy(s)

Answer 6

answer questions about actions or only about the environment?

what does it mean when a cave is smelly?

ontology of a domain; constants or unary predicates

reveals misconceptions, requiring us to go back to step 3.

Question 7

Knowledge Engineering Process (2)
5 Encode a description of the specific problem instance. This step is simple if…
Example: There is no pit in square [1,1]: ¬Pit([1,1]).

6 Pose queries to the inference procedure. This is the reward: We get answers without…Example: Where are the pits? AskVars(KB, ∃x Pit(x))

7 Debug the knowledge base. If knowledge is missing, some queries cannot be answered.
Example: if the knowledge base includes the diagnostic rule
∀s Smelly(s) ⇒ Adjacent Home(Wumpus),s, instead of the biconditional for finding the Wumpus, then the agent will never be able to prove the absence of Wumpus.

Answer 7

the ontology is well thought out. Problem instances come from sensors or are added as sentences.

writing an application-specific solution algorithm.