2
$\begingroup$

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.

$\endgroup$
1
3
$\begingroup$

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}$$

$\endgroup$
7
  • $\begingroup$ Yes, so I'm asking how to find z. $\endgroup$ – Gqqnbig Aug 29 '13 at 14:59
  • $\begingroup$ 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. $\endgroup$ – Cameron Buie Aug 29 '13 at 15:07
  • $\begingroup$ I added my real problem to my question, which is much more complicated. I'm afraid your current solution will not work. $\endgroup$ – Gqqnbig Aug 29 '13 at 15:16
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Cameron Buie Aug 30 '13 at 10:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Gqqnbig Aug 30 '13 at 10:47
2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

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.