Week 4 Miscellany

The person next to me in tutorial asked if associativity worked between conjunction and disjunction. For example:
\[ P \wedge (Q \vee R) \overset{?}{\Leftrightarrow} (P \wedge Q) \vee R \]At first, I said "sure, why not?" not really thinking about it, but really, the two expressions mean different things.
\[ P \wedge (Q \vee R) \Leftrightarrow (P \wedge Q) \vee (P \wedge R) \\

(P \wedge Q) \vee R \Leftrightarrow (P \vee R) \wedge (Q \vee R)\]Namely, the second one is true whenever \(R\) is true. As a truth table,
\[\begin{array}{c c c | c | c}
P & Q & R & P \wedge (Q \vee R) & (P \wedge Q) \vee R \\ \hline
T & T & T & T & T \\
T & T & F & T & T \\
T & F & T & T & T \\
T & F & F & F & F \\
F & T & T & F & T \\
F & T & F & F & F \\
F & F & T & F & T \\
F & F & F & F & F \\
\end{array}\]Good to know.

Week 3

This past week focussed on conjunction, disjunction, negation, and implication. 

While I find conjunction and disjunction pretty straightforward, implication, in this context, doesn't come as readily. I learn best by writing things out and working through them, so that's what I'm going to do for implication.

The truth table for the implication \( P \Rightarrow Q \) is:
\[
\begin{array}{ r  r | c }

P & Q & P \Rightarrow Q \\ \hline

T & T & T \\

T & F & F \\

F & T & T \\

F & F & T \\
\end{array}\] As given in class, we also have \[ P \Rightarrow Q \;\Leftrightarrow\; \neg P \vee  Q\]
With the above we can check that the contrapositive is the same as the regular implication:
\[\begin{align*}

\neg Q \Rightarrow \neg P &\;\Leftrightarrow\; \neg \neg Q \vee \neg P \\
&\;\Leftrightarrow\; Q \vee \neg P \\
&\;\Leftrightarrow\; \neg P \vee Q
\end{align*}\]
Next, let's translate an equivalence into conjunction and disjunction, starting by splitting the bi-implication into two implications:
\[\begin{align*}

P \Leftrightarrow Q &\;\Leftrightarrow\; ( P \Rightarrow Q ) \wedge (Q \Rightarrow P \\

&\;\Leftrightarrow\; (\neg P \vee Q) \wedge (\neg Q \vee P)\\

&\;\Leftrightarrow\; (\neg P \wedge \neg Q) \vee (\neg P \wedge P) \vee (Q \wedge \neg Q) \vee (Q \wedge P)\\

&\;\Leftrightarrow\; (\neg P \wedge \neg Q) \vee (P \wedge Q)


\end{align*}\]What about the transitive property?
\[\begin{align*}
((P \Rightarrow Q) \wedge (Q \Rightarrow R)) &\;\Rightarrow\; (P\Rightarrow R)\\

(\neg P \vee Q) \wedge (\neg Q \vee R) &\;\Rightarrow\; (\neg P \vee R)\\

\neg ((\neg P\vee Q) \wedge (\neg Q \vee R) &\;\,\vee\; (\neg P \vee R)\\

\neg(\neg P\vee Q) \vee \neg(\neg Q \vee R) &\;\,\vee\; (\neg P \vee R)\\

(P \wedge \neg Q) \vee (Q \wedge \neg R) &\;\,\vee\; (\neg P \vee R)\\

\end{align*}\]
as a truth table:
\[\begin{array}{c c c | c c c | c }
P & Q & R & (P \wedge \neg Q) & (Q \wedge \neg R) & (\neg P \vee R) & (P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (\neg P \vee R)\\\hline
T & T & T & F & F & T & T \\
T & T & F & F & T & F & T \\
T & F & T & T & F & T & T \\
T & F & F & T & F & F & T \\
F & T & T & F & F & T & T \\
F & T & F & F & T & T & T \\
F & F & T & F & F & T & T \\
F & F & F & F & F & T & T \\

\end{array}\]So it's a tautology. Great. (It would have been easier to just go straight to a truth table, but let's call it "good practice").

Finally, how does it look for \( P\Rightarrow (Q\Rightarrow R)\)?
\[\begin{align*}
P\Rightarrow (Q\Rightarrow R) &\;\Leftrightarrow\; \neg P \vee (\neg Q \vee R) \\

&\;\Leftrightarrow\; (\neg P \vee \neg Q) \vee R \\

&\;\Leftrightarrow\; \neg (P \wedge Q) \vee R \\
&\;\Leftrightarrow\; (P \wedge Q) \Rightarrow R\\

\end{align*}
\]
That's all I can really think of right now. A lot of this stuff is easier to show by just writing up a truth table, but I learn better if I can think about things multiple ways. Also, a truth table would show that \[ P \Rightarrow (Q \Rightarrow R)) \;\Leftrightarrow\; (P\Rightarrow R) \vee (Q\Rightarrow R)\] but I haven't figured out how to get there by manipulating terms.

Let's be precise.

We're now a week into the course, and we've been talking a lot about sets and statements about sets. A lot of this has revolved around English language or Python statements about sets, such as 

     not all({x in S2 for x in S1})

And

      Some male employee earns over 42,000.


While discussing sets in a way any English speaker might understand is useful, it helps me, personally, to put such statements into the cold, precise language of math.

Towards this goal, we'll start off by introducing some terminology. Then we'll move to applying the terminology to statements encountered in class. Finally we'll end with a brief discussion of why this sort of thing is useful.

Terminology

We'll use the standard \(\cup\) and \(\cap\) to denote set union and intersection, respectively. In other words: 
$$ \begin{align*} x \in A \cup B & \; \Leftrightarrow \; x \in A \text{ or } x \in B\ \\ x \in A \cap B & \; \Leftrightarrow \; x \in A \text{ and } x \in B \end{align*} $$
We'll also use \(\overline{X}\) to denote the complement of \(X\) (that is, not \(X\)), and \(\varnothing\) to denote the empty set.

The Meat

With this terminology, it's not too hard to translate statements used in the course. We'll be talking about two sets, \(S_1\) and \(S_2\).
$$\begin{align*} \text{''all } S_1 \text{ in } S_2 \text{''} & \;\Leftrightarrow\; S_1 \cap S_2 = S_1 \\ \text{''some/any } S_1 \text{ in } S_2 \text{''}  &\; \Leftrightarrow\; S_1 \cap S_2 \neq \varnothing  \\ \text{''no/none } S_1 \text{ in } S_2 \text{''} &\;\Leftrightarrow\; S_1 \cap S_2 = \varnothing \end{align*}$$ Negating these is easy—switch \( = \) to \(\neq\) and vice versa:
$$\begin{align*} \text{''not all } S_1 \text{ in } S_2 \text{''} & \;\Leftrightarrow\; S_1 \cap S_2 \neq S_1 \\ \text{''not some/any } S_1 \text{ in } S_2 \text{''}  &\;\Leftrightarrow\; S_1 \cap S_2 = \varnothing  \\ \text{''not no/none } S_1 \text{ in } S_2 \text{''} &\;\Leftrightarrow\; S_1 \cap S_2 \neq \varnothing \end{align*}$$ 
Applied to the statement at the beginning, "Some male employee earns over $42,000", we have, with \(M\) as the set of male employees and \(O\) as the set of employees earning over $42,000, 
$$ M \cap O \neq \varnothing$$
This also allows us to evaluate nonsense like "Not some not male employees earn not more than $42,000":
$$ \overline{M} \cap \overline{O} = \varnothing \; \Leftrightarrow \; F \cap L = \varnothing$$
where we have used (keeping in mind that the complement means "not", in a sense) \(F\) as the set of female employees (assuming all non-male employees are female) and \(L\) as the set of employees earning less than $42,000. In plain language, we have the statement "No female employees earn less than $42,000". 

Finally, an added bonus is that this way of thinking makes Venn diagrams damn easy.

It's a lot easier to translate a statement like "some male employees earn more than $42,000" onto the diagram now. Let the set of male employees be \(S_1\) and the set of high earners be \(S_2\). Then we have \(S_1 \cap S_2 \neq \varnothing\). In other words, the middle region must be occupied.

If you have any questions/thoughts or see any errors, leave me a comment.