Introduction to Logical Thought


Setting the Stage

Logic as the Gold Standard of Thought

Deduction at its Literary Best

Logical Doesn’t Mean Long or Complicated   


Statements and Truth Values

Truth Values

Exactly Two, No More No Less

Statements : The Basic Building Blocks

English Sentences versus Logical Statements


What Can Logical Statements Represent?


Claims about the World


Mathematical Claims

Hardware and Software Specifications

Claims about Programs and Their Performance

Database Integrity Constraints                         

Valid Arguments and Proofs

Argument (Proof)

Unstated Premises

Other Proof Structures

Bad Arguments

Remember the Critical Role of the Premises

Boolean Logic


The Building Blocks of Statements    

Operators and Operands        

Using Operators to Build Complex Statements     

Operator Precedence and Parentheses             

Formal Definitions of the Logical Operators          

Truth Table Definitions of Operators                


Truth Table Definitions of and, or, not, is equivalent to, implies             

Larger Logical Expressions   

Building Truth Tables for More Complex Logical Expressions   

The Truth Table App

Necessary and Sufficient Conditions   

Truth Tables with Three or More Variables           

The Size of the Truth Table Grows Quickly               

Operator Precedence  

Boolean Expressions in Programming             

Controlling Execution  

Boolean Expressions in Programming Languages         

Boolean Queries           

Definition and Examples           

English into Logic          

Boolean Logic Isn’t English       

Practice Converting Between English and Boolean Logic         

Validity, Satisfiability and Contradiction and Counterexamples         



Contradictions   (Unsatisfiability)


More Boolean Operators         

How Many Boolean Operators Could There Be?          

Some Additional Useful Operators    

Boolean Logic in Circuit Design            

The SAT Problem          

Boolean Logic Proofs

What Is a Proof?           

A Proof Is an Argument          

Premises and Theorems         

Setting Up a Proof        

Boolean Logic Proofs Using Truth Tables 


Not Enough Premises  

Wrong Premises           

Contradictory Premises

Proving Other Kinds of Claims               

Theorem upon Theorem          

Boolean Identities        

A List of Identities         

A Nonidentity – Converse        


The p’s and q’s are Placeholders 


A Tool for Checking Boolean Logic Proofs   

Back to Boolean Expressions in Programming   

Normal Forms  

Boolean Inference Rules          


Inference Rules Preserve Truth            

A List of Inference Rules (with Examples)

A Really Useful Problem Solving Technique: Debugging              

Inference Rules Are One Way Streets               

Using Inference Rules Correctly           

Suppose You Want More Rules            

Natural Deduction        


The Structure of a Natural Deduction Proof    

Law of the Excluded Middle     

Creating Natural Deduction Proofs      

Example Proofs (with Videos)  

Theorem upon Theorem (Again): Using Lemmas and Corollaries             

Soundness and Completeness               

Getting at Truth – An Inference System that is Sound and Complete     

Getting at Truth – Sound and Valid Arguments         

Predicate Logic

Introduction, Predicates  and Quantifiers    

Predicates and Quantifiers    

The Building Blocks of Statements    

Defining Predicates

Predicate Logic Well-Formed Formulas

We Inherit the Boolean Operators    


The Universe (Domain)

Quantifier Scope           

Does Quantifier Order Matter?            

Multiple Existential Quantifiers            

More On Using Predicate Logic          

One Notational Shorthand

More on Scope

Does Quantifier Position Matter?

Ground Instances

What If There Aren’t Any?       

Infix Predicates              


Translating to and from Predicate Logic Statements       

Getting Started – What Predicates and Objects to Use               

Functions or Predicates?          



Validity, Satisfiability, Contradiction and Counterexamples


Validity and Satisfiability in Predicate Logic


Predicate Logic Proofs

Identities and Inference Rules for Predicate Logic   

Moving On From Representation to Proof  

Review – Sound Arguments   

Review – Natural Deduction Proofs   

We Inherit All the Rules From Boolean Logic     

Quantifier Exchange    

New Rules for Instantiating and Generalizing Quantifiers           

Our Approach – Back and Forth to Boolean Logic

Working with Universal Quantified Statements: Arbitrary Elements

Working with Existentially Quantified Statements: “The One”             

Substituting One Variable for Another

Universal Instantiation              

Universal Generalization           

Existential Instantiation            

Skolem Functions

Existential Generalization         

Summary of the New Rules     

Creating Predicate Logic Proofs I and II           

Example Proofs (with Videos) 



Discussion and Problems

Practice Representing Claims in Logic

Some Key Ideas

Now We Need Practice

Weaker Statements/Stronger Statements     

Existentials in Implications     

Multiply Nested Quantifiers    

Necessary and Sufficient Conditions   

Converting Formal Claims       

Formal Claims are Easier Than Everyday Claims   

Mathematical Statements       

Using the Definitions of Primes and Composite Numbers

Rational and Irrational Numbers

Business Policies and Database Constraints       

Software Requirements Specifications

The Towers of Hanoi    

Specifications for a Sorting Program   

Specifications for a Business Application       

Converting Everyday Claims    

Choosing Appropriate Predicates        

English into Logic: Issues and Solutions

Getting Off the Ground

What do Words Mean?

What do Names Mean?

What does Not Mean?

We Must Overcome the Perils of English - Ambiguity

Structural Ambiguity

Logical Ambiguity

Referential Ambiguity

Situated Truth

Ambiguity of Some Logical Operators: OR, IMPLIES

“Paradoxes” of Material Implication

We Must Overcome the Perils of English – We Leave Out a Lot and are Sloppy

The Cooperative Principle and Conversational Implicature


We Omit the “obvious”

We’re Often Sloppy

Predicate Logic Doesn’t Solve All Our Representation and Reasoning Problems       

Sketching Some of the Problems         

Dichotomizing the Analog World        

The Sorites Paradox

Taming Vagueness in Describing the Everyday World

Taming Vagueness in Formal Applications

Statistical (Likelihood) Reasoning


Extending the Logical Framework                     

Nonmonotonic Reasoning       


The Closed World Assumption

Higher Order Logic and Equality           

Explicit Reasoning about Knowledge and Belief          

So Where Does That Leave Us?            

A Richer Catalogue of Reasoning and Proof Techniques

Real Proofs

What Are Proofs For?

What Do Real Proofs Look Like?         

Writing Proofs in English        

Direct Proofs  

Simple Direct Proofs in English             

Simple Direct Proofs in Mathematics  

Starting with Definitions           

Don’t Do Proofs Backwards     

Proof by Contradiction 

How Does a Proof by Contradiction Work?

Reductio ad Absurdum             

Proof By Contradiction

The Square Root of 2 is Irrational         

There is No Largest Prime Number      

Proving an Implication Using Contradiction
The Contrapositive (and Modus Tollens)

When Should We Try An Indirect Proof?  

Proof by Example or Counterexample             

The Key Ideas   

Prime Fermat Numbers            

Proof by Example         

Proof by Counterexample        

Mersenne Numbers     

Program (In)correctness and Proof by Counterexample           

Quantifier Exchange and Proof by Example/Counterexample       

Is It Really Impossible to Prove a Negative?          

Proof by Construction  

The Key Idea – When One Value Depends on Another   

The Usefulness of Constructive Proofs               

Divide and Conquer     

Use of Lemmas              

Copy and Paste             

Double Implication       

Proof by Case Enumeration     


The Mutilated Checkerboard

The Coffee Can Problem

The Daisy Petal Game  

Mathematical Induction           

Summation Notation   

The Principle of Mathematical Induction           

The Sum of the First n Positive Integers               

Proving Claims about Inequalities         

Induction Can be an Alternative Even When Other Proofs Exist           

Strong Induction            

The Fibonacci Sequence

Induction When the Objects Don’t Look Like Numbers        

Recursion and Induction            

Inductive Proofs of Other Recursively Defined Structures        

Inductive Proofs of Recursive Programs – The Towers of Hanoi               

Faulty Induction Proofs             

Stronger and Weaker Claims

Proving a Stronger Claim           


Strategies for Discovering Proofs          

Empirical Induction        

Induction from Observations   

Empirical Induction Leads the Way      

Statistical and Probabilistic Truth         

Everyday Reasoning     

Why It’s Hard    

When We Get to Declare What’s True