22
$\begingroup$

I would like to know if there is a rule to prove this. For example, if I use the distributive law I will get only $(A \lor A) \land (A \lor \neg B)$.

$\endgroup$
  • 2
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Oct 8 '17 at 13:10
  • $\begingroup$ A being true is necessary in both conditions and it's sufficient for the one on the left. $\endgroup$ – Millie Smith Oct 8 '17 at 16:14

11 Answers 11

55
$\begingroup$

I find pictures are great for anything simple enough to use them, which this is.

Rendered diagram

Remember:

AND means the area taken up by both things. So the middle one is what is taken up outside B, but also inside A. Their junction is not counted because it is inside A but not outside B.

OR means it is covered by either one or both. Both of them cover the part of A that is outside B, and the junction is covered by A (first picture) so it is counted too. All in all, you just have A again.

Sorry if this is too simplistic, not sure what level you are at.

$\endgroup$
  • $\begingroup$ For completeness, it could be good to show the case where B and A are disjoint and another case where B is A. $\endgroup$ – Eric Duminil Oct 8 '17 at 17:20
  • 11
    $\begingroup$ @EricDuminil I disagree. The great thing about this Venn diagram work is that it's valid whether or not any of the regions are empty. $\endgroup$ – Mark S. Oct 8 '17 at 19:48
  • 3
    $\begingroup$ +1 to Mark S.'s response. The thing about Venn diagrams, and the reason they're still (I hope!) taught in middle-school math classes, is that they actually work. If you (Eric) are wondering "but what if B and A are disjoint?..." then you haven't yet understood what a Venn diagram is actually representing. It's representing the four logical possibilities as four geometric regions: (A&B) [the middle wedge], (A&~B) [left crescent], (~A&B) [right crescent], and (~A&~B) [the rest of the page]. Coloring them in as Erin did helps us visualize a logical problem as a geometric problem. $\endgroup$ – Quuxplusone Oct 8 '17 at 20:39
  • $\begingroup$ @EricDuminil (intended for anyone reading this in future) if they're disjoint, the middle one will just be A (no part of A in inside B) so you have A or A = A, and if A = B, the middle will be empty (no part of A is outside B) so you'll have A or nothing = A $\endgroup$ – Erin Oct 8 '17 at 21:02
  • 1
    $\begingroup$ @djechlin: I was tired. If A is B, you can ignore both left and right parts. $\endgroup$ – Eric Duminil Oct 9 '17 at 11:31
48
$\begingroup$

There are many ways to see this. One is a truth table. Another is to use the distributive rule: $$ A \lor (A \land \lnot B) = (A \land \top) \lor (A \land \lnot B) = A \land (\top \lor \lnot B) = A \land \top = A. $$

$\endgroup$
  • $\begingroup$ In the second step, shouldn't that equal sign mean equivalence relation? $\endgroup$ – KumarAnkit Dec 31 '18 at 8:23
  • $\begingroup$ I’m using = in its usual meaning, as in 2+2=4. $\endgroup$ – Yuval Filmus Dec 31 '18 at 8:24
  • $\begingroup$ ok, can you explain the second step transition to third step? $\endgroup$ – KumarAnkit Dec 31 '18 at 8:25
9
$\begingroup$

I would use my least favourite inference rule: Disjunction Elimination. Basically, it says that if $R$ follows from $P$, and $R$ follows from $Q$, then $R$ must be true if $P \vee Q$: $$(P \to R), (Q \to R), (P \lor Q) \vdash R$$

So let's assume $A \lor (A \land \neg B)$. Set $P = A$, $Q = A \land \neg B$, $R = A$ and apply the rule:

  • If $P$ ($= A$) we are done.
  • If $Q = A \land \neg B$ then $A$ (by conjunction elimination, $S \land T \vdash S$)
  • By disjunction elimination $A \lor (A \land \neg B) \to A$.

The inverse is trivial: assume $A$, then by one of the variants of conjunction introduction ($S \vdash S \lor T$ for any $T$) $A \to A \lor (\cdots)$.

Here is a diagram of this proof:

Rendered Proof

$\endgroup$
  • 4
    $\begingroup$ I'm sorry, how did you draw that diagram? I smell the faintest smell of Coq. $\endgroup$ – Tobia Tesan Oct 8 '17 at 21:18
  • 1
    $\begingroup$ @TobiaTesan I was the one who "drew" the diagram. I used a software called slate to do so. $\endgroup$ – Sriotchilism O'Zaic Oct 8 '17 at 22:04
  • 1
    $\begingroup$ @EpsilonNeighborhoodWatch: thank you very much. Excuse me for further abusing your patience, but can that software be obtained in any way? The link on the header (www.cogsci.rpi.edu/slate) seems dead $\endgroup$ – Tobia Tesan Oct 8 '17 at 22:44
  • $\begingroup$ @TobiaTesan Microsoft's Visio can be used to draw diagrams like that, too. If you're affiliated with a university or large company that offers Microsoft software to students/employees, or if you have an MSDN subscription, you might have already-paid access to it. $\endgroup$ – Nat Oct 9 '17 at 4:59
  • $\begingroup$ @Nat Sure (or you can man up and do it in TikZ :P), but I was under the impression that the thing used by EpsilonNeighborhoodWatch had proof assistant features, hence my interest :) FWIW Proof General can do something like this, but the proof tree visualization is much uglier. $\endgroup$ – Tobia Tesan Oct 9 '17 at 7:32
5
$\begingroup$

Note that, when we know that $C$ implies $D$, we have $C \lor D = D$. This is analogous to taking the union of a set (corresponding to $D$) and one of its subsets ($C$): we get the largest set ($D$) back.

In your case, $C = A \land \lnot B$ and $D = A$, and the implication trivially holds.

$\endgroup$
3
$\begingroup$

A more intuitive look:

A is always true when A is true.

A & -B is only true when A is true.

Intuitively, applying OR to these two would produce a result C which is always true when A is true. As such, C is always true when A is true.

(Stop reading here if this explanation works for you.)

This is how I think about this problem. However, this explanation is not complete since all we've shown is that A -> C and not A <-> C.

So, let's also also show that C -> A.

A is always false when A is false.

A & -B is always false when A is false.

Intuitively, applying OR to these two would produce a result C which is always false when A is false. As such, C is always false when A is false; -A -> -C, which is the same thing as C -> A.

So A -> C and C -> A, so A <-> C.

$\endgroup$
3
$\begingroup$

Sometimes, people are confused by the letters. People like food, because it's easy to think about.

Pretend I ask you to flip a coin to choose between one OR the other of the following two options:

  • An Apple, OR...
  • An Apple, and definitely no Banana.

[The first is equal to "A", the second "A and not B". But don't think of the letters. Think about the apple, and the whether you also get a banana.]

That first one really means "An apple fersure, and maybe you'll get a banana."

So leaving something out is the same as saying "maybe".

Looking at them as a pair, whichever you get, there's definitely going to be an Apple involved. Yay. And if your coinflip picks the right one, you might get a Banana.

But isn't that the same as saying "maybe you'll get a Banana"? Just, with half the likelihood?

So all you can definitely logically say is, you'll get an Apple. You can't say anything about whether you'll get a Banana.

$\endgroup$
3
$\begingroup$

Similar to answer of Yuval Filmus. Using boolean algebra, in engineering notaion, and factoring (or factorising) out A.

$A+A\cdot\bar B=A\cdot(1+\bar B)=A\cdot1=A$

$\endgroup$
3
$\begingroup$

It seems as though no one mentioned it yet so I will go ahead.

The law to deal with these kinds of problems is the absorption law it states that p v (p ^ q) = p and also that p ^ (p v q) = p. If you try to use distributive law on this it will keep you going in circles forever:

(A v A) ^ (A v ~B) = A ^ (A v ~B) = (A ^ A) v (A ^ ~B) = A v (A ^ ~B) = (A v A) ^ (A v ~B)

I used the wrong symbol for not and equals but the point here is that when you are going in circles / when there is an and-or mismatch usually you should look to the absoprtion law.

B is irrelevant to the outcome as you will notice if putting this in a truth table.

$\endgroup$
  • $\begingroup$ This goes well with the apple and banana answer $\endgroup$ – Erin Oct 9 '17 at 11:37
  • 1
    $\begingroup$ @Erin +1 Further, it supplies a rule, whereas the apple and banana answer only appealed to intuition, and the OP asked for a rule, not intuition. $\endgroup$ – Rosie F Oct 9 '17 at 12:43
2
$\begingroup$

Another intuitive way to look at this:

If A is a set, then we can say any given object is either (in A) or (not in A).

Now look at S = A or (A and not B):

  • If an object is in A, then "A or anything" contains all elements in A, so the object will also be in S.

  • If an object isn't in A, then "A and anything" excludes all elements not in A, so the object is neither in A nor in (A and not B), so it isn't in S.

So the outcome is that any object in A is in S, and any object not in A isn't in S. So intuitively, the objects in S must be exactly those in A, and no other objects.

When two sets have identical elements, they are defined to be the same set. So A = S.

$\endgroup$
2
$\begingroup$

A simple method you can always use if you're stuck is case analysis.

Assume $A$ is true. In that case the left side is true, because true OR anything is true.

Assume $A$ is false. False AND anything is false. False OR false is false.

Since $A$ can have no more possible values, you've proven the proposition.

$\endgroup$
0
$\begingroup$
lets consider: 
  1) A as 1 and B as 0. 
  2) A as 0 and B as 1. 
  3) A as 1 and B as 1.
  4) A as 0 and B as 0.

using the first scenario : A or (A and !B) => 1 or ( 1 and 1) => 1 0r 1 => 1
using the second scenario: A or (A and !B) => 0 or ( 0 and 0) => 0 or 0 => 0
using the third scenario : A or (A and !B) => 1 or ( 1 and 0) => 1 or 0 => 1
using the fourth scenario: A or (A and !B) => 0 or ( 0 and 1) => 0 or 0 => 0

From the above four cases, the result always depends on A not on B, so the result is A.
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.