Logic as the Gold Standard
of Thought
Deduction at its Literary
Best
Logical Doesn’t Mean Long
or Complicated
Goals
Truth Values
Exactly Two, No More No
Less
Statements : The Basic
Building Blocks
English Sentences versus
Logical Statements
Paradoxes
Introduction
Claims about the World
Definitions
Mathematical Claims
Hardware and Software
Specifications
Claims about Programs and
Their Performance
Database Integrity
Constraints
Argument (Proof)
Unstated Premises
Other Proof Structures
Bad Arguments
Remember the Critical Role
of the Premises
The Building Blocks of Statements
Operators and Operands
Using Operators to Build
Complex Statements
Operator Precedence and
Parentheses
Formal Definitions of the
Logical Operators
Introduction
Truth Table Definitions of and, or,
not, is equivalent to, implies
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
Controlling Execution
Boolean Expressions in
Programming Languages
Definition and Examples
Boolean Logic Isn’t English
Practice Converting Between
English and Boolean Logic
Tautologies
Satisfiability
Contradictions
(Unsatisfiability)
Counterexamples
How Many Boolean Operators
Could There Be?
Some Additional Useful
Operators
A
Proof Is an Argument
Premises
and Theorems
Setting
Up a Proof
Introduction
Not Enough Premises
Wrong Premises
Contradictory Premises
Proving Other Kinds of Claims
Theorem
upon Theorem
A List
of Identities
A
Nonidentity – Converse
Computation
The
p’s and q’s are Placeholders
Simplification
A Tool
for Checking Boolean Logic Proofs
Back
to Boolean Expressions in Programming
Normal
Forms
Introduction
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
Introduction
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
Getting
at Truth – An Inference System that is Sound and Complete
Getting
at Truth – Sound and Valid Arguments
Predicates and Quantifiers
The Building Blocks of Statements
Defining Predicates
Predicate Logic Well-Formed Formulas
We Inherit the Boolean Operators
Quantifiers
The Universe (Domain)
Quantifier Scope
Does Quantifier Order Matter?
Multiple
Existential Quantifiers
One
Notational Shorthand
More
on Scope
Does Quantifier
Position Matter?
Ground
Instances
What
If There Aren’t Any?
Infix
Predicates
Equality
Getting
Started – What Predicates and Objects to Use
Functions
or Predicates?
Definitions
Negation
Meaning
Validity
and Satisfiability in Predicate Logic
Counterexamples
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
Example
Proofs (with Videos)
Lemmas
Discussion and Problems
Now We
Need Practice
Weaker
Statements/Stronger Statements
Existentials
in Implications
Multiply
Nested Quantifiers
Necessary
and Sufficient Conditions
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
Choosing
Appropriate Predicates
What do Words Mean?
What do Names Mean?
What does Not Mean?
Structural
Ambiguity
Logical
Ambiguity
Referential
Ambiguity
Situated
Truth
Ambiguity
of Some Logical Operators: OR, IMPLIES
“Paradoxes”
of Material Implication
The
Cooperative Principle and Conversational Implicature
Presuppositions
We
Omit the “obvious”
We’re
Often Sloppy
Sketching
Some of the Problems
The
Sorites Paradox
Taming
Vagueness in Describing the Everyday World
Taming
Vagueness in Formal Applications
Statistical
(Likelihood) Reasoning
Most
Nonmonotonic
Reasoning
Inheritance
The
Closed World Assumption
Higher
Order Logic and Equality
Explicit
Reasoning about Knowledge and Belief
So
Where Does That Leave Us?
What Are Proofs For?
What Do Real Proofs Look Like?
Writing
Proofs in English
Simple
Direct Proofs in English
Simple
Direct Proofs in Mathematics
Starting
with Definitions
Don’t
Do Proofs Backwards
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?
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?
The
Key Idea – When One Value Depends on Another
The
Usefulness of Constructive Proofs
Use of
Lemmas
Copy
and Paste
Double
Implication
Proof
by Case Enumeration
The Mutilated Checkerboard
The Coffee Can Problem
The
Daisy Petal Game
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
Proving
a Stronger Claim
Guards
Induction
from Observations
Empirical
Induction Leads the Way
Statistical
and Probabilistic Truth
Why
It’s Hard
When
We Get to Declare What’s True