Boolean functions: Logic, propositions.

121 Views Asked by At

By manipulating the expression algebraically. Prove the identities:

A- x + ~( x+y) = x+ ~y

B- x+ xy=x

C- x( x+y)=x

There is one that is not included in here: x * ~ x * ~ y= x * ~ y.

And I came up with

x+( x+ ~ y)= x + ~ y

x+ ~ y= x + ~ y.

But I'm lost on the other ones.

1

There are 1 best solutions below

3
On BEST ANSWER

$$x + \lnot( x+y) = x+ \lnot y$$ $$\equiv x + (\lnot x\cdot \lnot y) = (x + \lnot x)\cdot (x + \lnot y) = 1\cdot (x +\lnot y) = (x + \lnot y)\tag{A}$$

$$x + xy= x(1 + y) = x\tag{B}$$ $$x(x+y)= x. \;\tag C$$

(C) states: $x$ and $x+y$. To be true, both $x$ and $(x+y)$ must be true. So $x$ must be true. And, if $x$ is true, then so is $x+y$. This makes the expression (C) dependent only on $x$ (C is true if x is true, C is false if x is false.)

For the added question: $$x\cdot \lnot x \cdot \lnot y ?$$ We have $$\underbrace{x \cdot \lnot x}_{\large = 0}\cdot \lnot y = 0 \cdot \lnot y = 0$$

Be sure to understand and identify the steps I've taken above. In A, I used DeMorgan's, and the distributive property of addition over multiplication.

In B, I primarily used the "reverse" distribution of multiplication over addition. And since (true or y)= true = 1, we are left with x.