A Boolean Junction in k variables is f: {0, 1}^k rightarrow {0, 1}. A remarkable

Question

A Boolean Junction in k variables is f: {0, 1}^k rightarrow {0, 1}. A remarkable property of such functions is that they correspond to logical expression, where True = 1 and False = 0. For example, if k = 1, an example of a one-variable Boolean function is f(x) = 1 - x, which corresponds to the logical expression not A, since if x = 1 (correspondingly, .4 True) we have f(x) = 0 (not A False), and if x = 0 (A False), /(x) = 1 (not A True). Show that the two-variable Boolean function f(x, y):= x + y - xy corresponds to the logical expression (A or B). Find a Boolean function f(x, y, z) corresponding to the logical expression ((A & B) or (not A & C)).

Explanation / Answer

Here when x= 1, (i.e. A true) and y=1 ( i.e. B true) then

f(x,y) = x+y-xy = 1+1-1= 1-1=0 (A or B false)

Accordingly when x=0 ( i.e. A false) and y=0( i.e B false) then

f(x,y) = 0+0-0= 0 ( A or B false)

or if the case is that x=1 and y=0, then

f(x,y) = 1+0-0= 1 ( A true)

that means in each case, it corresponds to the logical expression (A or B).

It proves part (a).

===================================================================

LEt x=1 and y=1 and z=0, then

(A & B) or (-A & C )= (1 x 1) + (0 x 1) ( on plug in corresponding values of True and false)

= xy+(1-x)z

that will be our required boolean function in form f(x,y,z)

This is the answer of part (b)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.