<< Chapter < Page Chapter >> Page >

The next two exercises aren't meant to be difficult, but rather to illustrate that, while we've sketched these twoapproaches and suggested they are equivalent, we still need an exact definition.

For the indicator function f x y y x 2 on the domain of (pairs of) natural numbers, write down the set-of-pairs representationfor the corresponding binary relation. It's insightful to give the answer both by listing the elements,possibly with ellipses, and also by using set-builder notation.

In general , for a binary indicator function f , what, exactly, is the corresponding set?

0 0 1 1 2 4 3 9 i i 2 In set-builder notation, this is x y y x 2

In general, for an indicator function f , the correspondingset would be x y f x y (Note that we don't need to write

f x y
; as computer scientists comfortable with Booleansas values, we see this is redundant.)

Got questions? Get instant answers now!

For the relation hasPirate K T R U E on the set of (individual) WaterWorld locations, write down the indicator-function representationfor the corresponding unary relation. In general , how would you write down this translation?

f hasPirate x x K x T x R x U x E .

In general, for a (unary) relation R , f R x x R x R .

Got questions? Get instant answers now!

Since these two formulations of a relation, sets and indicator functions,are so close, we'll often switch between them (a very slight abuse of terminology).

Think about when you write a program that uses the abstract data type Set . Its main operation is elementOf . When might you use an explicit enumeration to encode a set,and when an indicator function? Which would you use for the set of WaterWorld locations?Which for the set of prime numbers?

Functions as relations

Some binary relations have a special property: each element of the domain occurs as the first itemin exactly one tuple. For example, isPlanet Earth Venus Sol Ceres Mars is actually a (unary) function. On the other hand, isTheSquareOf 0 0 1 1 1 -1 4 2 4 -2 9 3 9 -3 is not a function, for two reasons. First, some numbers occur as the first element of multiple pairs. Second, some numbers, like 3 , occurs as the first element of no pairs.

We can generalize this to relations of higher arity, also. This is explored in this exercise and this one .

Binary relations

One subclass of relations are common enough to merit some special discussion: binary relations. These are relations on pairs, like nhbr .

Binary relation notation

Although we introduced relations with prefix notation, e.g., < i j , we'll use the more common infix notation, i j , for well-known arithmetic binary relations.

Binary relations as graphs

In fact, binary relations are common enough that sometimes people use some entirely new vocabulary:A domain with a binary relation can be called vertices with edges between them. Together this is known as a graph . We won't stress these terms right now,as we're not studying graph theory.

Binary relations (graphs) can be depicted visually, by drawing the domain elements (vertices) as dots,and drawing arrows (edges) between related elements.

A binary relation with a whole website devoted to it is

has starred in a movie with
. We'll call this relation hasStarredWith over the domain of actors. Some sample points in this relation:
  • hasStarredWith Ewan McGregor Cameron Diaz , as witnessed by the movie A Life Less Ordinary , 1997.
  • hasStarredWith Cameron Diaz John Cusack , as witnessed by the movie Being John Malkovich , 1999.
You can think of each actor being a
location
, and two actors being
adjacent
to each other if they have ever starred in a movie together;two of these locations, even if not adjacent might have a multi-step path between them.(There is also a shorter path; can you think of it?The (in)famous Kevin Bacon game asks to find a shortest path from one location to thelocation Kevin Bacon. Make a guess, as to the longest shortest path leading from(some obscure) location to Kevin Bacon.)

Some other graphs:

  • Vertices can be tasks, with edges meaning dependencies of what must be done first.
  • In parallel processing, Vertices can be lines of code;there is an edge between two lines if they involve common variables.Finding subsets of vertices with no lines between them represent sets of instructions that can beexecuted in parallel (and thus assigned to different processors.)
  • Word ladders
    seek to transform one word to another by changing one letter at a time, while always remaining a word.For example, a ladder leading from WHITE to SPINE in three steps is:
    • WHITE
    • WHINE
    • SHINE
    • SPINE
    If a solution to such a puzzle corresponds to a path, what do vertices represent?What are edges? Do you think there is a path from any 5-letter word to another?

Questions & Answers

what does the ideal gas law states
Joy Reply
Three charges q_{1}=+3\mu C, q_{2}=+6\mu C and q_{3}=+8\mu C are located at (2,0)m (0,0)m and (0,3) coordinates respectively. Find the magnitude and direction acted upon q_{2} by the two other charges.Draw the correct graphical illustration of the problem above showing the direction of all forces.
Kate Reply
To solve this problem, we need to first find the net force acting on charge q_{2}. The magnitude of the force exerted by q_{1} on q_{2} is given by F=\frac{kq_{1}q_{2}}{r^{2}} where k is the Coulomb constant, q_{1} and q_{2} are the charges of the particles, and r is the distance between them.
Muhammed
What is the direction and net electric force on q_{1}= 5µC located at (0,4)r due to charges q_{2}=7mu located at (0,0)m and q_{3}=3\mu C located at (4,0)m?
Kate Reply
what is the change in momentum of a body?
Eunice Reply
what is a capacitor?
Raymond Reply
Capacitor is a separation of opposite charges using an insulator of very small dimension between them. Capacitor is used for allowing an AC (alternating current) to pass while a DC (direct current) is blocked.
Gautam
A motor travelling at 72km/m on sighting a stop sign applying the breaks such that under constant deaccelerate in the meters of 50 metres what is the magnitude of the accelerate
Maria Reply
please solve
Sharon
8m/s²
Aishat
What is Thermodynamics
Muordit
velocity can be 72 km/h in question. 72 km/h=20 m/s, v^2=2.a.x , 20^2=2.a.50, a=4 m/s^2.
Mehmet
A boat travels due east at a speed of 40meter per seconds across a river flowing due south at 30meter per seconds. what is the resultant speed of the boat
Saheed Reply
50 m/s due south east
Someone
which has a higher temperature, 1cup of boiling water or 1teapot of boiling water which can transfer more heat 1cup of boiling water or 1 teapot of boiling water explain your . answer
Ramon Reply
I believe temperature being an intensive property does not change for any amount of boiling water whereas heat being an extensive property changes with amount/size of the system.
Someone
Scratch that
Someone
temperature for any amount of water to boil at ntp is 100⁰C (it is a state function and and intensive property) and it depends both will give same amount of heat because the surface available for heat transfer is greater in case of the kettle as well as the heat stored in it but if you talk.....
Someone
about the amount of heat stored in the system then in that case since the mass of water in the kettle is greater so more energy is required to raise the temperature b/c more molecules of water are present in the kettle
Someone
definitely of physics
Haryormhidey Reply
how many start and codon
Esrael Reply
what is field
Felix Reply
physics, biology and chemistry this is my Field
ALIYU
field is a region of space under the influence of some physical properties
Collete
what is ogarnic chemistry
WISDOM Reply
determine the slope giving that 3y+ 2x-14=0
WISDOM
Another formula for Acceleration
Belty Reply
a=v/t. a=f/m a
IHUMA
innocent
Adah
pratica A on solution of hydro chloric acid,B is a solution containing 0.5000 mole ofsodium chlorid per dm³,put A in the burret and titrate 20.00 or 25.00cm³ portion of B using melting orange as the indicator. record the deside of your burret tabulate the burret reading and calculate the average volume of acid used?
Nassze Reply
how do lnternal energy measures
Esrael
Two bodies attract each other electrically. Do they both have to be charged? Answer the same question if the bodies repel one another.
JALLAH Reply
No. According to Isac Newtons law. this two bodies maybe you and the wall beside you. Attracting depends on the mass och each body and distance between them.
Dlovan
Are you really asking if two bodies have to be charged to be influenced by Coulombs Law?
Robert
like charges repel while unlike charges atttact
Raymond
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Intro to logic. OpenStax CNX. Jan 29, 2008 Download for free at http://cnx.org/content/col10154/1.20
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Intro to logic' conversation and receive update notifications?

Ask