Logic & Cartesian Products – Detailed Lecture Notes

Weekly practical session (this afternoon)
1. 1st hour: collaborative walkthrough of assigned exercises (tutors circulate, identical to MATM1534 tutorial style).
2. 2nd hour: first practical test (~30 min, directly based on those exercises, covers sets material).
3. Final ½ hour: immediate marking discussion – review solutions, highlight common errors.
Difficulty ladder
- Printed examples ⟶ simplest level.
- In-class exercises ⟶ one step harder.
- Practical-test questions ⟶ another small jump (still "practical").
- Later semester tests & the exam ⟶ progressively harder, but always built on earlier material.
Language & clarity assurances
- In all assessments the staff strive to remove ambiguity; instructions will be explicit.
- Students may raise a hand in any test/exam to request a re-phrasing if wording is unclear.
Administrative notes
- Online sign-in poll kept open; manual sign-in available for students without phones.
- Guarantee: no "completely unseen" monster questions that take an hour just to parse.

Notation & basic idea
- For sets $A$ and $B$, $A\times B$ is the set of all ordered pairs $\bigl(a,b\bigr)$ with $a\in A$ and $b\in B$.
- Order matters: generally $A\times B \neq B\times A.$
Worked example
- Let $A={x,\,y,\,z}, \qquad B={5,6}.$
- $A\times B={(x,5),\,(x,6),\,(y,5),\,(y,6),\,(z,5),\,(z,6)}.$
- $B\times A={(5,x),(5,y),(5,z),(6,x),(6,y),(6,z)}.$
Cardinality rule
- In general $|A\times B| = |A|\,|B|.$
- Here $|A|=3,\,|B|=2\Rightarrow |A\times B|=6$.
- Extends: for $n$ sets $|A<em>1\times A</em>2 \times\dots \times A<em>n| = \prod</em>{i=1}^n |A_i|.$
Product with itself
- $A\times A$ contains $3\times3=9$ ordered pairs; explicitly listed as $(x,x),(x,y),\dots,(z,z)$.
Higher-arity ordered tuples
- $A\times B\times C$ would give ordered triples $(a,b,c)$.
Non-emptiness requirement
- To form a meaningful Cartesian product each factor set must be non-empty; an empty set would yield an empty product.
Metaphorical glimpse ahead
- Later chapters will treat $(a,b)$ as a relation arrow from $a$ to $b$; ideas of inverses, reflexive pairs $(a,a)$, etc., will resurface.

Sentence: any grammatical string – question, command, exclamation, assertion – regardless of truth value.
Statement (proposition): a sentence equipped with a definitive truth value T (true) or F (false).
- Examples of statements
- "Today is Tuesday" (verifiably T or F).
- "I am tired" (still T/F even though subjective).
- "The solution of $x-2=0$ is $x=1$" (false, but still a proposition).
- Non-statement examples
- "Please do the prep work." (command)
- "Did you understand last week’s work?" (question)
Open (predicate) vs. closed sentences
- An open sentence contains variables whose instantiation affects truth.
- Example: $|x| + |y| = 1$ with $x\in S={-1,0,1}$ and $y\in T={1,2}$.
- Choosing $x=0,\,y=1$ makes the sentence true, thus turning it into a statement.
- Choosing $x=-1$ (with any $y$) makes it false.
- Notation: such an open sentence is often labelled $P(x,y)$; becomes a statement when $(x,y)$ is substituted.
Existential vs. universal proof hints
- To show truth universally: prove the statement for all variable choices.
- To show falsehood: a single counter-instance suffices ("house of cards collapses").
Teaser: upcoming coverage of vacuous implications – propositions of the form "If $P$ then $Q$" that are always true when $P$ is false.

Purpose: catalogue every truth-value combination of multiple statements, then compute composite logical expressions systematically.
Combinatorial size
- For $n$ statement variables $\text{number of rows}=2^n.$
- E.g. $n=3\Rightarrow 8$ rows; $n=5\Rightarrow 32$ rows.
Column setup protocol (recommended order)
1. List variables alphabetically ($P, Q, R,\dots$) as the first columns.
2. Fill the rightmost variable column by alternating $T,F,T,F,\dots$ until all rows are filled.
3. Move one column left; double the run-length: $T,T,F,F,T,T,F,F,\dots$
4. Continue leftward, doubling each time. The leftmost variable ends with half the table T then half F.
5. This guarantees that every row is unique – a binary counting pattern (Computer-Science interpretation: $T=1$, $F=0$).
Example for $P,Q,R$
$P$ $Q$ $R$
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Why it matters
- Subsequent columns can evaluate complex formulas, e.g.
  $\bigl(P \land Q\bigr) \lor \bigl(\lnot R\bigr) \to P.$
- Final column instantly reveals tautology (all T), contradiction (all F), or contexts generating F (counter-examples).
Flexibility
- Any alternate but systematic ordering (starting with $F,T,F,T,\dots$ etc.) works if row uniqueness is preserved; however sticking to the conventional pattern eases marking.

Chapter 2 agenda:
- Truth tables (today) ✔️
- Tomorrow: disjunction, conjunction, implication.
Long-term roadmap
- Later revisit of sets (relations, functions, cardinality arguments).
- Formal proof techniques (direct, contrapositive, contradiction, induction).
- Deeper dive into relations emerging from Cartesian products (reflexive, symmetric, transitive properties; inverses; equivalence relations).
Proof ethos
- Show a universal claim by tackling all cases.
- Show falsity with a single telling counter-case.
Practical advice reiterated
- Think carefully which cases to discard vs. explore.
- Avoid brute-force explosion by systematic case study.