\maketitle Introduction ============

My notes in my book aren’t super clean, this is why I’m writing this up. I also don’t want to forget all this stuff, what’s the point of learning it then? This will be a great way to offload this all to external storage and will make me remember it and do well on tests and get an A+ in this class.

Propositional Logic

A proposition is a statement that is by itself true or false. E.g. "I’m just like my country" (False). It’s not a command or imperative or question.

Propositional variables (usually written as lower case letters like $p, q, r$) represent some sort of proposition, such as "Shashank is awesome". Connectives encode the relationship between variables. Keith’s example: “If you liked it, then you should have put a ring on it.”

  • Every propositional variable is binary - it must be true or false.

You know enough about propositional connectives already.

Mathematical implication

You don’t know anything about this, you fool. Don’t think in the English sense of implies or and ever, it is all very unintuitive and solely defined on the basis of the truth table. The whole reason we have a symbolic notation is so as to not get tripped up by English.

$p\rightarrow q$ is true whenever $p \land \neg q$ is false.

An implication with a false antecedent is vacuously true. An implication with a true consequent is trivially true.

Truth table for $p\rightarrow q$:



Biconditional Connective

Biconditional is the same as "iff". iff, even though its name may say otherwise, always implies a two-way implies relationship. It’s that simple.


Proof by contradiction

In propositional logic, this looks like $(\neg p\rightarrow \bot)\rightarrow p$.

Operator precedence

For operators, associativity means that when the same operator appears in a row, then which operator occurrence we apply first. In the following, let Q be the operator $a Q b Q c$ If Q is left associative, then it evaluates as $(a Q b) Q c$

And if it is right associative, then it evaluates as $a Q (b Q c)$

Operator precedence is straightforward: it’s just $\neg, \land, \lor, \rightarrow, \iff$.

de Morgan’s Laws

Fairly easy. We concluded that $\neg (p \land q) = \neg p \lor \neg q$ and $\neg (p \lor q) = \neg p \land \neg q$. This is what the guy came up with.

NOT (p and q) = NOT p or NOT q

NOT (p or q) = NOT p and NOT q // this works because to convince you that the statement $p \lor q$ is false, I’d need to show you that $p$ is false and $q$ is false.

Incredibly useful equivalence: $\neg (p \rightarrow q) = p \land \neg q$

Similarly, $\neg (p \land \neg q) = \neg p \lor q$, which is the same as $p\rightarrow q$.

Sample problems

  • Translate

    • "p if q"

    • “If I will be in the path of totality, but there’s no solar eclipse today, I won’t see a total solar eclipse.”, where a: I will be in the path of totality. b: I will see a total solar eclipse. c: There is a total solar eclipse today.

    • "p, but q"

    • $\neg (p \rightarrow q)$

First-Order Logic

The adjective "first-order" distinguishes first-order logic from higher-order logic in which there are predicates having predicates or functions as arguments, or in which one or both of predicate quantifiers or function quantifiers are permitted.

It’s a logical system for reasoning about properties of objects. Gives booster packs to propositional logic with predicates, functions and quantifiers.

Equality can be applied to objects, for propositions use the equivalence symbol. Functions evaluate to objects, not propositions. Predicates are exactly like functions, but they evaluate to propositions. Examples of predicates: Cute(a), Kitty(a), so on.

Existentially-quantified statements are false unless there is a positive example. Universally-quantified statements are true unless there is a negative example.

Think of FOL as a mathematical programming language.

Good pairings

If there is some object you don’t care about, like Mt. Everest, being considered, you don’t want that to screw things up.

That’s why $\forall$ is usually paired with $\rightarrow$ and $\exists$ is paired with $\land$.

Suppose I say $\exists x. (Person(x) \land Cat(x))$, i.e. there is some x who is both a person and a cat. In reasonable words, this statement is likely to be false. Let $W$ be one such world where there are people and cats and robots, but no cat-people. If I say instead $\exists x.(Person(x)\rightarrow Cat(x))$, then in the world $W$ I can point to a robot and say: "that robot is $x$, so $Person(x)$ is false, making the inner statement vacuously true - so I have found an $x$ that satisfies the condition and the whole existential statement is true. So while $\exists x. (Person(x) \rightarrow Cat(x))$ is a perfectly okay First-Order Logic statement, it doesn’t do quite what we want it to. For $\exists$, the $\land$ prevents the statement from being true when you are considering an object you don’t care about.

Now for the example with $\forall$, we have that $\forall x. (Person(x) \rightarrow \neg Cat(x))$. This implies that for every single possible value of $x$, if $x$ is a Person, than $x$ is not a cat. If we didn’t have the implies, and instead had an $\land$, that would make the whole statement false for someone who isn’t a person (or isn’t a cat) - and would imply that we have values of $x$ for which the whole condition is false. We still understand what it is saying, but it is indirect. With the implies, we have that if $x$ is not a Person, the condition is vacuously true, and so we’re still chilling with the $\forall$ stuff.

Forget about "such that" - it’s just saying, for all $x$, the stuff in the brackets holds (or is true). Got it!

Negating quantifiers

This is rather important. The negation of "there is a cute puppy" is "NO puppy is cute". Think of a malevolent actor or some shit.

Rationale behind $\rightarrow$ being used in "All As are Bs" - we can live with some guys who aren’t A also being B. Why can’t $\land$ be used?


  • "SOme P is a Q"

  • using Happy(x) and WearingHat(x), write "every happy person wears a hat"

  • "All Ps are Qs"

  • "Every person loves someone else" using Person(p) and Loves(x, y)

  • "There is a cute puppy". $\exists x. (Puppy(x) \land Cute(x))$

  • The empty set exists. Using $Set(S)$ and $x\in y$.

  • there is a set with no elements. $\exists S. (Set(S) \land \forall x. x \not \in S$.


  • $\exists x. (P(x) \rightarrow Q(x))$

  • $\forall x. (Person(x) \rightarrow WearingHat(x)$

  • $\forall x. (P(x) \rightarrow Q(x))$

  • $\forall p (Person(p) \rightarrow (\exists y. (Person(y) \land y\not = x \land Loves(x,y))))$

  • $\forall x. (Puppy(x) \rightarrow \neg Cute(x))$ or $\forall x. (Puppy(x) \lor \neg Cute(x))$

  • $\exists z. (Set(z) \land (\forall x. (x \not \in y)))$

  • Every set has more than 0 elements. $\forall S. (Set(S) \rightarrow \exists x. x \in S)$

Binary Relations

Order matters $3 < 5$ is not the same thing as $5 < 3$. SOmetimes it is irrelevant, like for $=$.


Everyone has a bluetooth headset. $\forall a \in A$


No privileged position - like Facebook friends as opposed to Instagram followers.


"When a is related to b, and b is related to c, then a is related to c".



Equivalence relations

They are reflexive, symmetric and transitive. Equality, modular congruence, h is same color as g, x is same shape as y.

Equivalence relations group things together?

Equivalence Classes

$[x]_R = {y\in A | xRy}$\ "The set of all elements related to $x$ by R"

Is it ever possible for an element to be in two equivalence classes? No, because of transitivity.

Equivalence relation is a relation that is reflexive, symmetric and transitive.

Sys of Reps

If R is an equivalence relation over a set A, then a sys of reps is a set $X\subseteq A$ containing exactly one element from each equivalence class.

All sys of reps have the same cardinality. Why?

If X is a sys of reps for R, then no two elements in X are related to each other by R.

Equivalence relations help to partition a set. Good questions to ask?

What are the equivalence classes of the relation? What items get lumped together?

What items are kept separate? What’s the sys of reps?

What do equivalence relations do? They partition things.

What’s so special about reflexivity, transitivity and symmetry.

$\forall a \in A. \forall b \in A.\forall c \in A. (aRb \land bRc \rightarrow cRa)$.

Need to fill out a lot more here.


High school version, CS version

Take in inputs, give out outputs. Functions are deterministic in mathematics.

Each function has two sets associated with it, a domain and a codomain. For any $x$ in the domain $f(x)$ belongs to the codomain. There are things in the codomain that don’t have anything mapping to them.

Codomain is like the return type of a function.