Propositional & Predicate Logic, Inference & Formal Proof Techniques

1. Propositions and Logical Connectives

A proposition is a declarative statement that is either strictly true ($T$ or $1$) or strictly false ($F$ or $0$), but not both simultaneously. Propositional variables (typically denoted $p, q, r, s$) represent atomic propositions that cannot be decomposed into simpler assertions.

Compound propositions are synthesized from atomic variables using formal truth-functional operators:

| Operator Name | Notation | Meaning / Truth Condition | | :--- | :---: | :--- | | Negation | $\neg p$ or $\sim p$ | True precisely when $p$ is false. | | Conjunction | $p \land q$ | True if and only if both $p$ and $q$ are true. | | Disjunction | $p \lor q$ | True if at least one of $p$ or $q$ is true (inclusive OR). | | Exclusive OR | $p \oplus q$ | True if exactly one of $p, q$ is true; $p \oplus q \equiv (p \lor q) \land \neg(p \land q)$. | | Conditional (Implication) | $p \implies q$ | False only when $p$ is true and $q$ is false; otherwise true. | | Biconditional | $p \iff q$ | True if $p$ and $q$ possess identical truth values; $(p \implies q) \land (q \implies p)$. |

Crucial Insight on Material Implication: In classical formal logic, the conditional $p \implies q$ is truth-functional: if the antecedent $p$ is false, the compound proposition $p \implies q$ is vacuously true, regardless of the truth value of the consequent $q$. Thus, $p \implies q \equiv \neg p \lor q$.

2. Tautologies, Contradictions, and Logical Equivalence

• A compound proposition that is true for all possible assignments of truth values to its propositional variables is a tautology (denoted $\mathbf{T}$).
• A compound proposition that is false under every truth assignment is a contradiction (denoted $\mathbf{F}$).
• A compound proposition that is neither a tautology nor a contradiction is a contingency.

Definition 1.1 (Logical Equivalence): Two compound propositions $P$ and $Q$ are logically equivalent (written $P \equiv Q$ or $P \iff Q$ is a tautology) if they evaluate to identical truth values across all $2^n$ interpretations in their truth table.

Essential System of Logical Equivalences

1. Identity Laws: $p \land \mathbf{T} \equiv p$, $p \lor \mathbf{F} \equiv p$.
2. Domination Laws: $p \lor \mathbf{T} \equiv \mathbf{T}$, $p \land \mathbf{F} \equiv \mathbf{F}$.
3. Idempotent Laws: $p \lor p \equiv p$, $p \land p \equiv p$.
4. Double Negation: $\neg(\neg p) \equiv p$.
5. Commutative Laws: $p \lor q \equiv q \lor p$, $p \land q \equiv q \land p$.
6. Associative Laws: $(p \lor q) \lor r \equiv p \lor (q \lor r)$, $(p \land q) \land r \equiv p \land (q \land r)$.
7. Distributive Laws:

1. De Morgan's Laws:

1. Absorption Laws: $p \lor (p \land q) \equiv p$, $p \land (p \lor q) \equiv p$.
2. Negation Laws (Excluded Middle and Contradiction): $p \lor \neg p \equiv \mathbf{T}$, $p \land \neg p \equiv \mathbf{F}$.
3. Contrapositive Law: $p \implies q \equiv \neg q \implies \neg p$.

3. Normal Forms and Functional Completeness

A literal is a propositional variable $x$ or its formal negation $\neg x$.

Disjunctive Normal Form (DNF)

A proposition is in Disjunctive Normal Form (DNF) if it is expressed as a disjunction of minterms (conjunctions of literals):

Every truth table row that evaluates to $1$ generates exactly one minterm.

Conjunctive Normal Form (CNF)

A proposition is in Conjunctive Normal Form (CNF) if it is expressed as a conjunction of maxterms (clauses, which are disjunctions of literals):

Every truth table row that evaluates to $0$ generates a clause consisting of the negations of the literal assignments.

Theorem 1.1 (Functional Completeness): A set of logical connectives is functionally complete if every possible truth function of $n$ variables can be expressed using only operators from that set.

• The standard set $\{\neg, \land, \lor\}$ is functionally complete.

• By De Morgan's laws, $\{\neg, \land\}$ and $\{\neg, \lor\}$ are functionally complete.

• The singleton sets consisting of either NAND (Sheffer stroke $\uparrow$) or NOR (Peirce arrow $\downarrow$) are individually functionally complete:

1. Predicates and the Universe of Discourse

A predicate $P(x)$ is a statement containing one or more free variables $x$ that becomes a proposition with a definite truth value whenever specific constants from a specified domain (the universe of discourse $\mathcal{U}$) are assigned to those variables. The set of all $x \in \mathcal{U}$ such that $P(x)$ is true is known as the truth set (or extension) of $P(x)$.

2. The Universal and Existential Quantifiers

Quantification converts open predicate formulas into definitive mathematical propositions over a non-empty domain $\mathcal{U}$:

1. Universal Quantifier ($\forall$):

Asserts that $P(x)$ is true for every element $x \in \mathcal{U}$. If $\mathcal{U} = \{x_1, x_2, \dots, x_n\}$ is finite:

A single element $c \in \mathcal{U}$ for which $P(c)$ is false constitutes a counterexample, immediately refuting $\forall x \, P(x)$.

1. Existential Quantifier ($\exists$):

Asserts that there exists at least one element $x \in \mathcal{U}$ such that $P(x)$ is true. Over a finite domain:

1. Uniqueness Quantifier ($\exists!$):

The notation $\exists! x \, P(x)$ signifies that there exists one and only one element $x$ satisfying $P(x)$:

3. De Morgan's Laws for Quantifiers (Duality)

Theorem 1.2 (Quantifier Negation Duality): Let $P(x)$ be an arbitrary predicate over domain $\mathcal{U}$. Then:

Proof:

• $\neg \forall x \, P(x)$ is true $\iff$ It is not the case that $P(x)$ holds for all $x \in \mathcal{U}$ $\iff$ There exists at least one $x_0 \in \mathcal{U}$ such that $P(x_0)$ is false $\iff$ There exists $x_0 \in \mathcal{U}$ such that $\neg P(x_0)$ is true $\iff \exists x \, \neg P(x)$.
• Replacing $P(x)$ with $\neg P(x)$ and using double negation yields the second identity immediately. $\blacksquare$

4. Nested Quantifiers and Order Dependence

When multiple variables are bound, the order of distinct quantifiers is critical and generally non-commutative:

• $\forall x \forall y \, P(x, y) \equiv \forall y \forall x \, P(x, y)$ (Commutative for identical quantifiers).
• $\exists x \exists y \, P(x, y) \equiv \exists y \exists x \, P(x, y)$ (Commutative for identical quantifiers).
• Non-Commutativity of Alternating Quantifiers:

However, the converse does not hold!

• $\exists y \forall x \, P(x, y)$: There exists a single universal element $y$ that works for every choice of $x$.
• $\forall x \exists y \, P(x, y)$: For every choice of $x$, there exists a corresponding $y$ (which may depend entirely on $x$, i.e., $y = y(x)$).

Classic Mathematical Formulation (Cauchy Continuity): A function $f: \mathbb{R} \to \mathbb{R}$ is continuous at $x_0$ if:

Uniform continuity on an interval $I$ swaps the quantifiers:

In uniform continuity, $\delta$ depends solely on $\epsilon$, whereas in point-wise continuity $\delta$ depends on both $\epsilon$ and $x_0$.

1. Argument Forms and Validity

An argument in propositional logic is a sequence of propositions $p_1, p_2, \dots, p_k$ called premises, followed by a final proposition $q$ called the conclusion:

An argument form is valid if the conditional statement:

is a tautology. Validity is a structural property: if all premises are true, the conclusion is guaranteed to be true. An argument is sound if it is valid and all its premises are factually true in reality.

2. Classical Rules of Inference

| Rule of Inference | Premise Structure | Conclusion | Tautological Basis | | :--- | :--- | :---: | :--- | | Modus Ponens (Affirming the Antecedent) | $p \implies q$, $p$ | $\therefore q$ | $[(p \implies q) \land p] \implies q$ | | Modus Tollens (Denying the Consequent) | $p \implies q$, $\neg q$ | $\therefore \neg p$ | $[(p \implies q) \land \neg q] \implies \neg p$ | | Hypothetical Syllogism (Transitivity) | $p \implies q$, $q \implies r$ | $\therefore p \implies r$ | $[(p \implies q) \land (q \implies r)] \implies (p \implies r)$ | | Disjunctive Syllogism | $p \lor q$, $\neg p$ | $\therefore q$ | $[(p \lor q) \land \neg p] \implies q$ | | Addition | $p$ | $\therefore p \lor q$ | $p \implies (p \lor q)$ | | Simplification | $p \land q$ | $\therefore p$ | $(p \land q) \implies p$ | | Conjunction | $p$, $q$ | $\therefore p \land q$ | $(p \land q) \implies (p \land q)$ | | Resolution | $p \lor q$, $\neg p \lor r$ | $\therefore q \lor r$ | $[(p \lor q) \land (\neg p \lor r)] \implies (q \lor r)$ |

Remark on Resolution: The resolution rule is the foundation of automated theorem proving and logic programming (e.g., Prolog). Two clauses containing complementary literals $p$ and $\neg p$ are resolved into a single resolvent clause $q \lor r$.

3. Rules of Inference for Quantified Statements

1. Universal Instantiation (UI): If $\forall x P(x)$ is true, then $P(c)$ is true for any arbitrary element $c \in \mathcal{U}$.
2. Universal Generalization (UG): If $P(c)$ is proved for an arbitrary, generic element $c \in \mathcal{U}$ (with no special assumptions on $c$), then $\forall x P(x)$ is true.
3. Existential Instantiation (EI): If $\exists x P(x)$ is true, then there exists an element $c \in \mathcal{U}$ such that $P(c)$ is true (introducing a fresh constant symbol $c$).
4. Existential Generalization (EG): If $P(c)$ is true for some specific witness $c \in \mathcal{U}$, then $\exists x P(x)$ is true.

4. Common Deductive Fallacies

Arguments that mimic valid rules of inference but fail to be tautologies are fallacies:

Fallacy of Affirming the Consequent

• Form: $p \implies q$, $q$, therefore $\therefore p$.
• Fallacy verification: If $p$ is false and $q$ is true, the premises $(p \implies q)$ and $q$ are both true, but the conclusion $p$ is false. The conditional $[(p \implies q) \land q] \implies p$ evaluates to false when $(p, q) = (0, 1)$, hence it is not a tautology.

Fallacy of Denying the Antecedent

• Form: $p \implies q$, $\neg p$, therefore $\therefore \neg q$.
• Fallacy verification: If $p$ is false and $q$ is true, then $p \implies q$ is true, $\neg p$ is true, yet $\neg q$ is false.

Fallacy of Circular Reasoning (Begging the Question)

• Occurs when one of the premises assumes the truth of the conclusion being demonstrated.

1. Mathematical Proof Taxonomy

A proof is a rigorous, deductive argument demonstrating that a mathematical proposition is necessarily true under a set of accepted axioms and previously proven theorems.

``` Mathematical Proof Techniques │ ┌─────────────────────────┴─────────────────────────┐ ▼ ▼ Direct Proofs Indirect Proofs (P ⟹ Q via derivations) │ ┌─────────────────────┴─────────────────────┐ ▼ ▼ Contrapositive Proof Proof by Contradiction (¬Q ⟹ ¬P) (Assume P ∧ ¬Q ⟹ False) ```

2. Direct Proof Method

To prove an implication $P \implies Q$:

1. Assume the premise $P$ is true.
2. Unpack the formal mathematical definitions inherent in $P$.
3. Apply logical deductive steps, algebraic manipulations, and established lemmas.
4. Arrive at the conclusion $Q$.

Theorem 1.3: If $n$ is an odd integer, then $n^2$ is an odd integer. Direct Proof: Let $n$ be an odd integer. By definition of odd integers, there exists an integer $k \in \mathbb{Z}$ such that $n = 2k + 1$. Squaring both sides:

Since the integers are closed under multiplication and addition, $m = 2k^2 + 2k$ is an integer. Thus $n^2 = 2m + 1$, which satisfies the definition of an odd integer. $\blacksquare$

3. Proof by Contraposition

To prove $P \implies Q$, we establish the logically equivalent contrapositive statement:

This technique is particularly powerful when the negation $\neg Q$ provides more structured algebraic or algebraic-geometric information than $P$.

Theorem 1.4: Let $n \in \mathbb{Z}$. If $3n + 2$ is odd, then $n$ is odd. Proof by Contraposition:

• The statement has the form $P(n) \implies Q(n)$, where $P(n): 3n+2 \text{ is odd}$ and $Q(n): n \text{ is odd}$.

• The contrapositive is $\neg Q(n) \implies \neg P(n)$, i.e., "If $n$ is even, then $3n + 2$ is even."

• Assume $n$ is even. By definition, $n = 2k$ for some $k \in \mathbb{Z}$.

• Substitute $n = 2k$ into the expression:

• Since $k \in \mathbb{Z}$, $3k + 1$ is an integer. Therefore, $3n + 2$ is divisible by 2 and is even ($\neg P(n)$ holds).

• Since $\neg Q \implies \neg P$ is proved, the original implication $P \implies Q$ is true. $\blacksquare$

4. Proof by Contradiction (Reductio ad Absurdum)

To prove a theorem $T$, we assume its formal negation $\neg T$ and deduce a logical contradiction of the form $R \land \neg R$ (or equivalently derive $\mathbf{F}$). Since mathematics is consistent, the assumption $\neg T$ must be false, so $T$ must be true.

Theorem 1.5 (Euclidean Irrationality of $\sqrt{2}$): The number $\sqrt{2}$ is irrational. Proof by Contradiction:

• Assume for contradiction that $\sqrt{2}$ is rational. Then there exist integers $a, b \in \mathbb{Z}$ with $b \ne 0$ such that $\sqrt{2} = \frac{a}{b}$.

• Without loss of generality, assume the fraction is in irreducible lowest terms: $\gcd(a, b) = 1$.

• Squaring both sides yields $2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$.

• Thus $a^2$ is even, which implies $a$ is even (by contrapositive: if $a$ were odd, $a^2$ would be odd).

• Since $a$ is even, write $a = 2k$ for some $k \in \mathbb{Z}$.

• Substitute $a = 2k$ into the equation: $(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$.

• Hence $b^2$ is even, which implies $b$ is even.

• Both $a$ and $b$ are even, so $2 \mid a$ and $2 \mid b$, which implies $\gcd(a, b) \ge 2$.

• This directly contradicts the assumption that $\gcd(a, b) = 1$.

• Therefore, the initial assumption is false, and $\sqrt{2}$ is irrational. $\blacksquare$

5. Proof by Cases and Exhaustion

When proving a proposition $\forall x P(x)$, if the domain $\mathcal{U}$ can be partitioned into mutually exhaustive cases $C_1 \cup C_2 \cup \dots \cup C_k = \mathcal{U}$, we establish:

Exhaustive proofs systematically test every finite case (e.g., verifying that no integer $x$ in $\{1, 2, 3, 4\}$ satisfies $x^3 + x = 20$).

1. Constructive Existence Proofs

An existence proof for a statement $\exists x P(x)$ is called constructive if it explicitly produces a concrete witness $c \in \mathcal{U}$ and demonstrates directly that $P(c)$ holds, or provides an effective algorithm that computes such a witness in finite time.

Example 1.2 (Constructive Existence): Claim: There exist two distinct perfect cubes whose sum is a perfect cube. Witness: Euler showed that no positive solution exists for $n=3$, but allowing negative integers:

Or in the famous taxicab number problem, Ramanujan showed $1729 = 1^3 + 12^3 = 9^3 + 10^3$, constructively proving that a number expressible as the sum of two positive cubes in two distinct ways exists.

2. Non-Constructive Existence Proofs

A non-constructive existence proof proves that $\exists x P(x)$ must be true without providing any explicit witness or algorithm to construct it. This is typically achieved using the Law of the Excluded Middle ($P \lor \neg P$), the Mean Value Theorem, or Cantor's diagonal argument.

Theorem 1.6 (Irrational Powers Yielding a Rational Number): There exist irrational numbers $a$ and $b$ such that $a^b$ is rational.

Non-Constructive Proof: Consider the number $\sqrt{2}^{\sqrt{2}}$. We know $\sqrt{2}$ is irrational (Theorem 1.5). By the Law of the Excluded Middle, $\sqrt{2}^{\sqrt{2}}$ is either rational or irrational:

• Case 1: If $\sqrt{2}^{\sqrt{2}}$ is rational, then choosing $a = \sqrt{2}$ and $b = \sqrt{2}$ provides the required pair, since both $a, b$ are irrational and $a^b$ is rational.

• Case 2: If $\sqrt{2}^{\sqrt{2}}$ is irrational, then choose $a = \sqrt{2}^{\sqrt{2}}$ (which is irrational by the case hypothesis) and $b = \sqrt{2}$ (which is irrational). Then:

Since $2 = \frac{2}{1}$, it is rational! In either case, there exist irrational numbers $a$ and $b$ such that $a^b$ is rational. $\blacksquare$

Remark on Non-Constructivism: Notice that the proof does not determine whether $\sqrt{2}^{\sqrt{2}}$ is actually rational or irrational (the Gelfond-Schneider theorem later proved that $\sqrt{2}^{\sqrt{2}}$ is indeed transcendental and irrational, vindicating Case 2, but the proof above succeeds independently of that knowledge).

3. Interactive Truth Table & Logic Circuit Engine

The simulation below provides an interactive workspace for Boolean logic and circuit synthesis:

• Truth Table Generator: Evaluate arbitrary compound formulas involving $\neg, \land, \lor, \implies, \iff, \oplus$ over multiple variables.
• Circuit Gate Synthesizer: Observe real-time logic signal propagation through AND, OR, NOT, NAND, NOR, and XOR gates.
• Normal Form Decomposer: Inspect step-by-step minterm extraction for DNF and maxterm clauses for CNF.