# Inferring certain facts from transposition and resolution rule of propositional logic

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.

• Doesn't $A=T,B=T,C=F$ contradict (a)? Maybe a typo since the LHS of (a) and (b) are the same? Jul 22, 2017 at 15:03
• 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.
– Maha
Jul 22, 2017 at 15:07
• The RHS of (a) is false with the example I gave? Jul 22, 2017 at 15:08
• Resolution and consensus (in the propositional context) denote the same theorem. @Shuri2060 the RHS is in CNF. Just apply distributivity. Jul 22, 2017 at 15:09
• @FabioSomenzi I'm confused - we have $T\implies F$ with the example for (a)? (ignore the previous comment on (b) - I misread it) Jul 22, 2017 at 15:16

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.

• 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?
– Maha
Jul 22, 2017 at 15:41
• 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. Jul 22, 2017 at 15:49
• @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. Jul 22, 2017 at 18:43

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.