0
$\begingroup$

For those who commented on my previous questions, sorry for the lack of information and explanation. Clearly I did not do a good job of explaining myself so I deleted the question and hope this one goes better.

EDIT: here is what I have so far, can anyone tell me if it is right/wrong? http://www.box.net/shared/static/hrv9rh7ukt.jpg

I know how to perform standard tree method satisfiable tests but this question I am having trouble with because it has to do with elections.

Question:

Use the tree method to determine whether or not the following set of sentences is statisfialbe. If so, specify a satisfying case for its atomic sentences (ie aRjb, dRic, bRja, and cPid).

{bRja $\rightarrow$ dRic, dRic $\rightarrow$ $\neg$cPid, dRic $\rightarrow$ aRjb, $\neg$dRic $\rightarrow$ cPid, cPid $\rightarrow$ bRja, aRjb $\rightarrow$ cPid}

I think the format of the sentences is standard nomenclature but if it is not, ill will do my best to explain it. P refers to Social Preternce while R refers to Rule.

UPDATE:

I set the following

A = aRjb

B = bRja

C = cPid

D = dRic

So then the tree looks like:

  • $B \lor D$
  • $D \lor \neg C$
  • $D \lor A$
  • $D \lor C$
  • $C \lor B$
  • $A \lor C$

Maybe its because I haven't done even standard tree methods in a while but can anyone help me on how to check if it is satisfiable?

EDIT UPDATE:

bPia $\rightarrow$ cPia

aPic $\rightarrow$ (aPib $\lor$ bPic)

Conc, ($\neg$aPib $\land$ $\neg$bPia) $\land$ ($\neg$aPic $\land$ $\neg$cPia) $\rightarrow$ ($\neg$aPic $\land$ $\neg$cPia)

Can I solve it like the rest by substituting each "clause" with a letter?

So I would set bPia to B1, bPic to B2, cPia to B1, aPib to A1, aPic to A2, and solve like a normal tree?

  • 0
    Hi eric -- glad to see you haven't given up yet :-) Thanks for making more of an effort this time to explain what you're talking about. I don't know the format of the sentences (which may or may not indicate that it's not "standard nomenclature" :-), but I don't think it's relevant, since they're referred to as "atomic" in the question, so if I understand correctly this is just a logic question and one doesn't have to know about any of the election stuff to answer it?2011-04-05
  • 0
    Thanks, @"joriki. I believe this is simply a logic question however I think the format would be considered an election style because cPid means i prefers c to d.2011-04-05
  • 0
    @eric: You says you know how to perform standard tree-method satisfiability tests, and you agree that this is simply a logic question. Then you should explain what's preventing you from applying the standard method that you know.2011-04-05
  • 0
    @eric: In case the problem is that these sentences are not in the form of disjunctive clauses, note that $A \rightarrow B$ is equivalent to $\neg A \lor B$.2011-04-05
  • 0
    well i'm not 100% sure it is purely a logic question. I don't see how I would apply the normal logic rules to such format as cPid, which means i would prefer c to d.2011-04-05
  • 0
    @eric: The fact that it says "atomic sentences (i.e. aRjb, dRic, bRja, and cPid)" seems to indicate that you're not supposed to worry about the actual meaning of these sentences but regard them as atomic, i.e. literals that you can individually choose to be true or false in order to satisfy the set of sentences.2011-04-05
  • 0
    @joriki, exactly, that is why I am confused.2011-04-05
  • 0
    @eric: It might help to take a look at http://en.wikipedia.org/wiki/Atomic_sentence.2011-04-05
  • 0
    I reread the question and I think the atomic reference is kinda a second question. Like if its satisfiable, then pretend each statement is atomic and determine a satisfying case.2011-04-05
  • 0
    @eric: If what you wrote isn't the original question, then it's hard to tell. I suggest you copy the question as written. More generally speaking, it seems that again you've taken part of a question out of a wider context and assumed that people here would be able to correctly guess the context. Or perhaps you're not aware of how much things depend on context? I think you'll find that if you pay more attention to these things, you won't have such a hard time getting help.2011-04-05
  • 0
    what i put is the original question, in full.2011-04-05
  • 0
    lets say that they are indeed atomic, so how would i perform the truth table since there is no conclusion to set to negative. Do I set them all to negative then go from there?2011-04-05
  • 0
    @eric: Sorry, I misunderstood your statement about rereading the question. About the method: You should perhaps give a reference to the method you're trying to apply. I was thinking of this method: http://www.computational-logic.org/iccl/master/lectures/summer07/sat/slides/semantictrees.pdf, and you don't need a truth table or a conclusion for that; all you need to know is how to convert the implications into disjunctive clauses, which I wrote above.2011-04-05
  • 0
    yeah ok thanks. so i'm going to convert from implications to disjunctive clauses then use the tree method to check for validity. correct?2011-04-05
  • 0
    I think so, yes -- as far as I understand the question, that's what I'd do. (Assuming you meant "check for satisfiability" instead of "check for validity" -- being more precise also helps prevent misunderstandings and complications.)2011-04-05
  • 0
    Also, do you have more info or a link on the conversion process. Something that lists all the formulas for converting implications to conjunctions2011-04-05
  • 0
    You need to convert them to disjunctions, not conjunctions. All you need is what I wrote in the comment above -- that turns each implication into a disjunctive clause.2011-04-05
  • 0
    yes, you are correct. i will try this once i wake up and let you know how it went, thanks.2011-04-05
  • 0
    @Joriki, I have updated original question. I have converted to disjunctions and simplified by using letters but now am stuck with the most basic part of the problem, to check if it is satisfiable.2011-04-05
  • 0
    @eric: Hi eric -- hope you had a good sleep. I posted a link above to an explanation of the tree method. If you say which part of it you don't understand, I think that will be more efficient than if I explain the entire method from scratch.2011-04-05
  • 0
    Dear Joriki, I tried attempting the tree but I think I am doing it wrong cause I don't see why it would end up so big. Here is a picture I took showing my work, please let me know what you think. Thanks. http://www.box.net/shared/static/hrv9rh7ukt.jpg2011-04-06
  • 0
    Ok, so I solved it properly, I closed all the branches. The question says, "If so [satisfiable], specify a satisfying case for its atomic sentences (ie. aRjb, dRic, bRja, and cPid)." What does this mean though? I'm not sure how to do this...2011-04-06
  • 0
    If you closed all the branches, that means this set of sentences is not satisfiable, so you don't have to worry about the "if so" part -- by definition, you could only specify a satisfying case if the set turned out to be satisfiable.2011-04-06
  • 0
    By the way, your result is correct. You can also see that the set of sentences is not satisfiable like this: It contains a cycle of implications $A\rightarrow B\rightarrow C\rightarrow D \rightarrow A$, so the atomic sentences would all have to have the same truth value -- but then it's not possible to satisfy the remaining two implications, $D\rightarrow \neg C$ and $\neg D\rightarrow C$, which force $C$ and $D$ to have opposite truth values.2011-04-06
  • 0
    Thanks, jokriki, you've been a great help. Can you please check this truth tree I am doing? I think I have completed it correctly but want to be sure. http://www.box.net/shared/static/5odobvruoq.jpg2011-04-06
  • 0
    If you don't mind, could you please look at the work I did in that link? Thanks.2011-04-06
  • 0
    @eric: I don't have the time right now; I'll try to take a look later in the day.2011-04-06
  • 0
    @eric: Yes, the truth tree looks OK. The image doesn't contain the conclusions you draw from it, though; just the tree itself.2011-04-06
  • 0
    Ok, thanks. So unlike the last tree, this one is still open, so I assume it is satisfiable. In this case, what conclusions can I safely draw from the open branches?2011-04-06
  • 0
    @eric: Every open branch gives you an assignment that satisfies the set of clauses. For instance, the left-most branch gives you S false, P false, M false, I true, E true -- the fact that D doesn't occur in that branch means that you can choose D either way to complete the assignment (i.e. this branch gives you two assignments that satisfy the clauses). Some of the assignments you get in this way for different branches will be the same. The set of assignments you obtain in the end is the set of all possible assignments that satisfy the clauses.2011-04-06
  • 0
    Thanks Joriki, that makes sense, but just to clarify, should there be two E true? Or do we not count the first E true that begins the tree?2011-04-06
  • 0
    @eric: Two E's wouldn't make sense. It's not a question of counting. E is an atom that you can assign either the value "true" or the value "false". Assigning it the value "true" twice wouldn't make sense. E appearing in the branch merely shows that you can't assign "false" to E; if it appears twice, you just have two identical conditions preventing the assignment E -> false, but not two assignments E -> true.2011-04-06
  • 0
    Ok, that makes perfect sense to me. If you want you can just post something as an answer to the question so I can mark it as accepted for you. Thanks.2011-04-06

1 Answers 1

1

It is apparent from looking at the formulas listed in the question:

  • $B \lor D$
  • $D \lor \neg C$
  • $D \lor A$
  • $D \lor C$
  • $C \lor B$
  • $A \lor C$

that making $A, B, C, D$ all true is a satisfying assignment.