This question came up on my Exam Practice sheet. I understand the properties of the relations, but I'm having trouble doing it using strings. I put down my answers to the questions below. I would appreciate it if anybody could confirm or deny (and then explain) my answers and reasoning.
The flip-one-bit relation: define a binary relation R on a set of length-4 bit strings where s1Rs2 if and only if flipping a single bit (0 to 1 / 1 to 0) of s1 produces s2
A) Give an example of two strings s1 and s2 such that s1 R s2 holds.
s1 = 1001 , s2 = 1000
B) Give an example of two strings such that s1 R s2 does not hold.
s1 = 1101 , s2 = 1010
C) Is R reflexive? Explain.
No because s1Rs1 is false.
D) Is R symmetric? Explain.
Yes because s1Rs2 is true and s2Rs1 is also true.
E) Is R anti-symmetric? Explain.
No, because even though s1Rs2 is true and s2Rs1 is true s1 != s2
F) Is R transitive? Explain.
No, example:
s1Rs2 = (1001)R(1000) is true , s2Rs3 = (1000)R(1100) is true, s1Rs3 = (1001)R(1100) is false.
G) Is R an equivalence relation? Explain
No, it is not transitive.
H) Is R a partial order? Explain.
No, it is not reflexive or transitive.