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.

  • 1
    $\begingroup$ Check your aswer to part G. In part D you correctly concluded that $R$ is symmetric. So the conclusion in part G is correct, but the reason you gave is not. $\endgroup$ – Fabio Somenzi Mar 23 '17 at 2:50
  • $\begingroup$ For C, D, and E you are simply stating the definition and then asserting that R does or does not satisfy it. For the negative cases you can provide a counter-example like you did for F. For D though, you need an actual argument. $\endgroup$ – Derek Elkins Mar 23 '17 at 3:38
  • $\begingroup$ @FabioSomenzi Oops, just changed it to reflect that. $\endgroup$ – RaulT Mar 23 '17 at 4:01
  • $\begingroup$ @DerekElkins Right, I'll provide examples to those. I'm just hoping the logic is right, aka the relations are in fact correct. $\endgroup$ – RaulT Mar 23 '17 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.