{
"metadata": {
"name": "",
"signature": "sha256:8f113c190827c8683398b4a5edfeedc2c4a6ec6f24fff252055dae02486f09c0"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": [],
"source": [
"> This is one of the 100 recipes of the [IPython Cookbook](http://ipython-books.github.io/), the definitive guide to high-performance scientific computing and data science in Python.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 15.6. Finding a Boolean propositional formula from a truth table"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from sympy import *\n",
"init_printing()"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's define a few variables."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"var('x y z')"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can define propositional formulas with symbols and a few operators."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"P = x & (y | ~z); P"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"P.subs({x: True, y: False, z: True})"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, we want to find a propositional formula depending on x, y, z, with the following truth table:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%HTML\n",
"\n",
"
\n",
"\n",
"x | y | z | ?? | \n",
"
\n",
"\n",
"T | T | T | * | \n",
"
\n",
"\n",
"T | T | F | * | \n",
"
\n",
"\n",
"T | F | T | T | \n",
"
\n",
"\n",
"T | F | F | T | \n",
"
\n",
"\n",
"F | T | T | F | \n",
"
\n",
"\n",
"F | T | F | F | \n",
"
\n",
"\n",
"F | F | T | F | \n",
"
\n",
"\n",
"F | F | F | T | \n",
"
\n",
"
"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"\n",
"\n",
"\n",
"x | y | z | ?? | \n",
"
\n",
"\n",
"T | T | T | * | \n",
"
\n",
"\n",
"T | T | F | * | \n",
"
\n",
"\n",
"T | F | T | T | \n",
"
\n",
"\n",
"T | F | F | T | \n",
"
\n",
"\n",
"F | T | T | F | \n",
"
\n",
"\n",
"F | T | F | F | \n",
"
\n",
"\n",
"F | F | T | F | \n",
"
\n",
"\n",
"F | F | F | T | \n",
"
\n",
"
"
],
"metadata": {},
"output_type": "display_data",
"text": [
""
]
}
],
"prompt_number": 1
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's write down all combinations that we want to evaluate to True, and those for which the outcome does not matter."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"minterms = [[1,0,1], [1,0,0], [0,0,0]]\n",
"dontcare = [[1,1,1], [1,1,0]]"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, we use the SOPform function to derive an adequate proposition."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Q = SOPform(['x', 'y', 'z'], minterms, dontcare); Q"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's test that this proposition works."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Q.subs({x: True, y: False, z: False}), Q.subs({x: False, y: True, z: True})"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> You'll find all the explanations, figures, references, and much more in the book (to be released later this summer).\n",
"\n",
"> [IPython Cookbook](http://ipython-books.github.io/), by [Cyrille Rossant](http://cyrille.rossant.net), Packt Publishing, 2014 (500 pages)."
]
}
],
"metadata": {}
}
]
}