Mathematics for Computer Science

Chapter 4 Mathematical Data Types110

 relational inverse^1.

... and one extra:relational compositionwhich generalizes composition of

functions

a .RıS/ cWWD 9b 2 B:.a S b/AND.b R c/:

In other words,ais related tocinRıSif starting atayou can follow anS

arrow to the start of anRarrow and then follow theRarrow to get toc.^12

Here is one worked example to get you started:

 Search description:The set of pages containing the word “logic”

 Solution expression:M^1 .“logic”/

Find similar solutions for each of the following searches:

(a)The set of pages containing the word “logic” but not the word “predicate”

(b)The set of pages containing the word “set” that have been recommended by
“Meyer”

(c)The set of endorsers who have recommended pages containing the word “al-
gebra”

(d)The relation that relates endorsereand wordwiffehas recommended a page
containingw

(e)The set of pages that have at least one incoming or outgoing link

(f)The relation that relates wordwand pagepiffwappears on a page that links
top

(g)The relation that relates wordwand endorsereiffwappears on a page that
links to a page thaterecommends

(h)The relation that relates pagesp 1 andp 2 iffp 2 can be reached fromp 1 by
following a sequence of exactly 3 links

(^12) Note the reversal ofRandSin the definition; this is to make relational composition work like
function composition. For functions,fıgmeans you applygfirst. That is, if we lethbefıg,
thenh.x/Df.g.x//.