AI class unit 7

These are my notes for unit 7 of the AI class.

Representation with Logic

Introduction

{{#ev:youtubehd|pszEzBql4bw}}

Welcome back. So far we've talked about AI as managing complexity and uncertainty. We've seen how search can discover sequences of actions to solve problems. We've seen how probability theory can represent and reason with uncertainty. And we've seen how machine learning can be used to learn and improve.

AI is a big and dynamic field because we're pushing against complexity in at least three directions. First, in terms of agent design, we start with a simple reflex-based agent and move into goal-based and utility-based agents. Secondly, in terms of the complexity of the environment, we start with simple environments and then start looking at partial observability, at stochastic actions, at multiple agents, and so on. And finally, in terms of representation, the agent's model of the the world becomes increasingly complex.

In this unit we'll concentrate on that third aspect of representation, showing how the tools of logic can be used by an agent to better model the world.

Propositional Logic

{{#ev:youtubehd|_VjyktjNMoM}}

The first logic we will consider is called propositional logic. Let's jump right into an example, recasting the alarm problem in propositional logic. We have propositional symbols B, E, A, M and J corresponding to the events of a burglary occurring, of the earthquake occurring, of the alarm going off, of Mary calling, and of John calling. And just as in the probabilistic models, these can be either true or false, but unlike in probability, our degree of belief in propositional logic is not a number. Rather, our belief is that each of these is either true, false, or unknown. Now, we can make logical sentences using these symbols and also using the logical constants true and false by combining them together using logical operators. For example, we can say that the alarm is true whenever the earthquake or burglary is true with this sentence:

$(E\lor B)\Rightarrow A$

So that says whenever the earthquake or the burglary is true, then the alarm will be true. We use this V symbol to mean "or" and a right arrow to mean "implies".

We could also say that it would be true that both John and Mary call when the alarm is true. We write that as:

$A\Rightarrow (J\land M)$

And we use this symbol to indicate an "and". So this upward-facing wedge looks kind of like an "A" with the crossbar missing, and so you can remember "A" is for "and" where this downward-facing V symbol is the opposite of "and", so that's the symbol for "or".

Now, there's two more connectors we haven't seen yet. There's a double arrow for equivalent, also known as a biconditional, and a not sign for negation. So we could say if we wanted to that John calls if and only if Mary calls. We would write that as:

$J\Leftrightarrow M$

John is equivalent to Mary -- when on is true, the other is true; when one is false, the other is false. Or we could say that when John calls, Mary doesn't, and vice versa. We could write that as:

$J\Leftrightarrow \lnot M$

And this is the "not" sign.

Now, how do we know what the sentences mean? A propositional logic sentence is either true or false with respect to a model of the world. Now a model is just a set of true/false values for all the propositional symbols, so a model might be the set B is true, E is false, and so on. We can define the truth value of the sentence in terms of the truth of the the symbols with respect to the models using truth tables.

Truth Tables

{{#ev:youtubehd|eOp4UJl0ZIA}}

Here are the truth tables for all the logical connectives.

What a truth table does is list all the possibilities for the propositional symbols, so P and Q can be false and false, false and true, true and false, or true and true. Those are the only four possibilities, and then for each of those possibilities, the truth table lists the truth value of the compound sentence. So the sentence not P is true when P is false and false when P is true. The sentence P and Q is true only when both P and Q are true and false otherwise. The sentence P or Q is true when P or Q is true and false when both are false.

Now, so far, those mostly correspond to the English meaning of those sentences, with one exception, which is that in English, the word "or" is somewhat ambiguous between the inclusive and exclusive or, and this "or" means either or both.

We translate this mark into English P implies Q; or as: if P, then Q; but the meaning in logic is not quite the same as the meaning in ordinary English. The meaning in logic is defined explicitly by this truth table and by nothing else, but let's look at some examples in ordinary English.

If we have the proposition O and have that mean five is an odd number and P meaning Paris is the capital for France, then under the ordinary model of the truth in the real world, what could we say about the sentence $O\Rightarrow P$? That is, five is an odd number implies Paris is the capital of France. Would that be true or false? And let's look at one more example? If E is the proposition that five is an even number and M is the proposition that Moscow is the capital of France, what about $E\Rightarrow M$? Five is an even number implies Moscow is the capital of France. Is that true or false?

Note: For the question, please be sure to use the rules of logic, not ordinary English!

{{#ev:youtubehd|4HWzU7RhfZE}}

The answers are first, the sentence if five is an odd number, then Paris is the capital of France, is true in propositional logic. It may sound odd in ordinary English, but in propositional logic, this is the same as true implies true and if we look on this line -- the final line for P and Q, P implies Q is true.a

The second sentence: five is an even number implies Moscow is the capital of France. That's the same as false implies false, and false implies false according to the definition is also true.

Question

{{#ev:youtubehd|ae_9TnTNPU0}}

Here's a quiz. Use truth tables or whatever other method you want to fill in the values of these tables. For each of the values of P and Q -- false/false, false/true, true/false, or true/true -- look at each of these boxes and click on just the boxes in which the formula for that column will be true. So for which of these four boxes, if any, will the formula be true? And this formula, and this formula.