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

[ZING14]

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

[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.

[ZING14]

I have got all of them but transitive now... I do not know how to include c in my functions.  Transitive means: If aRb and bRc, then aRc. Here is my reflexive function... How can I change them to make it test for transitive?

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;
    }
}

[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.

[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.

[bradyzk]

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.

[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?

[walla]

@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

[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.

[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.

[bradyzk]

If you use a 2d array then, matrix[i][i] = 1 for all i in the array, is reflexive.

[ZING14]

My new reflexive function :

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; 
  }

[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

[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?

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;
    }
        
}

[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.

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;
	}
}