January 31 2017
ch 1 the fundamentals- logic and proofs
1.1 propositional logic
point give precise meaning to math statements
applications
-design of computer circuts see sec 1.2
-writing of software
-verification of correctness
-computer programs
-etc
proposition a statement that makes a declaration -that can be true or false but there is no burden to proove truth
examples
p= “2+2=4” T
q = “the sun comes up every day”
r = “the world is flat”
america is the best country – doesnt matter if its an opinion
2+2 = dog
non examples
any question
where are we
commands
make me a taco
2+2
building new proposions from odl propositions
1- negation (!P)
if p is a proposition
¬p means ‘not p’
or it is not the case
¬p = “it is not the case that 2+2=4” F
- conjunction (&)
if p and q are propositions
p˄q means ‘p and q’
2+2=4 and the sun will come up every day
p q
P |
Q |
p˄q |
T |
T |
T |
T |
F |
F |
F |
T |
F |
F |
F |
F |
- disjunction (||)
id p and q are 2 props
p˅q means ‘p or q’
2+2=4 or the sun comes up every day
in english can mean either a or b but not both (exclusive or) and a or b or both – inclusive or
P |
Q |
p˄q |
p˅q(inclusive or) |
T |
T |
T |
T |
T |
F |
F |
T |
F |
T |
F |
T |
F |
F |
F |
F |
- exclusive disjunction or direct sum
p⊕q means ‘p or q’ but also not both
p⊕q ‘ 2+2=4 or the sun comes up every day
can be shown ˅
P |
Q |
p˄q |
p˅q(inclusive or) |
p⊕q
(exclusive or) |
T |
T |
T |
T |
|
T |
F |
F |
T |
|
F |
T |
F |
T |
|
F |
F |
F |
F |
|
- conditional statements/implications
p→q means ‘if p then q’
if p is true then q is true
if 2+2 = 4 then the sun comes up every day
p implies q
if p is true q must be true
if q is true it doesnt rely on p for the statement to be true
P |
Q |
p˄q |
p˅q(inclusive or) |
p⊕q
(exclusive or) |
p→q |
T |
T |
T |
T |
F |
T |
T |
F |
F |
T |
T |
F |
F |
T |
F |
T |
T |
T |
F |
F |
F |
F |
F |
T |
- biconditionals
p↔q
(p → q) ∧ (q → p)
p if and only if q
this means
“(if p is true then q is true) and (if p is true then q is true)”
P |
Q |
p˄q |
p˅q(inclusive or) |
p⊕q
(exclusive or) |
p→q |
p↔q |
T |
T |
T |
T |
F |
T |
T |
T |
F |
F |
T |
T |
F |
F |
F |
T |
F |
T |
T |
T |
F |
F |
F |
F |
F |
F |
T |
T |
THE ORDER OD 5 AND 6 MATTERS THE FIRST IS DEPENDANT ON THE LAST
7 Q→P converse of p→q
8 ¬q →¬p contrapositive of p→q
9 ¬p→¬q inverse of p→q
p˄q |
7 |
8 |
9 |
T |
? |
t |
? |
F |
? |
f |
? |
Recent Comments