I am working on a question for an assignment and I am to declare a clause in Conjunctive Normal Form that says exactly one of three predicates is true. Or given a bit of context - given three suspects and exactly one is guilty.

My first attempt to capture this in FOL (where A, B, and C are constants) Guilty$(A) \lor \text{Guilty}(B) \lor \text{Guilty}(C)$ but I do not think that this restricts to exactly one.

Attempts to better capture as only one can be guilty is Guilty$(x) \land \lnot \text{Guilty}(y) \land \lnot \text{Guilty}(z)$ thought I do not think this is quite right either as it maybe wouldn't play nice when using resolution proofs?

I know I mentioned this is for homework but this an isolated clause - the actual question is to write an answer extraction proof which I am not asking about as I want to figure it out on my own but this clause is causing a bit of trouble with that.

Thanks in advance.

  • $\begingroup$ I think you want to find the CNF of :\begin{align} &(\text{Guilty}(x)\land\neg\text{Guilty}(y)\land\neg\text{Guilty}(z))\\ &\lor(\neg\text{Guilty}(x)\land\text{Guilty}(y)\land\neg\text{Guilty}(z))\\ &\lor(\neg\text{Guilty}(x)\land\neg\text{Guilty}(y)\land\text{Guilty}(z))\\ \end{align} $\endgroup$ – Manx Nov 22 '19 at 4:53
  • $\begingroup$ Ah, I see. I am not sure how this would work within a resolution proof though? $\endgroup$ – Mason Baran Nov 22 '19 at 4:56
  • $\begingroup$ you want to convert it from DNF to CNF with a resolution proof $?$ $\endgroup$ – Manx Nov 22 '19 at 5:06
  • $\begingroup$ @MasonBaran If you are satisfied with your answer, then please click the green check to close the post. Thanks! $\endgroup$ – RyRy the Fly Guy Nov 25 '19 at 1:11

If you prefer a more systematic approach, the CNF of a statement can be found easily with the following 3 steps:

$1.$ Negate the statement.

$2.$ Construct the DNF of the negated statement.

$3.$ Negate the statement again (once it is in DNF), and apply DeMorgan's Laws.

An example below...

Given propositions $G(a),G(b),$ and $G(c)$, consider each possible scenario:

scenario $1$: $G(a)$ is true while $G(b),G(c)$ are false

scenario $2$: $G(b)$ is true while $G(a),G(c)$ are false

scenario $3$: $G(c)$ is true while $G(a),G(b)$ are false

Now we can translate this rather intuitively into DNF as follows:

$(G(a) \wedge \neg G(b) \wedge \neg G(c)) \vee (G(b) \wedge \neg G(a) \wedge \neg G(c)) \vee (G(c) \wedge \neg G(a) \wedge \neg G(b))$

But we have a problem here: we have our statement in DNF, but what we really want is the DNF of the negation. So, let's begin step $1$ above by negating the statement and then use DeMorgan's Law to find...

$\neg \bigg[ (G(a) \wedge \neg G(b) \wedge \neg G(c)) \vee (G(b) \wedge \neg G(a) \wedge \neg G(c)) \vee (G(c) \wedge \neg G(a) \wedge \neg G(b)) \bigg]$

$\Leftrightarrow \bigg[ \neg G(a) \vee G(b) \vee G(c) \bigg] \wedge \bigg[ \neg G(b) \vee G(a) \vee G(c) \bigg] \wedge \bigg[ \neg G(c) \vee G(a) \vee G(b) \bigg]$

We now have the negated statement in CNF. My suggestion is to convert this into DNF by applying the distribution law numerous times and then simplifying with other applicable equivalencies. Once you have done this, you have completed step $2$, and you may complete the final step - step $3$ above - rather straightforwardly.


Thinking about it more - would the clause (assuming x, y, and z are variables and can be substituted) $Guilty(x) \lor Guilty(y) \lor Guilty(z)$ capture the sentence exactly only one is guilty? Pardon my ignorance, I am quite new to this.

  • $\begingroup$ No. That captures: "at least one is guilty". $~~\vee$ is not exclusive. $\endgroup$ – Graham Kemp Dec 20 '19 at 0:26

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.