# -*- coding: utf-8 -*-
"""
Created on Thu Sep 22 21:45:23 2016
@author: olepsky
"""
#from the lecture notes.
def forall(S, P):
for x in S:
if not P(x):
return False
return True
def product(X, Y):
return {(x,y) for x in X for y in Y}
def relation(R, X):
return R.issubset(product(X, X))
def isReflexive(X, R):
return relation(R,X) and forall(X, lambda x: ((x,x) in R))
# P implies Q could be translated to Python as P<=Q
def isSymmetric(X, R):
return relation(R,X) and forall(X, lambda x: forall(X, lambda y: ((x,y) in R) <= ((y,x) in R)))
def isTransitive(X, R):
return relation(R,X) and forall(X, lambda x: forall(X, lambda y: forall(X, lambda z: ((x,y) in R and (y,z) in R) <= ((x,z) in R))))
def isEquivalence(X, R):
return isSymmetric(X, R) and isReflexive(X, R) and isTransitive(X, R)
C = {'Iceland', 'USA', 'Canada', 'Mexico', 'Australia', 'Norway', 'Sweden', 'Finland'}
D = {('USA', 'Canada'), ('USA', 'Mexico'), ('Norway', 'Sweden'), ('Sweden', 'Finland')}
print (D)
print("D is equivalence relation:", isEquivalence(C,D))
print("D is reflexive:", isReflexive(C,D))
#make D reflexive
S1={(x, x) for x in C}
D=D.union(S1)
print (D)
print("D is reflexive:", isReflexive(C,D))
print("D is equivalence relation:", isEquivalence(C,D))
print("D is symmetric:", isSymmetric(C,D))
#make D symmetric
#S2={(y, x) for y in C for x in C if (x,y) in D}
S2={(y, x) for (x,y) in D}
D=D.union(S2)
print (D)
print("D is symmetric:", isSymmetric(C,D))
print("D is equivalence relation:", isEquivalence(C,D))
print("D is transitive:", isTransitive(C,D))
#make D transitive
S3={(x, z) for x in C for z in C for y in C if ((x,y) in D and (y,z) in D)}
D=D.union(S3)
print (D)
print("D is transitive:", isTransitive(C,D))
print("D is equivalence relation:", isEquivalence(C,D))
#
def quotient(X, R):
return {frozenset({y for y in X if (x,y) in R}) for x in X}
print("C/D=",quotient(C,D))
#X = set(range(1,19))
#R = {(x,y) for x in X for y in X if x % 5 == y % 5}
#print ("R is equivalence relation:",isEquivalence(X,R))
#print (quotient(X,R))
#print ("max number of elements in X s.t. x % 5 == y % 5: ", max({len(x) for x in quotient(X,R)}))
