Home Page | The Book | The Courses |

Part I Language and Logical Form

1 Atomic Statements

1 1 Vagueness and Ambiguity

1 2 Logical English

1 3 Names

1 4 Predicates

1 5 Descriptions

1 6 Atomic Statements

2 Compound Statements

2 1 Truth Functional Connectives

2 2 Statements with Multiple Connectives

2 3 Parenthesis Dropping Conventions

3 Quantified Statements

3 1 Logical Variables

3 2 Conditions

3 3 Open Descriptions

3 4 Quantifiers

4 Expressing Arguments

4 1 Arguments

4 2 Deductive and Inductive Arguments

4 3 Some Practical Suggestions

4 4 Expressing the Logical Structures of Arguments

5 Defining Data Structures

5 1 Properties of the Identity Relation

5 1 1 Identity is Reflexive, Symmetric, and Transitive

5 1 2 Leibniz’s Law

5 2 Defining Data Structures

5 2 1 Sets

5 2 2 Bags

5 2 3 Sequences

5 2 4 Relations

5 2 5 Functions

5 2 6 Stacks

5 2 7 1-Dimensional Arrays

6 Expressing Problem Specifications

6 1 Functional Problem Specifications

6 2 What Can Go Wrong with Problem Specifications

6 3 Expressing Problem Specifications with Logical English

7 Expressing Program Designs

7 1 Pseudocode for Instructions

7 1 1 Atomic Instructions

7 1 2 Compound Instructions

7 2 Pseudocode for Algorithms

Part II Material Truth

8 Truth for Statements with At Most One Connective

8 1 The Laws of Excluded Middle and Noncontradiction

8 2 Atomic Statements

8 3 Truth Functional Connectives

8 3 1 Negation

8 3 2 Conjunction

8 3 3 Disjunction: Inclusive and Exclusive

8 3 4 Material Equivalence

8 3 5 Material Implication

8 4 Conditions

8 5 Quantified Statements

8 6 Summary of Material Truth Conditions

8 7 Some Applications

8 7 1 Short Cut Evaluation: “cand” and “cor”

8 7 2 Bitwise Extensions of Truth Functions

9 Truth for Statements with Multiple Connectives

9 1 Compound Statements

9 1 1 Computing Truth Values of Compound Statements

9 1 2 Reducing the Need for Parentheses

9 2 How to Make Truth Tables for Compound Statements

9 2 1 The Four Parts of a Truth Table

9 2 2 Organizing a Truth Table Calculation

9 3 Reading Truth Tables from Right to Left

10 Tracing Program Execution

10 1 Tracing Program Execution Forwards

10 1 1 Event Trace Tables

10 1 2 Value Trace Tables

10 1 3 Tracing with Complex Conditions

10 2 Tracing Program Execution Backwards

Part III Logical Truth

11 Truth Functional Forms

11 1 Overview

11 2 Truth Functional Forms

11 3 Interpretations of Truth Functional Forms

11 4 Truth Under an Interpretation

11 5 Truth Functional Truth, Falsity, and Contingency

11 6 Using Forms to Find the Logical Status of English Statements

11 7 Application to Simplifying Statements and Conditions

12 Truth Functional Properties of Program Designs

12 1 The General Form of Decision Tables

12 2 Limited Entry Decision Tables

12 2 1 The Basic Form

12 2 2 Simplifying Tables with “Don’t Care” Condition Entries

12 3 Extended Entry Decision Tables

12 4 Decision Tables and Other Control Structures

12 5 Consistency, Completeness, and Redundancy of Decision Tables

13 Quantified Forms

13 1 How Truth Functional Logic Differs from Quantificational Logic

13 2 Well Formed Forms

13 3 Interpretations of Wffs

13 4 Truth of Wffs in an Interpretation

13 5 Logical Truth of Wffs

13 6 Using Wffs to Determine the Logical Status of English Statements

13 7 Conditions Revisited

13 8 Summary of Classifications

14 Logical Equivalence

14 1 Truth Functional Equivalence

14 2 Applications of Truth Functional Equivalence

14 2 1 Equivalence and Simplification of Program Instructions

14 2 2 Equivalence and Simplification of SQL Select Instructions

14 3 Logical Equivalence

14 3 1 Logical Equivalence of Wffs

14 3 2 Logical Equivalence of Conditions

14 4 Applications of Logical Equivalence

14 4 1 Simplification of Problem Specifications

14 4 2 Detecting Redundancy

15 Logical Implication and Validity

15 1 Logical Implication and Validity

15 1 1 Logical Implication

15 1 2 Logical Validity

15 1 3 Soundness

15 2 Determining Validity

15 2 1 Degrees of Formality

15 2 2 Arguments and Corresponding Conditionals

15 2 3 Truth Functional Validity

15 2 4 Logical Validity

16 Rules of Inference

16 1 Limitations of Truth Table Tests

16 2 Rules of Inference

16 2 1 Formal Rules of Inference

16 2 2 Correct and Incorrect Rules of Inference

16 3 Some Truth Functional Rules of Inference

16 3 1 Examples of Correct Rules of Inference

16 3 2 Some Properties of Rules of Inference

16 3 3 Examples of Incorrect Rules of Inference (Formal Fallacies)

17 Proof

17 1 Kinds of Proof

17 1 1 Different Senses of Proof

17 1 2 Formal vs Informal Proofs

17 2 Two Ways of Organizing Proofs

17 3 Three Proof Strategies

17 3 1 Direct Proof

17 3 2 Conditional Proof

17 3 3 Indirect Proof

17 4 Applying Logic to Specific Subjects

17 4 1 Using Instances Of General Forms

17 4 2 Adding Nonlogical Justifications

18 Algorithmic Unsolvability Proofs

18 1 Algorithmic Solvability and Unsolvability

18 2 The Halting Problem is Algorithmically Unsolvable

18 3 Other Algorithmically Unsolvable Problems

19 Program Correctness Proofs

19 1 The Limits of Testing

19 2 Proofs Expressed in English Prose

19 3 Proofs Using Floyd’s Method of Invariant Assertions

19 4 Rules of Inference Involving Algorithms

19 4 1 Notation for Statements Involving Instructions

19 4 2 The Assignment Rule

19 4 3 Rules of Inference about Control Structures

19 5 Proofs Using Rules of Inference

20 Above and Beyond this Book

20 1 Other Texts on Classical Logic

20 1 1 Standard Texts

20 1 2 Computer Oriented Texts

20 2 Extensions of Classical Logic

20 2 1 Floyd-Hoare Logic

20 2 2 Temporal, Modal, and Dynamic Logics

20 3 Rivals to Classical Logic

20 4 Applications of Logic to Computing or Computing to Logic

20 4 1 Logic Circuits

20 4 2 3-Valued Logic and SQL

20 4 3 More on Expressing and Using Specifications

20 4 4 Logic Testing of Software

20 4 5 Computability and Algorithmic Unsolvability

20 4 6 AI and Computer Aided Reasoning

20 4 7 Quantum Computing and Programming

20 5 Programming Challenges

Solutions to Selected Exercises

Sources and Bibliography

Index