If A, B, and C are Boolean variables, which of the following statements are true?

2.5k Views Asked by At

I. $A\wedge (B\vee C) = (A\wedge B) \vee (A\wedge C)$

II. $A\vee (B\wedge C) = (A\vee B) \wedge(A\vee C)$

III. ($A\wedge B) \vee C = C \vee (B \wedge A)$

How can I do solve this? I'm not entirely sure how to go about this since I am fairly new to Discrete Math. Any help is greatly appreciated.

2

There are 2 best solutions below

2
On

Make truth tables for each of them.

In the first one, note that on the LHS, $A$ must always be true, and at least one of $B$ or $C$ must be true. This is obviously the same as the RHS, hence equality holds.

In the equation, note that at least one of $A$ or ($B$ and $C$) must be true. This also works for the right-hand side.

In the last one, note that at least one of ($A$ and $B$) or $C$ must be true. Note that if we set $A$ to true, $B$ to false, and $C$ to false, then the left-hand side is false. However, the right-hand side is true. Thus, this does not hold.

So the first two are true. The third is not.

0
On

You have to work with the distributive and associative properties of the operators $\lor$ (disjunction) and $\land$ (conjunction).

For the first one:

$$A\land(B\lor C)=(A\land B) \lor (A\land C), \text{ by the distributivity of $\land$ with $\lor$}.$$

If you want (or need) to prove this distributivity yourself, you can use something called a truth table. For all your varibales, here $A,B,C$ you put in all combinations of true and false for your variables, and check if the truth values for all of the rows match for your two expressions:

\begin{array}{|c|c|c|c|} \hline A& B & C & A\land(B\lor C) & (A\land B) \lor (A \land C) \\ \hline T& T & T & T & T\\ \hline T &T &F & T & T\\ \hline T &F &T & T & T\\ \hline T &F &F & F & F\\ \hline F &T &T & F & F\\ \hline F &T &F & F & F\\ \hline F &F &T & F & F\\ \hline F &F &F & F & F\\ \hline \end{array} Since all truth values in the fourth and fifth column for the expressions we want to check match, these two expressions are equivalent and the statement is true.

Try it yourself for the second and third statement by writing out the truth table.

If the expressions get crazy long, you can also create columns with intermediate results.