Boolean Expression

Consider a Boolean algebra (B, ∨,∧,',0,1).A Boolean expression over Boolean algebra B is defined as

1. Every element of B is a Boolean expression.
2. Every variable name is a Boolean expression.
3. If a₁ and a₂ are Boolean expression, then a₁,'∨ a₂ and a₁∧ a₂ are Boolean expressions.

Example: Consider a Boolean algebra ({0, 1, 2, 3},∨,∧,',0,1).

1. 0∨x
2. (2∧3)
3. (x₁∨ x₂)∧ (x₁∧x₃)

are Boolean expressions over the Boolean Algebra.

    A Boolean expression that contains n distinct variables is usually referred to as a Boolean expression of n variables.

Evaluation of Boolean Expression:

Let E (x₁,x₂,....x_n)be a Boolean Expression of n variables over a Boolean algebra B. By an assignment of values to the variables x₁,x₂,....x_n, means an assignment of elements of A to be the values of the variables.

    We can evaluate the expression E ( x₁,x₂,....x_n) by substituting the variables in the expression by their values.

Example: Consider the Boolean Expression

            E( x₁,x₂,x₃)=(x₁∨ x₂ )∧(x₁∨ x₂ )∧(x₂∨ x₃)

over the Boolean algebra ({0,1}, ∨,∧,')

By assigning the values x₁=0,x₂=1,x₃=0 yields

            E (0, 1, 0) = (0∨1)∧(0∨1)∧(1∨0)=1∧1∧0=0.

Equivalent Boolean Expressions:

Two Boolean expressions of n variables are said to be equal if they assume the same value for every assignment of values to the n variables.

Example: The following two Boolean algebras (x₁∧x₂)∨(x₁∧ x₃ ) and x₁∧ (x₂∨ x₃) are equivalent.

We may write E₁( x₁,x₂,....x_n)=E₂( x₁,x₂,....x_n) to mean the two expressions E₁( x₁,x₂,....x_n) and E₂( x₁,x₂,....x_n)are equivalent.

Example: The Boolean expression (x₁∧x₂∧x₃)∨(x₁∧x₂ )∨(x₁∧x₃) over the Boolean algebra ({0, 1}, ∨,∧,') defines the function f in figure.

Min-term: A Boolean Expression of n variables x₁,x₂,....x_n is said to be a min-term if it is of the form x₁∧x₂∧x₃∧....∧x_n

where x_i is used to denote x_i or x_i'.