diff options
| author | hardythe1 | 2015-05-05 14:21:39 +0530 |
|---|---|---|
| committer | hardythe1 | 2015-05-05 14:21:39 +0530 |
| commit | 435840cef00c596d9e608f9eb2d96f522ea8505a (patch) | |
| tree | 4c783890c984c67022977ca98432e5e4bab30678 /Elements_of_discrete_mathematics/Chapter1.ipynb | |
| parent | aa1863f344766ca7f7c20a395e58d0fb23c52130 (diff) | |
| download | Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.tar.gz Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.tar.bz2 Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.zip | |
add books
Diffstat (limited to 'Elements_of_discrete_mathematics/Chapter1.ipynb')
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter1.ipynb | 498 |
1 files changed, 498 insertions, 0 deletions
diff --git a/Elements_of_discrete_mathematics/Chapter1.ipynb b/Elements_of_discrete_mathematics/Chapter1.ipynb new file mode 100755 index 00000000..56b9d58d --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter1.ipynb @@ -0,0 +1,498 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:de0a0f66aff079301941637787a8030ad1f216bb6fd8c51b1e13503001244ca2"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "1 Sets and Propositions"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 11:Page 21"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To find the number of computers that support one or more of the three kinds of hardware considered, namely;Floating point arithmetic unit, magnetic disk storage and graphical display terminal.\"\n",
+ "A1=2#Set of computers with floating point arithmetic unit\n",
+ "A2=5#Set of computers with magetic disk storage\n",
+ "A3=3#Set of computers with graphical display terminal\n",
+ "A1_intersection_A2=2#Set of computers with floating point arithmetic unit and magentic disk storage\n",
+ "A1_intersection_A3=1#Set of computers with floating point arithmetic unit and graphical display terminal\n",
+ "A2_intersection_A3=3#Set of computers with magnetic disk storage and graphical display terminal \n",
+ "A1_intersection_A2_intersection_A3=1#Set of computers with floating point arithmetic, magnetic disk storage and graphical display terminal\n",
+ "#By the principle of inclusion and exclusion\n",
+ "A1_union_A2_union_A3=A1+A2+A3-A1_intersection_A2-A1_intersection_A3-A2_intersection_A3+A1_intersection_A2_intersection_A3\n",
+ "print A1_union_A2_union_A3,\"of the six computers have one or more of the three kinds of hardware considered\"\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To find the number of computers that support one or more of the three kinds of hardware considered, namely;Floating point arithmetic unit, magnetic disk storage and graphical display terminal.\n",
+ "5 of the six computers have one or more of the three kinds of hardware considered\n"
+ ]
+ }
+ ],
+ "prompt_number": 1
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 12:Page 21"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"We consider 200 students of courses Discrete Mathematics and Economics. A party is being organized which can be attended only by students who are not in either of the courses as these two courses have exams scheduled the next day.\"\n",
+ "students=200# Total number of students \n",
+ "DM=50 # Number of students who have taken Discrete Mathematics\n",
+ "ECO=140 # Number of students who have taken Economics\n",
+ "DM_and_ECO=24 # Number of students who have taken both Discrete Mathematics and Economics\n",
+ "one_or_both=(DM+ECO-DM_and_ECO) # Number of students who have taken either one or both the courses\n",
+ "print \"Number of students who take either one or both the courses is equal to\",one_or_both\n",
+ "print \"Consequently, the number of students who will be at the party is\", (students-one_or_both)\n",
+ "print \"Suppose that 60 of the 200 are underclass students \"\n",
+ "UC_students=60 # Number of underclass students\n",
+ "dm=20 # Number of underclass students who have taken Discrete Mathematics\n",
+ "eco=45 # Number of underclass students who have taken Economics\n",
+ "dm_and_eco=16 # Number of underclass students who have taken both Discrete Mathematics and Economics\n",
+ "# A1 is the set of students in the course Discrete Mathematics\n",
+ "# A2 is the set of students in the course Economics\n",
+ "# A3 is the set of underclass students\n",
+ "A1_union_A2_union_A3=DM+ECO+UC_students-DM_and_ECO-dm-eco+dm_and_eco\n",
+ "print \"Thus, the number of upperclass students who will go to the party is\",(students-A1_union_A2_union_A3)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "We consider 200 students of courses Discrete Mathematics and Economics. A party is being organized which can be attended only by students who are not in either of the courses as these two courses have exams scheduled the next day.\n",
+ "Number of students who take either one or both the courses is equal to 166\n",
+ "Consequently, the number of students who will be at the party is 34\n",
+ "Suppose that 60 of the 200 are underclass students \n",
+ "Thus, the number of upperclass students who will go to the party is 23\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 13:Page 22"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To find the number of cars which have neither a radio nor an air conditioner nor white-wall tires out of the thirty cars assembled in a factory\"\n",
+ "cars=30 # Total number of cars assembled in a factory\n",
+ "A1=15 # Set of cars with radio\n",
+ "A2=8 # Set of cars with air-conditioner\n",
+ "A3=6 # Set of cars with white-wall tires\n",
+ "A1_intersection_A2_intersection_A3=3\n",
+ "A1_intersection_A2=3 # Since |A1_intersection_A2| >=|A1_intersection_A2_intersection_A3|\n",
+ "A1_intersection_A3=3 # Since |A1_intersection_A3| >=|A1_intersection_A2_intersection_A3|\n",
+ "A2_intersection_A3=3 # Since |A2_intersection_A3| >=|A1_intersection_A2_intersection_A3|\n",
+ "A1_union_A2_union_A3=A1+A2+A3-A1_intersection_A2-A1_intersection_A3-A2_intersection_A3+A1_intersection_A2_intersection_A3 # By the principle of inclusion and exclusion\n",
+ "print \"There are at most\",A1_union_A2_union_A3,\"cars that have one or more options.\"\n",
+ "print \"Consequently,there are at least\",(cars-A1_union_A2_union_A3),\"cars that do not have any options\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To find the number of cars which have neither a radio nor an air conditioner nor white-wall tires out of the thirty cars assembled in a factory\n",
+ "There are at most 23 cars that have one or more options.\n",
+ "Consequently,there are at least 7 cars that do not have any options\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 14:Page 24"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To determine the number of integers between 1 and 250 that are divisible by 2,3,5,7\"\n",
+ "A1=250/2 # Number of integers between 1 and 250 that are divisible by 2\n",
+ "A2=250/3 # Number of integers between 1 and 250 that are divisible by 3\n",
+ "A3=250/5 # Number of integers between 1 and 250 that are divisible by 5\n",
+ "A4=250/7 # Number of integers between 1 and 250 that are divisible by 7\n",
+ "A1_intersection_A2=250/(2*3) # Number of integers between 1 and 250 that are divisible by 2 and 3\n",
+ "A1_intersection_A3=250/(2*5) # Number of integers between 1 and 250 that are divisible by 2 and 5\n",
+ "A1_intersection_A4=250/(2*7) # Number of integers between 1 and 250 that are divisible by 2 and 7\n",
+ "A2_intersection_A3=250/(3*5)# Number of integers between 1 and 250 that are divisible by 3 and 5\n",
+ "A2_intersection_A4=250/(3*7)# Number of integers between 1 and 250 that are divisible by 3 and 7\n",
+ "A3_intersection_A4=250/(5*7)# Number of integers between 1 and 250 that are divisible by 5 and 7\n",
+ "A1_intersection_A2_intersection_A3=250/(2*3*5) # Number of integers between 1 and 250 that are divisible by 2,3 and 5\n",
+ "A1_intersection_A2_intersection_A4=250/(2*3*7) # Number of integers between 1 and 250 that are divisible by 2,3 and 7\n",
+ "A1_intersection_A3_intersection_A4=250/(2*5*7) # Number of integers between 1 and 250 that are divisible by 2,5 and 7\n",
+ "A2_intersection_A3_intersection_A4=250/(3*5*7) # Number of integers between 1 and 250 that are divisible by 3,5 and 7\n",
+ "A1_intersection_A2_intersection_A3_intersection_A4=250/(2*3*5*7) # Number of integers between 1 and 250 that are divisible by 2,3,5 and 7\n",
+ "A1_union_A2_union_A3_union_A4=A1+A2+A3+A4-A1_intersection_A2-A1_intersection_A3-A1_intersection_A4-A2_intersection_A3-A2_intersection_A4-A3_intersection_A4+A1_intersection_A2_intersection_A3+A1_intersection_A2_intersection_A4+A1_intersection_A3_intersection_A4+A2_intersection_A3_intersection_A4-A1_intersection_A2_intersection_A3_intersection_A4\n",
+ "print \"A1 is the set of integers between 1 and 250 that are divisible by 2\"\n",
+ "print \"A2 is the set of integers between 1 and 250 that are divisible by 3\"\n",
+ "print \"A3 is the set of integers between 1 and 250 that are divisible by 5\"\n",
+ "print \"A4 is the set of integers between 1 and 250 that are divisible by 7\"\n",
+ "print \"|A1_union_A2_union_A3_union_A4|=\",A1_union_A2_union_A3_union_A4\n",
+ "\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To determine the number of integers between 1 and 250 that are divisible by 2,3,5,7\n",
+ "A1 is the set of integers between 1 and 250 that are divisible by 2\n",
+ "A2 is the set of integers between 1 and 250 that are divisible by 3\n",
+ "A3 is the set of integers between 1 and 250 that are divisible by 5\n",
+ "A4 is the set of integers between 1 and 250 that are divisible by 7\n",
+ "|A1_union_A2_union_A3_union_A4|= 193\n"
+ ]
+ }
+ ],
+ "prompt_number": 4
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 15:Page 29"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Truth table for (p and q)and (not p)\"\n",
+ "def truth_table(p,q):\n",
+ " return (p and q) and (not p)#Logical representation of the given boolean exoression\n",
+ "print \"p\\tq\\t(p and q)\\t(not p)\\t(p and q) and (not p)\"\n",
+ "for a in (True,False):\n",
+ " for b in (True,False):#Loops that generate the possible input values\n",
+ " print a,\"\\t\",b,\"\\t\",a and b,\"\\t\\t\",not a,\"\\t\",truth_table(a,b)\n",
+ " \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Truth table for (p and q)and (not p)\n",
+ "p\tq\t(p and q)\t(not p)\t(p and q) and (not p)\n",
+ "True \tTrue \tTrue \t\tFalse \tFalse\n",
+ "True \tFalse \tFalse \t\tFalse \tFalse\n",
+ "False \tTrue \tFalse \t\tTrue \tFalse\n",
+ "False \tFalse \tFalse \t\tTrue \tFalse\n"
+ ]
+ }
+ ],
+ "prompt_number": 5
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 21:Page 33"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Consider the truth tables of (P and negation_P)\"\n",
+ "print \"Here all the entries in the last column are false\"\n",
+ "def truth_table_and(p):\n",
+ " return p and (not p)#Representation of logical AND\n",
+ " \n",
+ "print \"p\\tnegation_p\\tp_and_negation_p\"\n",
+ "print \"---------------------------------------------\"\n",
+ "for q in (True,False):#generates the combination of inputs\n",
+ " res=truth_table_and(q)\n",
+ " print q,\"\\t\\t\",not q,\"\\t\\t\",res\n",
+ " \n",
+ " \n",
+ "print \"Consider the truth tables of (P or negation_P)\"\n",
+ "print \"Here all the entries in the last column are true \"\n",
+ "def truth_table_or(p):\n",
+ " return p or (not p)#Representation of logical OR\n",
+ " \n",
+ "print \"p\\tnegation_p\\tp_or_negation_p\"\n",
+ "print \"----------------------------------------------\"\n",
+ "for q in (True,False):#generates the combination of inputs\n",
+ " res=truth_table_or(q)\n",
+ " print q,\"\\t\\t\",not q,\"\\t\\t\",res\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Consider the truth tables of (P and negation_P)\n",
+ "Here all the entries in the last column are false\n",
+ "p\tnegation_p\tp_and_negation_p\n",
+ "---------------------------------------------\n",
+ "True \t\tFalse \t\tFalse\n",
+ "False \t\tTrue \t\tFalse\n",
+ "Consider the truth tables of (P or negation_P)\n",
+ "Here all the entries in the last column are true \n",
+ "p\tnegation_p\tp_or_negation_p\n",
+ "----------------------------------------------\n",
+ "True \t\tFalse \t\tTrue\n",
+ "False \t\tTrue \t\tTrue\n"
+ ]
+ }
+ ],
+ "prompt_number": 6
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 23:Page 35"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Restaurent 1 says 'Good food is not cheap'\"\n",
+ "print \"Restaurent 2 says 'Cheap food is not good'\"\n",
+ "#Generating prepositions from the given sentences\n",
+ "g='Food is good'\n",
+ "c='Food is cheap'\n",
+ "print \"g->negation c means 'Good food is not cheap'\"\n",
+ "print \"c->negation g means 'Cheap food is not good'\"\n",
+ "def g_implies_negation_c(g,c):\n",
+ " if g==True and not(c)==False:# Implementation of logical implication\n",
+ " return 'False'\n",
+ " else:\n",
+ " return 'True'\n",
+ "\n",
+ "def c_implies_negation_g(g,c):\n",
+ " if c==True and not g==False:# Implementation of logical implication\n",
+ " return 'False'\n",
+ " else:\n",
+ " return 'True'\n",
+ "print \"g\\t\\tc\\t|\\t\\tnegation_g\\t\\t\\tnegation_c\\t\\t\\tg_implies_negation_c\\t\\t\\tc_implies_negation_g\"\n",
+ "print \"---------------------------------------------------------------------------------------------------------------------------------------------------------------\"\n",
+ "for a in (False,True):#Generate the possible inputs\n",
+ " for b in (False,True):\n",
+ " print (\"%5s%10s\\t\\t|%20s%30s%35s%40s\"%(a,b,not a,not b,g_implies_negation_c(a,b),c_implies_negation_g(a,b)))\n",
+ " \n",
+ " \n",
+ "print \"Since both g_implies_negation_c and c_implies_negation_g values in the truth table are similar, it is proved that 'Good food is not cheap' and 'Cheap food is not good are the same'\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Restaurent 1 says 'Good food is not cheap'\n",
+ "Restaurent 2 says 'Cheap food is not good'\n",
+ "g->negation c means 'Good food is not cheap'\n",
+ "c->negation g means 'Cheap food is not good'\n",
+ "g\t\tc\t|\t\tnegation_g\t\t\tnegation_c\t\t\tg_implies_negation_c\t\t\tc_implies_negation_g\n",
+ "---------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
+ "False False\t\t| True True True True\n",
+ "False True\t\t| True False True True\n",
+ " True False\t\t| False True True True\n",
+ " True True\t\t| False False False False\n",
+ "Since both g_implies_negation_c and c_implies_negation_g values in the truth table are similar, it is proved that 'Good food is not cheap' and 'Cheap food is not good are the same'\n"
+ ]
+ }
+ ],
+ "prompt_number": 7
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 24:Page 35"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "def implication(p,q,r,s):#Implementation of logical implicaion\n",
+ " part1=((p and q) or (p and r) )\n",
+ " if part1==True and s==False:\n",
+ " return 'False'\n",
+ " else:\n",
+ " return 'True'\n",
+ "def equivalent(p,q,r,s):#Implementation of logical expression\n",
+ " return (((not p) or((not q) and (not r)))or s)\n",
+ "print \"\\tp\\tq\\tr\\t\\ts\\t\\t|((p and q)or(p and q))->s\\t((negation_p or(negation_q and negation_r))or s)\"\n",
+ "print \"--------------------------------------------------------------------------------------------------------------------------------------\"\n",
+ "for a in (False,True):\n",
+ " for b in (False,True):\n",
+ " for c in (False,True):\n",
+ " for d in (False,True):#Genetates all possible combinations of inputs\n",
+ " print (\"%8s%8s%10s%15s|%35s%35s\" %(a,b,c,d,implication(a,b,c,d),equivalent(a,b,c,d)))\n",
+ " \n",
+ "print \"Therefore, they are proved to be equivalent\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\tp\tq\tr\t\ts\t\t|((p and q)or(p and q))->s\t((negation_p or(negation_q and negation_r))or s)\n",
+ "--------------------------------------------------------------------------------------------------------------------------------------\n",
+ " False False False False| True True\n",
+ " False False False True| True True\n",
+ " False False True False| True True\n",
+ " False False True True| True True\n",
+ " False True False False| True True\n",
+ " False True False True| True True\n",
+ " False True True False| True True\n",
+ " False True True True| True True\n",
+ " True False False False| True True\n",
+ " True False False True| True True\n",
+ " True False True False| False False\n",
+ " True False True True| True True\n",
+ " True True False False| False False\n",
+ " True True False True| True True\n",
+ " True True True False| False False\n",
+ " True True True True| True True\n",
+ "Therefore, they are proved to be equivalent\n"
+ ]
+ }
+ ],
+ "prompt_number": 10
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 55:Page 55"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"EUCLIDEAN ALGORITHM\"\n",
+ "def GCD(n,m):#Euclidean algorithm to compute GCD\n",
+ " if n>=m and (n%m==0):\n",
+ " return m\n",
+ " else:\n",
+ " return GCD(m,n%m)\n",
+ "print \"GCD(25,6) by Euclidean algorithm =\",GCD(25,6),\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "EUCLIDEAN ALGORITHM\n",
+ "GCD(25,6) by Euclidean algorithm = 1\n"
+ ]
+ }
+ ],
+ "prompt_number": 11
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 56:Page 55"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"EUCLIDEAN ALGORITHM\"\n",
+ "def GCD(n,m):#Euclidean algorithm to compute GCD\n",
+ " if n>=m and (n%m==0):\n",
+ " return m\n",
+ " else:\n",
+ " return GCD(m,n%m)\n",
+ "print \"GCD(18,4) by Euclidean algorithm =\",GCD(18,4),#Final comma in all print statements is to eliminate new line character in the end of it\n",
+ "print \"\\nGCD(26,2) by Euclidean algorithm =\",GCD(26,2),\n",
+ "print \"\\nGCD(28,8) by Euclidean algorithm =\",GCD(28,8),\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "EUCLIDEAN ALGORITHM\n",
+ "GCD(18,4) by Euclidean algorithm = 2 \n",
+ "GCD(26,2) by Euclidean algorithm = 2 \n",
+ "GCD(28,8) by Euclidean algorithm = 4\n"
+ ]
+ }
+ ],
+ "prompt_number": 12
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file |