Newer
Older
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This notebook describes the [logic.py](https://github.com/aimacode/aima-python/blob/master/logic.py) module, which covers Chapters 6 (Logical Agents), 7 (First-Order Logic) and 8 (Inference in First-Order Logic) of *[Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu)*. See the [intro notebook](https://github.com/aimacode/aima-python/blob/master/intro.ipynb) for instructions.\n",
"We'll start by looking at `Expr`, the data type for logical sentences, and the convenience function `expr`. Then we'll cover `KB` and `ProbKB`, the classes for Knowledge Bases. Then, we will construct a knowledge base of a specific situation in the Wumpus World. We will next go through the `tt_entails` function and experiment with it a bit. The `pl_resolution` and `pl_fc_entails` functions will come next. \n",
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"metadata": {
"collapsed": true
},
{
"cell_type": "markdown",
"metadata": {},
"The `Expr` class is designed to represent any kind of mathematical expression. The simplest type of `Expr` is a symbol, which can be defined with the function `Symbol`:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"x"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Symbol('x')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Or we can define multiple symbols at the same time with the function `symbols`:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can combine `Expr`s with the regular Python infix and prefix operators. Here's how we would form the sentence for \"P and not Q\":"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"outputs": [
{
"data": {
"text/plain": [
"(P & ~Q)"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
"This works because the `Expr` class overloads the `&` operator with this definition:\n",
"\n",
"```python\n",
"def __and__(self, other): return Expr('&', self, other)```\n",
" \n",
"and does similar overloads for the other operators. An `Expr` has two fields: `op` for the operator, which is always a string, and `args` for the arguments, which is a tuple of 0 or more expressions. Let's take a look at the fields for some `Expr` examples:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'&'"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sentence = P & Q\n",
"\n",
"sentence.op"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P.op"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"()"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P.args"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(x, y)"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is important to note that the `Expr` class does not define the *logic* of Propositional Logic; it just gives you a way to *represent* expressions. Think of an `Expr` as an [abstract syntax tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree). Each of the `args` in an `Expr` can be either a symbol, a number, or a nested `Expr`. We can nest these trees to any depth. An `Expr` can represent any kind of mathematical expression, not just logical sentences. For example:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(((3 * f(x, y)) + (P(y) / 2)) + 1)"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
"3 * f(x, y) + P(y) / 2 + 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Operators for Constructing Logical Sentences\n",
"Here is a table of the operators that can be used to form sentences. Note that we have a problem: we want to use Python operators to make sentences, so that our programs (and our interactive sessions like the one here) will show simple code. But Python does not allow implication arrows as operators, so for now we will create them using functions (but Python will display them using arrows). Alternately, you can always use the more verbose `Expr` constructor forms:\n",
"| Operation | Book | Python Input | Python Output | `Expr` Input\n",
"|--------------------------|----------------------|-------------------------|---|---|\n",
"| Negation | ¬ P | `~P` | `~P` | `Expr('~', P)`\n",
"| And | P ∧ Q | `P & Q` | `P & Q` | `Expr('&', P, Q)`\n",
"| Or | P ∨ Q | `P`<tt> | </tt>`Q`| `P`<tt> | </tt>`Q` | `Expr('`|`', P, Q)\n",
"| Inequality (Xor) | P ≠ Q | `P ^ Q` | `P ^ Q` | `Expr('^', P, Q)`\n",
"| Implication | P → Q | `implies(P, Q)` | `P ==> Q` | `Expr('==>', P, Q)`\n",
"| Reverse Implication | Q ← P | `rimplies(P, Q)` |`Q <== P` | `Expr('<==', Q, P)`\n",
"| Equivalence | P ↔ Q | `equiv(P, Q)` |`P ==> Q` | `Expr('==>', P, Q)`\n",
"Here's an example of defining a sentence:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(~(P & Q) <=> (~P | ~Q))"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"equiv(~(P & Q), (~P | ~Q))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## `expr`: a Shortcut for Constructing Sentences\n",
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
"We can't write `(~(P & Q) <=> (~P | ~Q))` as a Python expression, because Python does not have the `<=>` operator. But we can do something almost as good:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(~(P & Q) <=> (~P | ~Q))"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expr('~(P & Q) <=> (~P | ~Q)')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The function `expr` takes a string as input, and parses it into an `Expr`. The string can contain arrow operators: `==>`, `<==`, or `<=>`. And `expr` automatically defines any symbols, so you don't need to pre-define them:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"sqrt(((b ** 2) - ((4 * a) * c)))"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expr('sqrt(b ** 2 - 4 * a * c)')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For now that's all you need to know about `expr`. Later we will explain the messy details of how it is implemented."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Propositional Knowledge Bases: `PropKB`\n",
"The class `PropKB` can be used to represent a knowledge base of propositional logic sentences.\n",
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
"We see that the class `KB` has four methods, apart from `__init__`. A point to note here: the `ask` method simply calls the `ask_generator` method. Thus, this one has already been implemented and what you'll have to actually implement when you create your own knowledge base class (if you want to, though I doubt you'll ever need to; just use the ones we've created for you), will be the `ask_generator` function and not the `ask` function itself.\n",
"\n",
"The class `PropKB` now.\n",
"* `__init__(self, sentence=None)` : The constructor `__init__` creates a single field `clauses` which will be a list of all the sentences of the knowledge base. Note that each one of these sentences will be a 'clause' i.e. a sentence which is made up of only literals and `or`s.\n",
"* `tell(self, sentence)` : When you want to add a sentence to the KB, you use the `tell` method. This method takes a sentence, converts it to its CNF, extracts all the clauses, and adds all these clauses to the `clauses` field. So, you need not worry about `tell`ing only clauses to the knowledge base. You can `tell` the knowledge base a sentence in any form that you wish; converting it to CNF and adding the resulting clauses will be handled by the `tell` method.\n",
"* `ask_generator(self, query)` : The `ask_generator` function is used by the `ask` function. It calls the `tt_entails` function, which in turn returns `True` if the knowledge base entails query and `False` otherwise. The `ask_generator` itself returns an empty dict `{}` if the knowledge base entails query and `None` otherwise. This might seem a little bit weird to you. After all, it makes more sense just to return a `True` or a `False` instead of the `{}` or `None` But this is done to maintain consistency with the way things are in First-Order Logic, where, an `ask_generator` function, is supposed to return all the substitutions that make the query true. Hence the dict, to return all these substitutions. I will be mostly be using the `ask` function which returns a `{}` or a `False`, but if you don't like this, you can always use the `ask_if_true` function which returns a `True` or a `False`.\n",
"* `retract(self, sentence)` : This function removes all the clauses of the sentence given, from the knowledge base. Like the `tell` function, you don't have to pass clauses to remove them from the knowledge base; any sentence will do fine. The function will take care of converting that sentence to clauses and then remove those."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TODO: More on KBs, plus what was promised in Intro Section"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Appendix: The Messy Details of the Implementation of `expr`\n",
"\n",
"How does `expr` parse a string into an `Expr`? It turns out there three tricks:\n",
"\n",
"1. We do a string substitution, replacing `\"==>\"` with `\"|InfixOp('==>', None)|\"`.\n",
"2. We `eval` the resulting string in an environment in which every identifier\n",
"is bound to a symbol with that identifier as the name.\n",
"3. A coordination between `Expr` and `InfixOp` creates the proper nested `Expr`.\n",
"That must sound very confusing, so we'll explain it in detail. Consider the sentence `\"P ==> Q\"`. If we try to evaluate that we get a `SyntaxError` because `==>` is not valid Python syntax. So we substitute it away, using the function `expr_handle_infix_ops` (from the `utils` module):"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"\"P |InfixOp('==>', None)| Q\""
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expr_handle_infix_ops('P ==> Q')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
"What does that mean? To Python, for any expression `op`, \"`P |op| Q`\" is the same as \"`((P | op) | Q)`\". So the first step is:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"InfixOp('==>', P)"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"first = (P | InfixOp('==>', None))\n",
"\n",
"first"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`InfixOp('==>', P)` means an infix operator whose operator string is `'==>'` and whose left-hand element is `P`. What happened here is that the `__or__` method in `Expr` says that if the object on the right is an `InfixOp`, then the result is an `InfixOp` whose `lhs` is the `Expr` on the left of the `\"|\"`.\n",
"\n",
"In the second step, we combine this with `Q`:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(P ==> Q)"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"first | Q"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What happened here is that the `__or__` method for `InfixOp` says that when combined with anobject on the right, return a new `Expr` whose `op` and first `arg` comes from the `InfixOp` and whose second `arg` is the object on the right. This [trick](http://code.activestate.com/recipes/384122-infix-operators/) is due to [Ferdinand Jamitzky](http://code.activestate.com/recipes/users/98863/).\n",
"\n",
"Note that we can also use this notation in our own code, or in an interactive session, like this:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"((P & Q) ==> P)"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P & Q |implies| P"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Unfortunately, this puts `implies` at the same precedence as `\"|\"`, which is not quite right. We get this:"
{
"cell_type": "code",
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(((P & Q) ==> P) | Q)"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P & Q |implies| P | Q"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"which is probably not what we meant; when in doubt, put in extra parens:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"((P & Q) ==> (P | Q))"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P & Q |implies| (P | Q)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"# Authors\n",
"\n",
"This notebook by [Chirag Vertak](https://github.com/chiragvartak) and [Peter Norvig](https://github.com/norvig).\n",
"\n"
]
}
],
"metadata": {
"kernelspec": {
"language": "python",
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",