Introduction to Logic Formulas and Set Theory

Course Administrative Requirements

  • Quiz 1 Deadline: The first quiz is due tomorrow at 9:00 AM. It can be attempted multiple times.

  • Assignment Submission Policy: All assignments from this point forward must be handwritten to be accepted.

    • Typing assignments is prohibited and carries the risk of a score of zero unless special permission is granted.
    • Handwriting visibility is mandatory. Writing on a tablet using a stylus is permitted, provided the actual handwriting is visible.

De Morgan’s Law in Natural Language

  • Contextual Interpretation: In logic, the way phrases are spoken in English must be analyzed for their logical meaning.
    • Example statement: "I am not working on Friday or Saturday."
    • Logical Translation: If pp is "working on Friday" and qq is "working on Saturday," the person means they are not working on Friday AND they are not working on Saturday.
    • Expressions: %%\neg(p \lor q)%% is logically equivalent to %%\neg p \land \neg q%%. This transition demonstrates De Morgan's Law within everyday language.

Deriving Well-Formed Formulas (DNF)

  • DNF Construction via Truth Tables: A formula (ff) can be constructed by looking at the final output column of a truth table.

    • Minterms: These are the individual logical configurations for each row where the output is True (TT).
    • Process: For every row that gives a TT output, write a conjunction (AND) of the variables. If a variable is listed as False (FF) in that row, use its negation (¬\neg).
    • Final Formula: Connect all individual minterms using the OR (∨\lor) operator.
    • Example Table Scenario:
    • Row where P=FP=F, Q=TQ=T, R=FR=F produces the minterm: %%\neg P \land Q \land \neg R%%.
    • Row where P=FP=F, Q=TQ=T, R=TR=T produces the minterm: %%\neg P \land Q \land R%%.
    • Row where P=TP=T, Q=TQ=T, R=TR=T produces the minterm: %%P \land Q \land R%%.
    • Final Full DNF: %%(\neg P \land Q \land \neg R) \lor (\neg P \land Q \land R) \lor (P \land Q \land R)%%.
  • Full DNF Characteristics: Full DNFs are generally not simplified. This lack of simplification allows for the immediate comparison of two formulas to determine if they are identical.

  • Satisfiability vs. Validity:

    • Satisfiable: A formula is satisfiable if there is at least one model (a row in the truth table) that results in a True (TT) output.
    • Valid: A formula is valid only if every single model in the truth table results in a True (TT) output. If even one row results in False (FF), the formula is not valid.

Fundamental Set Definitions and Cardinality

  • Set Definition: A set is an unordered collection of distinct objects.

    • Unordered: The order of elements does not matter. The set %%\{1, 2, 3\}%% is identical to %%\{3, 2, 1\}%%.
    • Distinct: No elements are repeated. A collection such as %%\{1, 2, 5, 5\}%% is not a set because the value 5 is repeated.
  • Notation:

    • Curly brackets %%\{\dots\}%% denote a set.
    • Round brackets %%(\dots)%% signify a list or sequence where order does matter.
    • Membership is denoted by the symbol %%\in%%. For example, 1∈A1 \in A reads as "1 is an element of A."
  • Cardinality (Size): The size of a set is the number of distinct elements it contains. This can involve nested sets.

    • Example set: %%\{5, \{2\}, \{3, 4\}\}%%.
    • This set contains exactly three elements: the number 5, the set %%\{2\}%%, and the set %%\{3, 4\}%%.
    • Pedantic distinction: The number 5 is not the same as the set containing five, %%\{5\}%%, so 5≠{5}5 \neq \{5\}.

Standard Sets of Numbers

  • Natural Numbers (N\mathbb{N}): Counting numbers starting from 1 (1,2,3,…1, 2, 3, \dots). Zero was only introduced roughly a thousand years ago.

  • Integers (Z\mathbb{Z}): Whole numbers, including positives, negatives, and zero. The letter ZZ comes from the German word for number, Zahlen.

  • Rational Numbers (Q\mathbb{Q}): Numbers that can be written as a fraction of integers %%\frac{a}{b}%% where b≠0b \neq 0. Rational numbers include all integers because any integer nn can be written as %%\frac{n}{1}%%. The letter QQ stands for quotient.

  • Real Numbers (R\mathbb{R}): Any number with a possibly infinite decimal expansion. This includes numbers that cannot be written as fractions (irrational numbers), such as %%\pi%% or %%\sqrt{2}%%. Real numbers can have decimals that terminate or go on forever without a repeating pattern.

  • Complex Numbers (C\mathbb{C}): An extension of math that allows for the square root of negative numbers (−1\sqrt{-1}). While they may not exist in "physical reality," they are mathematically functional and have many applications.

Predicate Set Notation and Logical Conditions

  • Predicate Form: Used to remove ambiguity in set definitions. The format is generally %%\{\text{variable type} : \text{conditions}\}%%.

    • Example: A={x∈R:1000<x≤2000}A = \{x \in \mathbb{R} : 1000 < x \le 2000\}.
    • Evaluation: 1010∈A1010 \in A is true; 1000.5∈A1000.5 \in A is true; 1000∈A1000 \in A is false because the range is strictly greater than 1000.
  • Representing Logic with Sets:

    • To define the set of odd natural numbers starting at 3, one might write: %%\{x \in \mathbb{N} : \neg(2|x) \land x \ge 3\}%%, where ∣| denotes divisibility.
    • Alternatively, using the algebraic form for odd numbers: %%\{2k+1 : k \in \mathbb{Z}, k \ge 1\}%%.

The Empty Set (Null Set)

  • Definition: A set containing no elements, denoted as %%\emptyset%% or %%\{\}\0025%.
  • Visualization: Consider it like a bag with nothing inside. You can put an empty bag inside another bag: %%\emptyset \in \{\emptyset\}%% is true.
  • Logical Contradictions: Highlighting a set such as %%\{x \in \mathbb{R} : x^2 < 0\}%% results in the empty set because no real number's square is negative.

Subsets and Logical Implication

  • Subset Definition: AA is a subset of BB (denote A⊆BA \subseteq B) if every element of AA is also an element of BB.
  • Logical Connection: The subset relation is an "if-then" statement. A⊆B≡∀x(x∈A→x∈B)A \subseteq B \equiv \forall x (x \in A \rightarrow x \in B).
    • Example: If VV is the set of vowels and LL is the set of letters in the English alphabet, then V⊆LV \subseteq L. This is equivalent to saying "If something is a vowel, then it is also a letter."
  • Special Properties:
    • Reflexivity: Every set is a subset of itself (A⊆AA \subseteq A).
    • Empty Set Property: The empty set is a subset of every set (∅⊆A\emptyset \subseteq A). This is logically valid because the implication "If x∈∅x \in \emptyset, then…" has a false premise, making the entire proposition vacuously true.

Set Operations

  • Intersection (%%A \cap B%%): Elements that belong to both set AA and set BB. This corresponds to the logical operator AND.

    • Disjoint Sets: Two sets are disjoint if their intersection is the empty set (A∩B=∅A \cap B = \emptyset). Examples include the set of people sitting vs. people standing, or the set of vowels vs. consonants.
    • Domination Law Application: %%A \cap \emptyset = \emptyset%% because "something AND false is always false."
  • Union (%%A \cup B%%): Elements that belong to set AA OR set BB (inclusive). In the union, elements that appear in both sets are not repeated.

  • The Inclusion-Exclusion Principle: To find the size of the union of two sets, use the formula:   %%|A \cup B| = |A| + |B| - |A \cap B|%%

Quantitative Application Example

  • Problem: There are 100 students studying Chemistry or Physics. 60 students study Physics, and 45 study Chemistry. How many study both?
  • Variable Assignments:
    • Set AA: Students studying Physics (∣A∣=60|A| = 60).
    • Set BB: Students studying Chemistry (∣B∣=45|B| = 45).
    • Union: Students studying Chemistry or Physics (∣A∪B∣=100|A \cup B| = 100).
  • Calculation:   %%100 = 60 + 45 - |A \cap B|%%%%100 = 105 - |A \cap B|%%%%|A \cap B| = 5%%
  • Result: Exactly 5 students study both Chemistry and Physics.

Questions & Discussion

  • Q: Determining Well-Formed Formulas from Truth Tables:   Can we use logic laws to find the DNF?   A: Yes, logic laws can be used to simplify expressions, but for academic testing purposes, finding the full DNF through truth tables is the required method.

  • Q: Membership in Nested Sets:   Why is five not an element of a set like %%\{\{5\}, \{2\}\}%%?   A: The elements are the objects listed inside the primary brackets. Here, the first object is a "set containing five," not the discrete number five itself. To reach the five, you must go into the subset.

  • Q: Ambiguity in Sequences:   If a sequence is written as 3,5,7,…3, 5, 7, \dots, what does it mean?   A: It could mean odd integers greater than 1 (9,11,…9, 11, \dots) or it could mean odd primes (11,13,…11, 13, \dots). Concrete predicate definitions are necessary to remove this ambiguity.

  • Q: Excluding False Rows in DNF:   Why do we ignore the rows where the outcome is False?   A: The goal is to create a formula that specifically characterizes the True outputs. By linking only the True models with OR, the formula will only return True for those specific cases.