CS70 Guide
  • This site is now deprecated
  • LaTeX Reference
  • Discrete Math
    • Overview
    • Propositional Logic
    • Proofs
    • Stable Matching
    • Graphs
    • Modular Arithmetic
    • RSA Cryptography
    • Polynomials
    • Countability
    • Computability
  • Probability
    • Overview
    • Counting
    • Discrete Probability
    • Hashing and the Union Bound
    • Expectation and Variance
    • Concentration Inequalities
    • Continuous Probability
    • Markov Chains
    • The Beta Family
    • The Gamma Family
    • Conditional Expectation and Variance
Powered by GitBook
On this page
  • What are Propositions?
  • Connectives
  • Implication
  • Quantifiers
  • Exercises
  • Resources

Was this helpful?

  1. Discrete Math

Propositional Logic

PreviousOverviewNextProofs

Last updated 2 years ago

Was this helpful?

What are Propositions?

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

  • Statements like "Birds can fly".

  • Well defined equations with no free variables like 1+1=31 + 1 = 31+1=3.

Propositions are not:

  • Variables like xxx or 555.

  • Equations with free variables like P(x)=yP(x) = yP(x)=y.

  • 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:

  • Conjunction is the and operation: for P∧QP \land QP∧Qto be true, PPPand QQQmust both be true.

  • Disjunction is the or operation: for P∨QP \lor QP∨Qto be true, either PPPor QQQmust be true.

  • Negation is the not operation: if PPPis true, then ¬P\lnot P¬Pis false.

    • The law of the excluded middle states that PPPand ¬P\lnot P¬P cannot both be true.

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:

¬(P∨Q)  ⟺  (¬P∧¬Q)\lnot(P \lor Q) \iff (\lnot P \land \lnot Q)¬(P∨Q)⟺(¬P∧¬Q)

"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

P

Q

T

T

T

T

T

F

F

F

F

T

T

F

F

F

T

T

(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

¬(∀x)(P(x))  ⟺  (∃x)(¬P(x))\lnot(\forall x)(P(x)) \iff (\exists x)(\lnot P(x))¬(∀x)(P(x))⟺(∃x)(¬P(x))
(P∨Q)∧R≡(P∧R)∨(Q∧R)(P \lor Q) \land R \equiv (P \land R) \lor (Q \land R)(P∨Q)∧R≡(P∧R)∨(Q∧R)
P  ⟹  QP \implies QP⟹Q

Contrapositive Equivalence: If P implies Q, then ¬Q  ⟹  ¬P\lnot Q \implies \lnot P¬Q⟹¬P.

Note that this is different from the converse, which is Q  ⟹  PQ \implies PQ⟹P. This statement is not logically equivalent!

P Q

P Q

Note that the truth table for P  ⟹  QP \implies QP⟹Q is equivalent to the one for ¬P∨Q\lnot P \lor Q¬P∨Q! That means this formula is logically the same as P  ⟹  QP \implies QP⟹Q.

(∃x∈N)(x=x2)(\exists x \in \mathbb{N})(x=x^2)(∃x∈N)(x=x2)

You could think about the parentheses almost like defining a scope of variables, like what might happen in programming! Here, the first clause is defining an arbitrary variable xxxto be any natural number.

Is the expression ∀x∃y(Q(x,y)  ⟹  P(x))\forall x \exists y (Q(x,y) \implies P(x))∀x∃y(Q(x,y)⟹P(x))equivalent to the expression ∀x((∃y Q(x,y))  ⟹  P(x))\forall x ((\exists y \ Q(x,y)) \implies P(x))∀x((∃y Q(x,y))⟹P(x))? (Source: Discussion 0 2a)

No, they are not equivalent. We can see this more clearly by converting the implication Q  ⟹  PQ \implies PQ⟹P to ¬Q∨P\lnot Q \lor P¬Q∨P as was demonstrated in the Truth Table section above. On the left side, this conversion is straightforward, yielding ∀x∃y(¬Q(x,y)∨P(x))\forall x \exists y (\lnot Q(x,y) \lor P(x))∀x∃y(¬Q(x,y)∨P(x)).

On the right side, we'll need to invoke De Morgan's Laws to convert the 'exists' into a 'for all' since it was negated. This yields ∀x(∀y¬(Q(x,y))∨P(x))\forall x (\forall y\lnot(Q(x,y)) \lor P(x))∀x(∀y¬(Q(x,y))∨P(x))which is not the same thing!

An integer aaais said to divide another integer bbb if aaais a multiple of bbb. Write this idea out using propositional logic (a divides b can be written as a∣ba \mid ba∣b).

a∣b  ⟺  (∃q∈Z)(a=qb)a \mid b \iff (\exists q \in \mathbb{Z})(a = qb)a∣b⟺(∃q∈Z)(a=qb)

In plain English: "There exists an integer qqqsuch that when we multiply qqqwith bbb, we get aaa."

Note 1: Discussion 0:

  ⟹  \implies⟹
  ⟺  \iff⟺
https://www.eecs70.org/assets/pdf/notes/n1.pdf
https://www.eecs70.org/assets/pdf/dis00a.pdf