# Determining whether the set is reflexive, symmetric, anti symmetric and transtitive

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 11-14-2011
ZING14
Determining whether the set is reflexive, symmetric, anti symmetric and transtitive
I am having trouble finding out how to code this. I understand what each one is and know how to tell by looking but cannot figure out how to create functions to check whether it is either reflexive, symmetric, anti-symmetric, and/or transitive (it can be more than one). Here is the exact problem. Given a set of binary relations, determine whether the set is reflexive, symmetric, anti symmetric and/or transitive. Here are the sets:

0 1 2 3
0 0
1 1
2 2
3 3

x y z
x y
y z
y y
z z

x y z
x x
y z
x y
z y
x z
y y
z x
y x
z z

1 2 3 4 5 6 7 8
1 4
1 7
2 5
2 8
3 6
4 7
5 8
6 6
1 1
2 2
• 11-15-2011
manasij7479
>I understand what each one is and know how to tell by looking but cannot figure out how to create functions to check whether it is either reflexive, symmetric, anti-symmetric, and/or transitive (it can be more than one).

First do it by hand....
Then put the exact same steps into your functions.
• 11-15-2011
ZING14
Transitive??
I have got all of them but transitive now... I do not know how to include c in my functions. &nbsp;Transitive means: If aRb and bRc, then aRc. Here is my reflexive function... How can I change them to make it test for transitive?

Code:

void reflexive(int a[], int sizeOfA, int b[], int sizeOfB){
int i, j;
bool test;
bool hold = true;

for(i = 0; i < sizeOfA; i++)
{
if(hold == true)
{
for(j = 0; j < sizeOfB;)
{
if(b[j]==a[i] && b[j+1]==a[i])
{
hold = true;
break;
}
else
{
hold = false;
j++;
}
}
}
}
if(hold == true)
{
test = true;
cout << "Reflextive - Yes" << endl;
}
else
{
test = false;
cout << "Reflextive - No" << endl;
}
}

• 11-15-2011
walla
why do you have && b[j+1]==a[i]?
I believe the condition of b[j]==a[i] is enough.

Anyway in reflexive the naive way is to check each 2 couples (let's say (a,b) and (b,c)) and then check if there is (a,c) pair).
Of course there are much better ways.
• 11-15-2011
ZING14
@walla- are you stating my reflexive does not work properly? Also, can you help me in the right direction for determining the transitive function? Thanks.
• 11-15-2011
To test if something is transitive you would need to use for loops. In a 2d arrary it would look like this. If M[i][j] = 1, and M[j][k] = 1, then M[i][k] = 1. If thats true it is transitive. Your reflexive is simply i != i for all i.
• 11-15-2011
ZING14
@ bradzk - For my transitive function, your saying to use 3 for loops and pointers? Also, what is M? Your telling to use i,j,k. Also, what do you mean i != i for all i in my reflexive function?
• 11-16-2011
walla
Quote:

Originally Posted by ZING14
@walla- are you stating my reflexive does not work properly? Also, can you help me in the right direction for determining the transitive function? Thanks.

yes.
00
11
22
will give false in your reflexive function
• 11-16-2011
ZING14
@walla - changing it to b[j]==a[i] still comes back false. So implement it by saying if (a,b) and (b,c), look for (a,c)? Can you give pseudo code of what you mean? Thanks.
• 11-16-2011
walla
Don't worry for now about transitive, your reflexive function isn't right.
First of all the definition of reflexive set is that each number x in the area will have (x,x) relation.
So to build an appropriate reflexive function first you need to know all the elements in the area.
Then you will need to check that for each one of them there is a (x,x) relation.
• 11-16-2011
If you use a 2d array then, matrix[i][i] = 1 for all i in the array, is reflexive.
• 11-16-2011
ZING14
My new reflexive function :

Code:

void reflexive(int a[], int sizeOfA, int b[], int sizeOfB)
{
bool hold = true;

for(i = 0; i < sizeOfA && hold; ++i )
{
for( int j = 0; j < sizeOfB && hold; ++j )
{
int elemA = a[i];
int elemB = b[i];

if(a[i] == b[i])
{
hold = true;
break;
}
}
if(hold == false)
{
cout << "Reflexive - No" << endl;
break;
}
}
if(hold == true)
cout << "Reflexive - Yes" << endl;
}

• 11-16-2011
walla
This solution is not good.
1. You don't use j.
2. hold can not get false.
May I suggest to compile and run examples on your function before posting it?
I will suggest these simple examples for a start:

1. (0,0),(1,1) - reflexive
2. (0,0),(1,1),(1,2) - not reflexive
3. (1,2),(2,1),(1,1),(2,2) - reflexive

Hope it helps. Try and error is the best way to learn :)
• 11-16-2011
ZING14
Ok, thank you for being patient with me walla. I believe this is close. I should be getting reflexive for sets 1 and 3. Although, it gave me reflexive for all of them which I know is wrong. Is one of my loops bad?

Code:

void reflexive(int a[], int sizeOfA, int b[], int sizeOfB)
{
bool hold = true;
for(int i = 0; i < sizeOfA; ++i)
{
hold = false;
for(int j = 0; j < sizeOfB; ++j)
{
if(a[i] == b[j])
{
hold = true;
break;
}
}
if(hold = false)
{
cout << "Reflexive - No" << endl;
break;
}
}
if(hold = true)
{
cout << "Reflexive - Yes" << endl;
}

}

• 11-16-2011
ZING14
I've modified it a bit but it wants me to create pointers to the objects a[i] and b[i] I don't know why.

Code:

void reflexive(int a[], int sizeOfA, int b[], int sizeOfB)
{
bool hold = true;
for(int i = 0; i < sizeOfA; ++i)
{
int a = a[i];
int b = b[i];
hold = false;
for(int j = 0; j < sizeOfB; ++j)
{
if(a[j] == b)
if(b[j] == a)
hold = true;
break;
}
if(hold = false)
{
cout << "Reflexive - No" << endl;
break;
}
}
if(hold = true)
{
cout << "Reflexive - Yes" << endl;
}
}

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last