Transcript Lecture Slides

CS128 – Discrete Mathematics for
Computer Science
CS128 course website:
http://web.mst.edu/~tauritzd/courses/cs128/f
s2009
Dr. Daniel Tauritz (Dr. T)
Department of Computer Science
[email protected]
http://web.mst.edu/~tauritzd/
Propositional Logic
Definition
A statement (or proposition) is a
sentence that is true or false but not
both.
•
•
•
•
•
•
•
•
Truth values
Logical connectives
Negation, conjunction, disjunction
or vs. xor
Order of operations
Compound statements
Statements vs. statement forms
Truth Tables
Definition
Two statement forms are called logically
equivalent if, and only if, they have
identical truth values for each possible
substitution of statements for their
statement variables.
Definition
Two statements are called logically
equivalent if, and only if, they have
logically equivalent forms when identical
component statement variables are
used to replace identical component
statements.
De Morgan’s Laws
The negation of an and statement is
logically equivalent to the or statement
in which each component is negated.
The negation of an or statement is
logically equivalent to the and statement
in which each component is negated.
Definition
A tautology is a statement form that is
always true regardless of the truth
values of the individual statements
substituted for its statement variables. A
statement whose form is a tautology is a
tautological statement.
Definition
A contradiction is a statement form that is
always false regardless of the truth
values of the individual statements
substituted for its statement variables. A
statement whose form is a contradiction
is a contradictory statement.
Definition
If p and q are statement variables, the
conditional of q by p is “If p then q” or “p
implies q”. It is false when p is true and
q is false; otherwise it’s true. We call p
the hypothesis (or antecedent) of the
conditional and q the conclusion (or
consequent).
Definition
The contrapositive of a conditional
statement of the form “If p then q” is
“If ~q then ~p”
Symbolically: The contrapositive of p→q
is ~q →~p
Definition
An argument is a sequence of statements
and an argument form is a sequence of
statement forms. All argument
statements, except for the final one, are
called premises (or assumptions or
hypotheses); the final statement is
called the conclusion.
Definition
To say that an argument form is valid
means that regardless of the substituted
statements, if the resulting premises are
true, then the conclusion is also true.
To say that an argument is valid means
that its form is valid.
Testing the validity of an argument form
1.Identify premises and conclusion
2.Construct truth table
3.If there is any row in which all the
premises are true and the conclusion
false, then the form is invalid; otherwise
it’s valid
Tip: you only need to complete critical rows
(rows whose premises are all true)
Definition
A syllogism is an argument form
consisting of two premises and a
conclusion.
Modus Ponens
If p then q
p
tf q
Modus Tollens
If p then q
~q
tf ~p
Additional rules of inference
Generalization
p
tf p v q
q
tf p v q
Specialization
p^q
tf p
p^q
tf q
Predicate Logic
Definition
A predicate is a sentence that contains a
finite number of variables and becomes
a statement when specific values are
substituted for the variables. The
domain of a predicate variable is the set
of all values that may be substituted.
Example
Let P(x) be the predicate “x3 > x” with
domain the set R of all real numbers.
P(1): 1>1 False
P(-1): -1>-1 False
P(2): 8>2 True