-1
$\begingroup$

I have seen various statements with negation( or complement) operators and when i try to negate them using De Morgan's law , i become confused about how to negate.

The main doubts are what variables to negate and what operators to negate.

Example:- ~(p^q)= ~p∨~q (according to De Morgan's)

Doubt1 but for ~(p=q) should i blindly negate everything like ~p!=~q or should i do p!=q ?

Doubt2 Can DeMorgan's law be applied to this below statement(it contains addition operator )?

x and y are 4 bit signed numbers (2s complement..)

x - y can be obtained by:

!(!x + y) because

If z is an n-bit number then !z=2^n−1−z.

So...

!(!x+y)=2^n−1−(2^n−1−x+y)=x−y.

but if I try to simplify the expression using DeMorgan's law

I get !(!x+y)=x+!y

and x+!y is not equal to x-y (in 2's complement).

So I am not able to find out my mistake. Can someone please help.

$\endgroup$
  • $\begingroup$ You write "Can DeMorgan's law be applied to this below statement". Which statement? De Morgan Law applies to boolean variables , not integers values unless you treat them as TRUE if its value is not 0, FALSE otherwise. $\endgroup$ – fade2black Oct 15 '17 at 18:18
  • $\begingroup$ @fade2black to this statement. !(!x + y) , this expression is to calculate x-y $\endgroup$ – Pranjal Kanyal Oct 15 '17 at 19:57
2
$\begingroup$

Relating to "can we apply De Morgan's laws to any operator", De Morgan's Laws are applicable in De Morgan algebras (by definition), which is a bit broader than just Boolean algebras. Fuzzy logic is a non-Boolean example where De Morgan's Laws hold (and can properly be called that, despite relating operations that we normally call minimum and maximum). The laws definitely cannot be applied to all operators all the time.

This actually also answers your first question, De Morgan's Laws do not even apply to $\sim(p=q)$ in the first place.

Generalizing further, laws that look like De Morgan's Laws show up when a pair of operation is each others "mirror image": operation A becomes B when you work in a mirror image of the applicable number line, and vice versa. If you go that far, laws like these show up as, if being really generous with the naming, "variants of De Morgan's Laws":

  • $-\min(a, b) = \max(-a, -b)$
  • $-\text{avg-round-down}(a, b) = \text{avg-round-up}(-a, -b)$
  • $-\lfloor x \rfloor = \lceil -x \rceil$ (not even a 2-operand operation, but I think it's relevant here)

Note that all of these are "directional", they care about the built-in "direction" of the number line so mirroring it makes a difference.

Relating more to your second question (the addition thing), subtraction and addition are not related through a variant of De Morgan's Law. In fact if you mirror addition (with negation), you get back addition: $-(-x + -y) = x + y$. A fundamental problem here is that addition does not care about the inherent "direction" of the number line, so of course it had to be its own mirror image - from the point of view of addition, nothing has really changed.

An other way to say that is that addition does not have a "bias" in any particular direction, while what the mirroring would do is switch the direction of the bias. Mirroring with complement in bitvector arithmetic doesn't help, although a stray 1 shows up and makes it look like there might have been a bias, bitvector addition actually isn't biased.

An other problem here is that addition is commutative while subtraction is anticommutative, but the mirror image of a commutative operation is still commutative - all the mirroring does is change the direction of the space you're in, the operation still acts the same way, just maybe in a different direction.

That said, $x - y = \sim(\sim x + y)$ (also part of your second question) does make sense now that we're thinking about mirroring and changing the direction of space. Imagine $x$ and $y$ as being arrows, then $\sim x$ turns that arrow around, we add $y$ to it, and then we flip the result around too. Geometrically, it makes sense that the effect is that $y$ was reversed and added to $x$.. but there is of course a catch, because $x - y \neq x + \sim y$. The funny thing here is that addition is sort of "centered" on zero, while the mirroring operation we're using mirrors $0 \leftrightarrow -1$, so we either need two mirroring operations to cancel out that problem or an explicitly offset: obviously also $x - y = x + \sim y + 1$.

That's not an example of De Morgan's Laws in action. By those laws, both operands would be mirrored so the entire operation happens in the context of a mirrored number line. But $\sim(\sim x + \sim y) = x + y + 1$, where that extra +1 shows up again because the offsets from both inner mirroring operations are added, but only compensated for once by the outer mirroring operation. This is of course nowhere near a subtraction, it's more like a version of $-(-x + -y) = x + y$ except it works out less well.

$\endgroup$
  • $\begingroup$ Lots of interesting stuff here, but are you able to clarify in the answer how it answers the question (which it seems is dealing with a Boolean algebra)? $\endgroup$ – D.W. Oct 16 '17 at 14:12
  • $\begingroup$ do you mean that every odd number of mirror operations on addition implicitly inserts -1 to the expression? $\endgroup$ – Pranjal Kanyal Oct 17 '17 at 15:11
  • $\begingroup$ @PranjalKanyal not in general, but mirroring with bitwise complement "shifts" the number line as well in a sense, and addition cares about that shift. If you do it again it shifts back (it's the same shift, but since the number line was already mirrored it has the opposite effect), which can compensate. An odd number of such mirroring operations (in succession) would end up with a net shift but for an even number it can cancel out. $\endgroup$ – harold Oct 17 '17 at 15:18
  • $\begingroup$ Pretty helpful information. To sum it up Do you mean that in this expression x−y=∼(∼x+y) DeMorgans law is not applicable because the negation(1s complement) here is a "mirror" operation? And when i applied the first mirror operation to the expression inside paranthesis, every operator and operand got mirrored and resulted in x+~y , and the mirror of addition led to the shifting back of number line . So now we need to add 1 to it to get the correct result $\endgroup$ – Pranjal Kanyal Oct 17 '17 at 15:29
  • $\begingroup$ @PranjalKanyal De Morgan's Law is not applicable at all there. In my last paragraph I don't discuss how addition and subtraction are related through De Morgan's Laws (they are not) but rather how two well-known relations between them can be explained in the same framework of mirroring things. $\endgroup$ – harold Oct 17 '17 at 15:44
5
$\begingroup$

De Morgan laws are precisely the following formulas: $$\lnot(p \land q) \iff \lnot p \lor \lnot q$$ and $$\lnot(p \lor q) \iff \lnot p \land \lnot q$$ You may only apply them in the above two situations. Anything else, whether it involves numbers, addition, equality, etc., has nothing to do with de Morgan laws.

There may be some generalizations of de Morgan laws which might be applicable in some other situations, and there might be some other rules that are similar to de Morgan laws, but given what you are asking, it's best not to worry about them.

In some situations, you can indirectly apply de Morgan laws if you first bring your formula into a suitable form. For example $\lnot (p = q)$ where $p$ and $q$ are Boolean values, we need to notice that $p = q$ is just $p \Leftrightarrow q$, which is $(p \Rightarrow q) \land (q \Rightarrow p)$, which is then $(\lnot p \lor q) \land (\lnot q \lor p)$, and so \begin{align*} \lnot (p = q) &\iff \lnot (p \Leftrightarrow q) \\ &\iff \lnot ((p \Rightarrow q) \land (q \Rightarrow p)) \\ &\iff \lnot ((\lnot p \lor q) \land (\lnot q \lor p)) \\ &\iff \lnot (\lnot p \lor q) \lor \lnot (\lnot q \lor p) \tag{by de Morgan}\\ &\iff (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot p) \tag{by de Morgan} \\ &\iff (p \land \lnot q) \lor (q \land \lnot p) \end{align*}

Supplemental: Since the OP is asking about applicability of de Morgan laws, let me expand on this a bit. The basic de Morgan lawss hold in any Boolean algebra, examples of which are the propositional calculus and the powerset of a set. These are mentioned by the OP. There are other cases two, for instance $$-\max(x, y) = \min(-x, -y)$$ and $$-\min(x,y) = \max(-x, -y)$$ holds in real numbers. This idea leads to further investigations of de Morgan laws in algebra, of which I know next to nothing.

Another kind of generalization of de Morgan laws is $$(\lnot \forall x . \phi(x)) \iff \exists x . \lnot \phi(x)$$ and $$(\lnot \exists x . \phi(x)) \iff \forall x . \lnot \phi(x).$$ But I still stand by my original advice that one should learn to walk before one tries running.

$\endgroup$
  • $\begingroup$ got the convincing answer to doubt 1 . But what do you have to say about doubt 2 ? Is applying deMorgan law in the expression !(!x + y) for simplification a wrong approach? Thus expression calculates x-y $\endgroup$ – Pranjal Kanyal Oct 15 '17 at 20:01
  • $\begingroup$ Yes it's completely wrong to apply laws when they are inapplicable. Learn the basics first. $\endgroup$ – Andrej Bauer Oct 15 '17 at 21:19
  • $\begingroup$ ok.. apart from boolean expressions deMorgan law can be applied to sets (set theory)also right ? Are boolean expressions and set theory the only two cases where its applied? $\endgroup$ – Pranjal Kanyal Oct 16 '17 at 6:16
  • $\begingroup$ I updated my answer. $\endgroup$ – Andrej Bauer Oct 16 '17 at 7:14

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.