Boolean Functions

Definition

A Boolean function is a function whose variables and output take values from the Boolean set {0, 1} or {false, true}. It maps one or more binary inputs to a single binary output according to a logical expression.

If the function has n input variables, then it is written as:

$$f : \{0,1\}^n \rightarrow \{0,1\}$$

This means the function accepts an n-bit input tuple and returns either 0 or 1.

Example

If f(x, y) = x AND y, then:

• f(0, 0) = 0
• f(0, 1) = 0
• f(1, 0) = 0
• f(1, 1) = 1

This function outputs 1 only when both inputs are 1.

Main Content

1. Basic Structure of Boolean Functions

• A Boolean function consists of:
• Inputs: binary variables such as x, y, z
• Logical operators: AND, OR, NOT, XOR, NAND, NOR, XNOR
• Output: a single binary result
• Boolean functions can be represented in several ways:
• Truth tables
• Boolean expressions
• Logic circuits
• Venn diagrams
• A truth table lists all possible input combinations and the corresponding output.

Example: AND function

This table shows the behavior of the AND operation clearly.

2. Common Types of Boolean Functions

Constant functions

• Always return the same value, either 0 or 1
• Example: f(x) = 0 or f(x) = 1

Identity function

• Output equals the input
• Example: f(x) = x

Negation function

• Output is the opposite of the input
• Example: f(x) = NOT x

Binary logical functions

• Functions using two variables
• Examples:
  • AND
  • OR
  • XOR

Multivariable Boolean functions

• Use more than two variables
• Example: f(x, y, z) = x AND (y OR z)

Example of OR function

OR gives 1 if at least one input is 1.

3. Representation and Simplification of Boolean Functions

• Boolean functions can be written using algebraic notation:
• f(x,y) = x' + y
• f(x,y,z) = xy + x'z
• Common symbols:
• + means OR
• · or adjacency means AND
• ' means NOT
• Boolean expressions can often be simplified using:
• Boolean algebra laws
• De Morgan’s laws
• Karnaugh maps
• Algebraic manipulation
• Simplification is important because it reduces:
• number of gates in circuits
• cost
• power consumption
• delay

Example of simplification

$$f = x + xy$$

Using the absorption law:

$$x + xy = x$$

So the function simplifies to just x.

ASCII logic idea

x ----+----[AND]----+
      |             |
      +-------------[OR]---- f
y ---------[AND]----+

This shows how logic combinations can be built from basic operations.

Working / Process

1. Identify the input variables and their possible values

• Determine how many binary variables the function has.
• List all possible combinations of 0 and 1.
• Example: for two variables x and y, the combinations are 00, 01, 10, 11.

2. Apply the logical rule or expression

• Use the Boolean operators specified by the function.
• Evaluate the expression row by row in a truth table.
• Example: for f(x,y)=x+y, the output is 1 whenever either input is 1.

3. Interpret, simplify, and implement the function

• Read the result from the truth table or expression.
• If possible, simplify the expression using Boolean algebra.
• Then implement it using logic gates in a circuit or use it in a program or decision system.

Advantages / Applications

• Boolean functions are the basis of digital circuit design, including logic gates, adders, multiplexers, flip-flops, and processors.
• They are used in computer programming for conditions, loops, comparisons, and control structures like if, else, while, and switch.
• They are essential in mathematical logic and set theory, where logical operations correspond to union, intersection, and complement.
• Boolean functions are widely used in automation and control systems, such as alarms, sensors, and industrial controllers.
• They help in optimization, allowing engineers to reduce circuit complexity, cost, and energy usage.
• They support decision-making models in artificial intelligence, databases, search systems, and digital communication.

Summary

Boolean functions are binary-valued logical mappings that describe how inputs of 0 and 1 produce a binary output. They are the core of digital logic and are represented using expressions, truth tables, and circuits.