# Given $x \wedge y=\mathbf{F}$, how to simplify $x \wedge \lnot y$?

Given that the boolean expression $x \wedge y=\mathbf{F}$, how to simplify $x \wedge \lnot y$?

Is the above question equivalent to the following question?

Find z so that $\lnot(x \wedge y)\rightarrow \left [ (x \wedge \lnot y) \Leftrightarrow z \right ]$ is a tautology.

If the two are equivalent, can you solve the problem from the two perspectives if possible?

I want formal ways which can handle two or even ten variables because this is the simplified version of my real question. I'm writing a program that has complicate logic.

    if (!a && b && d)
{
//do action a
}
else if (!a && b && !d)
{
//do action b
}
else if (!b && c || a && c)
{
//do action c
}
else if(a && !c || !b && !c)
{
//do action d
}
else
{//do action e  }


Given !a && b && d is false, can we simplify !a && b && !d?

Given !a && b && d=!a && b && !d=false, can we simplify !b && c || a && c?

Given !a && b && d=!a && b && !d=!b && c || a && c=false, can we simplify a && !c || !b && !c?

I try to simplify the if condition in order to lower the CPU usage.

If we know that $x\wedge y$ is false, then $x$ and $y$ are not both true. Thus, $x\wedge\neg y$ is true if and only if [fill in the blank with one of $x,y$] is true. The filled-in blank is the desired $z$ / "simplified" version of $x\wedge\neg y$.

Added: Given that $\neg a\wedge b\wedge d$ is false, then \begin{align}\neg a\wedge b\wedge\neg d &= (\neg a\wedge b\wedge\neg d)\vee F\\ &= (\neg a\wedge b\wedge\neg d)\vee(\neg a\wedge b\wedge d)\\ &= (\neg a\wedge b)\wedge(d\vee\neg d)\\ &= (\neg a\wedge b)\wedge T\\ &=\neg a\wedge b.\end{align}

Given that $\neg a\wedge b\wedge d$ and $\neg a\wedge b\wedge\neg d$ are false (that is, that $\neg a\wedge b$ is false), then we know $$T=\neg(\neg a\wedge b)=a\vee\neg b,$$ so \begin{align}(\neg b\wedge c)\vee(a\wedge c) &= (a\wedge c)\vee(\neg b\wedge c)\\ &= (a\vee\neg b)\wedge c\\ &= T\wedge c\\ &= c.\end{align}

Given that $\neg a\wedge b\wedge d$ and $\neg a\wedge b\wedge\neg d$ and $(\neg b\wedge c)\vee(a\wedge c)$ are false (that is, that $a\vee\neg b$ is true and $c$ is false), then \begin{align}(\neg b\wedge\neg c)\vee(a\wedge\neg c) &= (a\wedge\neg c)\vee(\neg b\wedge\neg c)\\ &= (a\wedge T)\vee(\neg b\wedge T)\\ &= a\wedge\neg b\\ &= T.\end{align}

• Yes, so I'm asking how to find z. – Gqqnbig Aug 29 '13 at 14:59
• Oops! My answer had an error. Now fixed. The blank can be filled in by $x$, the other by $y$. I leave it to you to determine which. – Cameron Buie Aug 29 '13 at 15:07
• I added my real problem to my question, which is much more complicated. I'm afraid your current solution will not work. – Gqqnbig Aug 29 '13 at 15:16
• I have added to my answer. Take a look and see if it helps you in your bigger question. DeMorgan's laws and distributivity are good things to keep in mind, as are the facts that $p\wedge T=p\vee F=p.$ – Cameron Buie Aug 30 '13 at 10:24
• It's great! This is exactly what I want! The result you simplified is simpler than mine. It proves that my "action e" will never be executed. It is of great help to me. – Gqqnbig Aug 30 '13 at 10:47

This is quite similar to Cameron's answer, worded a bit differently. If $x\land y$ is false, then by DeMorgan, either $x$ is false or $y$ is false.

Case 1 ($x\equiv F$). In this case $(x\land \neg y)$ is false, so $(x\land \neg y)\equiv F\equiv\ ?$.

Case 2 ($y\equiv F)$. In this case $(x\land \neg y)\equiv x\land T\equiv\ ?$

You should be able to fill in the question marks now.

I find a solution to solve my first set of problem, that is to use the substitution method.

Simplify $x \wedge \lnot y$: \begin{align} & x \wedge \lnot y \\ = & x \wedge \lnot y \vee \mathbf{F} \\ = & x \wedge \lnot y \vee x \wedge y \\ = & x \end{align}

Simplify !b && c || a && c, get (! a && b) || c. It seemingly isn't much simplified.

Simplify a && !c || !b && !c, get 'True'.

For the second question, I transform $\lnot(x \wedge y)\rightarrow \left [ (x \wedge \lnot y) \Leftrightarrow z \right ]$ to conjunctive normal form $(\lnot x \vee y \vee z) \wedge (x \vee \lnot z)$.

We know to make $(\lnot x \vee y \vee z) \wedge (x \vee \lnot z)$ a tautology, $(\lnot x \vee y \vee z)$ and $(x \vee \lnot z)$ should be tautology first.

From the first part, z could be x or $\lnot y$; from the second part, z could be x. As a result, the only solution is z=x.