forallx PDF Download – Introduction to Formal Logic (P.D. Magnus) BSCS/Philosophy

BSCS and Philosophy students can download forallx, P.D. Magnus’s free introduction to formal logic, as a complete PDF. The book takes you from evaluating everyday arguments in English through two formal languages — sentential logic (SL) and quantified logic (QL) — and ends with a full natural deduction proof system, all in six compact chapters.

What makes forallx worth knowing by name is that it is the original text a whole family of university logic courses is built on: forallx:Cambridge, forallx:Calgary and more than a dozen other university-specific remixes all start from this book and its Creative Commons license. For a first course in formal logic — whether it is taught inside Computer Science or Philosophy — this is the base version: no institution-specific notation choices, just the standard six-chapter build from arguments to proofs.

Book Overview

Chapter List

Chapter 1: What is Logic?

Difficulty: Easy · Key topics: arguments, premises and conclusions, deductive validity, inductive vs. deductive arguments, tautology, contradiction, contingent sentences, logical equivalence, consistency

The chapter defines an argument as a series of sentences — premises followed by a conclusion — and immediately separates the ordinary sense of “argument” (a shouting match) from the logical sense. It defines deductive validity precisely: an argument is valid exactly when it is impossible for the premises to be true and the conclusion false, illustrated with a silly-but-valid “oranges are musical instruments” argument and a true-premises-but-invalid “Paris is in France” argument, to show validity is about form, not actual truth. It contrasts this with inductive arguments, which generalize from cases and are never deductively valid no matter how much evidence is added. It then defines tautology, contradiction and contingent sentence, logical equivalence and consistency, and closes by introducing formal languages through Aristotle’s syllogisms, previewing why the book moves from English into symbols.

Key Points:

• An argument is a series of sentences: the earlier ones are premises, the final one is the conclusion.
• An argument is deductively valid exactly when it is impossible for the premises to be true and the conclusion false — validity is about form, not actual truth.
• A valid argument can have a false premise or a silly conclusion; true premises and a true conclusion do not by themselves make an argument valid.
• Inductive arguments generalize from many cases to all cases and are never deductively valid, however much evidence supports them.
• A tautology is true as a matter of logic; a contradiction is false as a matter of logic; a contingent sentence is neither.
• Two sentences are logically equivalent when they must always share the same truth value.
• A set of sentences is inconsistent when it is logically impossible for all of them to be true at once.

Memory Tip: When checking validity, imagine the premises are true and ask only whether the conclusion could still be false — not whether the conclusion sounds reasonable. The “oranges are musical instruments” example is designed to break the instinct to judge validity by how sensible the conclusion sounds.

Common Mistake: Treating a “good argument” (one with believable premises) as the same thing as a “valid argument” (one with airtight form). The London/Beijing/Paris example has all true premises and a true conclusion, yet is invalid, because the premises have nothing to do with the conclusion.

Important Questions:

• What makes an argument deductively valid? It is impossible for its premises to all be true while its conclusion is false — validity is a matter of the argument’s form, not the actual truth of its sentences.
• Why isn’t a strong inductive argument deductively valid? Because no matter how many supporting cases you add, it always remains logically possible for a counter-example to occur, so the conclusion is never guaranteed.

Chapter 2: Sentential Logic

Difficulty: Easy · Key topics: sentence letters, symbolization keys, the five connectives (¬, &, ∨, →, ↔), atomic sentences, well-formed formulas, object language vs. metalanguage

The chapter introduces SL, a formal language whose basic units are entire sentences represented by capital letters. A symbolization key pairs each sentence letter with an English sentence for one specific translation problem; the same letter can mean something different in a different problem. It works through all five connectives — negation, conjunction, disjunction, conditional and biconditional — with worked English-to-SL examples for each, including tricky cases like “unless” (translated as disjunction) and the difference between “not happy” and “unhappy” (which are not logically the same). It closes by formally defining a well-formed formula (wff) as anything buildable from sentence letters by the connective rules, and distinguishes the object language (SL) from the metalanguage (English) used to talk about it.

Key Points:

• SL has five connectives: ¬ (negation), & (conjunction), ∨ (disjunction), → (conditional), ↔ (biconditional).
• A symbolization key states what each sentence letter means for one specific translation; it does not carry over to a different problem.
• Once part of a sentence becomes an atomic sentence letter, its internal structure is lost — you cannot paraphrase “B and energetic” and expect it to work.
• “Unless A, B” is symbolized as A ∨ B, using the logical equivalence between “unless” and disjunction.
• A well-formed formula (wff) is anything built from sentence letters by finitely many applications of the connective rules; not every string of symbols is a wff.
• The main connective of a sentence is the last one applied in building it, and its column in a truth table gives the truth value of the whole sentence.

Memory Tip: Double-check every negation translation by asking “does this really mean ‘it is NOT the case that…’?” — “Elliott is unhappy” is not automatically ¬H for “Elliott is happy,” because being unhappy and merely not-happy aren’t guaranteed to be the same state.

Common Mistake: Matching English connective-words to symbols mechanically. “Unless,” “even though” and “but” all need care — “unless” becomes ∨, not a conditional, which is the translation most students guess first.

Important Questions:

• What is a symbolization key? An interpretation that pairs each sentence letter with an English sentence for one specific translation, so the letters can be read back into meaningful sentences.
• How do you symbolize “Unless you wear a jacket, you will catch cold”? As J ∨ D, using the equivalence between “unless A, B” and “A ∨ B.”

Chapter 3: Truth Tables

Difficulty: Medium · Key topics: truth-functional connectives, complete truth tables, partial truth tables, testing for tautology/contradiction/contingency, testing argument validity

The chapter defines a truth-functional connective as one whose compound sentence’s truth value depends only on the truth values of its parts — true of all five SL connectives, which is what makes truth tables possible at all. It builds up complete truth tables step by step, showing how to fill in a compound sentence’s column from its parts’, using (H & I) → H as a running example. It then defines tautology, contradiction, contingency, logical equivalence, consistency and argument validity purely in terms of what appears in a complete truth table’s rows. The final section teaches partial truth tables: showing something is NOT a tautology, NOT valid or NOT consistent needs only one carefully chosen row, while proving the positive claim generally needs the full table — summarized in the book’s own “yes/no” reference table.

Key Points:

• A connective is truth-functional when the compound’s truth value depends only on the truth values of its parts; all five SL connectives are truth-functional.
• A complete truth table has one row for every combination of truth values of the sentence letters involved — 2ⁿ rows for n sentence letters.
• A sentence is a tautology in SL if its main-connective column is 1 on every row of a complete table; a contradiction if it is 0 on every row.
• An argument is valid in SL if no row makes every premise 1 and the conclusion 0.
• Disproving a claim (not a tautology, not valid, not consistent) needs only a one-line partial table; proving the positive claim generally needs the complete table.
• Two sentences are logically equivalent in SL exactly when their main-connective columns match on every row.

Memory Tip: Memorize the chapter’s own “yes/no” pairing: tautology, contradiction, equivalence and validity need a COMPLETE table to confirm, but their opposites need only ONE row to refute. Most homework problems ask you to disprove something, so this shortcut saves real time.

Common Mistake: Building a full 2ⁿ-row table when a one-line partial table was enough — for example, filling in every row to show a sentence is not a tautology, when a single row where it comes out false already proves it.

Important Questions:

• How many rows does a complete truth table need for a sentence with 4 different sentence letters? 16 rows (2⁴), one for every combination of true and false.
• What is the fastest way to show an argument is invalid using truth tables? Find one row where every premise is 1 and the conclusion is 0 — a one-line partial table is enough.

Chapter 4: Quantified Logic

Difficulty: Medium · Key topics: predicates, singular terms, monadic and polyadic predicates, universal and existential quantifiers, scope, universe of discourse, identity, expressions of quantity

The chapter opens by showing SL’s limit directly: “Willard is a logician; all logicians wear funny hats; therefore Willard wears a funny hat” is obviously valid in English but comes out invalid once flattened into SL, because sentence letters cannot capture the “all F are G” structure that makes it work. QL fixes this with predicates (properties or relations, symbolized with capital letters and blanks) and terms — constants for specific things, variables as placeholders. It introduces the universal quantifier ∀ and existential quantifier ∃, each requiring a variable and a scope, plus the universe of discourse (UD) that fixes what “everyone” ranges over. The chapter ends with identity (=), needed to translate “else,” “besides” and “only,” and to count things precisely — “there are at least two Fs” requires ∃x∃y(Fx & Fy & x≠y), not just two existential quantifiers.

Key Points:

• QL adds predicates (e.g. “___ is a dog”) and terms: constants a–w for specific things, variables x, y, z as placeholders.
• The universal quantifier ∀x and existential quantifier ∃x must each be followed by a variable and a formula containing it, called the quantifier’s scope.
• ∀xA is logically equivalent to ¬∃x¬A — either quantifier is technically sufficient, but QL keeps both for readability.
• Identity (=) is required to translate “else,” “besides” and “only,” and to count things: “at least two Fs” needs ∃x∃y(Fx & Fy & x≠y).
• The universe of discourse (UD) fixes what “everyone” or “everything” ranges over in a translation and must be stated explicitly.
• An argument can be valid in English yet invalid once translated into SL, because SL cannot represent the internal “all F are G” structure that QL exists to capture.

Memory Tip: Whenever you see “no one besides X” or “only X,” reach for identity (= / ≠) immediately — these phrases cannot be translated correctly with quantifiers alone, and this is the single most common QL translation trap.

Common Mistake: Assuming ∃x∃y(Fx & Fy) means “at least two Fs.” Without x≠y, x and y can refer to the same thing, so the sentence is true even with only one F in existence.

Important Questions:

• What is the “scope” of a quantifier? The formula immediately following it that it quantifies over — in ∀xHx, the scope of ∀x is Hx.
• Why does “All logicians wear funny hats; Willard is a logician; so Willard wears a funny hat” need QL rather than SL? SL can only replace whole sentences with letters, losing the “all F are G” structure that makes the argument valid; QL keeps that structure with predicates and quantifiers.

Chapter 5: Formal Semantics

Difficulty: Hard · Key topics: object language vs. metalanguage, the valuation function, truth value assignments, interpretations and models in QL, extension of a predicate, entailment, constructing partial models

The chapter formalizes, with mathematical precision, what chapters 2 and 4 did informally. For SL it defines a valuation function v that assigns 1 or 0 to every sentence, built in two stages matching the recursive definition of a wff: base cases for atomic sentences via a truth value assignment a, then rules for every connective. For QL it defines an interpretation as a universe of discourse plus an extension (the set of things a predicate is true of) for every predicate and a referent for every constant, building toward the idea of a model. It introduces the double turnstile ⊨ for entailment — “A ⊨ B” means no model makes A true and B false — and redefines tautology, contradiction, contingency, equivalence, consistency and validity in terms of models rather than truth-value rows. A worked example shows how to build a small partial model, fixing only the predicates and constants that actually matter, to disprove a claim.

Key Points:

• The valuation function v assigns 1 or 0 to every sentence of SL and must match the connective rules exactly — e.g. v(¬A)=1 whenever v(A)=0.
• A truth value assignment a fixes a truth value for every atomic sentence letter — a full assignment is like one very long row of a truth table.
• In QL, an interpretation gives a universe of discourse (UD), an extension for each predicate, and a referent for each constant.
• A ⊨ B (“A entails B”) means there is no model in which A is true and B is false; ⊨ A means A is true in every model.
• A tautology in QL is true in every model and a contradiction is false in every model — the same shape as SL’s definitions, stated over models instead of truth-value rows.
• A partial model, fixing only the predicates and constants that matter to a specific sentence, is enough to disprove a claim — a complete model would need infinitely many entries.

Memory Tip: Hold onto the chapter’s own formula: interpretation + state of the world = truth or falsity. An interpretation alone (what a symbol means) is never enough to fix a sentence’s truth value; you also need to know how the world actually is.

Common Mistake: Trying to write out a “complete” model for QL by hand. A model must assign an extension to every predicate and a referent to every constant, which is impossible to list in full — you only ever need a partial model covering what matters to the sentence at hand.

Important Questions:

• What is the extension of a predicate? The set of things in the universe of discourse the predicate is true of, given an interpretation — e.g. extension(F) = {Batman, Superman, Spiderman, …} if F means “fights crime.”
• What does A ⊨ B mean? That B is true in every model in which A is true — there is no model that makes A true and B false.

Chapter 6: Proofs

Difficulty: Hard · Key topics: natural deduction, introduction and elimination rules, reiteration, derived rules (modus tollens, hypothetical syllogism, dilemma), rules of replacement, proof strategy, soundness and completeness

The chapter builds a natural deduction proof system from the ground up, starting with disjunctive syllogism and modus ponens as motivating examples, then formalizing the idea that a proof is a numbered sequence beginning with the premises, where every later line follows from earlier ones by a named rule. It gives an introduction and an elimination rule for every connective, worked out one at a time (conjunction first: &I and &E), then adds derived rules — modus tollens, hypothetical syllogism, dilemma — that prove nothing new but shorten proofs that basic rules alone could already do, and rules of replacement for rewriting subformulas mid-proof. A dedicated proof-strategy section teaches working backwards from the conclusion’s main connective and forwards from the premises’ available elimination rules, plus indirect proof (assume the negation, derive a contradiction). The chapter closes by defining the single turnstile ⊢ (provability) and stating soundness (everything provable is valid) and completeness (everything valid is provable) as the two properties that make the proof system match the semantics exactly.

Key Points:

• A natural deduction proof is a numbered sequence starting from the premises, where every later line follows by a stated rule referencing earlier line numbers.
• Every connective has an introduction rule (how to derive it as the main connective) and an elimination rule (what follows from it).
• A derived rule (modus tollens, hypothetical syllogism, dilemma) proves nothing new — it is shorthand for a longer proof using only the basic rules.
• Indirect proof (reductio): to prove A, assume ¬A, derive a contradiction, and conclude A.
• ⊢ (the single turnstile) marks that a proof exists; a theorem is a sentence provable with no premises at all.
• Soundness means every provable argument really is valid; completeness means every valid argument is provable — together they say provability and validity coincide exactly.

Memory Tip: Work from both ends at once: look at the conclusion’s main connective to guess the last rule you will need (work backwards), and look at the premises’ main connectives to see which elimination rules are already available (work forwards). Most proofs are solved by meeting in the middle.

Common Mistake: Reaching for a rule that isn’t in the system instead of noticing the target can already be proven by combining basic rules in a subproof — the book’s own derivation of the Dilemma rule from eleven ordinary lines is the standing example of this.

Important Questions:

• What is a derived rule, and why add it if it isn’t strictly necessary? A rule (like modus tollens) that makes no new proofs possible but shortens ones you could already do — added purely for convenience.
• What does it mean for a proof system to be sound and complete? Sound: every provable argument really is valid. Complete: every valid argument can be proven. Together, provability and validity coincide exactly.

Appendix A: Other Symbolic Notation

Appendix · Difficulty: Easy · Key topics: alternative connective symbols, reading other logic textbooks and papers

Since no single symbol set is universal across logic textbooks and journal articles, this short appendix is a translation table between forallx’s own notation and the notation used elsewhere, so a reader isn’t thrown by an unfamiliar symbol in a different source. It covers alternative symbols for negation, conjunction, the material conditional and the material biconditional, and briefly notes that some older texts write conjunction by simple juxtaposition (writing “AB” for “A and B”) rather than with any explicit symbol at all.

Key Points:

• Negation is also written with the swung dash ∼ in many other texts, alongside forallx’s own ¬.
• Conjunction is also written with ∧ or a raised dot •, or in older texts by simple juxtaposition (AB), instead of forallx’s &.
• The material conditional is also written with the hook ⊃ instead of forallx’s arrow →.
• The material biconditional is also written with the triple bar ≡, especially in systems that use ⊃ for the conditional.

Memory Tip: Skim this appendix once before opening a second logic textbook or a journal article — seeing ∼P, P⊃Q or P≡Q for the first time is confusing only because the symbols are unfamiliar, not because the logic is different.

Important Questions:

• What does P ⊃ Q mean in a text that uses this notation? Exactly what forallx writes as P → Q — the material conditional; ⊃ and → are two common symbols for the same connective.
• Why do different logic textbooks use different symbols for the same connectives? There is no single universal notation for formal logic — ¬/∼, &/∧/•, →/⊃ and ↔/≡ are all different typographic conventions for the identical logical operators.

Appendix C: Quick Reference

Appendix · Difficulty: Easy · Key topics: characteristic truth tables, standard SL symbolizations, standard QL symbolizations, identity-based symbolizations

This appendix is a one-page cheat sheet gathering the characteristic truth tables for all five connectives (in both T/F and 1/0 notation) alongside a table of standard English-to-SL and English-to-QL translation patterns — “unless,” “only if,” “all Fs are Gs,” “only j is G,” definite descriptions like “the F is G,” and both readings of “the F is not G.” It is meant as a fast lookup once the chapter material is already understood, condensing chapters 2 through 4 onto a single page you can check a translation or a proof step against.

Key Points:

• Gathers the characteristic truth tables for ¬, &, ∨, →, ↔ in one place, in both T/F and 1/0 notation.
• Gives the standard SL symbolization for “unless,” “neither…nor” and “both…and” in one table.
• Gives the standard QL symbolization for “All Fs are Gs,” “Some Fs are Gs,” “No Fs are Gs” and “Not all Fs are Gs.”
• Covers identity-based patterns: “Only j is G,” “Everything besides j is G,” and definite descriptions like “The F is G,” including both readings of “The F is not G.”

Memory Tip: Use this appendix the way you’d use a formula sheet in a math class — check a translation here after you already understand why it’s true from chapter 2 or chapter 4, not as a shortcut to skip learning the reasoning.

Important Questions:

• How is “Only j is G” symbolized using identity? ∀x(Gx ↔ x=j) — everything that is G is identical to j, and j is G.
• How is a definite description like “The F is G” symbolized in QL? ∃x(Fx & ∀y(Fy → x=y) & Gx) — there is something that is F, everything that is F is that same thing, and it is G.

Download forallx PDF (Free)

This book is free from its official source. Click below to open P.D. Magnus’s own forallx homepage, where you can download the complete PDF and find the LaTeX source if you want to adapt the book yourself.

How to Study This Book

Chapters 1 through 3 (What is Logic?, Sentential Logic, Truth Tables) form the first third of the book and a natural stopping point for a course that only covers sentential/propositional logic. Read them strictly in order — Chapter 3’s truth tables directly test the symbolizations you build in Chapter 2, so skipping ahead makes the truth-table exercises harder to check by hand.

Chapter 4 (Quantified Logic) is the hinge of the book. It only makes sense once Chapters 1 to 3 are solid, because it repeatedly compares what QL can capture against what SL missed — the “Willard is a logician” argument from Chapter 1 reappears specifically to make this point. Do not attempt Chapter 4 as a stand-alone reading.

Chapter 5 (Formal Semantics) is the most abstract chapter, and many courses treat it as optional or defer it to a second course. It formalizes, with mathematical precision, what Chapters 2 through 4 did informally — the valuation function, truth value assignments, and QL’s models. A course focused purely on translation and proofs can move from Chapter 4 straight to Chapter 6; a course preparing students for further logic, metatheory or philosophy of language should not skip it.

Chapter 6 (Proofs) is the longest chapter and depends on Chapters 2 and 4 for the connectives and quantifiers it manipulates. Do not start natural deduction before symbolization is comfortable — every proof line requires correctly reading the main connective of a formula, and that skill has to already be automatic.

Appendix C (Quick Reference) is worth printing once Chapters 2 through 4 are done. It condenses every symbolization pattern in the book onto one page you can check your own translations and proofs against, without re-reading whole sections.

What the book does not cover: modal logic (the possibility operator is mentioned only in passing, in Chapter 3, to explain why it is not truth-functional), inductive logic, and any metatheory beyond the soundness and completeness statements at the very end of Chapter 6. A course that needs modal logic as a follow-on topic should look at a dedicated modal logic text, or at one of the university-specific forallx remixes (forallx:Calgary, for instance) that extend this same base text with additional modal logic and metatheory chapters.

Used In These Programs

This book is used for the Logic / Introduction to Formal Logic course in: BS Computer Science. It is equally suited to a Philosophy department’s Introduction to Logic or Symbolic Logic course. Browse all Logic books or all Computer Science books.

Who Should Read This

forallx suits any student taking a first course in formal or symbolic logic, whether it is offered by a Computer Science department, a Philosophy department, or cross-listed between the two. BSCS students meet the same natural deduction ideas again later in automated theorem proving, formal verification and the theory of computation; Philosophy students meet quantifiers and formal semantics again in metaphysics and philosophy-of-language courses that assume comfort with this material. It is not a substitute for a discrete mathematics course — it does not cover set theory, combinatorics, graph theory or algorithmic complexity — so CS students who need those topics should pair it with a dedicated discrete math text, whose own proof-writing chapters build directly on the natural deduction skills this book teaches.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS and Philosophy programs, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.

FAQs

Related Books

• Discrete Mathematics: An Open Introduction – Oscar Levin (4th Edition)
• Database Management System – IT Series BSCS
• Open Data Structures – Pat Morin (Java Edition)
• Calculus Volume 1 – Strang & Herman (OpenStax)

forallx is the cleanest way to meet formal logic for the first time — six chapters take you from spotting bad arguments in English to proving valid ones with a full natural deduction system, and the free licence means you can keep the PDF, or the LaTeX source, for as long as you need it. Browse more Computer Science books for the rest of your semester.

forallx: An Introduction to Formal Logic, Version 1.4, by P.D. Magnus, University at Albany, State University of New York. Free under the Creative Commons Attribution 4.0 International licence. Official source: https://www.fecundity.com/logic/ — source repository: https://github.com/OpenLogicProject/forallx