Implication Let p and 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.
Converse: The conditional statement \(q \implies p\) is called converse.
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\)”
\(\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 conjunction and \(\exists\) over disjunction, however we cannot distribute \(\forall\) over disjunction nor can we distribute \(\exists\) over conjunction
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.
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
\(\forall{x}P(x) \implies P(c)\)
\(P(c)\) for an arbitrary \(c \implies\)\(\forall{x}P(x)\)
\(\exists{x}P(x) \implies P(c)\) for some element c
\(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 \(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”
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 p_2 \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. (Note 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.
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}{2}\) is always greater than the geometric mean \(\sqrt{xy}\). Prove if its always true.
Lets work backwards, we assume the conclusion and now \[
\begin{gathered}
\frac{x+y}{2} > \sqrt{xy} \\
\text{ which leads to: } \\
(x-y)^2 > 0
\end{gathered}
\] 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}\)
Tiling
This will be an example where we will analyze the checkerboard tiling and try to answer/proof some conjectures. A checkerboard is a rectangle divided into squares of the same size by vertical and horizontal lines. A domino is a rectangular piece that is 1x2 or 2x1 squares, we say a board is tiled by dominos when all its squares got covered with no overlapping dominoes and no dominoes overhanging the board.
checkerboard
Example: Can we tile the standard 8x8 checkerboard using dominoes?
Solution: We can find multiple such ways, 32 dominoes plaed veritically can be the one or 32 placed horizontally. For a constructive proof any of the found way proves the conjecture.
Example: Can we tile a board obtained by removing one of the four corner squares of a standard checkerboard?
Solution: Removing one square means now we left with 63, and tiling says no domino should overlap or overhang and each domino cover 2 squares hence we can only cover an even number of square. So we can prove by contradiction that this checkerboard cannot be tiled.
Example: Can we tile the board obtained by deleting the upper left and lower right corner squares of a standard checkerboard?
Solution: In this setting the tiles are still even \(64-2=62\) but we need to be careful. First it might not be a good idea to try proving this exhaustively, we need another method so we can color the checkerboard alternatively with a different color and apply logic.
Proof: Suppose we can use dominoes to tile this checkerboard with opposite squares removed. This checkerboard contains \(64-2=62\) squares and the tiling would use \(62/2=31\) dominoes. Note that each domino covers 1 black and 1 white hence the tiling will cover \(31\) black and \(31\) white squares. However when removing the opposite corner squares the checkerboard is left with either “\(32\) white squares and \(30\) black” or “\(32\) black squares and \(30\) white”. This contradicts the assumption that we can tile this checkerboard.
Example: Lets talk about triminoes as shown in the following figure, An 8x8 checkerboard with one of its corner square removed has \(63\) squares and \(63/3=21\) so it seems a tiling by straight trimiones might exist but when we tried we aren’t able to find one. Exhaustive proves isn’t practical so can we apply the above learnt technique here to prove? (Note: Only by straight triminoes)
Solution: So lets color the checkerboard with 3 alternative colors, blue, black and white as shown in figure below
Here we can see that there are 21 blue, 20 black and 22 whites with each color is on the corner. We need to understand something crucial here (as we are hoping this method might work)
One coloring gives unequal counts \(\rightarrow\) tiling is definitely impossible
All colorings give equal counts \(\rightarrow\) this method is inconclusive, not proof of possibility
Proof (by contradiction):
Assume a valid tiling exists.
Step 1 — Set up the coloring. Assign each square a color based on its diagonal: color = \((i + j) \mod 3\). This splits the 64 squares into three groups of sizes 21, 21, and 22.
Step 2 — Choose the labeling. Look at which diagonal group the removed corner belongs to. Label that group “blue.” Label the group of 22 as “white.” Label the remaining one “black.” After removing the corner, the remaining 63 squares have counts: 20 blue, 21 black, 22 white.
Step 3 — The contradiction. Every straight triomino (three in a row, horizontal or vertical) covers exactly one square from each of the three diagonal groups — so one blue, one black, one white. If a valid tiling with 21 triominoes existed, it would need exactly 21 of each color. But we have 20 blue, 21 black, 22 white. That’s a contradiction.
Conclusion: No such tiling exists. \(\blacksquare\)
