AI: Representation Logic

Representation – agents model of the world (could be increasingly complex. Representation uses tools of logic could be used by an agent to better model the world.

Propositional Logic

B (burglary occurring) E(earthquake) A(Alarm) M(Marry calls police) J(John calls police)

True False

( E v B ) => A ( Alarm is True whenever either Eathrquake or Burglary is True)

A=> (J ^ M) (When Alarm is True both Mary and John is True)

J <=> M (bioconditional: John calls when and only when Marry calls, John is equivalent to Mary)

J <=> !M (John isequivalent to not Marry)

Propositional logic either True or False with respect to a model of the world. Model is just a set of true/false values for all the propositional symbols.

Example: {B:True, E:False, …}

P => Q (P implies Q)

Terminology

VALID sentence is one that is true in every possible model, for every combination of values of the propositional symbols.

SATISFIABLE sentence is one that is true in some models, but not necessary in all the models.

UNSUTISFIABLE sentance is one that is false for all models.

Limitations

No capability to handle Uncertainty

Supports only events that are true or false in the world. Cannot handle objects that have proporties (color, size etc.)

There are no shortcuts to succinctly talk about a lot of different things happening (example with vacuum world with thousand locations)

First Order Logic 

Addresses limitations of No Objects and No Shortcuts.

Relations to Propositional Logic and Probability Theory. We are going to talk about them in terms of what they say about the world, which we call the ontological commitment of these logics, and what tupes of beliefs agents can have using these logics, which we call epistemological commitments.

	WORLD	BELIEF
FIRST-ORDER LOGIC	Relations, Objects, Functions	T/F/?
PROPOSITIONAL LOGIC	Facts	T/F/?
PROBABILITY THEORY	Facts	[0..1] in R

Another way to look at the representation is to break the world up into representations that are atomic, meaning a representation of the state is just an individual state with no pieces inside of it. And that’s what we used for search and problem solving. We have a state A and then we transitioned to another state like state B. And all we could say about those states was are they identical to each other or not, and maybe is one of them a goal state or not.  But there wasn’t any internal structure to those states.

atomic (Problem solving | A   B )

factored

structured

In propositional logic, as well as in probability theory, we break up the world into a set of facts that are true or false, so we call this a factored representation, that is representation of an individual state of the world, that is the representation of an individual state of the world is factored into several variables – the B and E and A and M and J, for example. And those could be Boolean variables or in some types of representations, not in propositional logic – they can be other types of variables besides Boolean.

3rd type, the more complex type of representation, we call structured. And in a structured representation, an individual state is not just a set of values for variables, but it can include relationship between objects, a branching structure, and complex representations and relations, between one object and another. And that we see in traditional programming languages, in databases, that’s more powerful representation and that what we’ve got in First Order Logic.

How does First Order logic work? What does it do?

Like propositional logic we start with model. In propositional logic a model was a value for each propositional symbol. So we might say that the symbol P was true and the symbol Q was false {P:T, Q:F}, and that would be a model that corresponds to what’s going on in a possible world.

In First Order Logic we start off with a set of objects.

We can have a set of constants that refer to those objects

Constants: {A, B, C, D, 1, 2, 3, CEE}.

But I don’t have one-to-one correspondence between constants and objects. I could have 2 different constant names that refer to the same object – CEE and C. Or some objects could don’t have any names at all.

Also have set of functions. Function is defined by mapping between object and object.

Functions: 

Number of: {A-> 1, B-> 3, C->3, D->2}

 In addition to functions I can have relations. For example I could have the Above relation, and I could say in this model of the world the Above relation is a set of tuples. So that is a binary relation holding between 2 objects, say 1 block is above another block. We can have another type or relations for example unary relation “Vowel”. Vowel is true only of the objects that we call A, than that’s a set of tuples of length 1 that contains just A. We can have relations Rainy which doesn’t refer to any objects at all, only to current situation.

Relations: 

Above: {[A,B], [C,D]}

Vowel: {[A]}

Rainy: {} {[]}

Syntax

First Order Logic defined by Sentences and Terms. 

Sentences

Atomic sentences are predicates corresponding to relations.

Vowel (A)

Above (A,B)

2 = 2 – quality relations

Operators

Sentences could be combined with all operators from propositional logic: ^, v, ~, =>, <=>

Terms (unlike propositional logic)

Describe/refer to objects, could be constants, variables, functions.

A, B, 2

x, y

NUMBEROF (A) – which is just another name or another expression that refers to the same object as 1.

Quantifiers

Vacuum World Example

First Order means that relations are on object but not on relations. If they are on relations it would be Higher Order.