Cheap and Secure Web Hosting Provider : See Now

Question about idempotent and Dominance Laws in Boolean Algebra

, , No Comments
Problem Detail: 

If I have the following statements:

For Idempotent:

Since X * X = X, would that imply that ~X * ~X = ~X

For Dominance:

Since X + 1 = 1 would that imply that ~X + 1 = 1

Asked By : user3395308
Answered By : Yuval Filmus

The principle of substitution states that if $\varphi$ is a valid (fully parenthesized) formula in variables $x_1,\ldots,x_n$ and $e_1,\ldots,e_n$ are arbitrary expressions, then if we substitute $e_i$ for $x_i$ in $\varphi$ (you have to substitute all occurrences of $x_i$ by $e_i$) we still get a valid formula. You can apply this principle to your examples.

Perhaps the principle will become easier to understand if we take an example from algebra. Consider the identity $(x+y)(x-y) = x^2-y^2$. If we substitute $2a$ for $x$ and $1+a$ for $y$ then we get $((2a)+(1+a))((2a)-(1+a)) = (2a)^2-(1+a)^2$, which is still valid. The same happens in your case.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54214

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback