Symbolic Logic and Formal Languages

Mathematics is communicated through a highly specialized formal language designed to eliminate the ambiguity inherent in natural languages. This language consists of a syntax (the rules for combining symbols) and a semantics (the meaning assigned to those symbols). Mastery of this notation is not merely about memorization; it is about understanding the logical structure of thought.

The Anatomy of a Proposition

A proposition is a declarative statement that is either true or false, but not both. In formal logic, we use letters ($P,Q,R$) to represent these atomic propositions. The standard logical connectives allow us to build complex formulas:

1. Negation ($\neg$): $\neg P$ is true if and only if $P$ is false.
2. Conjunction ($\wedge$): $P\wedge Q$ is true if and only if both $P$ and $Q$ are true.
3. Disjunction ($\vee$): $P\vee Q$ is true if at least one of $P$ or $Q$ is true (inclusive or).
4. Implication ($⟹$): $P⟹Q$ is false only if $P$ is true and $Q$ is false. It is logically equivalent to $\neg P\vee Q$.
5. Biconditional ($⟺$): $P⟺Q$ is true only if $P$ and $Q$ have the same truth value.

Predicates and Quantifiers

While propositional logic handles whole statements, Predicate Logic (or First-Order Logic) allows us to look inside the statements. A predicate $P(x)$ is a property that can be true or false depending on the value of the variable $x$ from a specified domain $D$.

To make general statements about these variables, we use Quantifiers:

• The Universal Quantifier ($\forall$): The statement $\forall x\in D,P(x)$ asserts that $P(x)$ is true for every element in the domain.
• The Existential Quantifier ($\exists$): The statement $\exists x\in D,P(x)$ asserts that there exists at least one element in the domain for which $P(x)$ is true.
• Uniqueness Quantifier ($\exists !$): Often used to denote that there exists exactly one element satisfying the property.

Quantifier Scoping and Binding

The order of quantifiers is critical. For instance, consider the domain of real numbers $\mathbb{R}$:

• $\forall x\exists y(x+y=0)$ is True (every number has an additive inverse).
• $\exists y\forall x(x+y=0)$ is False (there is no single number $y$ that is the inverse for every $x$).

A variable is bound if it is within the scope of a quantifier; otherwise, it is free. A formula with no free variables is called a sentence and has a fixed truth value.

Set-Theoretic Notation

Sets are the fundamental building blocks of modern mathematics. We use consistent notation to describe relationships between elements and sets:

• Membership: $a\in S$ ($a$ is an element of $S$).
• Subset: $A\subseteq B$ ($\forall x,x\in A⟹x\in B$).
• Proper Subset: $A\subset B$ ($A\subseteq B$ and $A\ne B$).
• Set Builder Notation: $\{x\in S\mid P(x)\}$ represents the set of all elements in $S$ that satisfy the predicate $P$.

Standard Number Systems

Throughout this course, we refer to the following standard sets:

• $\mathbb{N}$: The set of Natural numbers $\{0,1,2,\dots \}$ (conventionally includes 0 in pure math).
• $\mathbb{Z}$: The set of Integers $\{\dots ,-2,-1,0,1,2,\dots \}$.
• $\mathbb{Q}$: The set of Rational numbers $\{\frac{p}{q}\mid p,q\in \mathbb{Z},q\ne 0\}$.
• $\mathbb{R}$: The set of Real Numbers (the completion of $\mathbb{Q}$).
• $\mathbb{C}$: The set of Complex Numbers $\{a+bi\mid a,b\in \mathbb{R},i^2=-1\}$.

Operational and Relational Symbols

Mathematical notation extends to operations (functions) and relations:

• Summation and Product: ${\sum }_{i=1}^n{a}_i$ and ${\prod }_{i=1}^n{a}_i$.
• Functions: $f:A\to B$ denotes a function mapping domain $A$ to codomain $B$. The notation $x\mapsto f(x)$ describes the specific mapping of an element.
• Equivalence Relations: $\sim$ or $\equiv$ denote relations that satisfy reflexivity, symmetry, and transitivity.

The Importance of Syntactic Rigor

Consider the Epsilon-Delta definition of a limit: ${\lim }_{x\to a}f(x)=L⟺\forall ϵ>0,\exists \delta >0,\forall x(0<|x-a|<\delta ⟹|f(x)-L|<ϵ)$ This dense symbolic string replaces a clumsy natural language explanation. It specifies the exact dependence of $\delta$ on $ϵ$ and the order of operations. Without symbolic rigor, advanced mathematics would collapse under its own complexity.

Implementing Logic via Computation

While we focus on pure mathematics, the parallels to formal logic in computer science are profound. We can model logical operations to verify complex boolean expressions.

type Proposition = boolean;

const and = (p: Proposition, q: Proposition): Proposition => p && q;
const or = (p: Proposition, q: Proposition): Proposition => p || q;
const not = (p: Proposition): Proposition => !p;
const implies = (p: Proposition, q: Proposition): Proposition => !p || q;
const iff = (p: Proposition, q: Proposition): Proposition => p === q;

// Example: Verifying De Morgan's Law ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
const verifyDeMorgan = () => {
  const values = [true, false];
  for (const p of values) {
    for (const q of values) {
      const lhs = not(and(p, q));
      const rhs = or(not(p), not(q));
      console.log(`P=${p}, Q=${q} | LHS=${lhs}, RHS=${rhs} | Match=${lhs === rhs}`);
    }
  }
};

This computational approach allows us to “calculate” truths in propositional logic, though it does not scale to the infinite domains required for predicate logic.