## Propositional Logic

A system that deals with Proposition (statements).

## Proposition

A declarative sentence that is either true or false (but not both) is a proposition.

Also known as a statement.

These sentences would be considered propositions:

- It is Thursday today (true).
- I am 14 years old (false).
- 1 + 1 = 3 (false).

Usually denoted using lowercase letters $p$, $q$, $r$, $s$ or $t$.

p = It rained yesterday. q = I am happy.

The truthfulness or falsity of a proposition is called its Truth Value. Denoted by $T$ or $F$, or 1 and 0 in computer science.

We can use connectives to change or combine the meaning of propositions. For example, $\neg p$ negates the value of p. If it's true, it becomes false and vice versa.

## Truth Table

A truth table allows us to consider all possible combinations of proposition logic systems.

For example, consider $\neg p$:

$p$ | $\neg p$ |
---|---|

1 | 0 |

0 | 1 |

We can use truth tables to help us understand the truth values of other connectives within propositional logic.

## Connective

### Negation (NOT)

Symbol: $\neg p$

An operator that negates a proposition.

- $p$ = I will pass my exam.
- $\neg \ p$ = I will NOT pass my exam.

In Boolean Algebra, it's equivalent to $1 - T(p)$

Truth table

$p$ | $\neg p$ |
---|---|

1 | 0 |

0 | 1 |

## Disjunction (OR)

Symbol: $p \lor q$

True when p OR q is true.

Truth table

$p$ | $q$ | $p \lor q$ |
---|---|---|

1 | 0 | 1 |

0 | 1 | 1 |

1 | 1 | 1 |

0 | 0 | 0 |

Equivalent to $\max(T(p), T(q))$

## Conjunction (AND)

Symbol: $p \land q$

True only when p AND q is true.

Truth table:

$p$ | $q$ | $p \land q$ |
---|---|---|

1 | 0 | 0 |

0 | 1 | 0 |

1 | 1 | 1 |

0 | 0 | 0 |

Equivalent to multiplication $T(p) \times T(q)$

## Implication (If...Then)

Symbol: $p \rightarrow q$

If p is true, then q is true.

Truth table

$p$ | $q$ | $p \rightarrow q$ |
---|---|---|

1 | 1 | 1 |

0 | 1 | 1 |

1 | 0 | 0 |

0 | 0 | 1 |

Think of it as a promise. Only false when promise is broken.

## Bi-conditional: $\leftrightarrow$

Symbol: $p \leftrightarrow q$

Truth table

$p$ | $q$ | $p \leftrightarrow q$ |
---|---|---|

1 | 1 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

0 | 0 | 1 |

Equivalent to equality check: $T(p) = T(q)$

## Exclusive-Or

Symbol: $p \oplus q$

p or q but not both.

Also called XOR.

Truth Table

$p$ | $q$ | $p \oplus q$ |
---|---|---|

1 | 1 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

0 | 0 | 0 |

Truth table is opposite of bi-conditional.

## Operator Precendence

- $\neg$
- $\land$
- $\lor$
- $\rightarrow$
- $\leftrightarrow$

## Tautology

A statement that is always true.

For example: $p \lor \neg p$ is always true.

$p$ | $\neg p$ | $p \lor \neg p$ |
---|---|---|

1 | 0 | 1 |

0 | 1 | 1 |

## Consistent

A formula that is true in at least one scenario.

## Contradiction

A formula that is never true.

For example: $p \land \neg p$

$p$ | $\neg p$ | $p \land \neg p$ |
---|---|---|

1 | 0 | 0 |

0 | 1 | 0 |

Also called "inconsistent".

## Equivalence

If two formula are equivalent if they have identical truth tables.

Denoted by: $\equiv$

$A \equiv B$ means A and B have the same Truth Table.

Note: equivalence is relation, not connective.

Can prove De Morgan's Laws using a truth table.

$\neg (p \land q) \equiv \neg p \lor \neg q$

$p$ | $q$ | $\neg (p \land q)$ | $\neg p$ | $\neg q$ | $\neg p \lor \neg q$ |
---|---|---|---|---|---|

1 | 1 | 0 | 0 | 0 | 0 |

1 | 0 | 1 | 0 | 1 | 1 |

0 | 1 | 1 | 1 | 0 | 1 |

0 | 0 | 1 | 1 | 1 | 1 |

$(p \rightarrow q) \equiv (\neg p \land q)$