Foundations: Logic and Proofs

Propositional Logic

• Proposition: A declarative sentence (a sentence that declares a fact) that is either true or false, not both.

Some basic logical operators

Operator	Symbol	Meaning
Conjuction	\(\wedge\)	True if both P and Q propositions are true, else False
disjunction	\(\vee\)	True if either of P and Q is true or both, else False
negation	\(\neg\)	Negates the prposition
exclusive or	\(\oplus\)	True when exactly one of P and Q is true, false otherwise (removes the “both true” property from OR)

\(p \oplus q \equiv (p \wedge \lnot q) \vee (\lnot p \wedge q)\)(true if exactly one of P or Q is true, but not both.)

De Morgan Law

• \(\lnot (p_1 \wedge p_2 \wedge p_3 \wedge ..) \equiv (\lnot p_1 \vee \lnot p_2 \vee \lnot p_4 \vee ...)\)
• \(\lnot (p_1 \vee p_2 \vee p_3 \vee ...) \equiv (\lnot p_1 \wedge \lnot p_2 \wedge \lnot p_3 \wedge ...)\)

Conditional Statements

• Implication Let p anmd q be propositions. The conditional statement \(p \implies q\) is the proposition “if p, then q”, it is false when p is true and q is false and true otherwise. In the conditional statement \(p \implies q\), p is called hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).

  • “if \(p\), then \(q\)”, “\(p\) implies \(q\)”, “if \(p\), \(q\)”, “\(p\) is sufficient for \(q\)”, “\(q\) if \(p\)”, “\(q\) whenever \(p\)”, “\(q\) is necessary for \(p\)”, “a necessary condition for \(p\) is \(q\)”, “\(q\) follows from \(p\)”, “\(q\) unless \(\lnot p\)”

  • Above them “\(q\) unless \(\lnot p\)” might not be obvious, but it make sense if we treat “unless” with “or” (these are interchangeable). In langauge it means if \(\lnot p\) is false, then \(q\) must be true. That is same as saying if \(p\) is true then \(q\) has to be true to affirmate the proposition.

  • Contraverse: The conditional statement \(q \implies p\) is called contraverse.

  • Contrapositive: The conditional statement \(\lnot q \implies \lnot p\) is called contrapositive.

  • Inverse: The conditional statement \(\lnot p \implies \lnot q\) is the called the inverse.

  • Note:

    \(p \implies q \equiv \lnot p \vee q\)

    \(p \implies q \equiv \lnot q \implies \lnot p\) (implication and its contrapositive are equivalent)

    \(q \implies p \equiv \lnot p \implies \lnot q\) (converse of implication and its inverse are equivalent)

• Biconditional Statement Let \(p\) and \(q\) are propositions then biconditional statement is, $ p q$ means “\(p\) if and only if \(q\)”. This is true when \(p\) and \(q\) both have true values else false

  • “\(p\) is necessary and sufficient for \(q\)”, “if \(p\) then \(q\) and conversely”, “\(p\) iff \(q\)”, “\(p\) exactly when \(q\)”

  • \(p \iff q \equiv (p \implies q) \wedge(q \implies p)\)

    \(p \iff q \equiv (\lnot p \vee q) \wedge (\lnot q \vee p) \equiv \lnot ((p \wedge \lnot q) \vee (\lnot p \wedge q)) \equiv \lnot (p \oplus q)\)

Precedence of logical operators

Operator	Precedence (decreasing order)
\(\lnot\)	1
\(\wedge\)	2
\(\vee\)	3
\(\implies\)	4
\(\iff\)	5

Propositional Equivalences

• Tatuology: A compound prposition that is always true

• \(p \vee \lnot p\)

• Contradiction: A compound proposition that is always false.

  • \(p \wedge \lnot p\)

• Contingency: A compound proposition that is neither a tautology nor a contradiction

• Logically Equivalent: Compound propositions that have same truth values in all possible cases, denoted by \(\equiv\)

  • The compound propositions \(p\) and \(q\) are called logically equivalent if \(p \iff q\) is a tautology

• Some useful equivalence laws

Law	Expressions
Identity	\(p \wedge T \equiv p,\; p \vee F \equiv p\)
Domination	\(p \vee T \equiv T,\; p \wedge F \equiv F\)
Idempotent	\(p \vee p \equiv p,\; p \wedge p \equiv p\)
Commutative	\(p \vee q \equiv q \vee p,\; p \wedge q \equiv q \wedge p\)
Associative	\((p \vee q) \vee r \equiv p \vee (q \vee r),\; (p \wedge q) \wedge r \equiv p \wedge (q \wedge r)\)
Distributive	\(p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r),\; p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)\)
Absorption	\(p \vee (p \wedge q) \equiv p,\; p \wedge (p \vee q) \equiv p\)
Negation	\(p \vee \lnot p \equiv T,\; p \wedge \lnot p \equiv F\)

• Some logical equivalnce involving conditional statements
  • \((p \implies q) \wedge / \vee (p \implies r) \equiv p \implies (q \wedge / \vee r)\)
  • \((p \implies r) \wedge / \vee (q \implies r) \equiv (p \wedge / \vee q) \implies r\)
• Some logical equivalnce involving Biconditional statements
  • \(p \iff q \equiv \lnot p \iff \lnot q\)
  • \(p \iff q \equiv (p \wedge q) \vee (\lnot p \wedge \lnot q)\)
  • \(\lnot(p \iff q) \equiv (p \wedge \lnot q) \vee (\lnot p \wedge q) \equiv p \oplus q \equiv p \iff \lnot q\)

Satisfiability

A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. If no such assigment is possible and proposition is false for every input it becomes unsatisfiable.

The n-queen problem

Sudoku problem

Predicates and Quantifiers

• Predicate: A proposition with variables.
• Universal Quantifier: The universal quantification of \(P(x)\) is the statement “\(P(x)\) for all values of \(x\) in domain”. The notation \(\forall{x}P(x)\). An element for which \(P(x)\) is false is called the counterexample to \(\forall{x}P(x)\).
• Existential Quantifier: The existential quantification of \(P(x)\) is the statement “There exists an element \(x\) in the domain such that \(P(x)\)”. The notation \(\exists{x}P(x)\).
  • Uniqueness quantifier: \(\exists_{1}P(x)\) or \(\exists{!x}P(x)\)

The quantifiers \(\forall\) and \(\exists\) have higher precedence than all logical operators from propositional calculus.

NOTE: We can distribute \(\forall\) over conjugation and \(\exists\) over disjunction, however we cannot distribute \(\forall\) over disjunction now can distribute \(\exists\) over conjuction

Example:

Suppose \(P(x)\): x integer is even; \(Q(x)\): x integer is odd

\(\forall{x}(P(x) \vee Q(x))\): “all integer is even or odd”, now if we even go ahead and distribute the universal quantifier over disjunction then we get \(\forall{x}P(x) \vee \forall{x}Q(x)\) means “all integer is even or all integers is odd”, now this is an incorrect statement as an integer can be even or odd, not both.

We can say the distributed statement here is more stronger.

• Negation of Quantifiers
  • \(\lnot \forall{x}P(x) \equiv \exists{x} \lnot P(x)\)
  • \(\lnot \exists P(x) \equiv \forall{x} \lnot P(x)\)

Nested Quantifiers

We can nest the quantifiers such that one quantifier is within the scope of the other, example: \(\forall{x}\exists{y}(x + y = 0)\)

The order of the quantifiers used matters unless all are universal or all are existential quantifiers

Example:

Statement: Every real number except zero has a multiplicative inverse

\(\forall{x}((x \ne 0) \to \exists{y}(xy = 1))\)

Rules of Inference

Following are the rules to perform inference, read them as seeing if the LHS is True then what to the RHS

1. \((p \wedge (p \implies q)) \implies q\)
2. \((\lnot q \wedge (p \implies q)) \implies \lnot p\)
3. \(((p \implies q) \wedge (q \implies r)) \implies (p \implies r)\)
4. \(((p \vee q) \wedge \lnot p) \implies q\)
5. \(p \implies (p \vee q)\)
6. \((p \wedge q) \implies p\)
7. \(((p) \wedge (q)) \implies (p \wedge q)\)
8. \(((p \vee q) \wedge (\lnot p \vee r)) \implies (q \vee r)\)

Among them the “resolution rule” is often used in computer programs to automate reasoning tasks like theorem proving. It might be non-trivial to get so I’ll like to discuss it’s expansion here, remember we consider the LHS to be True. \[ \begin{aligned} &((p \vee q) \wedge (\lnot p \vee r)) \implies (q \vee r) \\ &\text{we can expand the LHS as} \\ &(p \wedge \lnot p) \vee (p \wedge r) \vee (q \wedge \lnot p) \vee (q \wedge r) \\ &\text{Since } p \wedge \lnot p \equiv F \text{ and we can simplify the 2nd two parts by distributive law as:}\\ &(p \wedge r) \vee (q \wedge (\lnot p \vee r)) \\ &\text{Now remember we are still in LHS so this all has to be True} \end{aligned} \] Right now we are stuck at something as to show that: \[ A \vee B \implies C \] where \(A = p \wedge r\) and \(B = (q \wedge (\lnot p \vee r))\) and \(C = q \vee r\)

We can exploit the following implication property we’ve seen earlier as \[ A \implies C \\ B \implies C \\ Then \\ A \vee B \implies C \] Now all we need to do is to inference whether each of those individual \(A\) and \(B\) does imply the \(q \vee r\), so lets start with \(A\).

If we said \(p \wedge r\) is True means, both \(p\) and \(r\) are True, which directly implies to \(q \vee r\) must have to be True as \(r\) is True.

Now talking about the \(q \wedge (\lnot p \vee r)\) to be True then both \(q\) and \(\lnot p \vee r\) have to be True, now which again signifies that the final statement \(q \vee r\) will be true because \(q\) is True.

From both these conclusions we can now say \[ p \wedge r \implies q \vee r \\ q \wedge (\lnot p \vee r)) \implies q \vee r \\ then, \\ (p \wedge r) \vee q \wedge (\lnot p \vee r)) \implies q \vee r \text{ Proved} \]

Edit: LOL writing this I realised we could’ve done this at the very start \(((p \vee q) \wedge (\lnot p \vee r)) \implies (q \vee r)\) and taking 2 cases of \(p \equiv T/F\) which woud’ve gave the exact same results without expansion and then contracting (Eq 2 and 3) 🥲

Inference rules for quantified statements

1. \(\forall{x}P(x) \implies P(c)\)
2. \(P(c)\) for an arbitrary \(c \implies\) \(\forall{x}P(x)\)
3. \(\exists{x}P(x) \implies P(c)\) for some element c
4. \(P(c)\) for some element \(c \implies\) \(\exists{x}P(x)\)

With the help of these we can make the inference decisions by combining the rules

Example:

If \(\forall{x}(P(x) \implies Q(x)) \wedge P(a) \implies Q(a)\)

Introduction to Proofs

Some terminology

• Theorem: A statement that can be shown to be true.
• Axioms/Postulates : Statements used in a proof, these are assumed to be true.
• Lemma: A less important theorem that is helpful in a proof of other results.
• Corollary: A theorem that can be established directly from a theorem that has been proved.
• Conjecture: A statement that is being proposed to be true statement, usually on the basis of some partial evidence, a heuristic argument or the intuition.

Methods of Proving Theorems

Direct Proofs

To prove \(p \implies q\), we assume \(p\) is true; subsequent steps are constructed by inference rules following the previous assumption leading to show that \(q\) is also true. Direct proof begin with premise, continue with a sequence of deductions and end with the conclusion.

Example: If \(n\) is an odd integer then, then \(n^2\) is odd

We need to show \(\forall{x}(P(x) \implies Q(x))\) where \(P(x)\) is \(x\) is an odd integer and \(Q(x)\) is \(x^2\) is an odd integer. Going by direct proof we assume, the premise \(P(x)\) is true then \(x = 2k + 1\) then \(x^2 = (2k + 1)^2 = 2(2k^2 + 2k) + 1\) this is by definition the odd integer hence we can say \(Q(x)\) is also True.

Proof by Contraposition

Often times attempt of direct proofs reach dead ends. We need more methods and methods that does not start with premises and end with conclusions are called indirect proofs.

Proof by contraposition is an extremely useful indirect proof method. It use the fact that the conditional statement \(p \implies q\) is equivalent to its contrapositive \(\lnot q \implies \lnot p\).

Example-1: Prove that if \(n\) is an integer and \(3n+2\) is odd then \(n\) is odd

Attempting to do a direct proof here could be assuming the premise that it, \(n\) is an integer and \(3n+2 = 2k + 1\) which gives \(n = \frac{2k-1}{3}\) this is not clear conclusion and kind of a stuck state so we will try by contraposition.

The first step of contraposition is to assume that the conclusion of the statement if false. So we assume \(n\) is even, hence \(n = 2k\), now we can write the premise as \(3n + 2 = 2(3k + 1)\), hence premise is also coming to be even, which is a negation of the premise. So in logic we achieved \(\lnot q \implies \lnot p\) means original statement was correct.

Example-2: Prove that if \(n = ab\) where \(a\) and \(b\) are positive integers then \(a \leq \sqrt{n}\) or \(b \leq \sqrt{n}\)

Lets proceed with contraposition, assuming the conclusion is false means \[ \lnot{Q} = \lnot(a \leq \sqrt{n} \vee b \leq \sqrt{n}) = (a > sqrt{n}) \wedge (b > \sqrt{n}) \] Then we can get \(ab > n\) which shows that \(ab \ne n\) (Negation of the premise) hence we proved \(\lnot Q \implies \lnot P\) hence the assumed hypothesis was false, means original statement was true.

• Vacous and Trivial Proofs: We can quickly prove that a conditional statement \(p \implies q\) is true when we know that \(p\) is false, then we have a proof called vacous proof, often used to establish the special cases of a theorem. We can also quickly show the proof if we know that \(q\) is always true, this is called trivial proof.

• A Little Proof Strategy: Usually for statements like \(\forall{x}(P(x) \implies Q(x))\) start with a direct proof and try to form some deduction about conclusion, if it does not seems to be possible (hypothesis such as \(x\) is irrational or \(x \ne 0\)) that are difficult to reason from are a clue that an indirect proof might be your best bet.

Proof by Contradiction

In such proofs, we first assume the negation of the conclusion. We then use the premise and the negation of the conclusion to arrive at a contradiction. The reason this is valid is because of logical equivalence as \(p \implies q\) and \((p \wedge \lnot q) \implies F\)

Why the above is logically equivalent?

\(p \implies q \equiv \lnot p \vee q\) and $(p q) F (p q) F p q $

To prove an implication \(p \implies q\) by contradiction, assume \(p \wedge \lnot q\). If from these assumptions one can derive a contradiction (⊥), then \(p \implies q\) holds.

Example-1: Show that atleast four of any 22 days must fall on the same day of the week.

Lets first try to form this into \(P \implies Q\) form. We can re-write the sentence as “If there are 22 days chosen then atleast 4 of them must fall on the same day of week”

\(P\): “22 calendar days are selected”

\(Q\): “There exists a weekday on which at least 4 of the selected days fall”

\(Q: \exists{d} \in \{Mon, Tue, ..., Sun\} s.t. \#(d) \geq 4\)

\(\lnot Q: \forall{d}, \#(d)<3\)

So we assume the \(p \wedge \lnot q\) here i.e. there are 22 days selected then Every weekday has at most 3 of the 22 days.. So now since each week has 7 days so total there will be \(7 \times 3=21\) but wait we assumed \(P\) as true that says only 22 days were selected but now we are getting 21? This is the contradiction. Hence our assumption \(\lnot Q\) was False so the original statement is indeed True.

Example-2: Prove that \(\sqrt{2}\) is irrational by giving a proof by contradiction

So assume \(\sqrt{2}\) is a rational number, then we can write \(\sqrt{2} = \frac{p}{q}\) where \(p\) and \(q\) are in simplest form and \(q \ne 0\). Now squaring both sides we get \(2 = \frac{p^2}{q^2}\) now this gave \(p^2 = 2q^2\) which is weird because we already said \(p\) and \(q\) are in the simplest form i.e. they don’t have any common multiple, but here it seems not because if we write \(\frac{p \times p}{q \times q}\) then there should not be anything common, but 2 is comming common from the expression hence this is a contradiction, means assuming negation of conclusion was false, hence \(\sqrt{2}\) is an irrational number.

• Proof by Contraposition as special case of Proof by Contradiction: Proof by contraposition is a special-case of Proof by contradiction, we can re-write the proof by contraposition to contradiction by assuing one more condition. In contraposition to prove \(p \implies q\) we show that \(\lnot q \implies \lnot p\) means we assume the \(\lnot q\) and then leads to prove \(\lnot p\). So if we also assume \(p\) then this will lead to contradiction as we proved \(\lnot p\) but assumed the \(p\) .

• Proving biconditional statements: We can show that \((p \implies q) \wedge (q \implies p)\)

Sometimes a theorem states that several propositions are equivalent. Such a theorem states that all propositions \(p_1,p_2, ..., p_n\) are equivalent. This can be written as \(p_1 \iff p2 \iff ... \iff p_n\) which states that all propositions have same truth values and consequently that for all \(i\) and \(j\) with \(1 \leq i \leq n\) and \(1 \leq j \leq n\) \(, p_i\) and \(p_j\) are equivalent. One way to prove these are mutually equivalent is to the tautology: \[ p_1 \iff p_2 .... \iff p_n \iff (p_1 \implies p_2) \wedge (p_2 \implies p_3) \wedge ... \wedge (p_n \implies p_1) \] This is more efficient than proving all \(p_i\) and \(p_j\) pairs for equivalence. (Not there will be \(n^2 - n\) such conditional statements)

• Counterexamples: Statements like \(\forall{x}P(x)\) we just need to find one counterexample to disprove them.

Proof Methods and Strategy

Proof by cases

In these types of proofs we check the each possible case from domain to exhaust and show that conclusion is true, this is only when its possible i.e. some finite and possibly doable domain.

To prove something \((p_1 \vee p_2 \vee ... \vee p_n) \implies q\) we use the tautology \[ [(p_1 \vee p_2 \vee ... \vee p_n ) \implies q] \wedge [(p_1 \implies q) \wedge (p_2 \implies q) \wedge ... \wedge(p_n \implies q)] \]

Without Loss of Generality

In general, when the phrase “without the loss of generality” is used in a proof (often abbreviated as WLOG) we assert that by proving one case of a theorem, no additional argument is required to proof other specified cases i.e. they follow by making straightforward changes to the argument, or by filling in some straightforward initial steps. Proof by cases can be made much more efficient when the notion of WLOG is employed. Incorrect use of this principle, leads to unfortunate errors.

Existence Proof

A theorem of this type is a proposition of the form \(\exists{x}P(x)\) where \(P\) is the predicate and a proof of proposition of this form is called “existence proof”. Multiple ways to do these proofs, a straightforward is to find the element that satisfies the predicate, this type of proof is called constructive proof.

There are also non-constructive proof, in which most common is to use proof by contradiction, and show that the negation of existential quantification implying contradiction

Uniqueness Proof

Some theorems assert the existence of a unique element with a particular property. To prove such we need to show that such an element exists and no other element is possible.

Proof Strategies

Forward and Backwards Reasoning

In forward reasoning we start with premise, deduce steps and use theorems to reach the conclusion, this is a common reasoning and sometimes it might leave us stuck in complicated results.

In backward reasoning, to prove some statement \(q\), we try to find some statement \(p\) that we can prove with the property \(p \implies q\)

Example-1: For 2 positive real numbers \(x\) and \(y\) the arithmetic mean \(\frac{x+y}{w}\) is always greater than the geometric mean \(\sqrt{xy}\). Prove if its always true.

Lets work backwards, we assume the conclusion and now \[ \begin{aligned} &\frac{x+y}{2} > \sqrt{xy} \\ &\text{which leads to:} \\ &(x-y)^2 > 0 \end{aligned} \] since \((x-y)^2 > 0\) when \(x \ne y\) it follows the final inequality to be true. Now we can use these steps backwards for drafting our proof.

Proof: Suppose \(x\) and \(y\) are distinct positive real numbers. Then \((x-y)^2 > 0\) and solving this we get \(\frac{x+y}{2} > \sqrt{xy}\)