## 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

1. $\neg$
2. $\land$
3. $\lor$
4. $\rightarrow$
5. $\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.

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)$