Transcript Introduction to Database Systems

The Logic and Language of Proofs
Proposition: Informal introduction to logic.
Definition: A proposition ( or statement) is a sentence that is
either TRUE or FALSE.
He is handsome.
WHAT TIME IS IT?.
5 + 7.
Please open the door.
Instructor: Hayk Melikya
Introduction to Abstract Mathematics
[email protected]
1
Logic
Logic is not only the foundation of mathematics, but
also is important in numerous fields including law,
medicine, and science. Although the study of logic
originated in antiquity, it was rebuilt and formalized in
the 19th and early 20th century. George Boole (Boolean
algebra) introduced mathematical methods to logic in
1847 while Georg Cantor did theoretical work on sets
and discovered that there are many different sizes of
infinite sets.
Introduction to Abstract Mathematics
2
Statements or Propositions





A proposition or statement is a declaration which is either
true or false.
Some examples:
2+2 = 5 is a statement because it is a false declaration.
Orange juice contains vitamin C is a statement that is true.
Open the door. This is not considered a statement since we
cannot assign a true or false value to this sentence. It is a
command, but not a statement or proposition.
Introduction to Abstract Mathematics
3
Negation
The negation of a statement, p , is “not p” and is
denoted by ┐ p
 Truth table:
 p
┐p
T
F
F
T


If p is true, then its negation is false. If p is false, then its negation is
true.
Introduction to Abstract Mathematics
4
Conjuction
In ordinary English, we are building new propositions from old
ones via connectors. Similar way we will construct new propositions
from old ones in mathematics too.
Definition: If P and Q are proposition then P^Q is a new proposition which
referred to as the conjunction of P and Q. The proposition P^Q is true if
and only if both P and Q are true propositions.
P
Q
P Q
T
T
T
T
F
F
F
T
F
F
F
F
Introduction to Abstract Mathematics
5
Conjunction (logical product or multiplication)

A conjunction is only true when both p and q are true. Otherwise, a
conjunction of two statements will be false:

Truth table:
p
q
T
T
F
F
T
F
T
F
Introduction to Abstract Mathematics
p

q
T
F
F
F
6
Conditional statement

To understand the logic behind the truth table for the conditional statement, consider the
following statement.

“If you get an A in the class, I will give you five bucks.”
Let p = statement “ You get an A in the class”
Let q = statement “ I will give you five bucks.”
Now, if p is true (you got an A) and I give you the five bucks, the truth value of
p
q is true. The contract was satisfied and both parties fulfilled the agreement.
Now, suppose p is true (you got the A) and q is false (you did not get the five bucks). You
fulfilled your part of the bargain, but weren’t rewarded with the five bucks.
So p
q is false since the contract was broken by the other party.
Now, suppose p is false. You did not get an A but received five bucks anyway. (q is true) No
contract was broken. There was no obligation to receive 5 bucks, so truth value of p
q
cannot be false, so it must be true.
Finally, if both p and q are false, the contract was not broken. You did not receive the A and
you did not receive the 5 bucks. So p
q is true in this case.








Introduction to Abstract Mathematics
7
Truth table for conditional

p
q
T
T
F
F
T
F
T
F
Introduction to Abstract Mathematics
p
q
T
F
T
T
8
Variations of the conditional

Converse: The converse of p

Contrapositive: The contrapositive of
┐q
Introduction to Abstract Mathematics
q is
q
p
p
q is
┐p
9
Examples

Let p = you receive 90%
Let q = you receive an A in the course
p
q?

If you receive 90%, then you will receive an A in the course.

Converse: q

If you receive an A in the course, then you receive 90%
Is the statement true? No. What about the student who receives a score
greater than 90? That student receives an A but did not achieve a score of
exactly 90%.



Introduction to Abstract Mathematics
p
10
Example 2








State the contrapositive in an English sentence:
Let p = you receive 90%
Let q = you receive an A in the course
p q?
If you receive 90%, then you will receive an A in the course
┐q
┐p
If you don’t receive an A in the course, then you didn’t receive 90%.
The contrapositive is true not only for these particular statements but for all
statements , p and q.
Introduction to Abstract Mathematics
11
Logical equivalent statements
pq
Show that

We will construct the truth tables for both sides and determine that
the truth values for each statement are identical.

The next slide shows that both statements are logically equivalent.
The red columns are identical indicating the final truth values of
each statement.
Introduction to Abstract Mathematics
is logically equivalent to
p  q

12
Introduction to Abstract Mathematics
13