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.