EE 364 Supplemental – Week 01
Logical Operations
Q: What is truth?
A: A function, \(t: \{\text{statements}\} \to \{0, 1\}\).
Compare: knowledge = justified true belief.
\(P\) and \(Q\) are statements with truth value \(T\) or \(F\).
Logical Connectives
AND: \[ t(P \mathbin{\&} Q) = \min(t(P), t(Q)) \]
| \(P\) | \(Q\) | \(P \mathbin{\&} Q\) |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 0 | 0 |
OR: \[ t(P \lor Q) = \max(t(P), t(Q)) \]
| \(P\) | \(Q\) | \(P \lor Q\) |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 0 | 0 |
NOT: \[ t(\sim P) = 1 - t(P) \]
| \(P\) | \(\sim P\) |
|---|---|
| 1 | 0 |
| 0 | 1 |
IMPLICATION: \[ t(P \to Q) = \min(1,\; 1 - t(P) + t(Q)) \]
“or”: \(\min(1, \cdot)\); composed of \(t(\sim P)\) and \(t(Q)\).
| \(P\) | \(Q\) | \(P \to Q\) |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 0 | 1 |
XOR: \[ t(P \oplus Q) = |t(P) - t(Q)| \]
| \(P\) | \(Q\) | \(P \oplus Q\) |
|---|---|---|
| 1 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 0 | 0 |
BICONDITIONAL: \[ t(P \leftrightarrow Q) = 1 - |t(P) - t(Q)| \]
| \(P\) | \(Q\) | \(P \leftrightarrow Q\) |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 0 | 1 |
Intuition for Implication
Q: Why is \([\text{false} \to \text{true}]\) true?
A: By definition. But consider:
If given number \(x\) less than 10, then \(x\) less than 100.
i.e. \(x < 10 \to x < 100\)
| Case | Value | Statement | Evaluation | Result |
|---|---|---|---|---|
| 1 | \(x = 5\) | \(5 < 10 \to 5 < 100\) | true \(\to\) true | true |
| 4 | \(x = 200\) | \(200 < 10 \to 200 < 100\) | false \(\to\) false | true |
| 2 | \(x = 50\) | \(50 < 10 \to 50 < 100\) | false \(\to\) true | true |
| 3 | – | no such \(x\): \(x < 10\) and \(x \not< 100\) | – | – |
\(\therefore\) “trivially true” (i.e. true for all inputs).
Theorems from Truth Tables
- \(P \mathbin{\&} Q \implies P\)
- \(P \implies P \lor Q\)
Proof. By (binary) truth table:
| \(P\) | \(Q\) | \(P \mathbin{\&} Q\) | \(P \mathbin{\&} Q \Rightarrow P\) | \(P \Rightarrow P \lor Q\) | \(P \lor Q\) |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 0 |
All implication columns are 1 – tautology (“equivalent to truth”). \(\square\)
Quantifiers and De Morgan’s Laws
| Logic | Set | Quantifier |
|---|---|---|
| AND (\(\mathbin{\&}\)) | \(\cap\) | \(\forall\) |
| OR (\(\lor\)) | \(\cup\) | \(\exists\) |
\(\exists\) \(\leftrightarrow\) “Some” \(\qquad\) \(\forall\) \(\leftrightarrow\) “All”
For arbitrary \(A_\alpha\):
\[ \bigcap_\alpha A_\alpha = \left(\bigcup_\alpha A_\alpha^c\right)^c \] \[ x \in \bigcap_\alpha A_\alpha \implies \forall \alpha,\; x \in A_\alpha \]
\[ \bigcup_\alpha A_\alpha = \left(\bigcap_\alpha A_\alpha^c\right)^c \] \[ x \in \bigcup_\alpha A_\alpha \implies \exists \alpha' : x \in A_{\alpha'} \]
- Lemma
- A small theorem used to prove a larger theorem.
- Corollary
- A special case of a theorem.
Models
Models are abstractions of reality with simplified behavior and cause-effect.
A model is only as good as the modeller and the assumptions that underlie the model.
A useful model explains all relevant aspects (i.e. what you care about).
Ex: Assuming “bell shaped” model for class grades (i.e. “the curve”).
Goal: explain observed behavior. Ideal: simple and understandable rules.
Scientific Method
“engineering = science + money”
Each step requires modeller input and expert opinion.
Iterative process continues until model is sufficient (or run out of time/money) – “good enough”.
Types of Models
- Deterministic
- Same input produces same output. Ex: \(V = iR\).
- Random
- Same input may produce different output.
A random experiment is an observation that varies in an “unpredictable” way when repeated under the same conditions.
“Naive” Probability Theory
Ex: 3-balls in urn experiment.
- Shake and randomly select (“random sample”)
- Record #. Return ball (“with replacement”)
\(\therefore\) Sample space \(\Omega = \{1, 2, 3\}\).
Repeat experiment. Outcome varies unpredictably. Cannot infer single outcome given history.
Statistical Regularity
Regularity is a means to quantify predictability in the long run.
Each repetition called a “trial.”
Ex: Weak law of large numbers (WLLN) – average of outcomes from a long sequence of experiments yield approximately the same value.
Ex: Central limit theorem (CLT) – standardized average from a long sequence of experiments follow approximately the same “distribution.”
Relative Frequency
Ex: 3-balls in urn.
Define \(N_1(n)\), \(N_2(n)\), \(N_3(n)\) as number of times you observe 1, 2, 3 after \(n\) trials.
\(N_k(n)\) are random. After you run the experiment and compute them, they are not random – “realization” of a random variable.
Define the relative frequency: \[ f_k(n) = \frac{N_k(n)}{n} \quad \text{for } k = 1, 2, 3 \]
Statistical regularity means \(f_k(n)\) varies less as \(n\) grows large.
Specifically: \[ \lim_{n \to \infty} f_k(n) = p_k \]
A constant, called the probability of outcome \(k\).
Problems with the “Frequentist” Approach
Problems with the limit (in a mathematical sense). Must \(\lim f_k(n)\) always converge? No.
Impossible to repeat experiment infinite times. Only finite samples. How to compute \(p_k\)?
How to operate for experiments you cannot repeat? e.g. election outcome.
How to handle experiments with a continuous sample space? (continuum of outcomes) e.g. pick random number in interval \([0,1]\).
\(\therefore\) Need a more robust approach that maintains consistency with frequentist approach / intuitive understanding of probability.
Axiomatic Probability Theory
Idea: in random experiments, define outcomes and occurrence of events as sets.
General idea: probability is about measuring relative size of sets.
Basic Structure
Suppose an experiment yields a random outcome.
- The set of all possible results \(\Omega\) is the sample space.
- Elements of the sample space are outcomes.
- Events are a special class of subsets of the sample space, called measurable sets.
- The probability of an event is the “size” of the set relative to \(\Omega\).
Axiomatic probability theory uses the language of sets.
Language of Sets
| Operation | Notation | Definition |
|---|---|---|
| Intersection | \(A \cap B\) | \(\{x \in X : x \in A \mathbin{\&} x \in B\}\) |
| Union | \(A \cup B\) | \(\{x \in X : x \in A \lor x \in B\}\) |
| Complement | \(A^c\) | \(\{x \in X : x \notin A\}\) |
| Difference | \(A - B\) | \(A \cap B^c\) |
| Symmetric difference | \(A \triangle B\) | \((A \cap B^c) \cup (B \cap A^c)\) |
Subset: \[ A \subset B \iff \forall x:\; x \in A \to x \in B \]
Result of \(\subset\) is a proposition, not a set.
Equality: \[ A = B \iff A \subset B \;\mathbin{\&}\; B \subset A \]
De Morgan’s Laws
\[ A \cap B = (A^c \cup B^c)^c \] \[ A \cup B = (A^c \cap B^c)^c \]
\[ \bigcap_\alpha A_\alpha = \left(\bigcup_\alpha A_\alpha^c\right)^c \] \[ \bigcup_\alpha A_\alpha = \left(\bigcap_\alpha A_\alpha^c\right)^c \]
Compare: \(\min(x,y) = -\max(-x,-y)\) and \(\max(x,y) = -\min(-x,-y)\).
Logical Diversion – “How to Proof”
If-then
“if \(p\) then \(q\)”, “\(q\) if \(p\)”, “\(p \to q\)”
- Suppose “if” part is true
- Show “then” part is true (“prove”) or false (“disprove”)
If and only if
“\(p\) if and only if \(q\)”, “\(p\) iff \(q\)”, “\(p \leftrightarrow q\)”
- Prove \(p \to q\)
- Prove \(q \to p\)
Must do both.
Subset: “\(X \subset Y\)”
- Choose arbitrary element \(x \in X\)
- Show \(x \in Y\)
Equality: “\(X = Y\)”
- Show \(X \subset Y\)
- Show \(Y \subset X\)
Must do both.
Venn diagrams are NOT proofs. Helpful tools – use as guidance.
Example: \(A \cap B \subset A \subset A \cup B\)
Proof. Claim 1: \(A \cap B \subset A\)
\[ \begin{aligned} & x \in A \cap B &&\text{[assump.]} \\ &\therefore x \in A \text{ AND } x \in B &&\text{[defn } \cap\text{]} \\ &\therefore x \in A &&\text{[Lemma: } P \mathbin{\&} Q \Rightarrow P\text{]} \\ &\therefore A \cap B \subset A &&\text{[defn } \subset\text{]} \quad \square \end{aligned} \]
Claim 2: \(A \subset A \cup B\)
\[ \begin{aligned} & x \in A &&\text{[assump.]} \\ &\therefore x \in A \text{ OR } x \in B &&\text{[Lemma: } P \Rightarrow P \lor Q\text{]} \\ &\therefore x \in A \cup B &&\text{[defn } \cup\text{]} \\ &\therefore A \subset A \cup B &&\text{[defn } \subset\text{]} \quad \square \end{aligned} \]
What is Probability?
Q: What is probability?
A: It is a function. \(P: \mathcal{A} \to [0, 1]\).
CAT – Definition of a Probability Measure
Suppose \((X, \mathcal{A})\) is a measurable space, where \(X\) = sample space (all possible outcomes) and \(\mathcal{A}\) = all possible events.
Then \(P: \mathcal{A} \to [0, 1]\) is a probability measure iff \(P\) is CAT:
C.A. – Countably Additive: \[ P\left(\bigcup_{k=1}^{\infty} A_k\right) = \sum_{k=1}^{\infty} P(A_k) \quad \text{if } A_i \cap A_j = \emptyset \text{ when } i \neq j \]
(\(A_i\) and \(A_j\) are “mutually exclusive”)
T – Total: \[ P(X) = 1 \]
\((X, \mathcal{A}, P)\) is a probability space iff \((X, \mathcal{A})\) is a measurable space and \(P: \mathcal{A} \to [0, 1]\) is CAT.
Example: \([A \cup B = B] \to [A \subset B]\)
Prove or disprove.
Method of proof for “\(\to\)”: 1. Assume LHS, 2. Determine RHS true/false.
Proof. Suppose \(A \cup B = B\). [\(\therefore\) show \(A \subset B\).]
\[ \begin{aligned} &\text{1. pick } x \in A &&\text{[Assump.]} \\ &\therefore x \in A \text{ OR } x \in B &&\text{[Defn } \lor\text{]} \\ &\therefore x \in A \cup B &&\text{[Defn } \cup\text{]} \\ &\therefore x \in B &&\text{[Since } A \cup B = B \text{ by assump.]} \\ &\therefore A \subset B &&\text{[Defn } \subset\text{]} \quad \square \end{aligned} \]
Step 3 \(\to\) 4 is the key: the LHS gives \(A \cup B = B\), so membership in \(A \cup B\) is membership in \(B\).
Example: \(P[\emptyset] = 0\)
From CAT we only know \(P[X] = 1\). Derive the rest.
Proof. \(X = X \cup \emptyset\), and \(X\) and \(\emptyset\) are mutually exclusive since \(X \cap \emptyset = \emptyset\).
\[ \begin{aligned} P[X] &= P[X \cup \emptyset] \\ &\stackrel{\text{C.A.}}{=} P[X] + P[\emptyset] \\ \therefore\quad 1 &\stackrel{T}{=} 1 + P[\emptyset] \\ \therefore\quad P[\emptyset] &= 0 \quad \square \end{aligned} \]
Example: Monotony
\[ A \subset B \implies P(A) \leq P(B) \]
Proof. Suppose \(A \subset B\).
\[ \begin{aligned} B &= B \cap X = B \cap (A \cup A^c) \\ &= (B \cap A) \cup (B \cap A^c) &&\text{[Distributivity (proof req'd)]} \\ &= A \cup (B \cap A^c) &&\text{[since } A \subset B\text{]} \end{aligned} \]
\(A\) and \((B \cap A^c)\) are mutually exclusive: \(A \cap (B \cap A^c) = \emptyset\).
\[ \begin{aligned} \therefore P[B] &= P[A] + P[B \cap A^c] &&\text{[mut. excl. + CA]} \\ &\geq P[A] \quad \square \end{aligned} \]
Example: Addition Theorem
\[ P(A) + P(B) = P(A \cup B) + P(A \cap B) \]
Short proof via decomposition
\[ \begin{aligned} A &= A \cap X = A \cap (B \cup B^c) = \underbrace{(A \cap B) \cup (A \cap B^c)}_{\text{disjoint}} \\ B &= B \cap X = B \cap (A \cup A^c) = \underbrace{(B \cap A) \cup (B \cap A^c)}_{\text{disjoint}} \end{aligned} \]
\[ \begin{aligned} \therefore P(A) + P(B) &= P(A \cap B) + P(A \cap B^c) + P(A \cap B) + P(A^c \cap B) \\ &= \underbrace{P(A \cap B^c) + P(A \cap B) + P(A^c \cap B)}_{= P(A \cup B) \text{ (see Lemma below)}} + P(A \cap B) \\ &= P(A \cup B) + P(A \cap B) \end{aligned} \]
Detailed proof via Lemma
\[ A \cup B = (A - B) \cup (A \cap B) \cup (B - A) = (A \cap B^c) \cup (A \cap B) \cup (B \cap A^c) \]
From this: \(P(A \cap B^c) = P[A] - P[A \cap B]\) and \(P(B \cap A^c) = P[B] - P[A \cap B]\) (to prove).
Claim 1: \(A \cup B \subset (A - B) \cup (A \cap B) \cup (B - A)\)
Proof.
- Pick \(x \in A \cup B\) [Ass.]
- \(\therefore x \in A\) OR \(x \in B\) [defn \(\cup\)]
Case 1: \(x \in A\) AND \(x \notin B\)
\[ \begin{aligned} &\therefore x \in A \text{ AND } x \in B^c &&\text{[defn } {}^c\text{]} \\ &\therefore x \in A \cap B^c &&\text{[defn } \cap\text{]} \\ &\therefore x \in A - B &&\text{[defn } -\text{]} \end{aligned} \]
Case 2: \(x \notin A\) AND \(x \in B\)
\[ \begin{aligned} &\therefore x \in A^c \text{ AND } x \in B &&\text{[defn } {}^c\text{]} \\ &\therefore x \in B \cap A^c &&\text{[defn } \cap\text{]} \\ &\therefore x \in B - A &&\text{[defn } -\text{]} \end{aligned} \]
Case 3: \(x \in A\) AND \(x \in B\) \(\;\therefore x \in A \cap B\) [defn \(\cap\)]
Justification for case split: propositional logic lemma \(P \lor Q \iff (P \mathbin{\&} \neg Q) \lor (P \mathbin{\&} Q) \lor (\neg P \mathbin{\&} Q)\).
| \(P\) | \(Q\) | \(P \lor Q\) | \((P \mathbin{\&} \neg Q)\) | \((P \mathbin{\&} Q)\) | \((\neg P \mathbin{\&} Q)\) | RHS |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
\(\therefore\) valid.
- \(\therefore x \in (A - B) \cup (A \cap B) \cup (B - A)\) [Lemma]
- \(\therefore A \cup B \subset (A - B) \cup (A \cap B) \cup (B - A)\) [defn \(\subset\)]
\(\square\) Claim 1.
Claim 2: \((A - B) \cup (A \cap B) \cup (B - A) \subset A \cup B\)
Proof.
- Pick \(x \in (A - B) \cup (A \cap B) \cup (B - A)\) [Ass.]
- \(\therefore x \in (A - B)\) OR \(x \in A \cap B\) OR \(x \in B - A\) [defn \(\cup\)]
Case 1: \(x \in A - B\)
\[ \begin{aligned} &\therefore x \in A \cap B^c &&\text{[defn } -\text{]} \\ &\therefore x \in A \text{ AND } x \in B^c &&\text{[defn } \cap\text{]} \\ &\therefore x \in A &&\text{[Lemma: } P \mathbin{\&} Q \Rightarrow P\text{]} \\ &\therefore x \in A \text{ OR } x \in B &&\text{[Lemma: } P \Rightarrow P \lor Q\text{]} \\ &\therefore x \in A \cup B &&\text{[defn } \cup\text{]} \end{aligned} \]
Or can stop at \(x \in A\) and use reasoning above.
Case 2: \(x \in A \cap B\) – similarly follows.
Case 3: \(x \in B - A\) – similarly follows.
- \(\therefore x \in A \cup B\)
- \(\therefore (A - B) \cup (A \cap B) \cup (B - A) \subset A \cup B\) [defn \(\subset\)]
\(\square\) Claim 2.
\(\therefore A \cup B = (A - B) \cup (A \cap B) \cup (B - A)\) [defn \(=\), Claim 1 + 2]. \(\square\) Lemma.
Final Computation
\[ \begin{aligned} P(A) + P(B) &= P(A - B) + P(A \cap B) + P(B - A) + P(A \cap B) \\ &= P\Big((A - B) \cup (A \cap B) \cup (B - A)\Big) + P(A \cap B) &&\text{[disjoint, CA]} \\ &= P(A \cup B) + P(A \cap B) &&\text{[Lemma]} \end{aligned} \]
\(\square\)
QED = quod erat demonstrandum (“which was to be demonstrated”)