1

I was given a couple of proofs to work out like the one stated in my question. While I have successfully managed to prove all the others, this one has me stumped:

Show that (B and (A implies B)) is equivalent to B

My first steps were to transform the implication via material implication and then apply various double negations to the subterms but I just can't get rid of the A term.

Basically I am trying to get rid of the A term by somehow getting to (A and not A) or (A or not A) which I could cancel out in a conjunction or disjunction.

I have the feeling I am missing the forest for the trees, so I would be thankful for any pointers. Maybe some transformation rules I should take a closer look at.

The transformations we are allowed to use can be found at the bottom of the following site: http://www.millersville.edu/~bikenaga/math-proof/truth-tables/truth-tables.html

Edit: should have clarified we cannot use truth tables or conditional proofs.

André Berg
  • 21
  • 1
    Consider two cases: B is true and B is false. Or, to make things slightly harder, consider these two cases instead: A is true and A is false. –  Oct 15 '14 at 22:24
  • I don't see a list of transformation rules there, just a list of (abbreviations) for tautologies. – Doug Spoonwood Oct 15 '14 at 22:25
  • Apologies, the nomenclature is still a bit new to me. We are to apply the given tautologies to show the equivalence of the left and right hand side. We are not allowed to use truth tables as proof. – André Berg Oct 15 '14 at 22:43
  • Can you use conditional proof? I see the instructor who posted these notes mentions conditional proof in his homework problems. – Doug Spoonwood Oct 15 '14 at 22:56
  • 1
    No we cannot. We have to transform one or the other side of the equivalence expression until it matches the other side. We cannot suppose anything initially.

    It's a different instructor. We were just given that site to have some additional tautologies available than what was covered in the first lecture (in case we get stuck).

     – André Berg Oct 15 '14 at 23:10
  • From the long exchange of comments below, it is clear that the logical equivalences list in the site is lacking of the two Identity laws (see here) : $p \land T \leftrightarrow p$ and $p \lor F \leftrightarrow p$. They must be put in use with Excluded Middle as $T$ and Contradiction as $F$; otherwise, these two tautology are useless, because we are not able to substitute them in any equivalence... – Mauro ALLEGRANZA Oct 16 '14 at 15:44
  • 1
    We just had our guided excercises today and our instructor used both the Idempotent and Identity laws (sort of implying they are so basic to not be needing any further explanation) while showing a related equivalence proof. Oh well, in any case thanks for that handy PDF. Unfortunately I don't have the reputation to upvote your comment. – André Berg Oct 16 '14 at 21:10

3 Answers3

2

Alternative proof:

$\implies$

  1. $B\land [A\implies B]$ (Premise)

  2. $B$ (from 1)

  3. $B\land [A\implies B]\implies B$ (Conclusion 1, 2)

$\Longleftarrow$

  1. $B$ (Premise)

  2. $A\implies B$ (from 4)

  3. $B\land [A\implies B ]$ (from 4, 5)

  4. $B\implies B\land [A\implies B ]$ (Conlcusion 4, 6)

$\iff$

  1. $B\land [A\implies B]\iff B$ (from 3, 7)
Dan Christensen
  • 14,529
0

$$ b \wedge (\neg a \vee b) \equiv b \wedge \neg a \vee b \wedge b \equiv b \wedge \neg a \vee b \equiv b\wedge(\neg a \vee 1) \equiv b$$

  • Are you sure about your first step? Don't you have to distribute the first b across the parentheses? I realize you'll just get b V b (which is b), but it looks like you just removed the parentheses, so it's unclear what logic rule you were using. –  Oct 15 '14 at 22:23
  • @barrycarter that's what I did. –  Oct 15 '14 at 22:24
  • he did distribute, noticeable as he gets "b and b" not "b or b". – André Berg Oct 15 '14 at 22:26
  • Hmmm... you still need parentheses (and did you just edit your answer after my comment? ) –  Oct 15 '14 at 22:28
  • You commented after I edited I believe. Also, while parentheses may make it neater, they are not required. –  Oct 15 '14 at 22:30
  • Chantry Cargill, thank you for your illuminating the steps. Your step before the last that's basically how far I got in my better attempt. I don't quite understand how you get to (B and (not A or 1)) next. Is there a name for this tautology? – André Berg Oct 15 '14 at 22:30
  • @AndyBurg I reversed distribution of b. –  Oct 15 '14 at 22:31
  • @AndyBurg There is no such tautology. This answer isn't correct. – Doug Spoonwood Oct 15 '14 at 22:31
  • What do you mean it's not correct? If you can distribute b you can undistribite it. –  Oct 15 '14 at 22:33
  • @DougSpoonwood Care to explain rather than simply downvoting? Because $b \wedge (\neg a \vee 1) \equiv b\wedge \neg a \vee b$ is definitely valid. –  Oct 15 '14 at 22:41
  • well if we distribute b in the left hand side back we get (b and not a) or (b and 1) which would indeed be equivalent to (b and not a or b). I just wasn't aware of this undistributing leaving the 1 behind. – André Berg Oct 15 '14 at 22:47
  • @ChantryCargill So far as I can tell in this context, "1" could mean "false". Thus, your tautology is not valid here. Sure, if "1" means "true" your tautology works. But note that there is no symbol for true in his list of tautologies. So how did you use his tautologies to get that result? – Doug Spoonwood Oct 15 '14 at 22:49
  • @DougSpoonwood I see. So you're being purposefully anal about the way that I format. A very common form of writing true uses the number 1 in a lot of literature. Coming from a computer science major, it is my preferred way of writing true, so I used it in my explanation. Would you like me to swap it with true, or is this sufficient? –  Oct 15 '14 at 22:52
  • @AndyBurg Yes. $1 \wedge b$ is identical to $b$, so if you are to distribute out $b$, you are left with $1$. –  Oct 15 '14 at 22:52
  • @ChantryCargill You only responded to the first part of my comment. There is no "1" or any symbol for "truth" in his list of tautologies. So, you didn't get your result according to what you were allowed to use. And you can't replace any letter by "1" as you did. – Doug Spoonwood Oct 15 '14 at 22:55
  • that's probably on me not being thorough enough explaining the context. Indeed it is from a C.S. curriculum of which we had the first lecture yesterday and we also used 0 for false and 1 for true. – André Berg Oct 15 '14 at 22:57
  • @DougSpoonwood 1 is commonly used to represent true. I kind of see what you mean in an overly pedantic way, but it is a moot point, especially when the goal is to communicate mathematics to the OP, not you. I'm getting sufficiently annoyed at this point, so I'm going to leave the discussion here. –  Oct 15 '14 at 22:57
  • I am going to accept it as an answer now that I have understood how the undistributing works. Thanks to you both. – André Berg Oct 15 '14 at 22:59
  • 2
    @ChantryCargill In a formal system, you can only use what rules have gotten specified or what can get derived from the other rules and axioms given. How do you get to your formula with the "1" in it using what he's indicated as permissible? – Doug Spoonwood Oct 15 '14 at 22:59
0

Hint: Use a tautology table: http://en.wikipedia.org/wiki/Tautology_(logic)

davd
  • 312
  • 1
  • 2
  • 8