CS 201 - 11/25/14

ChiQat Lab

 - Class on Date:  12/02/2014  (Tuesday next week)
 - Lab Location-  SCE 408
 - Time Start:  11:00 AM
 - Time End:  12:15 PM


Chapter 14 in A&U, Predicate Logic

  Quantifiers:

     Existential Quantifier
       There exists X such that p(X) exists

     Universal Quantifier
       For all X, p(X) exists


      (ThereExists S)gradeA(S)

      (ForAll S)needsMoney(S)

Note the negation of these Quantifers

      ~( (ForAll S)needsMoney(S) )

      becomes: (ThereExits S)~needsMoney(S)


      ~( (ThereExists S)gradeA(S) )
  
      becomes: (ForAll S)~gradeA(S)

------------------------------

A conditional statement is an implication

      if p then q

      p -> q


The contrapositive of an conditional statement

     if ~q then ~p

     ~q -> ~p
  the contrapositive (of a true condition) 
       is always true

There are two common types of errors when dealing with
  these condition statements:

       converse error
       inverse error

    for the statement:  if p then q   (p -> q)

        the converse is:   if q then p  (q -> p)
           the converse cannot be counted as always
           being true.

        the inverse is:    if ~p then ~q   (~p -> ~q)
           the inverse cannot be counted as always
           being true

Example:
     If today is Thanksgiving, then tomorrow is Friday

    Converse:
     If Tomorrow is Friday, today is Thanksgiving.

    Inverse:
     If Today is not Thanksgiving,
         then tomorrow is not Friday

=======================================
Rule of Universal Modus Ponens

   Given:    (ForAll X) p(X)->q(X)    
                 (when p is True for some X then
                  q will also be true for that same X)

             p(A)    (p is true for this particular A)

             :. q(A) (q is also true for this
                          particular A)

===========================================
Rule of Universal Modus Tollens:

   Given:    (ForAllX) p(X)->q(X)    (p implies q)

             ~q(A)      (q is not true for this
                           particular A)

             :. ~p(A)   (p is also not true for this
                           particular A)

===========================================



Given the following information about a computer 
program, find the mistake in the program.

a. There is an undeclared variable or there is a syntax 
    error in the first five lines.
b. If there is a syntax error in the first five lines, 
   then there is a missing semicolon or a variable name 
    is misspelled.
c. There is not a missing semicolon.
d. There is not a misspelled variable name.

First: write out the statement symbolically

     z: There is an undeclared variable
     y: there is a syntax error in the first five lines
     x: there is a missing semicolon
     w: a variable name is misspelled

a.   z V y
b.   y -> ( x V w )
c.   ~x
d.   ~w
1.   ~x ^ ~W        ( by Rule of Conjuction on c and d )
2.   ~ ( x V W )    ( by DeMorgan's Law on 1 )
3.   ~y             ( by Modus Tollens on 2 and b )
4.   z              ( by Rule of Elimination on 4 and a )






You then encounter natives E and F.
   E says: F is a knave.
   F says: E is a knave.
How many knaves are there?

   z:  F is a knave  (F is not a knight)
   y:  E is a knave  (E is not a knight)
   x:  There are 2 knaves
   w:  There is 1 knave (and 1 knight)
   v:  There are 0 knave (and 2 knights)

0.   x V w V v    (There is either 0, 1 or 2 knaves)
1.   z -> ~(F says is true)   (Knaves always lie)
2.  ~z -> (F says is true     (Knights never lie)
3.   y -> ~(E says is true)   (Knaves always lie)
4.  ~y -> (E says is true     (Knights never lie)

     E says z
     F says y
s5. Suppose x is true (2 knaves: E is a knave  and F is a knave.)
s6.    y  (supposition)
s7.    z  (supposition)
s8.   ~z  (by Modus Ponens on 3 and s6)
  This gives us a contradiction, so the Supposition 5 is false
9.   ~x     (by Contradiction on 5, s7 and s8)
10.  w V v  (by elimination on 9 and 0 )

s11.  Suppose v is true (0 knaves: E is not a knight and F is not a knight)
s12.   ~y (supposition)
s13.   ~z (supposition)
s14.   z  (by Modus Pones on 4 and s12)
   Another contraditions so s11 is false
15.    ~v
16     w  (by elimination on 15 and 10)

=> This is one knave


All healthy people eat an apple a day.
Herbert is not a healthy person.
∴ Herbert does not eat an apple a day.

If a product of two numbers is 0, then at least one of the
numbers is 0.
For a particular number x, neither (2x + 1) nor (x − 7)
equals 0.
∴ The product (2x + 1)(x − 7) is not 0.

For all students x, if x studies discrete mathematics, then
x is good at logic.
Tarik studies discrete mathematics.
∴ Tarik is good at logic.

Any sum of two rational numbers is rational.
The sum r + s is rational.
∴ The numbers r and s are both rational.