How many symmetric relations are there on A

Assignment Help Theory of Computation

Reference no: EM131859089

Problem

1. Suppose A is a set having n elements.

a. How many relations are there on A?

b. How many reflexive relations are there on A?

c. How many symmetric relations are there on A?

d. How many relations are there on A that are both reflexive and symmetric?

2. Suppose R is a relation on a nonempty set A.

a. Define R' = R ∪ {(x, y) | yRx}. Show that Rs is symmetric and is the smallest symmetric relation on A containing R (i.e., for any symmetric relation R₁ with R ⊆ R₁, R' ⊆ R₁.

b. Define Rt to be the intersection of all transitive relations on A containing R. Show that Rt is transitive and is the smallest transitive relation on A containing R

c. Let equal to the set Rt in part R'' = R ∪ {(x, y) | ∃z (xRz and zRy} equal to the aet Rt in part

(b)? Either prove that it is, or give an example in which it is not. The relations Rs and Rt are called the symmetric closure and transitive closure of R, respectively.

Reference no: EM131859089

Questions Cloud

Calculate the total time to produce a batch : Calculate the total time it takes to produce a batch of 20 units using Anderson's traditional departmental structure. minutes

What is the cost of a chase strategy : Suppose management sets the level of regular workers for the year equal to the average demand and subcontracts out the rest. What is the cost of this strategy?

Contemporary thinking about sentencing : These issues influence contemporary thinking about sentencing. Please discuss, and distinguish between, each of the 5 major sentencing philosophies.

Spite of examples of wrongful convictions : Does it matter? Should the death penalty continue in spite of examples of wrongful convictions?

How many symmetric relations are there on A : How many relations are there on A? How many reflexive relations are there on A? How many symmetric relations are there on A?

Explain the manufacturers average inventory level : What is the manufacturer's average inventory level? What is the customer's average inventory level?

Discuss the techniques of compositional analysis : A contemporary response to Picasso's Guernica (1937) As we are beginning to see in class, images create in other times and places can still be understood.

What would you do as a hospital ceo to keep your patient : Many Americans are now traveling outside of the U. S. for elective medical procedures. What does this mean in terms of service area competitor analysis?

Disarm the negative responses of anger : Recite each stress-response state so the interrogator can take the actions necessary to disarm the four negative

User Account

All Pages