AN INTRODUCTION TO LOGIC
CONTENTS PROPOSITIONAL LOGIC WHAT IS PROPOSITIONAL LOGIC? VALIDITY, SATIS?ABILITY, AND CONTRADICTION CONSEQUENCE AND EQUIVALENCE FORMAL PROOFS PROOF BY INDUCTION MATHEMATICAL INDUCTION INDUCTION ON THE COMPLEXITY OF FORMULAS NORMAL FORMS HORN FORMULAS RESOLUTION CLAUSES RESOLVENTS COMPLETENESS OF RESOLUTION COMPLETENESS AND COMPACTNESS STRUCTURES AND ?RST-ORDER LOGIC THE LANGUAGE OF ?RST-ORDER LOGIC THE SYNTAX OF ?RST-ORDER LOGIC SEMANTICS AND STRUCTURES EXAMPLES OF STRUCTURES GRAPHS RELATIONAL DATABASES LINEAR ORDERS NUMBER SYSTEMS THE SIZE OF A STRUCTURE RELATIONS BETWEEN STRUCTURES EMBEDDINGS SUBSTRUCTURES DIAGRAMS THEORIES AND MODELS PROOF THEORY CONJUNCTIVE PRENEX NORMAL FORM SKOLEM NORMAL FORM HERBRAND THEORY HERBRAND STRUCTURES DEALING WITH EQUALITY THE HERBRAND METHOD RESOLUTION FOR ?RST-ORDER LOGIC UNI?CATION SLD-RESOLUTION PROLOG PROPERTIES OF ?RST-ORDER LOGIC THE COUNTABLE CASE CARDINAL KNOWLEDGE ORDINAL NUMBERS CARDINAL ARITHMETIC CONTINUUM HYPOTHESES FOUR THEOREMS OF ?RST-ORDER LOGIC AMALGAMATION OF STRUCTURES PRESERVATION OF FORMULAS SUPERMODELS AND SUBMODELS UNIONS OF CHAINS AMALGAMATION OF VOCABULARIES THE EXPRESSIVE POWER OF ?RST-ORDER LOGIC FIRST-ORDER THEORIES COMPLETENESS AND DECIDABILITY CATEGORICITY COUNTABLY CATEGORICAL THEORIES DENSE LINEAR ORDERS RYLL-NARDZEWSKI ET AL THE RANDOM GRAPH AND 0–1 LAWS QUANTI?ER ELIMINATION FINITE RELATIONAL VOCABULARIES THE GENERAL CASE MODEL-COMPLETENESS MINIMAL THEORIES FIELDS AND VECTOR SPACES SOME ALGEBRAIC GEOMETRY MODELS OF COUNTABLE THEORIES TYPES ISOLATED TYPES SMALL MODELS OF SMALL THEORIES ATOMIC MODELS HOMOGENEITY PRIME MODELS BIG MODELS OF SMALL THEORIES COUNTABLE SATURATED MODELS MONSTER MODELS THEORIES WITH MANY TYPES THE NUMBER OF NONISOMORPHIC MODELS A TOUCH OF STABILITY COMPUTABILITY AND COMPLEXITY COMPUTABLE FUNCTIONS AND CHURCH’S THESIS PRIMITIVE RECURSIVE FUNCTIONS THE ACKERMANN FUNCTION RECURSIVE FUNCTIONS COMPUTABLE SETS AND RELATIONS COMPUTING MACHINES CODES SEMI-DECIDABLE DECISION PROBLEMS UNDECIDABLE DECISION PROBLEMS NONRECURSIVE SETS THE ARITHMETIC HIERARCHY DECIDABLE DECISION PROBLEMS EXAMPLES TIME AND SPACE NONDETERMINISTIC POLYNOMIAL-TIME NP-COMPLETENESS THE INCOMPLETENESS THEOREMS AXIOMS FOR ?RST-ORDER NUMBER THEORY THE EXPRESSIVE POWER OF ?RST-ORDER NUMBER THEORY G¨ODEL’S FIRST INCOMPLETENESS THEOREM G¨ODEL CODES G¨ODEL’S SECOND INCOMPLETENESS THEOREM GOODSTEIN SEQUENCES BEYOND ?RST-ORDER LOGIC SECOND-ORDER LOGIC IN?NITARY LOGICS FIXED-POINT LOGICS LINDSTR¨OM’S THEOREM FINITE MODEL THEORY FINITE-VARIABLE LOGICS CLASSICAL FAILURES DESCRIPTIVE COMPLEXITY LOGIC AND THE P = NP PROBLEM WHAT IS PROPOSITIONAL LOGIC? IN PROPOSITIONAL LOGIC, ATOMIC FORMULAS ARE PROPOSITIONS ANY ASSERTION WILL DO FOR EXAMPLE, A = “ARISTOTLE IS DEAD,” B = “BARCELONA IS ON THE SEINE,” AND C = “COURTNEY LOVE IS TALL” ARE ATOMIC FORMULAS ATOMIC FORMULAS ARE THE BUILDING BLOCKS USED TO CONSTRUCT SENTENCES IN ANY LOGIC, A SENTENCE IS REGARDED AS A PARTICULAR TYPE OF FORMULA IN PROPOSITIONAL LOGIC, THERE IS NO DISTINCTION BETWEEN THESE TWO TERMS WE USE “FORMULA” AND “SENTENCE” INTERCHANGEABLY IN PROPOSITIONAL LOGIC, AS WITH ALL LOGICS WE STUDY, EACH SENTENCE IS EITHER TRUE OR FALSE A TRUTH VALUE OF 1 OR 0 IS ASSIGNED TO THE SENTENCE ACCORDINGLY IN THE ABOVE EXAMPLE, WE MAY ASSIGN TRUTH VALUE 1 TO FORMULA A AND TRUTH VALUE 0 TO FORMULA B IF WE TAKE PROPOSITION C LITERALLY, THEN ITS TRUTH IS DEBATABLE PERHAPS IT WOULD MAKE MORE SENSE TO ALLOW TRUTH VALUES BETWEEN 0 AND 1 WE COULD ASSIGN 0 75 TO STATEMENT C IF MISS LOVE IS TALLER THAN 75% OF AMERICAN WOMEN FUZZY LOGIC ALLOWS SUCH TRUTH VALUES, BUT THE CLASSICAL LOGICS WE STUDY DO NOT IN FACT, THE CONTENT OF THE PROPOSITIONS IS NOT RELEVANT TO PROPOSITIONAL LOGIC HENCEFORTH, ATOMIC FORMULAS ARE DENOTED ONLY BY THE CAPITAL LETTERS A, B, C, (POSSIBLY WITH SUBSCRIPTS) WITHOUT REFERRING TO WHAT THESE PROPOSITIONS ACTUALLY SAY THE VERACITY OF THESE FORMULAS DOES NOT CONCERN US PROPOSITIONAL LOGIC IS NOT THE STUDY OF TRUTH, BUT OF THE RELATIONSHIP BETWEEN THE TRUTH OF ONE STATEMENT AND THAT OF ANOTHER THE LANGUAGE OF PROPOSITIONAL LOGIC CONTAINS WORDS FOR “NOT,” “AND,” “OR,” “IMPLIES,” AND “IF AND ONLY IF ” THESE WORDS ARE REPRESENTED BY SYMBOLS: ¬ FOR “NOT,” ?FOR “AND,” ?FOR “OR,” ?FOR “IMPLIES,” AND ?FOR “IF AND ONLY IF ” AS IS ALWAYS THE CASE WHEN TRANSLATING ONE LANGUAGE INTO ANOTHER, THIS CORRES- PONDENCE IS NOT EXACT UNLIKE THEIR ENGLISH COUNTERPARTS, THESE SYMBOLS REPRESENT CONCEPTS THAT ARE PRECISE AND INVARIABLE THE MEANING OF AN ENGLISH WORD, ON THE