A Course in Symbolic Logic

✍ Scribed by Haim Gaifman

• Year: 2002
• Tongue: English
• Leaves: 371
• Category: Library

✦ Table of Contents

A Course in Symbolic Logic
Contents
Introduction
A Bit of History
“Critical Thinking”, what Symbolic Logic Is Not
The Research Program of Symbolic Logic
First-Order Logic
The Wider Scope of Artificial Languages
The Goals and the Structure of the Course
Chapter 1 Declarative Sentences
1.0
1.1 Truth-Values
1.1.0
Notation
1.1.1 Context Dependency
1.1.2 Types and Tokens
Indexicals and Demostratives
Some Kinds of Ambiguity
Eliminating Simple Context Dependencies
Note
1.1.3 Vagueness and Open Texture
Vagueness of Generality
1.1.4 Other Causes of Truth-Value Gaps
Non-Denoting Terms
Category Mistakes
1.2 Some Other Uses of Declarative Sentences
Fictional Contexts
Metaphors, Similes, and Aphorisms
Chapter 2 Sentential Logic: Some Basic Concepts and Techniques
2.0
Note
2.1 Sentential Variables, Connectives and Truth-Tables, Atomic Sentences
2.1.0
2.1.1 Negation
2.1.2 Conjunction
Repeated Applications and Grouping
Grouping Conventions
Homework 2.1
2.1.3 Truth-Tables
The Number of Rows
Homework 2.2
Sentences and Sentential Expressions
Sentences as Instances
Truth-Values of Sentential Expressions
Truth Functionality
2.1.4 Atomic Sentences in Sentential Logic
2.2 Logical Equivalence, Tautologies and Contradictions
2.2.0
Notation and Terminology
Note
Equivalence and Sentential Expressions
Truth-Table Checking
2.2.1 Some Basic Laws Concerning Equivalence
Reflexivity
Symmetry
Transitivity
Congruence Laws and Substitution of Equivalent Components
Some Terminology and Notation
‘Iff’
Non-Equivalent Sentences
Homework
2.3
2.4
Note
2.2.2 Disjunction
Homework 2.5
Grouping with Disjunctions
Homework 2.6
2.2.3 Logical Truth and Falsity, Tautologies and Contradictions
Note
Note
Note
Tautological and Contradictory Sentential Expressions
Homework 2.7
2.3 Syntactic Structure
2.3.0
Main Connective and Component Structure
Homework 2.8
Displayed Components
Occurrences
Displayed Occurrences
Terminology
Main Connectives in Sentential Expressions
Homework 2.9
Substitutions of Sentential Components
Note
Homework 2.10
Repeated Conjunctions and Disjunctions
2.3.1 Sentences as Trees
Homework 2.11
2.3.2 Polish Notation
Homework 2.12
2.4 Syntax and Semantics
2.5 Sentential Logic as an Algebra
2.5.0
Instances
Homework 2.13
Note
Left and Right Distributive Laws
2.5.1 Using the Equivalence Laws
Pushing-In Negations
De Morgan’s Laws for Repeated Conjunctions and Disjunctions
Pushing-In Conjunctions
WATCH IT
Simultaneous Distributing of Conjunctions
Pushing-In Disjunctions
Homework
2.14
2.15
WATCH IT
Pulling Out Negations and Common Factors
2.5.2 Additional Equivalence Laws
Note
Redundant Conjuncts and Disjuncts
Redundant Conjuncts
Redundant Disjuncts
Homework 2.16
Note
Homework 2.17
Small Sets of Laws
Homework 2.18
2.5.3 Duality
Duality of Sentential Expressions
Note
Homework 2.19
Note
2.6 Conditional and Biconditional
Conditional
Note
Note
Grouping Convention for →
Note
Homework
2.20
2.21
2.22
Note
Biconditional
Note
Homework 2.23
Grouping
Simplifying Expressions Containing Conditionals and Biconditionals
Homework 2.24
Chapter 3 Sentential Logic in Natural Language
3.0
Truth-Functional Compounds and The Truth-Value Test
Truth-Value Test
The Use of Hybrid Expressions
Note on Terminology
3.1 Classical Sentential Connectives in English
3.1.1 Negation
3.1.2 Conjunction
‘And’
Homework 3.1
Homework 3.2
3.1.3 Disjunction
Inclusive and Exclusive ‘Or’
‘Or’ with ‘Can’
Homework
3.3
3.4
3.1.4 Conditional and Biconditional
‘If’ and ‘Only If’, Sufficient versus Necessary Conditions
‘If’-Statements that Express Generality
Other Ways of Expressing Conditionals
Unless
Biconditional
Homework 3.5
Chapter 4 Logical Implications and Proofs
4.0
4.1 Logical Implication
Terminology and Notation
Note
Homework 4.1
Homework 4.2
Note
4.2 Implications with Many Premises
4.2.0
Notation
The Empty Premise List
4.2.1 Some Basic Implication Laws and Top-Down Derivations
Note
Equivalent Premise Lists
Note
Homework 4.3
4.2.2 Additional Implication Laws and Derivations as Trees
Terminology
Top-Down Derivations Written as Trees
Laws for Other Connectives and More on Top-Down Derivations
Note
Homework 4.4
Note
The Rule for Numbering Nodes in a Tree
Note
Note
Treatment of Negated Compounds
Homework
4.5
4.6
4.2.3 Logically Inconsistent Premises
Note
Homework 4.7
4.3 A Fool-Proof Method for Finding Proofs and Counterexamples
4.3.1 Validity and Counterexamples
Example
Equivalence for Counterexamples
4.3.2 The Basic Laws
Self-Evident Implications
Reduction Laws
Laws for Conjunction
Laws for Disjunction
Laws for Conditional
Laws for Biconditional
Reduction Laws for Negated Compounds
Laws for Negated Negations
Laws for Negated Conjunctions
Laws for Negated Disjunctions
Laws for Negated Conditionals
Laws for Negated Biconditionals
Branching Laws
Memorization
Elementary Implications
Claim
Proof
4.3.3 The Fool-Proof Method
Note
Note
Homework 4.8
Some Noteworthy Properties of the Method
Note
Homework 4.9
4.4 Proofs by Contradiction
4.4.0
4.4.1 The Fool-Proof Method for Proofs by Contradiction
Homework 4.10
The Laws for Proofs by Contradiction
Self-Evident Implication
Contradictory-Conclusion Law
Law for Negated Negations
Laws for Conjunctions and Negated Conjunctions
Laws for Disjunctions and Negated Disjunctions
Laws for Conditionals and Negated Conditionals
Laws for Biconditionals and Negated Biconditionals
4.5 Implications of Sentential Logic in Natural Language
4.5.0
Noteworthy Points
4.5.1 Meaning Postulates and Background Assumptions
Background Assumptions
4.5.2 Implicature
Implicature versus Ambiguity
The Principle of Adjusting
Homework 4.11
Chapter 5 Mathematical Interlude
5.0
5.1 Basic Concepts of Set Theory
5.1.1 Sets, Membership and Extensionality
Terminology
Extensionality
Ways of Denoting Sets
Variants of the Notation
Homework 5.1
Note
Singletons
The Empty Set
5.1.2 Subsets, Intersections, and Unions
Proper Subsets
Note
Intersections
Examples
Disjoint Sets
Unions
Examples
Repeated Intersections and Repeated Unions
Distributive Laws
Homework
5.2
5.3
5.1.3 Sequences and Ordered Pairs
Equality of Sequences
Ordered Pairs, Triples, Quadruples, etc.
5.1.4 Relations and Cartesian Products
Note
Note
Relations Over a Given Domain
Homework
5.4
5.5
Cartesian Products
Note
Examples
Cartesian Powers
Homework
5.6
5.7
5.8
Functions
Example
One-to-One Functions and Equinumerous Sets
Functions of Severed Arguments
5.2 Inductive Definitions and Proofs, Formal Languages
5.2.1 Inductive definitions
Note
Note
Operations on Sets, Monotonicity and Fixed Points
Note
Note
Note
Terminology and Notation
Homework 5.9
The Set of Maternal Descendants
Note
Inductive Definitions of Relations
Notation
Homework 5.10
5.2.2 Proofs by Induction
Example
Proofs By Induction on Natural Numbers
Note
Note
Strong Induction
5.2.3 Formal Languages as Sets of Strings
Strings Over Σ
Concatenation of Strings
Inductive Definitions of Sets of Strings
Prefixes of Strings
Homework 5.11
Note
Examples
Homework
5.12
5.13
Proofs by Induction on Strings
Claim
Proof
Homework 5.14
5.2.4 Simultaneous Induction
Chapter 6 The Sentential Calculus
6.0
6.1 The Language and Its Semantics
6.1.0
6.1.1 Sentences as Strings
Note
The Symbol-Counting Method
Main Claim
Proof
Proof
Note
Homework 6.1
Note
6.1.2 Semantics of the Sentential Calculus
Note
Note
Note
6.1.3 Normal Forms, Truth-Functions and Complete Sets of Connectives
Definition
Note
Theorem
Example
Note
Homework 6.2
Expressing Truth-Functions by Sentences
Definition
Example
Note
Theorem
Proof
Example
Example
Full DNFs and CNFs
Terminology
Definition
Examples
Note
Homework
6.3
6.4
Dummy Atoms
Note
General Connectives and Complete Connective Sets
Note
Homework
6.5
6.6
6.7
6.8
6.9
6.2 Deductive Systems of Sentential Calculi
6.2.1 On Formal Deductive Systems
Note
6.2.2 Hilbert-Type Deductive Systems
Proofs and Theorems
Terminology
Note
Note
Proofs as Trees
Notation
6.2.3 A Hilbert-Type Deductive System for Sentential Logic
Note
Homework 6.10
Proving that Something Is Provable
Derived Inference Rules
Proofs From Premises
Definition
Note
Example
Note
The Deduction Theorem
Note
Homework 6.11
6.2.4 Soundness and Completeness
Soundness
Completeness
The Completeness of HS1
Homework 6.12
Homework
6.13
6.14
6.15
Note
Note
6.2.5 Gentzen-Type Deductive Systems
Note
Soundness
Completeness
Terminology
The Deductive System GS1
Soundness and Completeness of GS1
The Gentzen-Type Deductive System GS2
Chapter 7 Predicate Logic Without Quantifiers
7.0
Individual Constants
Predicates
Note
7.1 PC_0, The Formal Language and Its Semantics
7.1.0
Note
Example
WATCH OUT
7.1.1 The Semantics of PC_0
Note
Homework
7.1
7.2
7.3
7.4
Substitutions of Individual Constants
7.2 PC_0 with Equality
7.2.0
Extensionality Principle
7.2.1 Top-Down Fool-Proof Methods For PC_0 with Equality
Equality Laws For Proofs-by-Contradiction
Note
Note
The Adequacy of the Method
Note
The Top-Down Method of 4.3.3 for PC_0 with Equality
Example
Gentzen-Type Systems for PC_0 with Equality
A Hilbert-Type System for PC_0 with Equality
Homework
7.5
7.6
7.7
7.8
7.3 Structures of Predicate Logic in Natural Language
7.3.1 Variables and Predicates
Variables as Place Markers
Deriving Predicates from English Sentences
7.3.2 Predicates and Grammatical Categories of Natural Language
Two Usages of ‘is’
Singular Terms
Note
7.3.3 Meaning Postulates and Logical Truth Revisited
7.4 PC_0^, Predicate Logic with Individual Variables
7.4.0
Terms
Well Formed Formulas, or Wffs
Atomic Wffs
The Sentences of PC_0^
Examples
Note
7.4.1 Substitutions
Examples
Examples
Variable Displaying Notation
7.4.2 Variables and Structural Representation
Watch Out
Homework 7.9
Note
Chapter 8 First-Order Logic, The Language and Its Relation to English
8.1 First View
8.2 Wffs and Sentences of FOL
8.2.0
Note
First-Order Wffs (Well-Formed Formulas)
Terminology
Unique Readability
Operants, Scopes and Subformulas
Nested Quantifiers
Grouping Conventions for Quantifier-Operants
8.2.1 Bound and Free Variables
Examples
The Binding Quantifier
Individual Constants
Sentences
8.2.2 More on the Semantics
Note
Variable Displaying Notation
Homework 8.1
Repeated Use of Bound Variables
8.2.3 Substitutions of Free and Bound Variables
Example
Note
Legitimate Substitutions of Free Terms
Substitution of Bound Variables
Legitimate Substitutions of Bound Variables
Legitimate Substitutions in General
Note
Homework 8.2
8.2.4 First-Order Languages with Function Symbols
Peano’s Arithmetic
8.3 First-Order Quantification in Natural Language
8.3.1 Natural Language and the Use of Variables
Homework 8.3
Concerning Gender
8.3.2 Some Basic Forms of Quantification
Watch Out
Note
Relativized Quantifiers
Many-Sorted Languages
Note
8.3.3 Universal Quantification
Distributive versus Collective ‘All’
Note
All with Negation
Solid Compounds
8.3.4 Existential Quantification
Solid Compounds of ‘Some’
‘There Is’, ‘There Exists’, ‘There was’, ‘There will be’
8.3.5 More on First Order Quantification in English
Generality of Time and Location
Universal Generalization
Existential Generalization
Temporal Aspects and Indexicality
Note
Non-Temporal Use of Temporal Terms
Existential Import
Something about ‘Someone’
Note
Generality through Indefinite Articles
Generality through Negation
Generalization through ‘Some’
General Advice
8.3.6 Formalization Techniques
Expressing Uniqueness
Homework 8.4
Divide and Conquer
Homework
8.5
8.6
Chapter 9 Models for FOL, Satisfaction, Truth and Logical Implication
9.1 Models, Satisfaction and Truth
9.1.0
Note
Notation and Terminology
Note
Note 1
Note 2
Note 3
9.1.1 The Truth Definition
Inductive Definition
Atomic Wffs
Sentential Compounds
Universal Quantifier
Existential Quantifier
A Special Kind of Induction
Note
Understanding the Logical Particles
Satisfaction
Ambiguity of ‘⊨’
Dependence on Free Variables
Example
Homework 9.1
9.1.2 Defining Sets and Relations by Wffs
Note
Examples
Repeated Quantifier Notation
Homework
9.2
9.3
9.2 Logical Implications in FOL
9.2.0
Satisfiable Sets of Wffs
Logical Equivalence
9.2.1 Proving Non-Implications by Counterexamples
(1)
(2)
Homework 9.4
9.2.2 Proving Implications by Direct Semantic Arguments
(3)
(4)
(5)
(6)
(7)
9.2.3 Equivalence Laws and Simplifications in FOL
Commutativity of Quantifiers of the Same Kind
Distributivity of Quantifier Over Appropriate Connective
De Morgan’s Laws for Quantifiers
Rules of Passage (x is not free in α)
Changing Bound Variables
Example
Pushing Negation Inside
Note
Expressing the Quantifiers in Terms of Each Other
Homework 9.5
9.3 The Top-Down Derivation Method for FOL Implications
9.3.0
9.3.1 The Implication Laws for FOL
Notation
New Constants
Substitution of Free Variables by New Constants
Universal and Existential Quantification
Negated Quantifications
For Languages with Equality
For Languages with Function Symbols
The Validity of the FOL Laws
Lemma 1
Lemma 2
Note
Proof of Lemma 2
Note
Instantiations
9.3.2 Examples of Top-Down Derivations
(Ⅰ)
Explanation
(Ⅱ)
(Ⅲ)
Explanation
(Ⅳ)
Note
(Ⅴ)
9.3.3 The Adequacy of the Method: Completeness
The Completeness of the Proof System
Homework 9.6
Homework
Chapter 2
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
2.16
2.17
2.18
2.19
2.20
2.21
2.22
2.23
2.24
Chapter 3
3.1
3.2
3.3
3.4
3.5
Chapter 4
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
Chapter 5
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12
5.13
5.14
Chapter 6
6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9
6.10
6.11
6.12
6.13
6.14
6.15
Chapter 7
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
7.9
Chapter 8
8.1
8.2
8.3
8.4
8.5
8.6
Chapter 9
9.1
9.2
9.3
9.4
9.5
9.6