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)


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 '14 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$ – Mauro ALLEGRANZA Jun 27 '14 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 '14 at 14:03

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.