**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.

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

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback