# Propositional Logic

## What are Propositions?

Propositions are anything that can be **true** or **false.** This could include:

Statements like "Birds can fly".

Propositions are **not:**

Statements that aren't clearly true or false, like "I like trains."

### Connectives

Simple propositions can be **joined together** to make complex statements. There are three basic ways to connect propositions together:

One example where we can see these components in action is in **De Morgan's Laws**, which state how negation can be **distributed** across conjunction or disjunction:

"If neither P nor Q are true, then P and Q must both be false."

"If P(x) isn't true for every x, then there exists an x where P(x) is false."

Another example of distribution is this congruence, which works for any combination of and's and or's.

### Implication

One proposition can **imply** another, which looks like this:

Roughly, implication in plain English can be stated in the form **if P, then Q.** However, there are a lot of nuances to what this really means!

#### Properties of Implication

**Reversible:**Q is true if P is true. However, be careful-*this doesn't necessary mean that Q implies P!***P is sufficient for Q:**Proving P allows us to say that Q is also true.**Q is necessary for P:**For P to be true, it is necessary that Q is true. (If Q is false, then P is also false.)

#### Truth Table

(If two propositions have the same truth table, then they are logically equivalent. However, it's still possible for a proposition to imply another even if their truth tables are different!)

### Quantifiers

Sometimes, we need to define a specific type of variable to work with in a propositional clause. For instance, take the proposition, *"There exists a natural number that is equal to the square of itself."* We could write this as:

## Exercises

**Note:** This idea is going to be important for a lot of future sections!

## Resources

Note 1: https://www.eecs70.org/assets/pdf/notes/n1.pdf Discussion 0: https://www.eecs70.org/assets/pdf/dis00a.pdf

Last updated