Boolean function

A short introduction

• Computers or electronic devices are composed of electronic circuit with inputs and outputs which use only 2 state 0 or 1.
• Boolean algebra is used to design those circuits.
• Three basic element:
  • Complement: $\bar{0} = 1, \bar{1} = 0$
  • Or (sum): 0 + 1 = 1
  • And (product): 1.0 = 0

Examples

• Example 1 : find the value of $1.0 + \overline{(0 + 1)}$.
• Example 2: translate $1.0 + \overline{(0 + 1)} = 0$, the equality found in Example 1, into a logical equivalence.
• Example 3: translate the logical equivalence $(T \wedge T) \vee \neq F \equiv T$ into an identity in Boolean algebra.

Definition

<aside> 💡 Definition 1.1.

Let B = 0, 1. Then $B_n = (x_1, x_2, ..., x_n)|x_i \in B$ for $1 \leq i \leq n$ is the set of all possible n-tuples of 0s and 1s. The variable x is called a Boolean variable if it assumes values only from B, that is, if its only possible values are 0 and 1. A function from $B_n$ to B is called a Boolean function of degree n.

</aside>

• Find the values of the Boolean function represented by $F(x,y) = x\bar{y}$.
• Find the values of the Boolean function represented by $F(x, y, z) = xy + \bar{z}$.
• Representing the second example in graphical illustration by using n-cube.
• How many different Boolean functions of degree n are there?

Boolean algebra identities

• Show that the distributive law x(y + z) = xy + xz is valid.