Transcript Propositional Logic

Propositional Logic
Reading: C. 7.4-7.8, C. 8
Announcements

Read discussion board frequently
• Questions answered
• New posts of client-server
• Today: version posted with improved IO on display and
timing

Mid-term evaluation on courseworks

Written homework
• Complete by next Tuesday (1 week)
• Do not do “predicate logic” on problem 10.5 (will be part
of next assignment)
• Should read “but use semantic networks and KL-one
type ” .. Do not extend the representation itself.
• Note that section 10.6 covers semantic networks and
description logics (another name for KL-one type)
2
Logic: Outline




Propositional Logic
Inference in Propositional Logic
First-order logic
Inference in FOL
3
Agents that reason logically

A logic is a:
• Formal language in which knowledge can be
expressed
• A means of carrying out reasoning in the language

A Knowledge base agent
• Tell: add facts to the KB
• Ask: query the KB
4
Towards General-Purpose AI

Problem-specific AI (e.g., Roomba)

General –purpose AI (e.g., logic-based)
• Specific data structure
• Need special implementation
• Can be fast
• Flexible and expressive
• Generic implementation possible
• Can be slow
5
Language Examples

Programming languages

Natural Language
• Formal, not ambiguous
• Lacks expressivity (e.g., partial information)
• Very expressive, but ambiguous:
•
•
Flying planes can be dangerous.
The teacher gave the boys an apple.
• Inference possible, but hard to automate

Good representation language
• Both formal and can express partial information
• Can accommodate inference
6
Components of a Formal Logic

Syntax: symbols and rules for combining them
What you can say

Semantics: Specification of the way symbols (and
sentences) relate to the world
What it means

Inference Procedures: Rules for deriving new sentences
(and therefore, new semantics) from existing sentences
Reasoning
7
8
Semantics



A possible world (also called a model) is an
assignment of truth values to each
propositional symbol
The semantics of a logic defines the truth of
each sentence with respect to each possible
world
A model of a sentence is an interpretation in
which the sentence evaluates to True
• E.g., TodayIsTuesday -> ClassAI is true in model
{TodayIsTuesday=True, ClassAI=True}
• We say {TodayIsTuesday=True, ClassAI=True} is a
model of the sentence
13
Exercise: Semantics
What is the meaning of these two
sentences?


If Shakespeare ate Crunchy-Wunchies
for breakfast, then Sally will go to
Harvard
If Shakespeare ate Cocoa-Puffs for
breakfast, then Sally will go to Columbia
14
Examples

What are the models of the following
sentences?

KB1: TodayIsTuesday -> ClassAI

KB2: TodayIsTuesday -> ClassAI,
TodayIsTuesday
15
Proof by refutation

A complete inference procedure

A single inference rule, resolution

A conjunctive normal form for the logic
19
Example: Wumpus World



Agent in [1,1] has no breeze
KB = R2 Λ R4 =
(B1,1<->(P1,2) V P2,1)) Λ⌐B1,1
Goal: show ⌐P1,2
27
Conversion Example
28