1

The expression I am working on is $xy'+x'y$. Is this the correct conversion to NOR? $$(x'+y)'+(x+y')'$$

Just adding for clarification

the question is in an old logic notation ( think it was used by Lewis Carroll)

  • the $'$ stands for negation
  • the $+$ stands for or
Thomas Andrews
  • 177,126
user122421
  • 21
  • 2
    NOR of what?${{}}$ – Git Gud Jan 19 '14 at 16:47
  • 1
    This question is not clear. You need to give some context and explain your notation/terminology. – Marc van Leeuwen Jan 19 '14 at 17:33
  • 1
    I'm guessing they mean converting a logical expression to one where the only truth functional operator is "NOR" or "$\downarrow$" as I've usually seen it written. In which case $p\vee q=(p\downarrow p)\downarrow(q\downarrow q)$ and $\neg p=p\downarrow p$. The rest of the operators follow naturally. Though $+$ in Boolean algebra is usually XOR, but that's an easy translation to make. – Malice Vidrine Jan 19 '14 at 22:14

2 Answers2

1

By "Nor form" I'm assuming you mean create a circuit of only variable inputs, their negation, and "Nor" gates. This is done sometimes with CMOS circuitry because of its simple low power nature.

First notice that if you have an expression of the form

$$(A \text{ or } B \text{ or } C...) \text{ and } (D \text{ or } E \text{ or } F...) \text{ or } ...$$

That it is equivalent to the expression:

$$(A \text{ nor } B \text{ nor } C...) \text{ nor } (D \text{ nor } E \text{ nor } F...) \text{ nor } ...$$

This can be seen using either demorgans, or just notice that the nots after the ors cancel with the nots before the ands.

The first expression above is called "conjunctive normal form". So the first thing you want to do is convert your expression to conjunctive normal form. There are general algorithms for doing this, but your XOR has an easy CNF:

$$x\bar y + \bar x y = x \text{ xor } y = (x \text{ or } y) \text{ and } (\bar x \text{ or } \bar y)$$

Then converting to NOR form is straightforward: $$(x \text{ or } y) \text{ and } (\bar x \text{ or } \bar y) = (x \text{ nor } y) \text{ nor } (\bar x \text{ nor } \bar y)$$

The answer you've given above is actually the "or" of 2 "nor" gates (or the nand of 2 or gates). While your answer is logically equivalent to your question, it isn't in a form directly made up of only nor gates.

DanielV
  • 23,556
0

If you want to see if you are right, write a truth table, with $L$ being left and $R$ being right side of your equation: $$ x=0,y=0 \Rightarrow L=0, R=0\\ x=0,y=1 \Rightarrow L=1, R=1\\ \text{etc} $$

Alternatively, take the complement of R, expand it, then take its complement.

user44197
  • 9,730