# Boolean Algebra

Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false

## Expressions

• Consistent: if it cannot be both true and false
• Complete: if every fully instantiated expression if true or false
• Tautology: if it evaluates to true for every combination of its propositional variables
• Contradiction: if it evaluates to false for every combination of its propositional variables

## Operators

### Exclusive Or

P or Q, but not both: .

F F F F F
F T T F T
T F T T F
T T F F F

### Nor

Neither P nor Q: .

F F T T T
F T F T F
T F F F T
T T F F F

### Negative And (NAND)

P and Q are not both true: .

F F T T T
F T T T F
T F T F T
T T F F F

### Conditional

If P, then Q: . It is sometimes described like this:

• P only if Q
• P is a sufficient condition of Q
• Q is a necessary condition for P
F F T T
F T T T
T F F F
T T T F

A conditional can also be expressed in the following form, called contrapositive: .

F F T T T
F T T F T
T F F T F
T T T F F

Proof:

### Biconditional (iff)

P if and only Q: .

F F T T T
F T F T F
T F F F T
T T T T T

## Truth Sets

The truth set of a statement is the set of all values of that make the statement true.

• The truth set of :
• The truth set of :