sum ! _Desca
John Rachlin discrete structures
Northeastern
Cogito, ergo
Copyright By PowCoder代写 加微信 powcoder
a logical formula from
truth table ,
F F T y¥#(CN FTF
include these cases TFTT )
f-a n – bnc)v1- anbnc)✓(an – bn- c)✓Can- bnc)
✓ (an b n – c) v Canbn e )
” Disguctiue
form ‘ (DNF):
(X. ^ ✗ z n . . . . )DM (g.n ya ^ . . .. )NBA ( – – – . )
Alternatively ,
The formula iwhatever
w e focus o n the false entries .
when – (- ar – b r – c) A – (- an b n –
De Morgan’s
: -(png)=-pv-q
so : n (na n – b n – c) = a ✓ b v c
v ^(narbr-c)=av-b C
(avbvc)rlav – b vc) “Conjunctive Normal Form ” (
(✗ ✓ Xzv. – – ,
) AAA ( ) MEH
(avbvc)A lav- b vc)
(ave)✓(bn- b)
(a v c Fave
Wa t c h F o r
These simplifying opportunities:
DNF • • . (pnqnr)✓(pngr- r)•*
^ (r ✓ – r ) distributive
complement
CNF•• • (pvqvr)^(pvqv-r)
Distributive
complement
O=F , 1=-1
LogicGates_
Arg=D- A^BAND
=☐-AVB OR A I)Io- NOR ,
A – Do- -A NOT%
÷i@ *§÷: .
±÷÷t÷EY÷Y÷:÷
N O T A N D N A N D O R N O R ✗O R ✗ N O R
-Do- =D- a.Do- =D- – =D- –
simplifyingacircu.la#-2D-DoBc-Ao-D-5
– ✗AnB)^ (Av- c))
((A^B^A)v(AnBn- c)
) Distributive
– ((AnB)✓ (A^B^- a)) AnA
Absorption
a n d humid
Designingacircuit-Anexan.rs/e-
Suppose 3 inputs Az A , Ao
which w e interpret a s a n unsigned binary #
111 or0to7,
lll ÷ Prime
Circuit outputs I if the input
(3-bits max)
Prime#: 2,3,5,7,11,13,17,19, s-
Note : • A prime # is a whole # > 1 whose
factors are 1 and itself.
• By convention , 1 is riot prime .
Numbers with more than two
factors a re
composite ”
• Largest known prim e has
23 million digits
• R S A Encryption
1 Oll l l00
f-azna n – ao)v1- azra nao)v(az^- a. ^ao)v(azra,n9o)
f-arena , )r 1-aovao)] ✓ [(aznao)^l- a. va ,)]
((-92^9)^-1) v ((aznao)1T )
f-az na , ) v (are ^ ao)
ao – D2 out ,
a .IT#-D- a
propositional
Aristotleofferedlhefollowing.by/logisim-
Socrates is
statement :
( ✗ is mortal ) But “X is a man” has no inherent
is a man)→
It’s true for som e Xs
and false for other.
firs-orderl.co#
claims about
X = representing
particular
predicates
establish claims about those
Human (Socrates) is tru e
Human (Socrates) → Mortal (Socrates)
universal Quantifier
th Human(x) → Mortal(x)
true for all objects , X
Prime(X)→ Odd(X)
False: ✗= 2 (one counter
example is !) enough
The existential Quantifier
” There exists In ✗
F. ✗ NEU – Professor (X ) ^ Teachers 1800 (X )
be true for
orieormore
Negatingf×_
– thPix)= Fx
[the Prime(x)→ oddCx)]
3-✗ a (Prime (x) → Odd (X) )
1-✗- l-PrimeCx)~ Odd(X))
3-✗ Prime(X) n – odd (X ) (True : 7=2
Negatingfx-J-xp.CH Pix = -✓x – )
– 3-✗ Unicorn (X)
Unicorn (x )
Quat-fyingour-ange.ofobjectsv-xc.IN
Fyc-IR: y¢☒ (some Real#saren’t rational )
Multi-argumentpredicatesv-x-vy-vzfmothercx.gl ) n Motherly, -2
Grandma (x ,z ) )
3-✗ try ✗ y = 0 (True , 21=0) read : There is an X which for
possible y values , ✗ – y proof by example .
7-✗thy ✗+y False .
We set the value of
and ask , is statement true ? No,
we can always find a
try3-✗ Xty= 0
Tru e . We imagine frying a ll possible values of y and , for each y
seeing if we can find an ✗
construction .
logicandproof.la
quantifiers
set time w e introduced
/for every X
there exists a n / there
We gave some examples with multiple
quantifiers a n d w e noted T.net
o rd e r the matter
of , quantifiers
✗ c- locks
lock has ita” opens .
Fyekeys : y
There is a key That opens
all locks ‘ ‘
2 n d is a very different statement!
Similarly : their ,
” Every Fyc- IR, theIR
” There is y3=✗
real#✗has a (TRUE )
a particular
fo r every
real # X . (FALSE)
IntroductionfoProofs_
mathematics a s
(truly infinite ) network of interconnected
ideas. A proof is like finding a path from o n e idea to the next .
5 -→ %”ifpthen ” “ifandonlyif”
often the path is not
obvious and w e
m ust find intermediate steps along the way
‘→ 4 → 2 → 2
s e a of built from
statements
a r e like islands of
truth amid bridges
contradiction .
other theorems
contradiction
definitions
, and A dragon
gp.g#Y+ucak
Statements
d. 1764 Moscow
A #statement is a sentence or mathematical
ex That is definitely true or false
U n k n o w n ‘s
c- 72 2+2=5 Goldbach’s
*£ 3 is even Prime113) then : even(x)
conjecture
N•+astatemÉwhich Prime(X) : The number ✗ is prime .
✗ > 5 : ✗ is greater than 5 . × ?
Example: V-a.b.snc- N, n>2 : a” +b” f-C”
” Fermat’s Last Theorem ”
: 1607- 1665
yygny.npyyyanay.am
A n d re w W ile s
1993 : ” Modular Forms , Elliptic curves, and Galois Representation,
÷÷÷÷::÷:÷:::
greater Than 2 is the sum of two prime numbers .
(nes ) → ftp.qc-P, n =p-18) WÉut
widely believed ftp.qc-P-n-P-qtobetrue#
T.hescarecrowbnewBro.int
he s u m of the square ro o ts of
any two sides of an isosceles triangle
is equal to the square root of
rq+ Ta = Fi (No)
V9+V4= Tg (No)
mathematical statement w o u l d
https://www.youtube.com/watch?v=IXpb-9fhoBM
3+97 41 -159
2 3 5 7 11 13 17 19
Consider ”
13 42008 4
17 4 3004 19 3
proofsw.thquantifiers-i-vx.tk/c-
F I E L specific
p.io?;i;ga,,a
X doesnt move
12–4 ⇒ ✗2=16 . : ✗2 iseven.
corre4Apmoad_ : suppose X is a n (arbitrarily chosen ) . a. n integer .
2k for some
KEZI (Defn of even)
:X ‘ is even (Defordeven)
Assume: show:
th Even Cx) → Even (X2) } Even Cx)
(Direct Proof)
Quantifiers : II-suffiT-H.ve
how to create it
Prove: F✗c-Even : ✗c-
Even Prime are , sets
EvenCx) n Prime(X)← Even
predicates ,
2 is divisible by only 1
i.2isanevenPrime •
arbitrarily
É Émostis
The worlds simplest proof ?
two arbitrary even
So ✗ + y = 2n -12m = 2 (ntm ) = 2k where K= n-1m
: ✗tyis even. Do
a) Prove sum of two odd integers is
Prove sum of even and odd is
hogicandproof-Direc-P.ro#
Proposition:p →
Thereforeq.
again at the truth table for p→g :
r¥¥F|P¥É} Implication i. automatically tru e if p is false
T f F } Implication is true if T T q is also true and
false if q is false
With direct proof w e apply modus
repeatedly :
what , would w e derive if p→q is false?
^ -(p→g)=pn-C-pug)
so deriving – of i.e , p n – q from assuming p
the implication i.e , – p → g) must
r-xample-V-xc.IOd d c x ) c → 0 d d ( ✗ 2 – 1 6 × – 1 8 )
✗ is odd iff ✗ 2-16×-18 is odd
we have to prove both : odd 4) → Odd (✗2+6×+8 ) Odd (X2-16×-18 ) → oddcx)
2A -11 (Defn of odd )
1)2 -1612A-11 ) -18
4 a ‘ +4 a -11 + 12 a -16 -18
= 4A? + 16a + 15 = 2(292+891-7)-1
where m=2a -18A-17
Therefore ✗2-16×+8 is odd (Defa of odd ) •
Contrapositive
How to prove: If✗2-16×-18 is oddthen✗isodd.
We could do another direct proof
but a contrapositive proof is simpler.
#P→Q Proposition :
w Outline :
Therefore – P •
Contrapositive of if ✗ 2+6×-18 is odd then ✗ odd .
If ✗ is not odd then ✗2+6×+8 is not odd .
if is II is
✗ e v e n , s o ✗ 2+6×-18
✗ = 2 a by definition
(2aYt6(2a)
4a2-112A -18
(292-1691-4)
= 2b where
b=2a46a -14
✗2-16×-18 is even
contrapositive example doesnt divide n ‘ -1 n
( with ) cases
n,n¥;uses?_
(works for neo too) 3 8
what is the contrapositive ?
If n is odd , 8 does divide n’
n=2a -11 Defn of
nh- I = (za-11)2-1 =
aora-11 iseven
1)a iseven: 4. 2m(2m-11)
= 8 m (2m-11
= 8k K= m(2m-11
ii)att is even : 4a(at 1) =4a(2m)
=8K(K=a.m)
proofbycontradictio.no
attire : Proposition.
proof : suppose
Thenefonec
P= -P→ (cn-
or (P→ (Cn- c))→ P=
it show you can
that – Pleads to a contradiction
This is a claim about a ll integers
c-Z, ifa’ iseven, a iseven
what is the
negation ?
Suppose: – the-2 (a”is even→ a is even)
– (a’ is even→a is even)
pefn’ ( – (- (a’ is even)v la iseven)p 21 77aiseven)nnlaiseven)
¥μafiFrFaeaeZ ( ‘
Thena = (2C1- = 4C +4C+I = 212C-12C)-11
Therefore a2 is odd
(K=2c2 -12C)
So a” isbothevenandodd (contradiction )
Prove : Tz irrational .
I 300’s BC (Euclid)
A real number ✗ is rational if
✗=&forsome pig
otherwise it is
irrational .
cancel out.
We further assume
¥ = 19-2–9-2
irrational
Proof ( By contradiction)
V2=g-⇒ 2=Pq÷or
So p’ is even , and so earlier proof. ) i.e , p=2k
is p. 82=2K’ ⇒qisalsoeven!
2g’ contradiction
both p and)q have a common factor(2)
: is irrational v2
aisratconalafdb.is/ratronaltheua.bisirational.Q
f- P V Q )
sappo-sei-N-l.ie
-(P→Q)or Pn-Q
Then there exists a , b
a is rational b is irrational and
Let a = myn mm c- 21
ab= My x.ge21
Thenab= 2¥=¥or b=¥1m
rational and irrational
( contradiction)
– (p → Q ) is
Therefore:P → Q
impossible
The-amaninfitenumber-fpr.ms
Note : Fundamental Theorem of Arithmetic :
integer greater than 1 is -either prime or can be made from
Unique product of prime factors .
1 0 4 ( composite
20= 2× 2✗5 2 52(composite)
13^4(compo
proof. Coy
) of contradiction
Then -there is last
✗ = (2) (3) (5) (7)
prime , call it p .
product of all primes
So each prime divides ✗
✗+ I = (2)(3)(5)- – – – (p) +1
✗+ I divisible by any prime ?
No ! For example , the next number that 2 divides into is ✗ -12 the next number that 3 divides is ✗-13
a re no prime factors
So X-11 is prime But ✗+1 >p .
the last Prime
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com