Propositional Logic & Sets Summary & Study Notes

💡 Propositions and Truth Values

• Definition: A proposition is a declarative sentence with a truth value $true$ or $false$. Use symbols such as $P$ and $Q$ to denote propositions.
• Example: $P$ = '5 is prime', $Q$ = '2+2=5'. Here $P$ is true and $Q$ is false. Propositions must be declarative statements, not questions, commands, or exclamations.

🔗 Logical Connectives

• Conjunction: $P \land Q$ is true iff both $P$ and $Q$ are true.
• Disjunction: $P \lor Q$ is true if at least one of $P$ or $Q$ is true.
• Implication: $P \rightarrow Q$ is false only if $P$ is true and $Q$ is false.
• Biconditional: $P \leftrightarrow Q$ is true when $P$ and $Q$ have the same truth value.
• Negation: $\neg P$ is the opposite truth value of $P$.
• Compound Propositions: Formed by combining base propositions with connectives; truth values are determined by truth tables.
• Equivalence: Two propositions are equivalent if they share the same truth values across all combinations.
• Tautology and Contradiction: A tautology is always true; a contradiction is always false.

🧭 Open Propositions, Quantifiers, and Negation

• Open propositions contain variables and depend on assigned values within a universe $U$. Example: $x > 5$.
• Quantifiers: Universal $\forall x \in U$ and existential $\exists x \in U$ convert open propositions into quantified statements. Nested quantifiers create richer structures.
• Negation of open propositions and quantifiers: $\neg (\forall x \in U) P(x) \equiv (\exists x \in U) \neg P(x)$ and $\neg (\exists x \in U) P(x) \equiv (\forall x \in U) \neg P(x)$.

✅ Validity of Arguments & Inference Rules

• Validity: An argument is valid if the premises guarantee the conclusion regardless of content.
• Formula validity: An argument form is valid if it is a tautology.
• Rules of Inference:
  • Modus Ponens: $P$, $P \rightarrow Q$ entail $Q$.
  • Modus Tollens: $\neg Q$, $P \rightarrow Q$ entail $\neg P$.
  • Hypothetical Syllogism (Chain Rule): $P \rightarrow Q$, $Q \rightarrow R$ entail $P \rightarrow R$.

🗃️ Sets: Descriptions and Basic Concepts

• Set: A well-defined collection of objects.
• Describing sets: Verbally, by complete listing, with partial listing, or using the set-builder notation.
• Empty set: $\emptyset$; the set with no elements.
• Finite and Infinite: Distinguished by the number of elements.
• Universal Set: The set of all elements under consideration, denoted by $U$.

🗂️ Set Relationships, Subsets, and Power Sets

• Subsets: $A \subseteq B$; if $A$ is contained in $B$. Proper subset: $A \subset B$, if $A \neq B$ and $A \subseteq B$.
• Equality and Equivalence: $A = B$ means identical elements; $|A| = |B|$ defines equivalent sets by cardinality.
• Power set: $\mathcal{P}(A)$ is the set of all subsets of $A$.
• Universal set and complements: $A^c = U \setminus A$.

🗂️ Set Operations & Venn Diagrams

• Union: $A \cup B$, Intersection: $A \cap B$, Complement: $A^c$ (relative to $U$).
• Symmetric Difference: $A \Delta B = (A \setminus B) \cup (B \setminus A)$.
• Venn Diagrams: Visual tool to represent relationships and operations between sets.

📚 Quick Takeaways

• Propositional logic builds rigorous reasoning using truth-functional connectives.
• Quantifiers allow statements about all or some elements of a universe.
• Sets provide a foundational language for mathematics and allow precise descriptions of collections and operations.

🧭 Well-Ordering Principle & Mathematical Induction

• Well-Ordering Principle: Every non-empty subset of the natural numbers $\mathbb{N}$ has a least element.
• Mathematical Induction: To prove a statement $P(n)$ for all $n \ge 0$, prove the base case $P(0)$ and the inductive step $P(k) \Rightarrow P(k+1)$; conclude $P(n)$ holds for all $n$. These tools underpin many proofs in number theory and combinatorics.