[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) 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]: *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',* --- ## A brief overview **_Propositions_**: True (1) and/or False (0) statements. **_Operations_** *(on propositions)*: i.e. combining propositions to build new propositions. **_Examples_** *(of operations)*: 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**. ---