sum ! _Desca
John Rachlin discrete structures
Northeastern
Cogito, ergo
Copyright By PowCoder代写 加微信 powcoder
É’ :÷÷÷÷¥ilE%÷:;¥-
a) Programming: if ( a > 5 o r b = false )
execute code
Mathematical proofs a b o u t hard problems
e . g prove th a t comparison – based sorting takes .
= Oln log n )
• A proof is a series of statements
that a r e ” statem ent
logically connected ” i. e o n e ,,
implies the next
• Statements : True o r False
c) Desi sing digital circuits =D2po-
” Logic circuits ”
The inputs a r e ” Boolean ” variables
thattakeon one oftwo values: 0 (false) or 1 (true)
student of Plato
Father of Western Philosophy
Founded his ow n school
The roots of education are
but the fruit is sweet
( attributed )
Propositions
denoted by letters
a.b.c , p, g, r
statements
cute will it snow ?
“”””|⇒”””””*’
I will earn Hooray! alot in cops
(Propositional ) 2.BasiclogiciAND.OR.NO#
it is raining umbrella I have my .
pnq is true if and only if both p and q a re true
io.IT/P- 1-= True 000FF F F=False
210TF F- 3 it T T
is on top!
sprinklers
p is true or q istrue OR BOTH .
” inclusive o r
F F inclusive TT←
is true ifandonlyif
is false .
a re related to sets .
✗: ✗c-AV✗c-B}(or
AnB= {✗: ✗c-A ^ ✗e-B} land)
a- = {✗ :-(✗c- A)} (not)
Bigger Truth tables for m o r e complex expressions
← note the sequence . If F=0 , -1=1 thentheseare binary#s 0. . . 7!
Equivalence .
If the truth tables are the same, thenthe two formulas are
equivalent .
Canb)✓(an- b)v(or-a)
Equivalence
a v (b n c) = (an b) ^ (a ve )
“”””^””” “””””^””
p,,T,, TFF,TT
Similarly ,
a^(bvc)= (arb)v(an
logical equivalences
know a s ” distributive laws ”
Rules A Logical
Distributive : Prove via truth table
or translate: p : cloudy g.snowing
Miami, Absorptcon.i-hevalucsf%Eamex.me?jcohitr:humit
depends only on P.
tryp-True.p-F.at#DeMorgans:
Convert to
Its not both hot and humid Ifs not hot OR not humid
is not mondayor
. tuesday =
Today is not Mon ?
Simplifying Logical
an(brc) @nb)✓ Canc)
Canb) ✓ (an – b)v (ch-
(an (bv – b)) v (on – a) Distrito.
Can-1) v (Cr- a)
Cave)n(ar- a)
(arbnc)✓ (anbn- c) -(ar- b)
((arb)n(c✓- e)) v – Cau- b) Distributive
(arb)v – lar- b) (arb) v f-an – – b)
complement
Distributive
(arb) v (-
b n ( a r –
^%,my)V(X,n✗z^×>^- g)
rlowmangfunckonsarethere.TW
o inputs , 4
A function is defined by the four
combinatorics
values fo r each combination
there a re 24
possible functions
O O O 1 NOR – A ^ – B – (Aub)
00I0 7(B→a)
0I1 no,a nA
0I0,notB-B Oll0 ✗ORA5B
0I1i NAND-AV-B-(ANB 1OOOANDAnB
0✗AMB I0INOR
I0I0 B I0I1 A→B
2 inputs ⇒ 4 output combinations ⇒ 2 ” functions
inputs ⇒ 2 ” output combinations
⇒ functions
Tautology : A Simplifies
statement that is always true
e.g p v – p = -1 Its raining or its not raining .
avbvc✓(-an-b^-c)=T
alice,bob,orco/inown a car or
contradiction :
A statement
Simplifies
e.g p n – p IF Its raining and its not.
a n b n c n ( – a u – b v – c) =
all of them own a car.
Aristotle: Law of non – contradiction
statements are true or fase , nd both.
Boole : Laws of Thought 11854)
” Boolean variable
in programming
Implication: p → q or p⇒q * ” If p then ” or ” P implies ”
p Today is Monday
. . office q. Rachlin has
Inot officeNo? in ⇒ Lie
Thursday & holding office hours – But I didnt Lie !
Rachlin Lied !
Its Monday and Rachlin
held office hours , so
Rachlin is
p → of = – p ✓ → – f = – p v8
Implication
If 2+2=5 then elephants are
“o: i. If Rachlin has office Hours, its Monday
NO!! (It might be Friday !)
p → 8 is nof logically equivalent to
(ppqp→qq→p_
FF-FT ¥ |f
contrapositive
I f its Tuesday , Rachlin has
I f Rachlin
doesn’t have ‘office hours
Then itsnt Tuesday. (True ?)
– if- g) v –
+ of → – p
worked hard on
turned in homework
: Earned a
good grade
– E → – (✗ n g) If you didnt earn a good didnt turn it
– 7- → l- X v – g) grade, you you didn’t workhard
R has OH .
of If Tuesday Then Rachlin has office hours
R. has 04 if
In v e rs e
r.*.n+nFposq=f-p-q
– Today i s No :
pvq =/ – qvp
Contrapositive
p→q= – q→ –
pv of Défn ofImp conditional Ident.
Bd”e4ionafInp1$,,af,£%→_PDefnqz
offof =p→ofn-p→- of it
, conditional
and only if
• The truth values are the same
both sides
• ✗NOR Gate !
p→q =p-q n q→ p
pqp-qq-p p←sq
OFF 1- FT 1- contra-
TF F T f positive. TTT
p→q = p→ q n – p→ – g
Proofs info/ require that w e
a) if a Then b b) if b then a
” iff” prove
→b b)- a →
contrapositive
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com