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 is "working on Friday" and is "working on Saturday," the person means they are not working on Friday AND they are not working on Saturday.
- Expressions: is logically equivalent to . This transition demonstrates De Morgan's Law within everyday language.
Deriving Well-Formed Formulas (DNF)
DNF Construction via Truth Tables: A formula () 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 ().
- Process: For every row that gives a output, write a conjunction (AND) of the variables. If a variable is listed as False () in that row, use its negation ().
- Final Formula: Connect all individual minterms using the OR () operator.
- Example Table Scenario:
- Row where , , produces the minterm: .
- Row where , , produces the minterm: .
- Row where , , produces the minterm: .
- Final Full DNF: .
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 () output.
- Valid: A formula is valid only if every single model in the truth table results in a True () output. If even one row results in False (), 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 is identical to .
- Distinct: No elements are repeated. A collection such as is not a set because the value 5 is repeated.
Notation:
- Curly brackets denote a set.
- Round brackets signify a list or sequence where order does matter.
- Membership is denoted by the symbol . For example, 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: .
- This set contains exactly three elements: the number 5, the set , and the set .
- Pedantic distinction: The number 5 is not the same as the set containing five, , so .
Standard Sets of Numbers
Natural Numbers (): Counting numbers starting from 1 (). Zero was only introduced roughly a thousand years ago.
Integers (): Whole numbers, including positives, negatives, and zero. The letter comes from the German word for number, Zahlen.
Rational Numbers (): Numbers that can be written as a fraction of integers where . Rational numbers include all integers because any integer can be written as . The letter stands for quotient.
Real Numbers (): Any number with a possibly infinite decimal expansion. This includes numbers that cannot be written as fractions (irrational numbers), such as or . Real numbers can have decimals that terminate or go on forever without a repeating pattern.
Complex Numbers (): An extension of math that allows for the square root of negative numbers (). 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 .
- Example: .
- Evaluation: is true; is true; 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: , where denotes divisibility.
- Alternatively, using the algebraic form for odd numbers: .
The Empty Set (Null Set)
- Definition: A set containing no elements, denoted as or .
- Visualization: Consider it like a bag with nothing inside. You can put an empty bag inside another bag: is true.
- Logical Contradictions: Highlighting a set such as results in the empty set because no real number's square is negative.
Subsets and Logical Implication
- Subset Definition: is a subset of (denote ) if every element of is also an element of .
- Logical Connection: The subset relation is an "if-then" statement. .
- Example: If is the set of vowels and is the set of letters in the English alphabet, then . 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 ().
- Empty Set Property: The empty set is a subset of every set (). This is logically valid because the implication "If , then…" has a false premise, making the entire proposition vacuously true.
Set Operations
Intersection (): Elements that belong to both set and set . This corresponds to the logical operator AND.
- Disjoint Sets: Two sets are disjoint if their intersection is the empty set (). Examples include the set of people sitting vs. people standing, or the set of vowels vs. consonants.
- Domination Law Application: because "something AND false is always false."
Union (): Elements that belong to set OR set (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:
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 : Students studying Physics ().
- Set : Students studying Chemistry ().
- Union: Students studying Chemistry or Physics ().
- Calculation:
- 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 ? 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 , what does it mean? A: It could mean odd integers greater than 1 () or it could mean odd primes (). 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.