0
$\begingroup$

I have following noted in my notebook:

  1. Transposition theorem (I hope thats what its called)
    $(A\wedge B)\vee (\neg A\wedge C)=(A\vee C)\wedge(\neg A\vee B)$
  2. Consensus rule for transposition theorem $(A\wedge B)\vee (\neg A\wedge C)\vee (B\wedge C)=(A\wedge B)\vee(\neg A\wedge C)$
  3. Resolution rule
    $(A\vee C)\wedge(\neg A\vee B)\rightarrow (B\vee C)$

Does this imply following?

a. From 2: $((A\wedge B)\vee(\neg A\wedge C))\rightarrow (B\wedge C)$
b. From 1 and 3: $(A\wedge B)\vee(\neg A\wedge C)\rightarrow (B\vee C)$

Its seems that these are obvious, however no book says states them explicitly. So, just confirming.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Doesn't $A=T,B=T,C=F$ contradict (a)? Maybe a typo since the LHS of (a) and (b) are the same? $\endgroup$ – Shuri2060 Jul 22 '17 at 15:03
  • $\begingroup$ Please let me use boolean algebra notation LHS=TT+FT=T and RHS=(T+F)(F+T)=T. Isnt it same? Prepared logic table for LHS on wolframalpha. Not able to prepare same for RHS. $\endgroup$ – anir123 Jul 22 '17 at 15:07
  • $\begingroup$ The RHS of (a) is false with the example I gave? $\endgroup$ – Shuri2060 Jul 22 '17 at 15:08
  • $\begingroup$ Resolution and consensus (in the propositional context) denote the same theorem. @Shuri2060 the RHS is in CNF. Just apply distributivity. $\endgroup$ – Fabio Somenzi Jul 22 '17 at 15:09
  • $\begingroup$ @FabioSomenzi I'm confused - we have $T\implies F$ with the example for (a)? (ignore the previous comment on (b) - I misread it) $\endgroup$ – Shuri2060 Jul 22 '17 at 15:16
0
$\begingroup$

a) Statement: $(A\wedge B)\vee (\neg A\wedge C)\vee (B\wedge C)\Rightarrow (A\wedge B)\vee(\neg A\wedge C)\rightarrow (B\wedge C)$

Proof (of not being the case): Let's do this with a truth table, I will just use the shortest formula.

\begin{array}{ccc|cccc} A & B & C & A\land B & \neg A \land C & B\land C\\ 1 &1&1 &1&0 &1\\ 1 &1&0 &1&0 &0\\ 1 &0&1 &0&0 &0\\ 1 &0&0 &0&0 &0\\ 0 &1&1 &0 &1&1\\ 0 &1&0 &0&0&0\\ 0 &0&1 &0 &1&0\\ 0 &0&0 &0 &0 &0\\ \end{array}

It would require more space and time to do the complete table recursively one by one. So instead at this point we can conclude that whenever column 4 or 5 has a "1" so should column 6 (definition of implication). So the implication does not hold for the case, A=T, B=T, C=F for example. The statement is false.

b) Statement: $(A\wedge B)\vee(\neg A\wedge C)\rightarrow (B\vee C)$

Proof:

\begin{array}{ccc|cccc} A & B & C & (A\land B) \lor (\neg A \land C) & B\lor C\\ 1 &1&1 &1&1 \\ 1 &1&0 &1&1 \\ 1 &0&1 &0&1 \\ 1 &0&0 &0&0 \\ 0 &1&1 &1&1\\ 0 &1&0 &0&1\\ 0 &0&1 &1 &1\\ 0 &0&0 &0 &0\\ \end{array}

So this is correct as whenever 4th column has a 1, so does 5th.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

a) does not follow from 2), and a) is in fact not valid

If a) would be valid, then we would have:

$((A\wedge B)\vee (\neg A\wedge C))\color{red}\land (B\wedge C)=(A\wedge B)\vee(\neg A\wedge C)$

but that is not what 2) says.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ If a) would be valid, we would have $\neg((A\wedge B)\vee (\neg A\wedge C))\color{red}\vee (B\wedge C)=(A\wedge B)\vee(\neg A\wedge C)$ as per the definition of implication: $x\rightarrow y=\neg x \vee y$, right? $\endgroup$ – anir123 Jul 22 '17 at 15:41
  • $\begingroup$ Sorry. I confused (a) and (1). Clearly, (a) is not valid. As noted in my comment to the OP, the implication goes in the other direction. $\endgroup$ – Fabio Somenzi Jul 22 '17 at 15:49
  • $\begingroup$ @Mahesha999 Well, given that a) is not valid, everything would follow if it were, so I probably didn't put that very well. What I meant is just that you cannot infer $B \land C$ from $(A \land B) \lor (\neg A \land C)$, for if you could, then you would be able to get the conjunction as I indicated, but all you can get is the much weaker disjunction. $\endgroup$ – Bram28 Jul 22 '17 at 18:43

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.