1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Predicate logic proof

  1. Oct 5, 2008 #1
    I have a question on my assignment that I'm having a great deal of trouble with.

    In this question we will
    consider a simplified model of the “People you may know” application in Facebook. The
    basic idea is that if two people have a common friend, then they may know each other. We
    will also take into account the fact in Facebook the relation “friend” is symmetric, that is,
    if X is a friend of Y , then Y is a friend of X.
    Thus, as a problem description P, we have the following two predicate logic sentences:

    8X8Y [(9Z(friend(X, Z) ^ friend(Z, Y ))) $ may know(X, Y )]
    8X8Y [friend(X, Y ) ! friend(Y,X)]

    Our goal is to show, using resolution refutation, that the following sentence g is implied by P:

    8X8Y [may know(X, Y ) ! may know(Y,X)].

    8 = universal quantifier
    9 = existential quantifier
    $ = biconditional
    ! = implication

    I have been able to derive the following clauses (this is for a logical programming class):

    c1: may_know(X,Y) :- friend(X,T), friend(T,Y)
    c2: friend(X,f(X,Y,T)) :- may_know(X,Y)
    c3: friend(f(X,Y,T),Y) :- may_know(X,Y)
    c4: friend(Y,X) :- friend(X,Y)
    c5: may_know(d,e) :-
    c6: :- may_know(e,d)

    I've attempted linear refutation which won't work. The question goes on to advise that you prove g from p "using your normal, mathematical, reasoning. Then, try to re-create the steps of your proof using resolution on your clauses." This is where I'm stuck, I'm not sure how I can prove g from p using either my clauses or my ordinary mathematical reasoning. Any help with this would be greatly appreciated.
  2. jcsd
  3. Oct 9, 2008 #2
    If X may know Y, then by the first statement, there exists a Z such that X is a friend of Z and Z is a friend of Y. This means, by application of the second statement, that Y is a friend of Z and Z is a friend of X. So by the first statement, Y may know X
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook