Boolean Algebra

Two Boolean values: true and false

Used to control flow of control in programs

• what happens next
• if a condition is true, we do one thing, if it's false we do something else

C has no Boolean data type--we substitute "boolean-valued" integer variables.

• we use 0 to mean false
• C interprets any non-zero value as true, but in general, we use 1 to mean true
• we can use #define to make this clearer to human readers:
  #define TRUE 1
  #define FALSE 0

Two kinds of operators in C return boolean values:

1. Arithmetic:

Example

int x, y;
...            /* initialize x and y somehow */
The expression x < y is a boolean expression; it returns true if the value stored in x is less than the value stored in y.

The operands for relational operands are typically numeric (int or float), but we also use them to compare characters.

Two kinds of operators in C return boolean values:

2. Logical:

Logical operators take boolean operands and return a boolean result.

&& and || take two operands

! takes one operand

The operands for logical operators can be:

• expressions using relational operators
• expressions using other logical operators
• boolean-valued variables

Examples:

x > y && y > z /* x and y are numeric types */

x && y /* x and y are boolean-valued variables */

(x && y) || !z /* x, y and z are boolean-valued variables */

Truth tables for logical operators:

Simplification of Boolean Expressions

Simplification requires the use of equivalences:

1. !(x = y) Û x != y
2. !(x < y) Û x >= y
3. !(x <= y) Û x > y
4. !(x > y) Û x <= y
5. !(x >= y) Û x < y
6. !(x && y) Û ! x || ! y
7. !(x || y) Û ! x && ! y
8. !(! x) Û x

Example:

!((!x && y) && (x || !y) 

Û !(!x && y) || ! (x || !y) (by g)

Û !(!x) || !y || !(x || !y) (by f)

Û !(!x) || !y || !x && !(!y) (by g)

Û x || !y || !x && y (by h, applied twice)