Question
You've probably heard of "Six degrees of Kevin Bacon" -- supposedly every actor can be connected to Kevin Bacon by a chain of no more than 6 movies with overlapping casts. For example. Bela Lugosi can be connected to Kevin Bacon in three hops: Bela Lugosi was in Abbott and Costello Meet Frankenstein (1948) with Vincent Price Vincent Price was in The Raven (1963) with Jack Nicholson Jack Nicholson was in A Few Good Men (1992) with Kevin Bacon I claim that BOB is even more well connected than Kevin Bacon: all actors can be connected to him in 2 or fewer hops -- "two degrees of BOB" Use quantiers and the predicate C(x, y) below to express the "two degrees of BOB" claim. C(x, y): actor x was in the cast of movie y The domains of C are actors (first argument) and movies (second argument), and you can assume that this is understood. Note that BOB is a constant in the domain of actors (and for the the purposes of this exercise, there is only one actor named BOB) In class we discussed ways to express reachability between two locations x and y. The predicate C(x,y)was used to indicate a direct connection from location x to location y and the predicate P(x,y) was used to indicate that there is at least one path (of 1 or more :"hops" as defined by C(x,y)) from x to y . For example, there might not be any direct flights from city A to city B. but you might be able to make the trip by changing planes are one or more intermediate cities). We expressed P(x,y) in terms of C() and P() itself (there is a kind of recursion in there). Now consider a predicate B(x,y) which we want to be true only when there are at least two node (location) disjoint paths from x to y or are directly connected. In other words, there are at least two paths which have no intermediate nodes in common. In the diagram below, is B(e,g) true? Why? is B(e,a) true? Why? Now write a quantified formula expressing the relationship between B(), P() and C(). It should take the form B(x,y) ** Hint (new): An observation is that B(x,y) is FALSE if and only if removing (or making "forbidden " some node z results in y not being reachable from x. In other words removing a single node disconnects x and y. So incorporating a predicate Pj(x,y,z) which is TRUE only when there is a path x-to-y that does not pass through node z (z is forbidden.) Your formula must be true only when the various predicates correspond to the meanings described above. The predicate C(x,y) is a "axiomatic", but the meanings of the other predicates are derived from C().
Explanation / Answer
(exists z[exists x{ C(BOB,x)land C(z,x)}landexists yexists w{C(z,y)land C(w,y)landexists u {C(w,u)land C(Kevin,u)}}])
