First-order logic : repesenting graphs

  1. How can we write a sentence in first-order logic that says that a graph has exactly 6 edges? i.e. G= (V,E) (logically implies) iff |E|=6 :eek:
     
  2. jcsd
  3. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Start simple. Replace 6 with 0. Can you figure out how?
    Replace 6 with 1. Can you figure out how?
    Replace 6 with 2. Can you figure out how?
     
  4. Actually no. I'm having trouble to represent the number of edges. I can express that there is an edge in a graph:

    There_Exists_x There_exists_y edge(x,y).

    but how can I express that there are n edges in the graph.

    Any ideas ?
     
  5. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Hrm. Your variables, then, must range over the vertices of the graph, and you assume that there is exactly one edge between a given pair of vertices?


    Anyways, so you've managed to solve (the complement of) my first problem: how to express that a graph has no edges.


    So let's move onto the next: how to express that a graph has a single edge... have you ever expressed before the notion that there is one (and only one) object that satisfies a given property?
     
  6. Im sorry. I dont know how to. I'm not so good at this.Any hints?
     
  7. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    You've never had to express something like:

    "This equation has a unique solution"?
     
  8. Ok... So, what does this have to do with that?
     
  9. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    You want to say "This graph has a unique edge". :tongue2:
     
  10. Ok. But a certain number of edges. I'm sorry if Im not getting what u mean. I'm not a mathematician by any means. Can u give me a simple sentence ?just to help me start and I will build up on it.
     
  11. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm saying that you should fully tackle the question of expressing the statement "This graph has exactly one edge" before moving on to the tougher statement "This graph has exactly six edges".


    You've already given a sample statement: You encoded: "This graph has at least one edge" as:

    Ex Ey: edge(x, y)

    Maybe you should explicitly write out the solution to my first exercise before moving onto the next: how can you encode: "This graph has zero edges"?
     
  12. Ex Ey: ~edge(x,y)

    Is this what u mean ?
     
  13. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    That's not correct. For example, take this graph:

    A B---C

    This graph has three vertices and one edge.

    Your statement "Ex Ey: ~edge(x, y)" is true for this graph -- for example, I can select x=A and y=B, and then "~edge(A, B)" is a true statement. However, the graph obviously does not have zero edges!


    In English, your statement says: "There exists a pair of vertices that don't have an edge between them". Do you see why?
     
  14. Yes I do. Maybe i can use

    ForAll_x ForAll_y : ~edge(x, y)

    ?????
     
  15. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, that one's exactly right. It says "For any pair of vertices, there does not exist an edge between them."


    Now onto exactly one edge...

    You already know how to say "This graph has at least one edge".


    I suggested considering the statement "This equation has a unique solution" because the expression of this statement in logic involves a useful trick that applies directly here...

    Another way to think about it is this: can you say "This graph does not have two distinct edges"?

    Or what about it's complement? "This graph has at least two distinct edges"
     
  16. I have no clue. :cry: Do u have any hints on how to express that it has 2 distinct edges ?
     
    Last edited: Apr 22, 2005
  17. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Okay, suppose you know that your graph has only one edge.

    I take two sheets of paper. On the first sheet of paper, I write down the name of an edge in your graph. On the second sheet of paper, I write down the name of an edge in your graph.

    What can you tell me about the two sheets of paper?
     
  18. they contain the same edge, since my graph has only one edge

    Ex Ey edge(x,y) , x=y

    ????
     
    Last edited: Apr 22, 2005
  19. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Bingo -- and as you realize, what you need to do is to figure out how to encode that into your statement!

    In other words, if we've written down the names of two edges, the names should be the same.
     
  20. So is this a correct statement in first-order logic

    Ex Ey edge(x,y) , x=y
     
  21. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Nope. That statement says:

    There exists two vertices such that there is an edge between them. Oh, and those two vertices happen to be equal!

    (Or, in less verbose language, it's saying there's a vertex with a loop on it)
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook
Similar discussions for: First-order logic : repesenting graphs
Loading...