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