🧩Discrete Mathematics Unit 1 – Introduction to Logic and Proofs

Key Concepts and Terminology

• Propositions statements that are either true or false, but not both simultaneously
• Logical operators connect propositions to form compound statements (conjunction, disjunction, negation, implication, biconditional)
• Truth tables visual representations of the possible truth values of a compound statement based on the truth values of its component propositions
• Tautology a statement that is always true regardless of the truth values of its component propositions
• Contradiction a statement that is always false regardless of the truth values of its component propositions
• Logical equivalence two statements are logically equivalent if they have the same truth value for all possible combinations of their component propositions' truth values
• Predicate a statement that contains variables and becomes a proposition when the variables are assigned specific values
• Quantifiers express the quantity or extent of a predicate (universal quantifier, existential quantifier)

Propositional Logic Basics

• Propositional logic deals with statements that can be either true or false, called propositions
• Simple propositions are the building blocks of propositional logic and cannot be broken down further (e.g., "The sky is blue")
• Compound propositions are formed by combining simple propositions using logical operators
• The truth value of a proposition is either true (T) or false (F)
• Propositional variables are used to represent propositions in a general sense (usually denoted by letters like p, q, r)
• Translating natural language statements into propositional logic involves identifying propositions and their relationships
• Parentheses are used to clarify the order of operations when multiple logical operators are present in a compound proposition

Logical Operators and Truth Tables

• Negation (¬) reverses the truth value of a proposition (e.g., if p is true, then ¬p is false)
• Conjunction (∧) combines two propositions with "and" (e.g., p ∧ q is true only when both p and q are true)
• Disjunction (∨) combines two propositions with "or" (e.g., p ∨ q is true when at least one of p or q is true)
• Implication (→) represents a conditional statement (e.g., p → q means "if p, then q")
  • The proposition before the arrow is the antecedent or hypothesis
  • The proposition after the arrow is the consequent or conclusion
• Biconditional (↔) represents "if and only if" (e.g., p ↔ q means p implies q and q implies p)
• Truth tables list all possible combinations of truth values for the component propositions and the resulting truth value of the compound proposition
• The number of rows in a truth table is 2^n, where n is the number of distinct propositional variables

Conditional Statements and Implications

• Conditional statements have the form "if p, then q" and are denoted as p → q
• The converse of p → q is q → p, obtained by swapping the antecedent and consequent
• The contrapositive of p → q is ¬q → ¬p, obtained by negating both the antecedent and consequent and swapping their order
• The inverse of p → q is ¬p → ¬q, obtained by negating both the antecedent and consequent
• A conditional statement is logically equivalent to its contrapositive
• The converse and inverse of a conditional statement are logically equivalent to each other
• A biconditional statement (p ↔ q) is true when p and q have the same truth value
  • It can be expressed as (p → q) ∧ (q → p)

Methods of Proof

• Direct proof assumes the hypothesis is true and uses logical reasoning to arrive at the conclusion
• Proof by contraposition proves the contrapositive of the statement (¬q → ¬p) instead of the original statement (p → q)
• Proof by contradiction assumes the negation of the statement is true and derives a contradiction, thereby proving the original statement
• Proof by cases breaks the proof into distinct cases and proves each case separately
• Proof by induction proves a statement for all natural numbers by proving a base case and an inductive step
  • The base case proves the statement for the smallest value (usually 0 or 1)
  • The inductive step assumes the statement is true for n and proves it for n+1

Quantifiers and Predicate Logic

• Predicate logic introduces variables and quantifiers to propositional logic
• The universal quantifier (∀) means "for all" or "for every" (e.g., ∀x P(x) means P(x) is true for every x in the domain)
• The existential quantifier (∃) means "there exists" or "for some" (e.g., ∃x P(x) means there is at least one x in the domain for which P(x) is true)
• The negation of a universally quantified statement is an existentially quantified statement with the predicate negated, and vice versa
  • ¬(∀x P(x)) is equivalent to ∃x ¬P(x)
  • ¬(∃x P(x)) is equivalent to ∀x ¬P(x)
• The domain of discourse is the set of all possible values for the variables in a predicate
• Bound variables are quantified by a universal or existential quantifier
• Free variables are not quantified and can take on any value from the domain

Common Proof Techniques

• Proof by example provides a specific instance that satisfies the statement, but does not prove it for all cases
• Proof by exhaustion proves a statement by checking all possible cases (feasible only for small, finite domains)
• Proof by counterexample disproves a statement by providing a single example where the statement is false
• Proof by construction provides a method for constructing an object that satisfies the statement
• Proof by contradiction in predicate logic assumes the negation of the statement and derives a contradiction
• Uniqueness proof shows that an object with a certain property is unique by assuming the existence of two such objects and deriving a contradiction
• Existence proof shows that an object with a certain property exists by either constructing an example or deriving a contradiction from assuming its non-existence

Applications and Problem-Solving

• Propositional and predicate logic are fundamental in computer science and mathematics
• They are used in designing digital circuits, programming languages, and algorithms
• Logical reasoning is essential for problem-solving and critical thinking
• Proofs are used to verify the correctness of algorithms and establish mathematical theorems
• Logical fallacies, such as affirming the consequent or denying the antecedent, can be identified and avoided using truth tables and logical equivalence
• Many real-world situations can be modeled and analyzed using propositional and predicate logic (e.g., database queries, software specifications, legal contracts)
• Solving problems using logic often involves translating natural language statements into formal logical notation, applying inference rules, and interpreting the results