Logic and Propositions: Comprehensive Study Notes

INTRODUCTION TO LOGIC

• Logic is the study of the principles that govern correct reasoning.
• Mastering formal logic is vital for computing students because propositional and predicate logic serve as the languages for conditional statements, loop invariants, database queries, circuit designs, and program specifications.
• This domain involves the mathematical language of logic, which includes propositions, logical connectives, predicates, quantifiers, and rules of inference.
• These components form the basis for standard methods of mathematical proof.

PROPOSITIONAL LOGIC

Definition and Recognition

• Proposition: A proposition is a declarative sentence that is either true or false, but not both. Every proposition has exactly one definite truth value.
• Non-propositions: Sentences that are not propositions include:
  • Questions.
  • Commands.
  • Sentences where truth depends on an unassigned variable (e.g., $x + 3 = 8$).
• Examples of Propositions:
  • "Gaborone is the capital of Botswana": This is a true proposition.
  • "$2 + 2 = 5$": This is a false proposition.
  • "Every even integer greater than 2 is the sum of two primes" (Goldbach’s Conjecture): This is a proposition because it has a definite truth value, regardless of whether mathematicians have yet proven what that value is.
• Notation: Propositions are typically denoted by lower-case letters như $p, q, r, s$, referred to as propositional variables or statement letters.
  • $p \equiv \text{true}$ indicates that the proposition $p$ is true.
  • $p \equiv \text{false}$ indicates that the proposition $p$ is false.

Logical Connectives and Compound Propositions

• Compound Propositions: Created by building upon existing propositions using logical connectives.
• Atomic Propositions: Propositions that cannot be broken down into further components.
• Negation ($\neg$): Let $p$ be a proposition. the negation of $p$ is written as $\neg p$ (read as "not $p$"). It is the proposition "It is not the case that $p$". The truth value of $\neg p$ is the exact opposite of $p$.
  • Truth Table for Negation:
    • If $p$ is true, $\neg p$ is false.
    • If $p$ is false, $\neg p$ is true.
• Conjunction ($\wedge$): The conjunction of $p$ and $q$ (read as "$p$ and $q$") is true only when both $p$ and $q$ are true; otherwise, it is false.
• Disjunction ($\vee$): The disjunction of $p$ and $q$ (read as "$p$ or $q$") is false only when both $p$ and $q$ are false; otherwise, it is true.
  • Inclusive vs. Exclusive "Or": The connective $\vee$ is an inclusive or, meaning it is true if either or both propositions are true. This differs from the exclusive or ($\oplus$), where the proposition is true only if precisely one of the variables is true.
• Exclusive Or ($\oplus$): The proposition $p \oplus q$ is true exactly when precisely one of $p$ or $q$ is true.

Conditional Statements

• Definition: The conditional statement $p \rightarrow q$ (read as "if $p$ then $q$") is false only when the hypothesis (antecedent) $p$ is true and the conclusion (consequent) $q$ is false. It is true in all other scenarios.
• Vacuous Truth: The statement $p \rightarrow q$ is considered true whenever $p$ is false, regardless of the truth value of $q$. This is because the statement makes no claim when the hypothesis is not met.
• Truth Table for Conditional ($p \rightarrow q$):
  • true, true: true
  • true, false: false
  • false, true: true
  • false, false: true
• English Equivalents for $p \rightarrow q$:
  • "$p$ implies $q$"
  • "$p$ is sufficient for $q$"
  • "$q$ is necessary for $p$"
  • "$q$ if $p$"
  • "$q$ whenever $p$"
  • "$q$ follows from $p$"
• Related Statements:
  • Converse: $q \rightarrow p$
  • Inverse: $\neg p \rightarrow \neg q$
  • Contrapositive: $\neg q \rightarrow \neg p$
  • Note: Only the contrapositive is logically equivalent to the original conditional statement ($p \rightarrow q$). The converse and inverse are generally not equivalent to the original.

Biconditional Statements

• Definition: The biconditional statement $p \leftrightarrow q$ (read as "$p$ if and only if $q$" or "iff") is true only when $p$ and $q$ possess the same truth value.
• Equivalence: $p \leftrightarrow q$ is true precisely when both $p \rightarrow q$ and $q \rightarrow p$ are true.

Precedence of Logical Operators

To minimize the need for parentheses, connectives are evaluated in a standardized order:

1. Negation ($\neg$)
2. Conjunction ($\wedge$)
3. Disjunction ($\vee$)
4. Conditional ($\rightarrow$)
5. Biconditional ($\leftrightarrow$)

PROPOSITIONAL EQUIVALENCES

Tautologies, Contradictions, and Contingencies

• Tautology: A compound proposition that is always true, regardless of the truth values of its variables (e.g., $p \vee \neg p$, the Law of the Excluded Middle).
• Contradiction: A compound proposition that is always false, regardless of variable truth values (e.g., $p \wedge \neg p$).
• Contingency: A compound proposition that is neither a tautology nor a contradiction (it is true for at least one assignment and false for at least one other).

Logical Equivalence

• Two compound propositions $A$ and $B$ are logically equivalent ($A \equiv B$) if $A \leftrightarrow B$ is a tautology, meaning they have identical truth tables.
• De Morgan's Laws:
  • $\neg (p \wedge q) \equiv \neg p \vee \neg q$
  • $\neg (p \vee q) \equiv \neg p \wedge \neg q$

Fundamental Logical Equivalences Toolkit

Rewriting Conditionals and Biconditionals

• Conditional as disjunction: $p \rightarrow q \equiv \neg p \vee q$
• Contrapositive law: $p \rightarrow q \equiv \neg q \rightarrow \neg p$
• Biconditional expansion: $p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$
• Other Identities:
  • $p \vee q \equiv \neg p \rightarrow q$
  • $p \wedge q \equiv \neg(p \rightarrow \neg q)$
  • $p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q$

Satisfiability

• Satisfiable: A compound proposition is satisfiable if there is at least one assignment of truth values to its variables that makes it true (called a solution).
• Unsatisfiable: A compound proposition is unsatisfiable if no such assignment exists (i.e., it is a contradiction).
• Importance: The satisfiability problem (SAT) is the archetypal NP-complete problem in computer science.

PREDICATES AND QUANTIFIERS

Predicates (Propositional Functions)

• Ordinary propositional logic cannot capture the internal structure of sentences like "$x > 3$".
• Definition: A predicate or propositional function $P(x)$ involves a variable $x$ from a domain of discourse $D$. It becomes a proposition once a specific value from $D$ is substituted for $x$.
• Example: Let $P(x)$ denote "$x^2 - 5x + 6 = 0$" with domain $Z$.
  • $P(2)$ is true ($0 = 0$).
  • $P(5)$ is false ($6 = 0$).

Quantifiers

• Universal Quantifier ($\forall$): The proposition "$P(x)$ is true for all values of $x$ in the domain $D$," denoted $\forall x P(x)$. A value that makes $P(x)$ false is a counterexample.
• Existential Quantifier ($\exists$): The proposition "there exists an element $x$ in the domain $D$ for which $P(x)$ is true," denoted $\exists x P(x)$. A value that makes $P(x)$ true is a witness.
• Bound vs. Free Variables: A variable associated with a quantifier is bound. A variable not associated with one is free. A statement with no free variables is a true proposition.
• Restricted Domain Shorthand:
  • $\forall x < 0 (x^2 > 0)$ is shorthand for $\forall x (x < 0 \rightarrow x^2 > 0)$.
  • $\exists x > 100 (\text{x is prime})$ is shorthand for $\exists x (x > 100 \wedge \text{x is prime})$.

Negating Quantifiers (De Morgan's Laws for Quantifiers)

• $\neg [\forall x P(x)] \equiv \exists x \neg P(x)$
• $\neg [\exists x P(x)] \equiv \forall x \neg P(x)$
• Negation swaps $\forall$ for $\exists$ and moves the negation symbol inside next to the predicate.

NESTED QUANTIFIERS

• Nested quantifiers occur when multiple quantifiers are applied in sequence (e.g., the definition of a limit in Calculus).
• Order Matters:
  • Quantifiers of the same type can be reordered ($\forall x \forall y \equiv \forall y \forall x$ and $\exists x \exists y \equiv \exists y \exists x$).
  • Mixed quantifiers cannot generally be reordered. $\forall x \exists y P(x, y)$ (where $y$ may depend on $x$) is not the same as $\exists y \forall x P(x, y)$ (which requires one single $y$ for all $x$).

RULES OF INFERENCE

Validity and Arguments

• Argument: A sequence of propositions (premises) followed by a final proposition (conclusion).
• Validity: An argument is valid if the conclusion is necessarily true whenever all premises are true. Formally, $(p_1 \wedge p_2 \wedge \dots \wedge p_n) \rightarrow q$ must be a tautology.
• Rule of Inference: A standard, verified argument form used as a single step in a proof.

Table of Rules for Propositional Logic

Rules for Quantified Statements

• Universal Instantiation: From $\forall x P(x)$, infer $P(c)$ for a particular element $c$.
• Universal Generalisation: From $P(c)$ for an arbitrary $c$, infer $\forall x P(x)$.
• Existential Instantiation: From $\exists x P(x)$, infer $P(c)$ for some element $c$.
• Existential Generalisation: From $P(c)$ for some witness $c$, infer $\exists x P(x)$.

Logic Fallacies

• Affirming the Consequent: Concluding $p$ from $p \rightarrow q$ and $q$. Invalid because $q$ might be true for other reasons.
• Denying the Hypothesis: Concluding $\neg q$ from $p \rightarrow q$ and $\neg p$. Invalid because $q$ might still be true even if $p$ is false.

INTRODUCTION TO PROOFS

Mathematical Definitions

• Theorem: A proposition proved true, usually significant.
• Proof: A valid chain of reasoning establishing a theorem's truth.
• Axiom (Postulate): A statement accepted as true without proof.
• Lemma: A minor theorem used as a stepping stone.
• Corollary: A theorem that follows directly from a proved theorem.
• Conjecture: A statement believed but not yet proved true. Once proved, it becomes a theorem.
• Even Integer: an integer $n$ such that $n = 2k$ for some integer $k$.
• Odd Integer: an integer $n$ such that $n = 2k + 1$ for some integer $k$.
• Rational Number: A real number $r$ that can be expressed as $a/b$ where $a, b \in Z$ and $b \neq 0$.
• Irrational Number: A real number that is not rational.

Proof Methods

• Direct Proof: To prove $p \rightarrow q$, assume $p$ is true and use axioms/definitions to show $q$ must be true.
  • Standard pattern: Unpack definition (e.g., $n = 2k$), compute algebraically, repackage into the required form.
• Proof by Contraposition: To prove $p \rightarrow q$, give a direct proof of the contrapositive $\neg q \rightarrow \neg p$. Assume $q$ is false and show $p$ must be false.
  • Example: To prove "if $3n + 2$ is odd, then $n$ is odd," it is easier to show "if $n$ is even, then $3n + 2$ is even."
• Proof by Contradiction: Assume the negation of what you want to prove (assume $\neg p$) and derive a contradiction ($r \wedge \neg r$). Since $\neg p$ leads to a falsehood, $p$ must be true.
• Proof by Cases: Establish $p \rightarrow q$ by proving it for an exhaustive list of individual scenarios ($p_1 \rightarrow q, p_2 \rightarrow q, \dots$). Example: Proving a property for all integers by checking cases for $n \leq -1$, $n = 0$, and $n \geq 1$.
• Existence Proofs:
  • Constructive: Explicitly find a witness $a$ that satisfies $P(a)$.
  • Nonconstructive: Show that an element must exist without finding it (e.g., using cases or contradiction).
• Uniqueness Proofs: To show a unique element exists, prove existence first, then prove that any arbitrary element satisfying the property must be equal to that first element.
• Counterexamples: A single counterexample is sufficient to disprove a universal statement $\forall x P(x)$.

Case Study: Proof by Contradiction of $\sqrt{2}$

1. Suppose $\sqrt{2}$ is rational: $\sqrt{2} = a/b$ where $\text{gcd}(a, b) = 1$.
2. Square both sides: $2 = a^2/b^2$, so $a^2 = 2b^2$.
3. $a^2$ is even, so $a$ is even (by lemma: even square implies even base). Let $a = 2c$.
4. Substitute: $(2c)^2 = 2b^2 \rightarrow 4c^2 = 2b^2 \rightarrow 2c^2 = b^2$.
5. $b^2$ is even, so $b$ is even.
6. If both $a$ and $b$ are even, $\text{gcd}(a, b) \geq 2$, contradicting the assumption $\text{gcd}(a, b) = 1$. Therefore, $\sqrt{2}$ is irrational.