Chapter 4

• Mathematical Logic


  Methods of reasoning, provides rules and techniques to determine whether an argument is valid
• Theorem


  A statement that can be shown to be true (under certain conditions)
• Statement (proposition)


  A declarative sentence that is either true or false, but not both
• Truth value


  One of the values "truth" or "falsity" assigned to a statement
• Negation


  The negation of p, written ~p, is the statement obtained by negating statement p
• Conjunction


  The conjunction of p and q, written p^q, is the statement formed by joining statements p and q using the word "and"
• Disjunction


  The disjunction of p and q, written pvq, is the statement formed by joining statements p and q using the word "or"
• Implication


  The statement "if p then q" is called an implication or condition. It is written p→q and read "If p, then q".
• Biimplication


  The statement "p if and only if q" is called the biimplication or biconditional of p and q. It is written p↔q.
• Statement Formulas


  • Symbols p,q,r,..., called statement variables
  • Symbols ~, ^, v, →, and ↔ are called logical connectives
  • A statement variable is a statement formula
  • If A and B are statement formulas, then the expressions (~A), (A^B), (AvB), (A→B) and (A↔B) are statement formulas
• Precedence of logical connectives:
• Tautology


  A statement formula A is a tautology if the truth value of A is T for any assignment of the truth values T and F to the statement variables occurring in A.
• Contradiction


  A statement formula A is a contradiction if the truth value of A is F for any assignment of the truth values T and F to the statement variables occurring in A.
• Logically Implies


  A statement formula A logically implies a statement formula B if the statement formula A→B is a tautology.
• Logically Equivalent


  A statement formula A is logically equivalent to a statement formula B if the statement formula A↔B is a tautology.
• Logical Equivalences
• Validity of Arguments


  An argument is logically valid if the statement formula A1^A2^...^An-1→An is a tautology, where A1, A2, ..., An-1 are the premises and An is the conclusion.
• Modus Tollens (Method of Denying)

  • p → q
  • ~q
  • ~p
• Premises


  • P
  • Q
• Disjunctive Syllogisms


  • p v q
  • ~p
  • ∴ p
• Hypothetical Syllogism


  • p → q
  • q → r
  • ∴ p → r
• Dilemma


  • p v q
  • p → r
  • q → r
  • ∴ r
• Conjunctive Simplification


  • p ∧ q
  • ∴ p
• Disjunctive Addition


  • p
  • ∴ p v q
• Conjunctive Addition


  • p
  • q
  • ∴ p ∧ q
• Formal Derivation


  1. Assume P

  2. Q

  3. Use Deduction Theorem (DT)

  4. Discharge P, conclude P → R
• Predicate Calculus allows identifying individuals together with properties and predicates
• Predicate or Propositional Function


  P(x) is a sentence where x is a variable and D is a domain, such that for each value of x in D, P(x) is either true or false
• Propositional function examples


  • P(x): x is an odd integer, where D is the set of positive integers
  • P(x): the baseball player hit over .300 in 2003, where D is the set of all baseball players
• 1. place predicate


  A sentence P(x1, x2,...,xn) containing variables x1, x2,...,xn such that on assignment of values to the variables from appropriate domains, a statement results
• Universal Quantifier


  For all x, P(x)
• Existential Quantifier


  There exists x, P(x)
• Bound Variable


  The variable appearing in Vx P(x) or Ex P(x)
• ~Vx P(x) = Ex ~P(x)
• ~Ex P(x) = Vx ~P(x)
• Formulas in Predicate Logic

  Statements, n-place predicates, and formulas constructed using logical connectives and quantifiers
• Universal Specification (US)


  If Vx P(x) is true, then P(a) is true for any arbitrary a in the domain
• Universal Generalization (UG)


  If P(a) is true for any arbitrary a in the domain, then Vx P(x) is true
• Existential Specification (ES)


  If Ex P(x) is true, then P(a) is true for some a in the domain
• Existential Generalization (EG)


  If P(a) is true for some a in the domain, then Ex P(x) is true