path: root/Elements_of_discrete_mathematics/Chapter1.ipynb

{
 "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": {}
  }
 ]
}