# Introduction to Logical Thought

## Introduction

### Setting the Stage

Logic as the Gold Standard of Thought

Deduction at its Literary Best

Logical Doesn’t Mean Long or Complicated

Goals

### 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?

Introduction

Definitions

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

Remember the Critical Role of the Premises

## Boolean Logic

### Statements

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

Introduction

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

Tautologies

Satisfiability

Counterexamples

### More Boolean Operators

How Many Boolean Operators Could There Be?

## 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

Introduction

Not Enough Premises

Wrong Premises

Proving Other Kinds of Claims

Theorem upon Theorem

### Boolean Identities

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

### Boolean Inference Rules

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

### Natural Deduction

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

### 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

Quantifiers

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

Equality

### Translating to and from Predicate Logic Statements

Getting Started – What Predicates and Objects to Use

Functions or Predicates?

Definitions

Negation

### Validity, Satisfiability, Contradiction and Counterexamples

Meaning

Validity and Satisfiability in Predicate Logic

Counterexamples

## 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)

Lemmas

### Soundness/Completeness/Decidability

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

Software Requirements Specifications

The Towers of Hanoi

Specifications for a Sorting Program

### 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

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

The Cooperative Principle and Conversational Implicature

Presuppositions

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

Taming Vagueness in Describing the Everyday World

Taming Vagueness in Formal Applications

Statistical (Likelihood) Reasoning

Most

### Extending the Logical Framework

Nonmonotonic Reasoning

Inheritance

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

How Does a Proof by Contradiction Work?

The Square Root of 2 is Irrational

There is No Largest Prime Number

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

### Invariants

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

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

Guards

### Empirical Induction

Induction from Observations