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.

$\endgroup$
9
  • $\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, 2017 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$
    – Maha
    Jul 22, 2017 at 15:07
  • $\begingroup$ The RHS of (a) is false with the example I gave? $\endgroup$
    – Shuri2060
    Jul 22, 2017 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, 2017 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, 2017 at 15:16

2 Answers 2

Reset to default
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.

$\endgroup$
3
  • $\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$
    – Maha
    Jul 22, 2017 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, 2017 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, 2017 at 18:43
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.

$\endgroup$

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.