1
FOUNDATIONS
1.1 Propositional and Predicate LogicJerrold W. Grossman
1.1.1 Propositions and Logical Operations
1.1.2 Equivalences, Identities, and Normal Forms
1.1.3 Predicate Logic
1.2 Set TheoryJerrold W. Grossman
1.2.1 Sets
1.2.2 Set Operations
1.2.3 Infinite Sets
1.2.4 Axioms for Set Theory
1.3 FunctionsJerrold W. Grossman
1.3.1 Basic Terminology for Functions
1.3.2 Computational Representation
1.3.3 Asymptotic Behavior
1.4 RelationsJohn G. Michaels
1.4.1 Binary Relations and Their Properties
1.4.2 Equivalence Relations
1.4.3 Partially Ordered Sets
1.4.4 n-Ary Relations
1.5 Proof TechniquesSusanna S. Epp
1.5.1 Rules of Inference
1.5.2 Proofs
1.5.3 Disproofs
1.5.4 Mathematical Induction
1.5.5 Diagonalization Arguments
1.6 Axiomatic Program VerificationDavid Riley
1.6.1 Assertions and Semantic Axioms
1.6.2 NOP, Assignment, and Sequencing Axioms
1.6.3 Axioms for Conditional Execution Constructs
1.6.4 Axioms for Loop Constructs
1.6.5 Axioms for Subprogram Constructs
1.7 Logic-Based Computer Programming ParadigmsMukesh Dalal
1.7.1 Logic Programming
1.7.2 Fuzzy Sets and Logic
1.7.3 Production Systems
1.7.4 Automated Reasoning
INTRODUCTION
This chapter covers material usually referred to as the foundations of mathematics, including logic, sets, and functions. In addition to covering these foundational areas, this chapter includes material that shows how these topics are applied to discrete mathematics, computer science, and electrical engineering. For example, this chapter covers methods of proof, program verification, and fuzzy reasoning.
GLOSSARY
action: a literal or a print command in a production system.
aleph-null: the cardinality of the set of natural numbers.
AND: the logical operator for conjunction, also written ∧.
antecedentL in a conditional proposition p → q (“if p then q”), the proposition p (“if-clause”) that precedes the arrow.
antichain: a subset of a poset in which no two elements are comparable.
antisymmetric: the property of a binary relation R that if aRb and bRa, then a = b.
argument form: a sequence of statement forms, each called a premise of the argument, followed by a statement form called a conclusion of the argument.
assertion: (or program assertion) a program comment specifying some conditions on the values of the computational variables; these conditions are supposed to hold whenever program flow reaches the location of the assertion.
asymmetric: the property of a binary relation R that if aRb, then .
asymptotic: A function f is asymptotic to a function g, written f(x) ~ g(x), if f(x) ≠ 0 for sufficiently large x and .
atom (or atomic formula): a simplest formula of predicate logic.
atomic formula: See atom.
atomic proposition: a proposition tha...