# 1 Sets and Propositions¶

## Example 11:Page 21¶

In [1]:
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."
A1=2#Set of computers with floating point arithmetic unit
A2=5#Set of computers with magetic disk storage
A3=3#Set of computers with graphical display terminal
A1_intersection_A2=2#Set of computers with floating point arithmetic unit and magentic disk storage
A1_intersection_A3=1#Set of computers with floating point arithmetic unit and graphical display terminal
A2_intersection_A3=3#Set of computers with magnetic disk storage and graphical display terminal
A1_intersection_A2_intersection_A3=1#Set of computers with floating point arithmetic, magnetic disk storage and graphical display terminal
#By the principle of inclusion and exclusion
A1_union_A2_union_A3=A1+A2+A3-A1_intersection_A2-A1_intersection_A3-A2_intersection_A3+A1_intersection_A2_intersection_A3
print A1_union_A2_union_A3,"of the six computers have one or more of the three kinds of hardware considered"

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.
5 of the six computers have one or more of the three kinds of hardware considered


## Example 12:Page 21¶

In [2]:
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."
students=200# Total number of students
DM=50 # Number of students who have taken Discrete Mathematics
ECO=140 # Number of students who have taken Economics
DM_and_ECO=24 # Number of students who have taken both Discrete Mathematics and Economics
one_or_both=(DM+ECO-DM_and_ECO) # Number of students who have taken either one or both the courses
print "Number of students who take either one or both the courses is equal to",one_or_both
print "Consequently, the number of students who will be at the party is", (students-one_or_both)
print "Suppose that 60 of the 200 are underclass students "
UC_students=60 # Number of underclass students
dm=20 # Number of underclass students who have taken Discrete Mathematics
eco=45 # Number of underclass students who have taken Economics
dm_and_eco=16 # Number of underclass students who have taken both Discrete Mathematics and Economics
# A1 is the set of students in the course Discrete Mathematics
# A2 is the set of students in the course Economics
# A3 is the set of underclass students
A1_union_A2_union_A3=DM+ECO+UC_students-DM_and_ECO-dm-eco+dm_and_eco
print "Thus, the number of upperclass students who will go to the party is",(students-A1_union_A2_union_A3)

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.
Number of students who take either one or both the courses is equal to 166
Consequently, the number of students who will be at the party is 34
Suppose that 60 of the 200 are underclass students
Thus, the number of upperclass students who will go to the party is 23


## Example 13:Page 22¶

In [3]:
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"
cars=30 # Total number of cars assembled in a factory
A1=15 # Set of cars with radio
A2=8 # Set of cars with air-conditioner
A3=6 # Set of cars with white-wall tires
A1_intersection_A2_intersection_A3=3
A1_intersection_A2=3 # Since |A1_intersection_A2| >=|A1_intersection_A2_intersection_A3|
A1_intersection_A3=3 # Since |A1_intersection_A3| >=|A1_intersection_A2_intersection_A3|
A2_intersection_A3=3 # Since |A2_intersection_A3| >=|A1_intersection_A2_intersection_A3|
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
print "There are at most",A1_union_A2_union_A3,"cars that have one or more options."
print "Consequently,there are at least",(cars-A1_union_A2_union_A3),"cars that do not have any options"

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
There are at most 23 cars that have one or more options.
Consequently,there are at least 7 cars that do not have any options


## Example 14:Page 24¶

In [4]:
print "To determine the number of integers between 1 and 250 that are divisible by 2,3,5,7"
A1=250/2 # Number of integers between 1 and 250 that are divisible by 2
A2=250/3 # Number of integers between 1 and 250 that are divisible by 3
A3=250/5 # Number of integers between 1 and 250 that are divisible by 5
A4=250/7 # Number of integers between 1 and 250 that are divisible by 7
A1_intersection_A2=250/(2*3) # Number of integers between 1 and 250 that are divisible by 2 and 3
A1_intersection_A3=250/(2*5) # Number of integers between 1 and 250 that are divisible by 2 and 5
A1_intersection_A4=250/(2*7) # Number of integers between 1 and 250 that are divisible by 2 and 7
A2_intersection_A3=250/(3*5)# Number of integers between 1 and 250 that are divisible by 3 and 5
A2_intersection_A4=250/(3*7)# Number of integers between 1 and 250 that are divisible by 3 and 7
A3_intersection_A4=250/(5*7)# Number of integers between 1 and 250 that are divisible by 5 and 7
A1_intersection_A2_intersection_A3=250/(2*3*5) # Number of integers between 1 and 250 that are divisible by 2,3 and 5
A1_intersection_A2_intersection_A4=250/(2*3*7) # Number of integers between 1 and 250 that are divisible by 2,3 and 7
A1_intersection_A3_intersection_A4=250/(2*5*7) # Number of integers between 1 and 250 that are divisible by 2,5 and 7
A2_intersection_A3_intersection_A4=250/(3*5*7) # Number of integers between 1 and 250 that are divisible by 3,5 and 7
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
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
print "A1 is the set of integers between 1 and 250 that are divisible by 2"
print "A2 is the set of integers between 1 and 250 that are divisible by 3"
print "A3 is the set of integers between 1 and 250 that are divisible by 5"
print "A4 is the set of integers between 1 and 250 that are divisible by 7"
print "|A1_union_A2_union_A3_union_A4|=",A1_union_A2_union_A3_union_A4

To determine the number of integers between 1 and 250 that are divisible by 2,3,5,7
A1 is the set of integers between 1 and 250 that are divisible by 2
A2 is the set of integers between 1 and 250 that are divisible by 3
A3 is the set of integers between 1 and 250 that are divisible by 5
A4 is the set of integers between 1 and 250 that are divisible by 7
|A1_union_A2_union_A3_union_A4|= 193


## Example 15:Page 29¶

In [5]:
print "Truth table for (p and q)and (not p)"
def truth_table(p,q):
return (p and q) and (not p)#Logical representation of the given boolean exoression
print "p\tq\t(p and q)\t(not p)\t(p and q) and (not p)"
for a in (True,False):
for b in (True,False):#Loops that generate the possible input values
print a,"\t",b,"\t",a and b,"\t\t",not a,"\t",truth_table(a,b)


Truth table for (p and q)and (not p)
p	q	(p and q)	(not p)	(p and q) and (not p)
True 	True 	True 		False 	False
True 	False 	False 		False 	False
False 	True 	False 		True 	False
False 	False 	False 		True 	False


## Example 21:Page 33¶

In [6]:
print "Consider the truth tables of (P and negation_P)"
print "Here all the entries in the last column are false"
def truth_table_and(p):
return p and (not p)#Representation of logical AND

print "p\tnegation_p\tp_and_negation_p"
print "---------------------------------------------"
for q in (True,False):#generates the combination of inputs
res=truth_table_and(q)
print q,"\t\t",not q,"\t\t",res

print "Consider the truth tables of (P or negation_P)"
print "Here all the entries in the last column are true "
def truth_table_or(p):
return p or (not p)#Representation of logical OR

print "p\tnegation_p\tp_or_negation_p"
print "----------------------------------------------"
for q in (True,False):#generates the combination of inputs
res=truth_table_or(q)
print q,"\t\t",not q,"\t\t",res

Consider the truth tables of (P and negation_P)
Here all the entries in the last column are false
p	negation_p	p_and_negation_p
---------------------------------------------
True 		False 		False
False 		True 		False
Consider the truth tables of (P or negation_P)
Here all the entries in the last column are true
p	negation_p	p_or_negation_p
----------------------------------------------
True 		False 		True
False 		True 		True


## Example 23:Page 35¶

In [7]:
print "Restaurent 1 says 'Good food is not cheap'"
print "Restaurent 2 says 'Cheap food is not good'"
#Generating prepositions from the given sentences
g='Food is good'
c='Food is cheap'
print "g->negation c means 'Good food is not cheap'"
print "c->negation g means 'Cheap food is not good'"
def g_implies_negation_c(g,c):
if g==True and not(c)==False:# Implementation of logical implication
return 'False'
else:
return 'True'

def c_implies_negation_g(g,c):
if c==True and not g==False:# Implementation of logical implication
return 'False'
else:
return 'True'
print "g\t\tc\t|\t\tnegation_g\t\t\tnegation_c\t\t\tg_implies_negation_c\t\t\tc_implies_negation_g"
print "---------------------------------------------------------------------------------------------------------------------------------------------------------------"
for a in (False,True):#Generate the possible inputs
for b in (False,True):
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)))

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'"

Restaurent 1 says 'Good food is not cheap'
Restaurent 2 says 'Cheap food is not good'
g->negation c means 'Good food is not cheap'
c->negation g means 'Cheap food is not good'
g		c	|		negation_g			negation_c			g_implies_negation_c			c_implies_negation_g
---------------------------------------------------------------------------------------------------------------------------------------------------------------
False     False		|                True                          True                               True                                    True
False      True		|                True                         False                               True                                    True
True     False		|               False                          True                               True                                    True
True      True		|               False                         False                              False                                   False
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'


## Example 24:Page 35¶

In [10]:
def implication(p,q,r,s):#Implementation of logical implicaion
part1=((p and q) or (p and r) )
if part1==True and s==False:
return 'False'
else:
return 'True'
def equivalent(p,q,r,s):#Implementation of logical expression
return (((not p) or((not q) and (not r)))or s)
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)"
print "--------------------------------------------------------------------------------------------------------------------------------------"
for a in (False,True):
for b in (False,True):
for c in (False,True):
for d in (False,True):#Genetates all possible combinations of inputs
print ("%8s%8s%10s%15s|%35s%35s" %(a,b,c,d,implication(a,b,c,d),equivalent(a,b,c,d)))

print "Therefore, they are proved to be equivalent"

	p	q	r		s		|((p and q)or(p and q))->s	((negation_p or(negation_q and negation_r))or s)
--------------------------------------------------------------------------------------------------------------------------------------
False   False     False          False|                               True                               True
False   False     False           True|                               True                               True
False   False      True          False|                               True                               True
False   False      True           True|                               True                               True
False    True     False          False|                               True                               True
False    True     False           True|                               True                               True
False    True      True          False|                               True                               True
False    True      True           True|                               True                               True
True   False     False          False|                               True                               True
True   False     False           True|                               True                               True
True   False      True          False|                              False                              False
True   False      True           True|                               True                               True
True    True     False          False|                              False                              False
True    True     False           True|                               True                               True
True    True      True          False|                              False                              False
True    True      True           True|                               True                               True
Therefore, they are proved to be equivalent


## Example 55:Page 55¶

In [11]:
print "EUCLIDEAN ALGORITHM"
def GCD(n,m):#Euclidean algorithm to compute GCD
if n>=m and (n%m==0):
return m
else:
return GCD(m,n%m)
print "GCD(25,6) by Euclidean algorithm =",GCD(25,6),

EUCLIDEAN ALGORITHM
GCD(25,6) by Euclidean algorithm = 1


## Example 56:Page 55¶

In [12]:
print "EUCLIDEAN ALGORITHM"
def GCD(n,m):#Euclidean algorithm to compute GCD
if n>=m and (n%m==0):
return m
else:
return GCD(m,n%m)
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
print "\nGCD(26,2) by Euclidean algorithm =",GCD(26,2),
print "\nGCD(28,8) by Euclidean algorithm =",GCD(28,8),

EUCLIDEAN ALGORITHM
GCD(18,4) by Euclidean algorithm = 2
GCD(26,2) by Euclidean algorithm = 2
GCD(28,8) by Euclidean algorithm = 4