Necessary vs. Sufficient Conditions In Detail
Table-Setting I Should Have Done Before HW1: Truth Tables!
Just one (❗️) “primary” axiom required for first-order predicate logic!
But, to make it more digestible, we can define some “helper axioms”:
- A unary operator “\(\neg\)”
- Intersubjective agreement: call it “not”
| \(p\) | \(\neg p\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
- A binary operator “\(\wedge\)”
- Intersubjective agreement: call it “and”
| \(p\) | \(q\) | \(p \wedge q\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The Single Axiom
[Axiom ] A binary operator “\(\barwedge\)”, defined (for human consumption) s.t. \(a \barwedge b \triangleq \neg(a \wedge b)\), but defined precisely as the binary operator which maps the blue cols into orange col:
| \(p\) | \(q\) | \(p \underset{\small\text{or}}{\vee} q\) | \(p \underset{\small\text{xor}}{\otimes} q\) | \(p \underset{\small\text{and}}{\wedge} q\) | \(p \underset{\small\text{nand}}{\barwedge} q\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 |
Deriving “Not”
Given Axiom , we can derive Axiom as a theorem (meaning, it does not need to be included as an axiom!):
\[ [\text{Theorem 1}] \; ~ p \barwedge p \text{ satisfies all properties of }\neg p \]
Therefore, define \(\neg p \triangleq p \barwedge p\)
Given Axiom and Theorem 1, we can derive Axiom as a theorem:
\[ [\text{Theorem 2}] ~ \neg(p \barwedge q) \text{ satisfies all properties of }p \wedge q \]
Therefore, define \(p \wedge q \triangleq \neg(p \barwedge q)\)
HW1 Clarification: Necessary vs. Sufficient
These are, at root, logical connectors: given “atomic” (non-implicational) logical predicates \(p\) and \(q\), we can form implicational predicates (here “\(\equiv\)” means “will always have the same logical value (T or F) as”):
| English | Logical Form | \(\equiv\) | Contrapositive Form | If True Then… |
|---|---|---|---|---|
| “If \(p\) then \(q\)” | \(p \Rightarrow q\) or \(q \Leftarrow p\) | \(\equiv\) | \(\neg q \Rightarrow \neg p\) | \(p\) sufficient for \(q\) |
| “If \(q\) then \(p\)” | \(q \Rightarrow p\) or \(p \Leftarrow q\) | \(\equiv\) | \(\neg p \Rightarrow \neg q\) | \(p\) necessary for \(q\) |
The truth table for \(\Rightarrow\) looks like:
| \(p\) | \(q\) | \(p \Rightarrow q\) | \(\neg p \vee q\) |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Which means, finally, we can “plug in” English statements for \(p\) and \(q\):
- \(p\) = «A law mandating segregation is in force in a polity»
- \(q\) = «Segregation emerges in the polity»
And evaluate based on \(p\) and \(q\) (board time!)