🔢Lower Division Math Foundations Unit 1 – Mathematical Reasoning & Logic Basics

Key Concepts and Definitions

• Mathematical logic studies the formal principles of valid inference and reasoning
• Propositions are declarative sentences that are either true or false, but not both
• Logical connectives (and, or, not, if-then, if and only if) join propositions to form compound propositions
• Truth tables display all possible truth values of a compound proposition based on the truth values of its component propositions
• Tautologies are compound propositions that are always true regardless of the truth values of their component propositions ($p \vee \neg p$)
• Contradictions are compound propositions that are always false regardless of the truth values of their component propositions ($p \wedge \neg p$)
• Logical equivalence means two compound propositions have the same truth value for all possible truth values of their component propositions
• Predicates are propositions containing variables, which become true or false when the variables are replaced with specific values ($P(x): x > 5$)

Logical Operators and Truth Tables

• Logical operators (connectives) are used to combine propositions into compound propositions
  • Conjunction ($\wedge$): "and" operator, true only when both propositions are true
  • Disjunction ($\vee$): "or" operator, true when at least one proposition is true
  • Negation ($\neg$): "not" operator, true when the proposition is false and vice versa
  • Implication ($\rightarrow$): "if-then" operator, false only when the antecedent is true and the consequent is false
  • Biconditional ($\leftrightarrow$): "if and only if" operator, true when both propositions have the same truth value
• Truth tables exhaustively list all possible combinations of truth values for the component propositions and the resulting truth value of the compound proposition
• Truth tables can be used to determine the logical equivalence of compound propositions
• De Morgan's laws describe the relationship between conjunctions, disjunctions, and negations: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$

Propositional Logic

• Propositional logic deals with propositions and their relationships using logical connectives, without considering the internal structure of the propositions
• Propositional variables ($p$, $q$, $r$, etc.) represent propositions in formulas
• Compound propositions are built using propositional variables and logical connectives
• Logical equivalences, such as De Morgan's laws and distributive properties, allow for the simplification and manipulation of compound propositions
• The rules of inference, such as modus ponens and modus tollens, enable the derivation of new propositions from existing ones
• Propositional logic is used in various fields, including computer science (Boolean algebra) and digital circuit design

Predicate Logic

• Predicate logic extends propositional logic by introducing predicates, quantifiers, and variables
• Predicates are functions that map elements from a domain to truth values ($P(x): x$ is even)
• Quantifiers specify the quantity of elements in the domain for which a predicate is true
  • Universal quantifier ($\forall$): "for all" elements in the domain, the predicate is true
  • Existential quantifier ($\exists$): "there exists" at least one element in the domain for which the predicate is true
• Variables in predicate logic can be bound (quantified) or free (unquantified)
• The domain of discourse specifies the set of elements over which the quantifiers and variables range
• Predicate logic allows for more expressive statements and reasoning compared to propositional logic ($\forall x \in \mathbb{R}, x^2 \geq 0$)

Proof Techniques

• Direct proof: Assumes the premises are true and uses logical steps to arrive at the conclusion
• Proof by contradiction: Assumes the negation of the conclusion and shows that it leads to a contradiction with the premises or known facts
• Proof by contraposition: Proves the contrapositive of the statement ($p \rightarrow q$ is equivalent to $\neg q \rightarrow \neg p$)
• Proof by cases: Divides the problem into exhaustive cases and proves the statement for each case
• Proof by induction: Proves a statement for all natural numbers by showing it holds for the base case and that if it holds for $n$, it also holds for $n+1$
  1. Base case: Prove the statement for the smallest value (usually 0 or 1)
  2. Inductive step: Assume the statement holds for $n$ (inductive hypothesis) and prove it for $n+1$
• Proof by example: Provides a counterexample to disprove a universal statement
• Existence proofs: Prove the existence of an object satisfying certain properties without necessarily constructing it

Set Theory Basics

• A set is a well-defined collection of distinct objects
• Elements or members are the objects within a set
• Sets can be represented using set-builder notation ($\{x \mid x \text{ is a prime number}\}$) or by listing elements ($\{2, 3, 5, 7, 11, \ldots\}$)
• The empty set ($\emptyset$ or $\{\}$) contains no elements
• Subsets are sets where every element is also an element of another set ($A \subseteq B$)
• Power set ($\mathcal{P}(A)$) is the set of all subsets of a given set
• Set operations include union ($A \cup B$), intersection ($A \cap B$), difference ($A \setminus B$), and complement ($A^c$ or $\overline{A}$)
• Venn diagrams visually represent sets and their relationships using overlapping circles

Applications in Problem Solving

• Logical reasoning is essential for analyzing and solving complex problems in various fields, such as mathematics, computer science, and philosophy
• Propositional and predicate logic help formalize arguments and assess their validity
• Set theory is used in database design, data analysis, and probability theory
• Boolean algebra, based on propositional logic, is fundamental to digital circuit design and computer programming
• Proof techniques are employed to establish the truth of mathematical statements and to verify the correctness of algorithms
• Logical fallacies, such as affirming the consequent or denying the antecedent, can be identified and avoided using logical reasoning skills
• Decision-making and strategic planning often involve logical reasoning to evaluate options and their consequences

Common Pitfalls and Tips

• Confusing necessary and sufficient conditions in implications ($p \rightarrow q$ does not imply $q \rightarrow p$)
• Mistakenly assuming the converse ($q \rightarrow p$), inverse ($\neg p \rightarrow \neg q$), or negation ($\neg p \rightarrow q$ or $p \rightarrow \neg q$) of an implication is equivalent to the original implication
• Incorrectly distributing negation over logical connectives (De Morgan's laws)
• Confusing the inclusive "or" ($\vee$) with the exclusive "or" (XOR)
• Misinterpreting the scope of quantifiers and their order in predicate logic statements
• Forgetting to consider all possible cases in a proof by cases or all elements in the domain for quantified statements
• Assuming the conclusion in a proof (circular reasoning) or making unjustified leaps in reasoning
• Practice translating natural language statements into formal logical notation to improve precision and clarity
• Use truth tables to verify the logical equivalence of compound propositions and to identify tautologies and contradictions
• Break down complex problems into smaller, more manageable components and apply logical reasoning to each part
• Be cautious of common logical fallacies and biases in arguments, such as ad hominem attacks, straw man arguments, and hasty generalizations