Discrete Structures Week 2 Flashcards
logical operators
produce new propositions out of old ones
- negation
- conjunction
-disconjunction
-exclusive or
-conditional
-biconditional
- equivalence
logical equivalence
p and q are equivalent id they have the same truth table
contrapositive
p -> q =(3lines) not q then not p
p if q is a different way to say…
q then p
p only if q means
p is T only if q is T so
not q -> not p = p -> q
1st Morgan Law
not (p ^ q) = not p v not q
every logical operator is equivalent to…
one that is written only in terms of ^, v, not
two operators A and B are logically equivalents if and only if…
A is true whenever B is true and A is false whenever B is false
2nd De Morgan Law
not (p v q) = not p ^ not q
- proof for this
T is # and F is #
and how to solve these problems
T is 1, F is 0
- compare is corresponding number with the operator
Contrapositive
p -> q = not q -> not p
De Morgan Laws
not (p ^ q) = not p v not q
- prove by truth table
not (p v q) = not p ^ not q
- two propositions proof
p = q if P =T whenever q = T and p =F whenever q =F
Tautology
a compound propositions that is always true
p v not p
contradiction
a compound propositions that is always false
p ^ not p
contingency
a compound proposition that is neither false or true always
p
Argument
an assertion that gives some propositions P1…Pn (premises) imply another proposition q(conclusion)
notation for arguments
P1…Pn |-> q
|-> is therefore
p1
p2
————-
three dots q
valid
an argument p1…pn |-> q is valid (q=T) whenever p1…on are true
fallacy
invalid
all premises (pn) are true but the conclusion(q) is false
theorem of arguments
an argument p1…pn three dots is valid if and only if p1 ^p2^…^pn -> q is always true
- proof of this
Modus Ponens
standard rules of inferences
p->q
p
——–
three dots q
hypothetical syllogism
standard rules of inferences
p->q
q->r
———
three dots p->r
