0
$\begingroup$

There were 3 people J, P, A. Only 2 people brought gifts to the party. If J brought a gift to the party, proof that P or A did not brought the gift.

What I can think about this sentence is: $ J, P \rightarrow ¬A, A \rightarrow ¬P \vDash ¬A \lor ¬P $

But with these premises and conclusion, I can't proof it in semantic way or proof theory by applying CNF to derive empty clause. I would like to ask for help that what should be the right premises and conclusion?

Thank you very much for any helps that you may provide.

Updated from suggestions:

$J, ¬(J\land P \land A) \vDash ¬A \lor ¬P $

$J, ¬(J \land (P \land A)) \vDash ¬A \lor ¬P $

$J, ¬J \lor ¬(P \land A) \vDash ¬A \lor ¬P $

$J, ¬J \lor ¬P \lor ¬A \vDash ¬A \lor ¬P $

Apply resolution to derive empty clause.

$J, ¬J \lor ¬P \lor ¬A, ¬(¬A \lor ¬P) \vdash $ Empty Clause

$J, ¬J \lor ¬P \lor ¬A, A \land P \vdash $ Empty Clause

Empty Clause $ \vdash $ Empty Clause

Thank you for all helps.

$\endgroup$
1
  • $\begingroup$ Why can't you solve this by semantics? You have to run through all possible combinations of truth-values for $J, P$ and $A$ and check if whenever all of the premises are True the conclusion is also True. If that's the case, then you've proven the original sentence (the one in natural language), otherwise you have found a counter-example and therefore the original sentence is not valid. $\endgroup$
    – frabala
    Mar 17, 2019 at 16:19

2 Answers 2

Reset to default
1
$\begingroup$

There were 3 people J, P, A. Only 2 people brought gifts to the party. If J brought a gift to the party, proof that P or A did not brought the gift.

We need the following axioms :

1) $J$ --- expressing the fact that "J brought a gift"

2) $\lnot (J \land P \land A)$ --- expressing the fact that "Only 2 people brought gifts", i.e. that ""Not all three...".

Then we have to transform 2) in clause form and apply Resolution.

$\endgroup$
1
  • $\begingroup$ Thank you very much for you help, I updated the solution and got the empty clause now. $\endgroup$
    – Naphatthara P
    Mar 17, 2019 at 15:58
0
$\begingroup$

Can you use the equivalence $A\to B \equiv \neg A \vee B$, to transform the goal $\neg A\vee\neg P$ into $A\to\neg P$?

If you are allowed to do that, things become quite easy afterwards.

$\endgroup$
1
  • $\begingroup$ Thank you very much, I updated the solution from what I understood so far. $\endgroup$
    – Naphatthara P
    Mar 17, 2019 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.