1. Why logic

Why logic?

### What is logic?
**In philosophy:** Logic was formed to "formalise correct argumentation and deduction".
**In mathematics:** Rules of logic are used to distinguish between correct and incorrect mathematical arguments (otherwise known as proofs).

Propositions

Proposition

A proposition is a **declarative sentence** of which we can meaningfully ask whether it is true $(T)$ or false $(F)$.

Sample syntax:

• Propositional / boolean random variables: $\text{Cavity = true}\mapsto \text{cavity}$ $\text{Cavity = false}\mapsto \neg \text{cavity}$
• Discrete random variables (finite or infinite) Given $\text{Weather}$ is one of $\{sunny,rain,cloudy,snow\}$ "$\text{Weather}=rain$" is a proposition
• Continuous random variables (bounded or unbounded) $\text{Temp}=21.6$; $\text{Temp}<22.0$; $\text{Temp}\ge 5.0\text{ AND }\text{Temp}\le 23.0$

Link to original

• Notations for true: $T,1,+$.
• Notations for false: $F,\perp ,0,-$.

For example:

• Today is Monday.
• $2+2=4$
• $2+2=5$

Not declarative:

• Hi, how are you?
• $x+y=4$

Propositional Logic

Propositional logic is the area of logic which deals with propositions, it is sometimes referred to as boolean logic.

Link to original

• We use propositional variables, denoted as lower case letters ($p,q,r$ or $p_1,p_2,..$) to denote propositions whose structure we don’t want to analyse further.
• We build compound expressions called formulas, denoting compound propositions. They are built from logical connectives and parentheses.

We can define a formula as a compound expression made up of propositions, logical connectives and parentheses.

Link to original

2. Logical connectives

Logical Connectives

Logical connective

A logical connective is an expression used to modify a statement or combine two or more statements.

Negation

Negation

Let $p$ be a proposition. The negation of $p$, which is denoted by $\neg p$, is the proposition that "it is not the case that $p$".

$$v(\neg A)=\{\begin{array}{ll}0,& \text{if }v(A)=1\\ 1,& \text{if }v(A)=0\end{array}$$

$p$	$\neg p$
T	F
F	T

For example:

• Let $p$ be that “Today is Tuesday”.
• $\neg p$ means “It is not the case that today is Tuesday”.
  • Or otherwise “Today is not Tuesday” or “It is not Tuesday today”.

Link to original

Conjuction

Conjunction

Let $p$ and $q$ be propositions. The conjunction of $p$ and $q$, denoted by $p\wedge q$, is the proposition that "$p$ and $q$".

$$v(A\wedge B)=\{\begin{array}{ll}1,& \text{if }v(A)=1\text{ and }v(B)=1\\ 0,& \text{if }v(A)=0\text{ or }v(B)=0\end{array}$$

$p$	$q$	$p\wedge q$
T	T	T
T	F	F
F	T	F
F	F	F

For example:

• Let $p$ be that “Today is Tuesday”.
• Let $q$ be that “It is raining today”.
• $p\wedge q$ is that “Today is Tuesday and it is raining today”.

But in English, $p \wedge q$ and $q \wedge p$ do not always mean the same thing.
- "Bob became sick and he visited the doctor."
- "Bob visited the doctor and he became sick."
 
This can be handled by dynamic conjunctions.

Link to original

Disjunction

Disjunction

Let $p$ and $q$ be propositions. The disjunction of $p$ and $q$, denoted by $p\vee q$, is the proposition that "$p$ (inclusive) or $q$".

$$v(A\vee B)=\{\begin{array}{ll}1,& \text{if }v(A)=1\text{ or }v(B)=1\\ 0,& \text{if }v(A)=0\text{ and }v(B)=0\end{array}$$

$p$	$q$	$p\vee q$
T	T	T
T	F	T
F	T	T
F	F	F

For example: “Students who have taken either maths of physics A-levels are admitted.”

Exclusive OR

$p$	$q$	$p\oplus q$
T	T	F
T	F	T
F	T	T
F	F	F

Link to original

Conditional Statements

Conditional statement

Let $p$ and $q$ be propositions. The conditional statement $p\to q$, is the proposition that "if $p$ then $q$". This is also called an implication.

$$v(A\to B)=\{\begin{array}{ll}1,& \text{if }v(A)=0\text{ or }v(B)=0\\ 0,& \text{if }v(A)=1\text{ and }v(B)=0\end{array}$$

$p$	$q$	$p\to q$
T	T	T
T	F	F
F	T	T
F	F	T

For example:

• If it is sunny today, we will go to the beach.
• If I am elected, I’ll lower taxes.

You may encounter some weird statements which are still true.
- "If the Moon is made of green cheese then $2\times2=5$." $(F \rightarrow F)$.
- "If the Moon is made of green cheese then $2\times2=4$." $(F \rightarrow T)$.
- "If London is in the UK then $2\times2=4$." $(T \rightarrow T)$.
  This is also known as irrelevant logic.

Link to original

Biconditional Statements

Biconditional statement

Let $p$ and $q$ be propositions. The biconditional statement $p⟺q$, is the proposition that "$p$ if and only if $q$". This is also called an bi-implication or an equivalence.

$$v(A⟺B)=\{\begin{array}{ll}1,& \text{if }v(A)=v(B)\\ 0,& \text{if }v(A)\ne v(B)\end{array}$$

$p$	$q$	$p⟺q$
T	T	T
T	F	F
F	T	F
F	F	T

There are some implicit uses of biconditional statements in English, for example:
- If you finish your meal then you can have desert, $p \rightarrow q$.
 
But we actually mean $p \iff q$:
- You can have desert if and only if you finish your meal.

Link to original

Link to original

Link to original

3. Tautologies, Satisfiability and Consistency

Tautologies, Satisfiability and Consistency

Computing truth tables of compound formulas

Given the formula: $(p\to (q\wedge r))\to ((p\wedge q)\to \neg r)$

• It has $2^3=8$ rows as it contains $3$ variables.

$p$	$q$	$r$	$\neg r$	$p\wedge q$	$(p\wedge q)\to (\neg r)$	$q\wedge r$	$p\to (q\wedge r)$	$(p\to (q\wedge r))\to ((p\wedge q)\to (\neg r))$
F	F	F	T	F	T	F	T	T
F	F	T	F	F	T	F	T	T
F	T	F	T	F	T	F	T	T
F	T	T	F	F	T	T	T	T
T	F	F	T	F	T	F	F	T
T	F	T	F	F	T	F	F	T
T	T	F	T	T	T	F	F	T
T	T	T	F	T	F	T	T	F

Precedence of logical operators

We have to use parantheses to not create confusion, for example $p\wedge q\vee r$ can have two different truth tables depending on how you parse it. To reduce the number of brackets, we agree $\neg$ takes priority, for example $\neg p\wedge q$ means $(\neg p)\wedge q$.

Propositional satisfiability

Tautology

A tautology (otherwise known as valid) is a formula that is true under all [[Interpretation|interpretations]], every row in a truth table of a tautology makes it true.

We can denote a tautology by $\boxed{\models x}$, where $x$ is a formula which is a tautology.

$p$	$\neg p$	$p\vee \neg q$
T	F	T
F	T	T

Given the set of formulas, $\Delta = \{ A_1, A_2, A_3 \}$, provided $\Delta \models \varphi$:
 
$$
	\begin{aligned}
		\Delta &\models \varphi \\
		A_1, A_2, A_3 &\models \varphi \\
		A_1 \land A_2 \land A_3 &\models \varphi \\
		A_1 , A_2 &\models A_3 \rightarrow \varphi \\
		A_1 &\models A_2 \rightarrow (A_3 \rightarrow \varphi) \\
		\emptyset &\models A_1 \rightarrow (A_2 \rightarrow (A_3 \rightarrow \varphi)) \\
	\end{aligned}
$$

Link to original

Contradiction

A contradiction is a formula that is false under all [[Interpretation|interpretations]].

$p$	$\neg p$	$p\wedge \neg q$
T	F	F
F	T	F

Link to original

Satisfiable

A formula $F$ is satisfiable if there is an interpretation $v$ that makes the formula $F$ true. We say $v$ satisfies $F$.

$p$	$\neg p$
T	F
F	T

A set $S=\{A_1,...,A_n\}$ of propositional formulae is satisfiable if there is an interpretation $v$ satisfying every formula in $S$.

Link to original

Consistency

Consistent

A collection of formulas is consistent if: ?

• Not only each and every formula in the collection is satisfiable.
• It is possible to find a truth table assignment with the propositional variables in them that make all of the formulas true at the same time.

Link to original

Given the following specifications:
- Message is stored in buffer or it is trasmitted. $p\vee q$
- Message is not stored in buffer. $\neg p$
- Message is stored in buffer then it is trasmitted. $p \rightarrow q$
 
|  $p$  |  $q$  | $p \vee q$ | $\neq p$ | $p\rightarrow q$ |
|:-----:|:-----:|:----------:|:--------:|:----------------:|
|   T   |   T   |     T      |    F     |        T         |
|   T   |   F   |     T      |    F     |        F         |
|  *F*  |  *T*  |   **T**    |  **T**   |      **T**       |
|   F   |   F   |     F      |    T     |        T         |

Link to original

4. Logical equivalence

Logical equivalence

Logically equivalent

Two formulae that have the same truth values in all possible cases are logically equivalent, denoted by $p\equiv q$.

For example, $p\to q$ and $\neg p\vee q$.

$p$	$q$	$\neg p$	$p\to q$	$\neg p\vee q$
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

This is not a logical connective but just a shorthand.

$p$ and $q$ are logically equivalent if and only if the formula $p⟺q$ is a [[Tautology|tautology]].

Link to original

List of well-known equivalences

You do not need to memorise these for the exam.

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[19],
	"scale":1.5
}

Link to original

5. Logically correct arguments

Logically correct arguments

Argument

An argument is a sequence of [[Proposition|propositions]].

$$\begin{array}{rlrl}& \underline{\begin{array}{l}{p}_1\\ p_2\\ ..\\ p_n\end{array}\}}& & n\text{ premises}\\ \therefore & q& & \text{one conclusion}\end{array}$$

You can read ”$p_1,p_2,...,p_n$, therefore $q$”.

Link to original

Logically correct

An argument is logically correct if in every situation that makes all premises true, the conclusion is true as well.

$$\boxed{\begin{array}{r}\underline{\begin{array}{l}{p}_1\\ p_2\\ ..\\ p_n\end{array}}\\ q\end{array}}\text{ is logically correct}⟺\text{the formula }(p_1\wedge p_2\wedge p_3\wedge ..\wedge p_n)\to q\text{ is a tautology}$$ Link to original

Situation

A situation is a row in the truth table of $p_1, p_2, .., p_n, q$ or otherwise a possible assignment for the propositional variables in $p_1, p_2, .., p_n, q$.

Link to original

Examples

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[21,22],
	"scale":1.5
}

Rules of inference

Inference rule

An inference rule is a representation of a valid step in a formal proof, indicating the conditions that must be satisfied before a conclusion can be obtained in the proof.

A rule will be presented in the form: $R:\frac{A_1,A_2,...,A_n}{B}$

$A_1,A_2,...,A_n$ are the premises or conditions of the rule, and $B$ is the conclusion.

Informally, $R:$ “if $A_1,A_2,...,A_n$ are true, then $B$ is also true.”

Alternatively, we use the syntax:

$$\begin{array}{c}{A}_1\\ A_2\\ ⋮\\ A_n\\ B\end{array}$$Link to original

We can always use a truth table to decide whether an argument is correct. This can be very tedious.

If we consider $10$ different variables, the truth table requires $2^{10}=1024$ rows.

Instead, we can establish the correctness of simple argument forms using rules of inference, and then use them to construct more complicated correct arguments.

For example, Modus ponens (the rule of detachment).

$$\begin{array}{llc}& p\to q& \text{If it snows today, then we will go skiing.}\\ & p& \text{It snows today.}\\ & & \\ \therefore & q& \text{We will go skiing.}\end{array}$$

Examples

Should practice trying to justify these!
There will be no exam Q in this module for building these, no need to memorise.

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[24],
	"scale":1.5
}

Link to original

6. Predicate logic basics

Predicate logic basics

Statements involving variables such as:

• $x>3$
• $x=y+4$
• Printer $x$ is networked to computer $y$.

Are quite often found in different places but these statements are neither true or false. As well as this, the variables $x$ and $y$ are not propositional variables but instead denote entities, which are things or objects.

We can formalise "$x>3$" as $\boxed{P(x)}$ where $x$ is a variable and $P$ is the predicate (property), which in this case is that it is “greater than 3”.

• By assigning a value (a concrete entity) to the variable, $P(x)$ becomes a proposition that has a truth value.
  • $P(5)$ means $5$ is greater than $3$ $⇝$ T
  • $P(1)$ means $1$ is greater than $3$ $⇝$ F
• We typically use upper case letters ($P,Q,A,B$) to denote predicates.

To formalise a statement such as "$x=y+4$", we use the predicate $Q(x,y)$, where:

• $x$ and $y$ are variables.
• $Q$ is the predicate connecting two things (otherwise called a binary predicate).
  • “the first number is the sum of the second number and $4$”
  • $Q(5,1):5=1+4⇝T$
  • $Q(6,6):6=6+4⇝F$

Link to original

7. Quantifiers

Quantifiers

Quantification is another way of creating a proposition from $P(x)$, it expresses the extent to which a predicate is true over a range of entities, called the domain.

Universal quantifier, $\forall$.

Universal quantifier

The universal quantification of $P(x)$ for a particular domain, denoted by $\forall xP(x)$, is the proposition "$P(x)$ is true for all values of $x$ from the domain". $\forall$ means "For all".

• The truth value of $\forall xP(x)$ might change if domain changes.
• Domain must always be specified when universal quantifier is used.

For example, take $P(x)$ is "$x>0$":

• For the domain of positive integers, $\forall xP(x)⇝T$.
• For the domain of all integers, $\forall xP(x)⇝F$.

To say “Everyone does not like Jane”, we write that for every $x$, $x$ does not like Jane:

$$(\forall x)(\neg Likes(x,jane))$$

In general, the notation for universal quantifiers is $(\forall x)(\phi)$ where $\phi$ is a formula in which $x$ and possible other variables may appear.

Link to original

Rules of inference ($\forall$)

Universal instantiation

A universal instantiation means for each and every entity $c$ in the domain we have a correct inference rule of the form: $$\boxed {\begin{array}{c}\underline{\forall xP(x)} \\P(c)\end{array}}$$

For example,

$$\begin{array}{lc}& \underline{\text{Everyone in the class is feeling miserable today.}}\\ \therefore & \text{Agi is feeling miserable today.}\end{array}$$

By universal instantiation, given the premise $(\forall x)\varphi (x)$, we may derive the conclusion $\varphi (x/t)$, where $t$ is any object in the domain:

$$\frac{(\forall x)\varphi (x)}{\varphi (x/t)}(\text{UI})$$

If $\varphi (x)$ holds for all the elements of the domain, it holds in particular for the element $t$ as well. Universal instantiation can be seen as $\forall$-elimination.

Link to original

Universal generalisation

A universal generalisation is $$ \boxed{\begin{array}{c} \underline{P(c) \textsf{ for any arbitrary entity } c \textsf{ in the domain}} \\ \forall x P(x)\end{array}} $$

By universal generalisation, given the premise $\varphi (x/t)$ takes place for a generic object $t$ of the domain, we may derive $(\forall x)\varphi (x)$:

$$\frac{\varphi (x/t)}{(\forall x)\varphi (x)}(\text{UG})$$

The object $t$ in the premise of $(\text{UG})$ must not be specific but arbitrary, i.e. we cannot make any assumption about $t$ other than it comes from the domain. Universal generalisation can be seen as $\forall I$.

Link to original

Existential quantifier, $\exists$.

Existential quantifier

The existential quantification of $P(x)$ for a particular domain, denoted by $\exists xP(x)$, is the proposition that "there exists a value for $x$ in the domain such that $P(x)$ is true".

• The truth value of $\exists xP(x)$ might change when domain changes.
• Domain must always be specified when used.

For example, take $P(x)$ is "$x<-3$":

• If the domain is all integers, then it is true.
  • We simply need to give one example, such as $x=-5$ then $P(-5)$ is true.
• If the domain is the positive integers, then it is false.

To say “(at least one) car is yellow”, we write that for some $x$, $x$ is yellow:

$$(\exists x)(Colour(x,yellow))$$

In general, the notation for existential quantifiers is $(\exists x)(\phi)$, where $\phi$ is a formula in which $x$ and possible other variables may appear..

Link to original

Rules of inference ($\exists$)

Existential generalisation

An existential generalisation means that for every entity $c$ in the domain, we have a correct inference rule of the form $$ \boxed{ \begin{array}{c} \underline{P(c)} \\ \exists x P(x) \end{array} } $$

For example:

$$\begin{array}{lc}& \underline{\text{Marla is reading the lecture notes.}}\\ \therefore & \text{There is someone in the class reading the lecture notes.}\end{array}$$

By existential generalisation, given that $\varphi (x/t)$ is known to hold for a particular object $t$ of the domain, we may derive $(\exists x)\varphi (x)$:

$$\frac{\varphi (x/t)}{(\exists x)\varphi (x)}(\text{EG})$$

This can be seen as $\exists I$.

Link to original

There are also deMorgan laws for quantifiers.

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[32],
	"scale":1.5,
	"rect":[40, 260, 40, 400]
}

Link to original

8. Theorems and proofs

Theorems and proofs

Theorem

A theorem is when a proposition can be shown to be true and is important enough.

Link to original

A proof of a theorem, $t$, is a sequence of propositions ending with $t$:

$$\begin{array}{rlrl}& \underline{\begin{array}{l}{p}_1\\ p_2\\ ..\\ p_n\end{array}\}}& & n\text{ premises}\\ & q& & \end{array}$$

Such that each and every of the premises is:

• Either an axiom.
• Or can be obtained from earlier premises in the sequence by a logically correct argument.

It is said that theorem $t$ follows from the axioms.

How are theorems stated

Many theorems assert that a property holds for all entities in a domain. The precise statement must include a universal quantifier, standard convention in mathematics is to omit it.

• The statement “if $x>5$, where $x$ is a positive integer, then $x^2>30$”
• Means that “for all positive integers $x$, if $x>5$, then $x^2>30$”

Link to original

9. Direct and indirect proofs

Direct and indirect proofs

Direct Proofs

Used to prove theorems of the form $\forall x(A(x)\to B(x))$:

• We choose an arbitrary entity from the domain.
  • Must be arbitrary, not specific but in the domain.
  • We need to use a pointer to refer to it.
  • We can pick any symbol to refer to it.
• Then we prove the conditional statement $A(y)\to B(y)$ for the arbitrary $y$ by a direct proof:
  • Assume $A(y)$ is true, use axioms, definitions and previously proven theorems, with inferences, to show that then $B(y)$ must also be true.
• We can then apply the rule of universal generalisation.

For example, given the theorem “If $n$ is an odd integer, then $n^2$ is odd”, the proof is:

• Let $n$ be an arbitrary integer.
• Assume $n$ is odd.
• Since $n$ is odd, let $n=2k+1$.
• Hence, $\begin{array}{rl}{n}^2& =(2k+1{)}^2\\ & =4k^2+2k+2k+1\\ & =4k^2+4k+1\\ & =2(2k^2+2)+1\text{ which is odd }\because 2n(..)\text{ even and}+1\text{ makes it odd}\end{array}$
• $\therefore$ $n^2$ must be odd if $n$ is an odd integer.

Indirect Proof

For example, show that at least $4$ of any $22$ dates in the calendar must fall on the same day of the week. We can try a proof by contradiction, which does not prove a result ‘directly’.

• Let $p$ be “at least $4$ of $22$ chosen dates fall on the same day of the week”.
• Suppose that $\neg p$ is true, that means “at most $3$ of $22$ chosen dates fall on the same day of the week”.
• We know that there are 7 days of the week, this implies at most $21$ dates could have been chosen, as for each of the $7$ days of the week, at most $3$ of the chosen dates could fall on that day.
• So, if $q$ is the statement that ”$22$ dates are chosen” then we found that $\neg p\to \neg q$.
• Using $q$ as a premise, we reached a contradiction by showing $(q\wedge \neg p)\to (q\wedge \neg q)$.
• We find that $q\wedge \neg q$ is a contradiction, it will always be false.
• As $q$ is true (our premise), $q\wedge \neg p$ can only be false when $\neg p$ is false, hence $p$ is true.

Link to original

10. Mistakes in proofs

Mistakes in proofs

Example 1

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[38],
	"scale":1.5
}

Example 2

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[39],
	"scale":1.5
}

Link to original

11. Proofs by induction

Proofs by induction

To prove a property $P(n)$ is true for all positive integers $n$, we:

• Basis step: Prove that $P(1)$ is true.
• Inductive step: Prove that the conditional statement $P(k)\to P(k+1)$ is true for all positive integers $k$.

To complete the inductive step of a proof by induction,

• assume that $P(k)$ is true for an arbitrary positive integer $k$
• show that under this assumption, $P(k+1)$ must also be true

The inductive hypothesis (IH) is the assumption that $P(k)$ is true.

Example

Show that for every positive integer, $n$, that $1+2+...+n=\frac{n(n+1)}{2}$.

• Basis step: $P(1)$ is true, because $1=\frac{1(1+1)}{2}$.
• Inductive step: For the inductive hypothesis, we assume that $P(k)$ holds for an arbitrary positive integer $k$. $$1+2+...+k=\frac{k(k+1)}{2}\text{ (IH)}$$

$$Underthisassumption:$$

\begin{aligned} \boxed{1 + 2 + … + (k + 1)} &= (1 + 2 + … + k) + (k + 1) \ &\stackrel{\textsf{by IH}}{=} \frac{k(k+1)}{2} + (k + 1) \ &= \frac{k(k + 1) + 2(k + 1)}{2} \ &= \frac{(k + 2)(k + 1)}{2} \ &= \boxed{ \frac{ (k + 1)((k + 1) + 1) }{2} } \end{aligned}

Link to original

12. The Simple Two Colour Theorem

The Simple Two Colour Theorem

title: Not on exam!

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[43,44],
	"scale":1.5
}

Link to original

13. All horses have the same colour

All horses have the same colour

title: Not on exam!

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[45],
	"scale":1.5
}

Take $k=1$, substitute into inductive step, find no overlap.

Link to original