Symbolic logic

• In mathematical logic, statements are declarative sentences which are either true or false.


• Suppose P is a statement, which may be true or false. The negation of P is a new statement which is denoted by ¬P. If P is true, then ¬P is false. If P is false, then ¬P is true.



• Suppose P and Q are both statements, each of which may be either true or false. The "and" operator is denoted by P/\Q, and it is defined so that it is true if P is true and Q is also true. It is false if P is false, if Q is false, or if both are false.
  Note: The words "and," "but," and "nor" are logically equivalent.



• Again suppose P and Q are both statements, each of which may be either true or false. The "or" operator is denoted by P\/Q, and it is defined so that it is true if P is true, if Q is true, or if both P and Q are true. It is false only when P is false and Q is false.
  
  Important: This is the "inclusive or," which means one or the other or possibly both. This is sometimes how we use "or" in English. e.g. "He must be crazy, or stupid!" (the target could be both crazy and stupid).
  
  Sometimes in English we use the "exclusive or," which means one or the other is true, but not both. e.g. "You will do what I say or I will bomb your country" (if you do what I say, I won't bomb your country).
  
  To avoid ambiguity, in mathematics we always use "or" in the inclusive sense.
  (The reason is because "inclusive or" is the opposite of "and," which makes it more convenient in logic than the "exclusive or.")
  
  



• Truth tables.
  
  • It is often convenient to use a truth table when working with logical operators.
  • Example: the truth table for the "not" operator.

    P	¬P
    T	F
    F	T

    How to read the truth table:
    • The first row gives the basic statement P and the operation we are performing on it, ¬P.
    • The first column gives all the possible truth values of P. Clearly P may be either true or false.
    • The second column gives the corresponding truth values of the operation ¬P. It just says that if P is true, ¬P is false, and vice versa.
  
  
  
  • Here is a truth table for the "and" operator. We start with two propositions P and Q. Each may be either true or false, so we have four possibilities and hence four rows.

    P	Q	P/\Q
    T	T	T
    T	F	F
    F	T	F
    F	F	F




• Q: Why do we use truth tables?
  A: They make it easy to verify logical operations.
  
  Example:
  "Inclusive or" is the opposite of "and."
  
  • If it is not true that "P is true and Q is true," then either P is false or Q is false or both are false.
  
  
  • Symbolically: ¬ (P /\ Q) is the same as (¬P) \/ (¬Q)
  
  
  • We can verify this with truth tables.
    • Truth table for ¬ (P /\ Q):

      P	Q	¬ (P /\ Q)
      T	T	F
      T	F	T
      F	T	T
      F	F	T

    
    
    • Truth table for (¬P) \/ (¬Q):

      P	Q	(¬P) \/ (¬Q)
      T	T	F
      T	F	T
      F	T	T
      F	F	T

    
    
    • Since the two truth tables are the same, these operations are equivalent.
      
      This gives us a simpler way of verifying logical assertions.



• Implications: if P and Q are statements, then the statement "if P, then Q" is denoted by P => Q. P is the hypothesis; Q is the conclusion.
  
  P => Q can also be read as
  • Q if P.
  • P implies Q.
  • P only if Q.
  
  Examples:
  Let P="The President fights a war" and Q="The President gets re-elected."
  • P => Q is "The President gets re-elected if he fights a war."
  • Q => P is "The President gets re-elected only if he fights a war."
  • ¬Q => ¬P is "If the President did not get re-elected, he did not fight a war."
  • ¬P => ¬Q is "If the President did not fight a war, he did not get re-elected."
  
  
  When is an implication valid?
  
  • First suppose the hypothesis P is true.
  • If Q is also true, then P => Q is true.
  • If Q is false, then P => Q is false.
  • What if the hypothesis P is false?
    
    Think of it like making a promise.
    e.g. "If you ever need money, I'll give it to you."
    
    This is still a genuine offer even if you never need money, whether I give you money or not. It's only false if you do need money and I don't give it to you.
    
    So if P is false, then P => Q is still true, regardless of Q.
  • Truth table for P => Q:
    

    P	Q	P => Q
    T	T	T
    T	F	F
    F	T	T
    F	F	T

  • Notice that this truth table is the same as the one for ¬(P /\ ¬Q). In words, "If P, then Q" is equivalent to "It is impossible that P happens without Q also happening."



• The statement "If P is true, then Q is true" is called a theorem in mathematics.
  • The statement "If Q is true, then P is true" is called the converse of the theorem.
    The converse of a valid theorem is not necessarily valid.
  
  
  • The statement "If Q is false, then P is false" is called the contrapositive of the theorem.
    
    A theorem is always equivalent to its contrapositive.
    (You will prove this using a truth table in your homework.)
    
    Examples: "If you do all the homework, you'll get at least 25 points on your final grade"
    (theorem) is equivalent to "If you don't get at least 25 points on your final grade, you didn't do all the homework."
    (contrapositive) but not to "If you get at least 25 points on your final grade, you must have done all the homework."
    (converse) nor to "If you don't do all the homework, you won't get at least 25 points on your final grade."
    (something else)
  
  
  • An equivalence between statements P and Q is written as P <=> Q and is read as "P is equivalent to Q" or "P if and only if Q."
    • Often "if and only if" is abbreviated to "iff."
    • Logically it means that P and Q are both true or both false.
    • It can also be stated as (P=>Q) /\ (Q=>P) (The theorem and its converse are both valid.)
    
    
    • Truth table for P<=>Q:

      P	Q	P <=> Q
      T	T	T
      T	F	F
      F	T	F
      F	F	T