Elementary Logic for Software Development

Detailed Contents


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

Top of Page