1
$\begingroup$

I have this boolean expression $$ f(a,b,c)_{Question}=nand(or(a,b) , nand(a, xor(b,c))) = \overline{(a+b)\cdot \overline{a(b\oplus c)}} $$ when I try to simplify the gates using boolean algebra, I get $$ f(a,b,c)_{Question}=or(nor(a,b) , and(a,xor(b,c)))=\overline{a+b}+(a\cdot(b⊕c)) $$

I need to simplify further and get $$ f(a,b,c)_{answer}=a\oplus(b \oplus \overline{a\cdot c}) $$ my function: $f_{answer}$ is justified by the criteria:

  • $f_{answer}$ uses lowest number of logical gates,(in our case minimum:3(xor,xor,and))
  • there may be n number of possible $f_{answer}$, example we can have another answer with same-minimum number of logical gates: $(a\oplus b) \oplus \overline{a\cdot c}$ is another possible answer,to our function,and it will be accepted,since it has only 3 logical gates,its is accepted

Question: So how can I find $f_{answer}$ when $f_{Question}$ is provided, what are the steps

but don't know what's the steps*,can anyone help?

I found these rules for xor:
enter image description here
from here but they are of no use

Edit:

when I expand** $ f(a,b,c)_{Question}=\overline{a+b}+a\cdot(b⊕c) $
I get $$ f(a,b,c)_{expanded}=\overline{(\overline{\overline{a}\overline{b}})\cdot (\overline{a\cdot\overline{\overline{b}\overline{c}}\cdot \overline{bc}})} $$

*The process to simplify,like "first remove brackets...", "Steps" is the answer I need for this question

**Which I think would be the first step in converting any, $f_{Question}$ to $f_{answer}$

$\endgroup$
9
  • 2
    $\begingroup$ What does "a xor (b,c)" mean, which appears just after your f(a,b,c) as part of the definition of f? [I would think xor is a binary connective, so should only appear between two boolean expressions, but I don't think (b,c) counts as a boolean expression,] $\endgroup$
    – coffeemath
    May 28, 2022 at 5:25
  • $\begingroup$ sorry for confusion,i mean xor(b,c) as b xor c and its not "a xor (b,c)",its "nand(a, xor (b,c))" which means !(a*(b xor c)), i think words may confuse,but you can understand the equation on right which uses symbols I guess $\endgroup$
    – Neptotech -vishnu
    May 28, 2022 at 5:37
  • 1
    $\begingroup$ Can you replace $b \oplus c$ by (b bar(c))+(bar(b) c)$ ? Here I mean by bar(x) to have x with a bar over it. $\endgroup$
    – coffeemath
    May 28, 2022 at 5:43
  • $\begingroup$ I simply mean to ask what I mentioned in my comment, unrelated to its application in your problem. In other words I'm asking whether my guess is right for a definition of $b \oplus c$ all in terms of just $\cdot,\ +,\ (overbar).$ $\endgroup$
    – coffeemath
    May 28, 2022 at 5:52
  • 1
    $\begingroup$ What I meant was to also convert the answer form to get rid of the $\oplus$ that are in it. Then you just have two expressions without $\oplus$ to check are equivalent, $\endgroup$
    – coffeemath
    May 28, 2022 at 7:56

2 Answers 2

Reset to default
2
$\begingroup$

More complex Boolean expression can be calculated using algebraic expressions for each gate.

In this system, we have

  • $\operatorname{OR}(a,b) = a+b-ab$
  • $\operatorname{AND}(a,b) = ab$
  • $\operatorname{NOR}(a,b) = 1-a-b+ab$
  • $\operatorname{NAND}(a,b) = 1-ab$
  • $\operatorname{XOR}(a,b) = a+b-2ab$

with the usual rule that $a^2=a$.

In this case, $or(nor(a,b) , and(a,xor(b,c)))$ becomes

$$1+ab-a-b+a(b+c-2bc)-(1+ab-a-b)(ab+ac-2abc)$$

$$=1+ab-a-b+ab+ac-2abc-ab-ac+2abc-ab-abc+2abc+ab+ac-2abc+ab+abc-2abc$$

$$=1+2ab-a-b+ac-2abc$$

And similarly, $a\oplus b\oplus\overline{ac}$ is represented by

$$(a+b-2ab)+(1-ac)-2(a+b-2ab)(1-ac)$$

$$=a+b-2ab+1-ac-2a-2b+4ab+2ac+2abc-4abc$$

$$=-a-b+2ab+1+ac-2abc$$

As the two last expressions in each case are the same, we can conclude that $$or(nor(a,b) , and(a,xor(b,c)))=a\oplus b\oplus\overline{ac}$$.

$\endgroup$
8
  • $\begingroup$ oh,i know they are same,i need some steps to convert the equation,anyway something interesting! $\endgroup$
    – Neptotech -vishnu
    May 28, 2022 at 8:46
  • $\begingroup$ can you explain how to turn back $1+2ab-a-b+ac-2abc$ to $a\oplus b\oplus\overline{ac}$ $\endgroup$
    – Neptotech -vishnu
    May 28, 2022 at 9:06
  • $\begingroup$ Do the same steps in reverse? It looks a bit artificial here though! $\endgroup$
    – JMP
    May 28, 2022 at 9:14
  • $\begingroup$ yes doing reverse will give the answer, but we can't know how to split terms and other stuffs,as the answer was only known,but not given. I should not split $2ab$ to $4ab-2ab$ without a reason(but I can do vice versa), as you say,it looks quite artificial, Is there no other way? $\endgroup$
    – Neptotech -vishnu
    May 28, 2022 at 9:19
  • 1
    $\begingroup$ If you use truth tables, they are both $A'B'C'+A'B'C+AB'C+ABC'$, but reversing the process is again too contrived. $\endgroup$
    – JMP
    May 28, 2022 at 9:26
1
+50
$\begingroup$

The truth table for your expression is:

$$\begin{array}{c|c|c|c}a&b&c&\overline{(a+b)\cdot\overline{a(b\oplus c)}}\\\hline F&F&F&T\\F&F&T&T\\F&T&F&F\\F&T&T&F\\T&F&F&F\\T&F&T&T\\T&T&F&T\\T&T&T&F\end{array}$$

which means that it should be possible to convert your expression $f_{\text{Question}}$ into the disjunctive normal form corresponding to this truth table, which is:

$$\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+a\overline{b}c+ab\overline{c}$$

And, indeed:

$$\begin{array}{rcll}\overline{(a+b)\cdot\overline{a(b\oplus c)}}&=&\overline{(a+b)\cdot\overline{a(b\overline{c}+\overline{b}c)}}&\text{definition of }\oplus\\&=&\overline{(a+b)\cdot\overline{ab\overline{c}+a\overline{b}c}}&\text{distributivity}\\&=&\overline{(a+b)\cdot((\overline{a}+\overline{b}+c)\cdot(\overline{a}+b+\overline{c})})&\text{de Morgan's law}\\&=&\overline{a}\overline{b}+ab\overline{c}+a\overline{b}c&\text{de Morgan's law}\\&=&\overline{a}\overline{b}(\overline{c}+c)+ab\overline{c}+a\overline{b}c&\text{as }c+\overline{c}\text{ is true}\\&=&\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+ab\overline{c}+a\overline{b}c&\text{distributivity}\\&=&\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+a\overline{b}c+ab\overline{c}&\text{commutativity}\end{array}$$

Now, if $f_\text{Answer}$ is really an equivalent formula, it should result in the same truth table. This means that, similarly, you can convert $f_\text{Answer}$ to the same disjunctive normal form:

$$\begin{array}{rcll}a\oplus(b\oplus(\overline{ac}))&=&a\oplus(b\oplus(\overline{a}+\overline{c}))&\text{de Morgan's law}\\&=&a\oplus(b\oplus(\overline{a}+\overline{c}))&\text{de Morgan's law}\\&=&b\oplus(a\oplus(\overline{a}+\overline{c}))&\text{commutativity and associativity of }\oplus\\&=&b\oplus(a\cdot\overline{\overline{a}+\overline{c}}+\overline{a}(\overline{a}+\overline{c}))&\text{definition of }\oplus\\&=&b\oplus(aac+\overline{a}\overline{a}+\overline{a}\overline{c}))&\text{de Morgan's laws, distributivity}\\&=&b\oplus(\overline{a}+c)&\text{tidy up}\\&=&b\overline{\overline{a}+c}+\overline{b}(\overline{a}+c)&\text{definition of }\oplus\\&=&ba\overline{c}+\overline{b}\overline{a}+\overline{b}c&\text{de Morgan's law}\\&=&ab\overline{c}+\overline{a}\overline{b}(\overline{c}+c)+(\overline{a}+a)\overline{b}c&\overline{a}+a,\overline{c}+c\text{ are true}\\&=&ab\overline{c}+\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+\overline{a}\overline{b}c+a\overline{b}c&\text{distributivity}\\&=&\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+a\overline{b}c+ab\overline{c}&\text{remove duplicates, commutativity}\end{array}$$

Phew! We've successfully transformed $f_\text{Question}$ and $f_\text{Answer}$ into their (common) disjunctive normal form, which means that we can now transform $f_\text{Question}$ into $f_\text{Answer}$ by first following the first transformation until reaching the disjunctive normal form, and then following the second transformation in reverse.

Of course, in the answer above, I mostly just applied the definition of $\oplus$ and well-known rules for $+$ and $\cdot$ (idempotency, commutativity, associativity, absorption, de Morgan's laws). Someone could come up with a longer or shorter proof. (In particular, a negation of a disjunctive normal form is a conjunctive normal form and it takes quite a bit of work to convert it back to a disjunctive normal form. We were lucky to have two negations above!) However, the idea is the same:

  • Either two expressions have the same truth table, in which case they have the same disjunctive normal form, and you can convert both to it - and therefore to each other,
  • Or they don't have the same truth table, and obviously, being not equivalent, they cannot be converted to each other.

See also: How to convert formula to disjunctive normal form?

$\endgroup$
10
  • $\begingroup$ You have shown, steps to convert Question to a Answer with lowest gate, but it's particular to this question only. What I really need is a general steps, that can be applied to any question,eg. $\overline{c}a+\overline{c}b$ cannot have it's first step as definition of $\oplus$, it needs distribute law first $\endgroup$
    – Neptotech -vishnu
    Jun 4, 2022 at 7:47
  • $\begingroup$ I think I may have misunderstood your question. Is it about (1) "Once you know the $f_\text{Answer}$, how do you convert $f_\text{Question}$ into $f_\text{Answer}$?", or is it about (2) "I don't even know $f_\text{Answer}$ with the minimal number of operations/gates, help me find it in general case, and prove that it is the same function as $f_\text{Question}$." $\endgroup$
    – Stinking Bishop
    Jun 4, 2022 at 8:55
  • $\begingroup$ My point for (2) is - to prove that two expressions are equivalent you don't need to transform one to another - you just need to check their truth tables. (That means their DNFs are the same, and so the transform from the first one to their common DNF and back to the second one can be done etc. etc., as above.) That is, unless this is a part of some exercise where you are explicitly asked to provide the steps. $\endgroup$
    – Stinking Bishop
    Jun 4, 2022 at 9:01
  • 1
    $\begingroup$ Well, DNF is always a solution and it has however many gates it ends up with (say $n$) so you can restrict yourself to $n$ gates or less. Or, in fact, you can already stop when you reach the number of gates used in $f_\text{Question}$ (in this example $4$)! $\endgroup$
    – Stinking Bishop
    Jun 4, 2022 at 9:23
  • 1
    $\begingroup$ As I said, take as $n$ the number of circuits in $f_\text{Question}$. If you can’t beat that, take $f_\text{Answer}=f_\text{Question}$. $\endgroup$
    – Stinking Bishop
    Jun 4, 2022 at 11:39

You must log in to answer this question.

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