Problem 3 - Applied Discrete Structures

Question

Let \(\left[B ; V_{1} \wedge_{+}-\right]\) be a Boolean algebra of order \(4,\) and let \(f\) be a Boolean function of two variables on \(B\). (a) How many elements are there in the domain of \(\mathrm{f?}\) (b) How many different Boolean functions are there of two, variables? Three variables? (c) Determine the minterm normal form of \(f\left(x_{1}, x_{2}\right)=x_{1} \vee x_{2}\). (d) If \(B=\\{0, a, b, 1\\},\) define a function from \(B^{2}\) into \(B\) that is not a Boolean function.

Step-by-Step Solution

Answer

(a) 16 elements; (b) 16 for 2 variables, 256 for 3 variables; (c) \( x_{1}\overline{x_{2}} \vee \overline{x_{1}}x_{2} \vee x_{1}x_{2} \); (d) Define using non-standard mappings.

Step 1: Determine the Domain Size for Two Variables

In a Boolean algebra of order 4, the set \( B \) contains 4 elements. The domain of a Boolean function with two variables \( f(x_{1}, x_{2}) \) consists of all possible pairs \( (x_{1}, x_{2}) \) where \( x_{1}, x_{2} \in B \). Hence, there are \( 4 \times 4 = 16 \) possible input pairs.

Step 2: Calculate Number of Boolean Functions for Two Variables

A Boolean function has a truth value for each possible outcome. For two variables taken from algebra of order 2 (e.g., \( \{0,1\} \)), there are \( 4 \) possible input pairs: (00, 01, 10, 11). Each pair maps to either 0 or 1. Hence, the total number of different Boolean functions is \( 2^4 = 16 \). In the case of two variables from algebra of order 4, it also follows that a function can take any of the 4 values for each possible input pair, hence \( 4^{16} \).

Step 3: Calculate Number of Boolean Functions for Three Variables

For three variables in order 2, there are \( 2^3 = 8 \) possible input combinations. As before, each output can be either 0 or 1, so the number of functions is \( 2^8 = 256 \).

Step 4: Determine the Minterm Normal Form

The function \( f(x_{1}, x_{2}) = x_{1} \vee x_{2} \) can be expressed in the minterm (or disjunctive normal) form by considering each minterm where the function's value is 1. These minterms correspond to the cases: (1,0), (0,1), (1,1). Thus, the minterm expression is \( m_{1} \vee m_{2} \vee m_{3} = x_{1}\overline{x_{2}} \vee \overline{x_{1}}x_{2} \vee x_{1}x_{2} \).

Step 5: Define a Non-Boolean Function from \(B^2\) Into \(B\)

Since the set \( B = \{0, a, b, 1\} \), a valid function \( g: B^2 \to B \) must map every pair in \( B^2 \) to an element in \( B \). A non-Boolean function may break Boolean rules like commutativity, associativity, or have undefined behavior for some inputs. For instance, selecting values arbitrarily for combinations such as \( g(a,b) = 1 \), \( g(a,a) = a + b \) (not a single element of \( B \)).

Key Concepts

Boolean function

A Boolean function is a mathematical construct used within the realm of Boolean algebra. It takes binary values of variables, such as 0 and 1, as inputs and produces a binary output. These functions underpin digital circuit design, computer logic, and programming.
For instance, a function with two variables, say \(f(x_1, x_2)\), will have outcomes based on combinations of these variables. If the set \(B\) has four elements as in the exercise, the domain for \(f\) consists of all possible pairs from these elements. This means, if \(B = \{0, a, b, 1\}\), \(f\) can take 16 different input pairs, making it expansive in terms of possibilities.
The number of unique Boolean functions, indeed grows as the number of variables increases. With two binary variables, each giving a binary output, there are \(2^4 = 16\) potential functions, while with three, the possibilities expand to \(2^8 = 256\). The complexity of creating comprehensive computing systems builds from these exponential possibilities.

Minterm normal form

Every Boolean function can be expressed in a format known as the **Minterm Normal Form** (MNF), which is a systematic way to represent Boolean expressions. It is formed by OR-ing (disjoining) the minterms. A minterm is essentially a unique AND-ed (conjoined) sequence of variables where the function evaluates to 1.
Consider the function \(f(x_1, x_2) = x_1 \vee x_2\). In MNF, this function is expressed by focusing on combinations where the function gives the result 1:

• \((1,0)\): The minterm is \(x_1\overline{x_2}\).
• \((0,1)\): The minterm is \(\overline{x_1}x_2\).
• \((1,1)\): The minterm is \(x_1x_2\).

Therefore, the minterm expression becomes \(x_1\overline{x_2} \vee \overline{x_1}x_2 \vee x_1x_2\). This systematic approach not only organizes the Boolean function neatly but also serves as the foundation for designing complex logical circuits.

Domain of a function

In the context of Boolean algebra, understanding the "domain of a function" is central to determining how many inputs a Boolean function can take. The domain refers to all the possible input combinations that the function might receive.
For instance, if a Boolean function \(f\) is defined over a domain \(B\) with four elements \(\{0, a, b, 1\}\), and \(f\) uses two variables, the domain becomes \(B^2\). This denotes all pairs of inputs from \(B\) multiplied by itself, resulting in \(16\) possible input combinations like \((0,0), (0,a), (0,b), \ldots, (1,1)\).
Understanding the domain is vital for determining how many different Boolean functions can exist. Larger domains mean more input combinations, which expands the variety of function outputs. This consideration is essential for tasks ranging from logical circuit design to algorithmic problem-solving.