---
# System prepended metadata

title: '[Notes](#fn1): Problem Class, 8 Oct'

---

# [Notes](#fn1): Problem Class, 8 Oct
> Group 11 -- Problem Class, MATH40001/40009 IUM
> Stergios M. Antonakoudis (stergios@imperial.ac.uk)

</br>

Welcome to IUM Problem Class Group 11. The focus of our discussion for today's class is on Problem Sheet 1 of Part I.

[^1]: <small> *These notes[^1] were typed up and created during and for the purposes of the discussion in the online session of Problem Class on MS Teams, similar to the use of a 'whiteboard',* </small>

---

## A brief overview

<u>**_Propositions_**</u>: True (1) and/or False (0) statements.           

<u>**_Operations_** *(on propositions)*</u>: i.e. combining propositions to build new propositions.

<u>**_Examples_** *(of operations)*</u>: Given propositions P and Q, we *define* (i.e. in lectures) ==new== propositions $\lnot P$, $P \land Q$, $P \lor Q$ and $P \implies Q$.


#### What does $P \implies Q$ mean?

Well, it is a proposition *i.e. a statement with a True or False value*. 
It is False (**_only_**) when the proposition $P$ is True and the proposition $Q$ is false and it is True otherwise (i.e. in all other cases for $P$ & $Q$).

In particular, we observe that $P \implies Q$  is True --- *by definition* --- whenever the proposition $P$ is false, regardless of the value of $Q$.

An equivalent way to express $P \implies Q$ is using $\lnot P \lor Q$. 
One way to prove that these two propositions are indeed equivalent is to write down the truth table for $P$ and $Q$ and check the True or False values of $P \implies Q$ and $\lnot P \lor Q$. 

A concise way to express the two are equivalent is to write:\
The proposition $(P \implies Q) \iff (\lnot P \lor Q)$ is True.

---

Truth table for $P$, $Q$, $P \implies Q$, $\lnot P \lor Q$ & $\lnot (P \implies Q)$.


$$ \rule{\hr}{0.4pt} $$


$$
\begin{array}{|c|c|c|c|c|} \hline
P & Q & P \implies Q & \lnot P \lor Q & \lnot (P \implies Q) \\ \hline
0&0&1&1&0\\
0&1&1&1&0\\
1&0&0&0&1\\
1&1&1&1&0 \\ \hline
\end{array}
$$

---

The following are (always) true (propositions):
$$1. \quad (P \implies Q) \iff (\lnot P \lor Q) $$
$$2. \quad \lnot (P \implies Q)  \iff \lnot (\lnot P \lor Q )$$

$$3. \quad \lnot (P \implies Q)  \iff P \land \lnot Q$$
because $$ \lnot (\lnot P \lor Q ) \iff P \land \lnot Q $$

---

**Problem 4 (a)**

 Is it possible to find three true-false statements P, Q and R, such that
 (P∨Q∨R)∧(¬P∨Q∨R)∧(¬P∨¬Q∨R)∧(¬P∨¬Q∨¬R)
 is true?
 
**Ideas (pre solution to 4(a))**

*GOAL*: Find true-or-false values for P, Q, R
so that all four of the following are true:

(P∨Q∨R), (¬P∨Q∨R), (¬P∨¬Q∨R) and (¬P∨¬Q∨¬R)

*Interlude: Is it possible to find true-false statement P so that P and ¬P are both true?* **NO**

**Solution to 4(a)**

If P is false, then ¬P is true; hence (¬P∨¬Q∨R) and (¬P∨¬Q∨¬R) are both true (-- regardless of whether Q and R are true or false).
(*See lectures notes*: "true ∨ Q" is "true" etc).
Likewise, if Q is true, then (P∨Q∨R) and (¬P∨Q∨R) are both true (-- regardless of whether P and R are true or false).

Therefore, when P=false, Q=true and R=true (or false), the proposition (P∨Q∨R)∧(¬P∨Q∨R)∧(¬P∨¬Q∨R)∧(¬P∨¬Q∨¬R) is true!

**QED** 


---

**Problem 5**
You need to use **INDUCTION**.

---
