Discrete Structures Quiz 1 Definitions Flashcards
proposition
a statement that is true or false
look at examples and proofs and homeworks
:0
truth value
of a proposition is T or F
Logical variables
denoting propositions with letters
negation
not
little corner p
Principle of noncontradiction (PNC)
a proposition and its negation can be true at the same time
conjunction
and
p ^ q
disconjunction
or
p v q
truth table
a logical variable is fully determined by its truth table
truth values of the operator if we are given the truth value of p and q
conditional
p -> q
if p then q
vacuously true
in conditionals, the assumption is F so whole propositions is vacuously true
biconidtional
p <-> q
or
p->q ^ q->p
exclusive or
only one can be true
p (circle with + inside) q
equivalence
2 logical operators are equivalent if they have the same truth tables
<=> or = with three lines
building p and q in the truth tables
half t of the previous one
contrapositive
p -> q
=(with 3 lines)
not q -> not p
1st de morgan law
not (p ^ q)
= with three lines
not p v not q
2nd de morgan law
not (p v q)
= with 3 lines
not p ^ not q
binary expressions
compare the corresponding one
tautology
compound propositions that is always true
contradiction
compound proposition that is always false
contingency
compound proposition that is neither true or false
argument
an assertion that gives some propositions p1…pn imply another proposition q
premises
p1..pn, propositions that imply a conclusion
conclusion
q
being implied by the premises
notation for arguments
p1…pn |-> q
OR
p1
…
pn
—-
three dots q
valid
an argument is valid whenever all premises are true
fallacy
premises are true but conclusion is false
theorem (of arguments)
an argument p1…pn three dots q is valid if and only if p1^…^pn ->q is always T
modus ponens
p ->q
p
—
three dots q
hypothetical syllogism
p->q
q->r
—
three dots p-> r
modus tollens
p->q
not q
—
therefore not p
propositional functions
predicates
have a domain and P(x)
where P(x) is the output as a propositions
universal quantifier
V-
for all
existential quantifier
E backwards
there is OR there exists
uniqueness quantifiers
E!
e is backwards
there is a unique
1st de morgan law for quantifiers
not (V-x, P(x))
= with three lines
Ex, P(x)
e is backwards
2nd de morgan law for quantifiers
not (Ex, P(x))
e is backwards
= with three lines
V- x, not P(x)
