1
$\begingroup$

I'm having a lot of trouble with two problems the first is:

1) (y*w) + y + w



 What I tried here is applying the distributive law as follows

(y*w) + (y+w)
((y+w) + y) * ((y+w) + w)
((y*w) + y) * ((y*w) + w)

then applying the absorption law and getting y*w but the answer is y + w, so I'm unsure how to get it using the laws of Boolean algebra.

2) The second problem I am having issues with is

Prove that if x*y = x then ~x*~y = ~y

What I tried was negating both sides of the first expression and plugging into the second but that isn't allowed in Boolean algebra it seems.

$\endgroup$
  • $\begingroup$ 1) Please ask only one question per post. 2) What does "simplify" mean here? $\endgroup$ – Raphael Oct 10 '17 at 11:13
1
$\begingroup$

The first question wants you to simplify a condition of the following sort:

I am looking for a job which is either interesting, or pays well, or is both interesting and pays well.

You can see that the last option is not really needed.

For the second question, note that

  • $x \land y = x$ is the same as $x \Rightarrow y$ ("$x$ implies $y$"), and
  • $\lnot x \land \lnot y = \lnot y$ is the same as $\lnot y \Rightarrow \lnot x$, which is the contrapositive of the first statement.
$\endgroup$
1
$\begingroup$

I will use $\land$ instead of * and $\lor$ instead of +.

a) You could simplify it as following:

$ \ \ \ (y\land w) \lor y \lor w = (y\land w) \lor (y \land T) \lor w = y\land(w \lor T) \lor w = (y \land T) \lor w = y \lor w$

b) and prove it as following:

Since $x \land y = x$ we have $\lnot x \lor \lnot y = \lnot x$ by De Morgan's law. By substituting $\lnot x$ in the given equality we have
$$\lnot x \land \lnot y = (\lnot x \lor \lnot y) \land\lnot y = (\lnot x\land \lnot y) \lor (\lnot y \land \lnot y) = (\lnot x\land \lnot y) \lor \lnot y = $$ $$=(\lnot x \lor T)\land \lnot y = T \land \lnot y = \lnot y$$


Recall that for any boolean $x$ and $y$ the following identities always hold

  • $x \lor T = T$
  • $x \land T = x$
  • $x \land x = x$
  • $x \lor x = x$
  • $\lnot(x \land y) = \lnot x \lor \lnot y \text{ (De Morgan's law)}$
  • $\lnot(x \lor y) = \lnot x \land \lnot y \text{ (De Morgan's law)}$
$\endgroup$
0
$\begingroup$

After you got here: ((y+w) + y) * ((y+w) + w) this is associative.

(y*w) + y + w
((y+y) * (y+w)) + w
(y * (y+w)) + w
(w + y) * ((w + y) + w)
(w + y) * (w + y)
w + y

Start with a truth table

y    w    y*w  (y*w) + y + w
0    0    0    0
0    1    1    0
1    0    1    0
1    1    1    1

The equivalency:

x * y = x
0   ?   0
1   ?   1
y = 0

expansion of x * 0 = x

~x * ~y = ~y
0    ~0   ~0
1    ~0   ~0

expansion of x * 1 = 1

$\endgroup$

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.