Skip to main content
⚡ Calmops
🤖 AI 🏗️ Architecture 🌐 Web 🗃️ Database ⚙️ DevOps 🌍 Network 💻 Programming 🧮 Algorithms 📐 Software Eng. ☁️ Cloud 🔒 Security 📈 Finance More →

Introduction to Formal Logic: Symbols, Notation, and Formal Systems

Created: December 19, 2025 12 min read

Introduction

Formal logic is the study of reasoning using precise symbols and rules. Unlike informal logic, which uses natural language and can be ambiguous, formal logic uses mathematical notation to represent logical statements and arguments with complete precision.

Formal logic is essential for:

  • Mathematics: Constructing rigorous proofs
  • Computer Science: Programming, algorithm design, artificial intelligence
  • Philosophy: Analyzing arguments with precision
  • Artificial Intelligence: Automated reasoning and knowledge representation
  • Formal Verification: Proving software and hardware correctness

This comprehensive guide introduces you to formal logic—its symbols, notation, and fundamental concepts.

Why Formal Logic?

Advantages of Formal Logic

Precision: Formal notation eliminates ambiguity present in natural language.

Rigor: Formal systems have explicit rules that can be checked mechanically.

Universality: Formal logic applies across all domains—mathematics, science, philosophy, etc.

Automation: Formal logic can be mechanized and implemented in computers.

Verification: Formal proofs can be verified by computers.

Limitations of Formal Logic

Abstraction: Formal logic abstracts away from real-world context.

Complexity: Formal notation can be difficult to learn initially.

Incompleteness: Some true statements cannot be proven in formal systems (Gödel’s Incompleteness Theorems).

Undecidability: Some problems cannot be solved by any algorithm.

Formal Languages

What is a Formal Language?

A formal language is a set of strings (sequences of symbols) constructed according to specific rules.

Components:

  • Alphabet: The set of symbols used
  • Grammar: Rules for combining symbols into valid strings
  • Syntax: Rules for what constitutes a well-formed formula

Example: Propositional Logic Language

Alphabet:

  • Propositional variables: p, q, r, s, …
  • Logical operators: ¬, ∧, ∨, →, ↔
  • Parentheses: (, )

Grammar:

  • A propositional variable is a well-formed formula (WFF)
  • If A is a WFF, then ¬A is a WFF
  • If A and B are WFFs, then (A ∧ B), (A ∨ B), (A → B), and (A ↔ B) are WFFs
  • Nothing else is a WFF

Examples of Valid WFFs:

  • p
  • ¬p
  • (p ∧ q)
  • ((p ∧ q) → r)
  • (¬p ∨ (q ∧ r))

Examples of Invalid Strings:

  • p ∧ ∧ q (two operators in a row)
  • (p ∧ q (mismatched parentheses)
  • p q r (no operators)

Symbolic Notation

Propositional Variables

Definition: Variables that represent propositions (statements that are true or false).

Notation: Lowercase letters: p, q, r, s, t, …

Example:

  • p = “It is raining”
  • q = “The ground is wet”
  • r = “I have an umbrella”

Logical Operators

1. Negation (NOT)

Symbol: ¬ (also written as ~, -, or NOT)

Meaning: “Not p” or “It is not the case that p”

Truth Table:

p ¬p
T F
F T

Example: ¬p = “It is not raining”

2. Conjunction (AND)

Symbol: ∧ (also written as &, ·, or AND)

Meaning: “p and q” (both p and q)

Truth Table:

p q p ∧ q
T T T
T F F
F T F
F F F

Example: p ∧ q = “It is raining and the ground is wet”

3. Disjunction (OR)

Symbol: ∨ (also written as |, +, or OR)

Meaning: “p or q” (at least one of p or q, possibly both)

Truth Table:

p q p ∨ q
T T T
T F T
F T T
F F F

Example: p ∨ q = “It is raining or the ground is wet”

4. Implication (IF-THEN)

Symbol: → (also written as ⊃, ⇒, or IF-THEN)

Meaning: “If p, then q” or “p implies q”

Truth Table:

p q p → q
T T T
T F F
F T T
F F T

Example: p → q = “If it is raining, then the ground is wet”

Key Point: An implication is false only when the antecedent (p) is true and the consequent (q) is false.

5. Biconditional (IF AND ONLY IF)

Symbol: ↔ (also written as ≡, ⇔, or IFF)

Meaning: “p if and only if q” (p and q have the same truth value)

Truth Table:

p q p ↔ q
T T T
T F F
F T F
F F T

Example: p ↔ q = “It is raining if and only if the ground is wet”

Operator Precedence

When multiple operators appear in a formula, we need to know which to apply first.

Precedence (highest to lowest):

  1. ¬ (Negation)
  2. ∧ (Conjunction)
  3. ∨ (Disjunction)
  4. → (Implication)
  5. ↔ (Biconditional)

Example: p ∧ q ∨ r means (p ∧ q) ∨ r, not p ∧ (q ∨ r)

Best Practice: Use parentheses to make your meaning clear, even when not strictly necessary.

Formal Systems

What is a Formal System?

A formal system consists of:

  1. Formal Language: Symbols and grammar
  2. Axioms: Statements assumed to be true
  3. Inference Rules: Rules for deriving new statements from existing ones

Example: Propositional Logic as a Formal System

Language: Propositional variables and logical operators (as described above)

Axioms: Tautologies (statements that are always true)

Inference Rules:

  • Modus Ponens: From p and p → q, infer q
  • Modus Tollens: From ¬q and p → q, infer ¬p
  • Hypothetical Syllogism: From p → q and q → r, infer p → r
  • Disjunctive Syllogism: From p ∨ q and ¬p, infer q
  • Conjunction: From p and q, infer p ∧ q
  • Simplification: From p ∧ q, infer p
  • Addition: From p, infer p ∨ q

Proofs in Formal Systems

A proof is a sequence of statements where each statement is either:

  • An axiom, or
  • Derived from previous statements using an inference rule

Example Proof:

Goal: Prove that (p → q) ∧ p → q

Proof:

1. (p → q) ∧ p          [Assumption]
2. p → q                [Simplification from 1]
3. p                    [Simplification from 1]
4. q                    [Modus Ponens from 2 and 3]

Conclusion: We have proven that (p → q) ∧ p → q

Quantifiers and Predicate Logic

Limitations of Propositional Logic

Propositional logic can express:

  • “It is raining” (p)
  • “It is raining and the ground is wet” (p ∧ q)
  • “If it rains, the ground gets wet” (p → q)

But it cannot express:

  • “All humans are mortal”
  • “Some birds can fly”
  • “There exists a prime number greater than 100”

These statements require quantifiers and predicates.

Predicates

A predicate is a function that takes one or more arguments and returns true or false.

Notation: P(x), Q(x, y), R(x, y, z), …

Examples:

  • Human(x) = “x is human”
  • Mortal(x) = “x is mortal”
  • Parent(x, y) = “x is the parent of y”
  • Greater(x, y) = “x is greater than y”

Universal Quantifier

Symbol: ∀ (for all, for every)

Meaning: “For all x, P(x)” or “Every x has property P”

Notation: ∀x P(x)

Example:

∀x (Human(x) → Mortal(x))
"For all x, if x is human, then x is mortal"
or
"All humans are mortal"

Truth Condition: ∀x P(x) is true if P(x) is true for every value of x in the domain.

Existential Quantifier

Symbol: ∃ (there exists, there is at least one)

Meaning: “There exists an x such that P(x)” or “At least one x has property P”

Notation: ∃x P(x)

Example:

∃x (Prime(x) ∧ Greater(x, 100))
"There exists an x such that x is prime and x is greater than 100"
or
"There exists a prime number greater than 100"

Truth Condition: ∃x P(x) is true if P(x) is true for at least one value of x in the domain.

Combining Quantifiers

Multiple Quantifiers:

∀x ∃y Parent(x, y)
"For all x, there exists a y such that x is the parent of y"
or
"Everyone has a parent"

Order Matters:

∀x ∃y Loves(x, y)
"For all x, there exists a y such that x loves y"
(Everyone loves someone)

∃y ∀x Loves(x, y)
"There exists a y such that for all x, x loves y"
(Someone is loved by everyone)

These have different meanings!

Negation of Quantified Statements

Negating Universal Quantifiers:

¬∀x P(x) ≡ ∃x ¬P(x)
"It is not the case that all x have property P"
is equivalent to
"There exists an x that does not have property P"

Negating Existential Quantifiers:

¬∃x P(x) ≡ ∀x ¬P(x)
"It is not the case that there exists an x with property P"
is equivalent to
"For all x, x does not have property P"

Logical Equivalence and Laws

Logical Equivalence

Two formulas are logically equivalent if they have the same truth value in every interpretation.

Notation: A ≡ B or A ⇔ B

Important Logical Laws

Identity Laws:

p ∧ T ≡ p
p ∨ F ≡ p

Domination Laws:

p ∨ T ≡ T
p ∧ F ≡ F

Idempotent Laws:

p ∨ p ≡ p
p ∧ p ≡ p

Double Negation Law:

¬(¬p) ≡ p

Commutative Laws:

p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p

Associative Laws:

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Distributive Laws:

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

De Morgan’s Laws:

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Absorption Laws:

p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p

Negation Laws:

p ∨ ¬p ≡ T (Law of Excluded Middle)
p ∧ ¬p ≡ F (Law of Non-Contradiction)

Implication Laws:

p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p (Contrapositive)
¬(p → q) ≡ p ∧ ¬q

Biconditional Laws:

p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)

Normal Forms

Conjunctive Normal Form (CNF)

A formula is in CNF if it is a conjunction of disjunctions.

Form: (p ∨ q ∨ r) ∧ (¬p ∨ s) ∧ (q ∨ ¬s ∨ t)

Advantages:

  • Useful for automated reasoning
  • Important for SAT solvers
  • Can be converted from any formula

Example Conversion:

Original: (p → q) ∧ (r → s)
Step 1: (¬p ∨ q) ∧ (¬r ∨ s)    [Implication law]
Result: Already in CNF

Disjunctive Normal Form (DNF)

A formula is in DNF if it is a disjunction of conjunctions.

Form: (p ∧ q ∧ r) ∨ (¬p ∧ s) ∨ (q ∧ ¬s ∧ t)

Advantages:

  • Can be read directly from truth tables
  • Useful for understanding when a formula is true

Example Conversion:

Original: (p ∨ q) ∧ r
Step 1: (p ∧ r) ∨ (q ∧ r)    [Distributive law]
Result: Already in DNF

Formal Semantics

Interpretations

An interpretation (or valuation) assigns truth values to all propositional variables.

Example:

Interpretation I:
p = T
q = F
r = T

Evaluating Formulas

Given an interpretation, we can evaluate any formula to determine its truth value.

Example:

Formula: (p ∧ q) → r
Interpretation: p = T, q = F, r = T

Evaluation:
(p ∧ q) → r
= (T ∧ F) → T
= F → T
= T

Satisfiability

A formula is satisfiable if there exists an interpretation that makes it true.

Example:

Formula: p ∧ q
Satisfiable? Yes (when p = T and q = T)

Validity (Tautology)

A formula is valid (or a tautology) if it is true in every interpretation.

Example:

Formula: p ∨ ¬p
Valid? Yes (true whether p is T or F)

Unsatisfiability (Contradiction)

A formula is unsatisfiable (or a contradiction) if it is false in every interpretation.

Example:

Formula: p ∧ ¬p
Unsatisfiable? Yes (false whether p is T or F)

Applications of Formal Logic

In Mathematics

Formal logic is used to:

  • Construct rigorous proofs
  • Verify mathematical theorems
  • Develop formal systems (set theory, number theory, etc.)

In Computer Science

Formal logic is used for:

  • Programming: Boolean expressions, conditional statements
  • Databases: SQL queries use logical operators
  • Artificial Intelligence: Knowledge representation and reasoning
  • Formal Verification: Proving software and hardware correctness
  • Automated Reasoning: SAT solvers, theorem provers

In Philosophy

Formal logic is used for:

  • Analyzing philosophical arguments
  • Formalizing philosophical concepts
  • Detecting logical fallacies

In Linguistics

Formal logic is used for:

  • Analyzing sentence structure
  • Representing meaning formally
  • Understanding natural language semantics

Online Learning Platforms

Interactive Tools

  • “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook on formal logic
  • “A Concise Introduction to Logic” by Patrick J. Hurley - Accessible introduction with examples
  • “Logic: The Laws of Truth” by Nicholas J.J. Smith - Modern comprehensive treatment
  • “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook
  • “Mathematical Logic” by Stephen Cole Kleene - Advanced formal logic

Academic Journals

  • Journal of Symbolic Logic - Leading journal on mathematical logic
  • Studia Logica - International journal on logic and philosophy
  • Logic and Logical Philosophy - Open access journal on logic research

Software and Programming Tools

  • Prolog - Logic programming language
  • Coq - Interactive theorem prover
  • Isabelle - Generic proof assistant
  • Z3 - SMT solver for automated reasoning
  • SWI-Prolog - Open-source Prolog implementation
  • Python - For implementing formal systems

Glossary of Key Terms

  • Axiom: A statement assumed to be true without proof
  • Biconditional: “If and only if” operator (↔)
  • Conjunction: “And” operator (∧)
  • Disjunction: “Or” operator (∨)
  • Formal Language: Set of strings constructed according to rules
  • Implication: “If-then” operator (→)
  • Inference Rule: Rule for deriving new statements
  • Interpretation: Assignment of truth values to variables
  • Negation: “Not” operator (¬)
  • Predicate: Function that returns true or false
  • Quantifier: Universal (∀) or existential (∃) operator
  • Satisfiability: Formula is true in some interpretation
  • Tautology: Formula that is always true
  • Validity: Formula is true in all interpretations

Conclusion

Formal logic provides a precise, rigorous framework for reasoning. By using symbols and formal systems, we can:

  • Eliminate ambiguity
  • Verify arguments mechanically
  • Automate reasoning
  • Prove theorems rigorously
  • Build intelligent systems

Understanding formal logic is essential for:

  • Advanced mathematics
  • Computer science and programming
  • Artificial intelligence
  • Philosophy and critical thinking
  • Formal verification and security

The next article in this series will dive deeper into Propositional Logic: Operators and Truth Tables, exploring the foundations of formal reasoning in detail.

What aspect of formal logic interests you most? Are you drawn to the mathematical precision, the philosophical applications, or the computational uses? Share your thoughts in the comments below!

Comments