# 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: \(P + Q = (P \land \lnot Q) \lor (\lnot P \land Q)\).

\(P\) | \(Q\) | \(P + Q\) | \(P \land \lnot Q\) | \(\lnot P \land Q\) |
---|---|---|---|---|

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: \(P \downarrow Q = \lnot P \land \lnot Q\).

\(P\) | \(Q\) | \(P \downarrow Q\) | \(\lnot P\) | \(\lnot 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: \(P \mid Q = \lnot P \lor \lnot Q\).

\(P\) | \(Q\) | \(P \mid Q\) | \(\lnot P\) | \(\lnot Q\) |
---|---|---|---|---|

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: \(P \rightarrow Q = \lnot P \lor 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

\(P\) | \(Q\) | \(P \rightarrow Q\) | \(\lnot 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*: \(P \rightarrow Q = \lnot Q \rightarrow \lnot P\).

\(P\) | \(Q\) | \(\lnot Q \rightarrow \lnot P\) | \(\lnot Q\) | \(\lnot P\) |
---|---|---|---|---|

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: \(P \iff Q = (P \rightarrow Q) \land (Q \rightarrow P)\).

\(P\) | \(Q\) | \(P \iff Q\) | \(P \rightarrow Q\) | \(Q \rightarrow P\) |
---|---|---|---|---|

F | F | T | T | T |

F | T | F | T | F |

T | F | F | F | T |

T | T | T | T | T |

## Laws

### DeMorganâ€™s Laws

### Commutative Laws

### Associative Laws

### Idempotent Laws

### Absorption Laws

### Double Negation Law

## Truth Sets

The truth set of a statement \(P(x)\) is the set of all values of \(x\) that make the statement \(P(x)\) true.

- The truth set of \(P(x)\): \(\{ x \mid P(x) \}\)
- The truth set of \(\lnot P(x)\): \(U \setminus \{ x \mid P(x) \}\)