How to prove that the problem is a tautology, using only replacement by equivalence(s) (1. negation, 2. distribution, 3. de Morgan's laws, 4. $x\leftrightarrow y\equiv(x\rightarrow y)\wedge(y\rightarrow x)$, 5. $x\rightarrow y\equiv\neg y\rightarrow \neg x$, 6. $\neg(x\rightarrow y)\equiv x\rightarrow \neg y$):

The problem: $(x \wedge(x\rightarrow y))\rightarrow y\\$

What I did was this:

$(x\wedge \neg(x\wedge\neg y))\rightarrow y\\(x\wedge(\neg x\vee y))\rightarrow y\\((x\wedge\neg x)\vee(x\wedge y))\rightarrow y\\$

Now I'm not sure if I'm allowed to do this:

$(F\vee(x\wedge y))\rightarrow y\\$

I conclude nothing changes when I remove $F$, since it's connected with OR operator.

$(x\wedge y)\rightarrow y$

Again, I just conclude it all depends on $y$, and since the values will be the same ($y\rightarrow y)$, it will always be true (tautology).

I understand I didn't actually use only replacements by equivalence, and that's my problem. What can't I see there that can be done to simplify the expression further?

EDIT: ok i got it, i'm an idiot, how to delete this? (there are no delete options)


1 Answer 1


I will try this way, assuming that you are allowed to "rewrite" : $(x∧(x→y))→y$ as :

$\lnot[x \land (\lnot x \lor y)] \lor y$.

By De Morgan we have :

$[\lnot x \lor \lnot (\lnot x \lor y)] \lor y$

and by De Morgan again :

$[\lnot x \lor (x \land \lnot y)] \lor y$.

This is :

$[(\lnot x \lor x) \land (\lnot x \lor \lnot y)] \lor y$

which is :

$[T \land (\lnot x \lor \lnot y)] \lor y$.

But $(T \land p) \leftrightarrow p$; thus we have :

$(\lnot x \lor \lnot y) \lor y$

which is :

$\lnot x \lor (\lnot y \lor y)$

and again :

$\lnot x \lor T$

which finally is :


  • $\begingroup$ Why however wasnt i allowed to jump to $((x\wedge\neg x)\vee(x\wedge y))\rightarrow y$? $\endgroup$
    – user160454
    Jun 27, 2014 at 13:52
  • $\begingroup$ @user160454 - you are right ! You are allowed to ... In this way, you get (as you have done) $(x∧y)→y$, then rewrite as $\lnot (x \land y) \lor y$ and go on ... $\endgroup$ Jun 27, 2014 at 13:55
  • $\begingroup$ Ok, then everything is clear, next I did was use this rule: $x\rightarrow y\equiv \neg x\vee y$, and got $y\vee(\neg x\vee\neg y)$ and then distribution... Tautology. $\endgroup$
    – user160454
    Jun 27, 2014 at 14:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .