Mathematics Archives - Page 34 of 60 - Shawn Zhong

1.2 Applications of Propositional Logic

Translating English Sentences • Steps to convert an English sentence to a statement in propositional logic ○ Identify atomic propositions and represent using propositional variables. ○ Determine appropriate logical connectives • Example: “If I go to Harry’s or to the country, I will not go shopping.” ○ p: "I go to Harry’s." ○ q: "I go to the country." ○ r: "I will go shopping." ○ p∨q→¬r • Example: “You can get an extra piece of pie if you have completed your homework or if you are extremely hungry” ○ p: You have completed your homework ○ q: You are extremely hungry ○ r: You can get an extra piece of pie ○ p∨q→r System Specifications • System and Software engineers take requirements in English and express them in a precise specification language based on logic. • Example: “The automated reply cannot be sent when the file system is full” ○ p: “The automated reply can be sent” ○ q: “The file system is full.” ○ q→¬ p Logic Puzzles • An island has two kinds of inhabitants, knights, who always tell the truth, and knaves, who always lie. • You go to the island and meet A and B. ○ A says “B is a knight.” ○ B says “The two of us are of opposite types.” • What are the types of A and B? ○ Let p and q be the statements that A is a knight and B is a knight, respectively. ○ So, then Øp represents the proposition that A is a knave and Øq that B is a knave. ○ If A is a knight, then p is true. Since knights tell the truth, q must also be true. Then (p ∧Øq)∨(Øp∧q) would have to be true, but it is not. So, A is not a knight and therefore Øp must be true. ○ If A is a knave, then B must not be a knight since knaves always lie. So, then both Øp and Øq hold since both are knaves. Logic Circuits • Electronic circuits; each input/output signal can be viewed as a 0 or 1. ○ 0 represents False ○ 1 represents True • Complicated circuits are constructed from three basic circuits called gates. ○ The inverter (NOT gate) takes an input bit and produces the negation of that bit. ○ The OR gate takes two input bits and produces the value equivalent to the disjunction of the two bits. ○ The AND gate takes two input bits and produces the value equivalent to the conjunction of the two bits. • More complicated digital circuits can be constructed by combining these basic circuits to produce the desired output given the input signals by building a circuit for each piece of the output expression and then combining them.

$Proposition 2: The Division Algorithm • Statement ○ Let a,b∈Z, where b 0 ○ Then ∃!q,r∈Z s.t. a=qb+r, and 0≤r b • Proof (Existence) ○ Let S≔{a−bq│q∈Za−bq≥0}⊆Z(≥0) ○ S is not empty § Let q∈Z s.t. q≤a/b § Then bq≤a § ⇒0≤a−bq § i.e. a−bq∈S ○ Thus S contains a unique minumum elemtent: call it r ○ Choose q∈Z s.t. § a−bq=r § ⇒a=bq+r ○ We still need to show 0≤r b § We know 0≤r, since r∈S, so we just need to show r b § If r≥b, then a−b(q+1)=a−bq−b=r−b≥0 § But a−b(q+1)∈S, and it is less than r § This is impossible, since r is minimum element of S § Thus, r b ○ Therefore we ve proven the existence of q and r • Proof (Uniqueness) ○ Suppose ∃q,q^′,r,r^′∈Z s.t. § a=bq+r, where 0≤r b § a=bq^′+r^′, where 0≤r^′ b ○ We must show q=q′ and r=r^′ ○ Suppose r≠r^′ § Without loss of generality, assume r^′ r § Then 0 r^′−r=(a−bq^′ )−(a−bq)=b(q−q^′ ) § Thus, ├ b┤|├ (r^′−r)┤, but 0 r^′−r≤r^′ b. § This is impossible, thus r=r^′ ○ We have bq+r=bq^′+r⇒q=q^′ ○ Therefore we ve proven the uniqueness of q and r • Note we can prove the following stronger statement ○ If a,b∈Z, and b≠0, then ∃!q,r∈Z ○ s.t. a=bq+r, and 0≤r |b| • Proof (Existence) ○ Assume b 0 ○ Choose q,r∈Z s.t. a=(−b)q+r, and 0≤r −b ○ Then a=b(−q)+r, and 0≤r |b| ○ This proves existence • Proof (Uniqueness) ○ Assume b 0 ○ Suppose ∃q,q^′,r,r^′∈Z s.t. § a=bq+r, where 0≤r b § a=bq^′+r^′, where 0≤r^′ b ○ Then § a=(−b)(−q)+r, where 0≤r |b|=−b § a=(−b)(−q′)+r^′, where 0≤r^′ |b|=−b ○ Since −b 0, our previous result implies −q=−q^′ ○ ⇒q=q′ and r=r^′ Greatest Common Divisor • If a,b∈Z, where either a≠0 or b≠0 • A greatest common divisor of a and b is a positive integer d s.t. ○ d|a and d|b ○ If e∈Z s.t. e|a and e|b then e|d • We write the g.c.d. of a and b, if it exists, as (a,b) • As a convention (0,0)≔0 Proposition 3: Uniqueness of Greatest Common Divisor • Statement ○ Let a,b∈Z, where either a≠0 or b≠0 ○ Suppose ∃d,d^′∈Z( 0) s.t. (1) d and d′ both divide a and b (2) If e∈Z s.t. e|a and e|b, then e|d and e|d^′ ○ Then d=d^′ • Proof ○ Combining properties (1) and (2), we have d|d′ and d^′ |d ○ Choose q,q^′∈Z s.t. dq=d′ and d^′ q^′=d ○ By substitution, we get dqq^′=d ○ Then qq^′=1⇒q=q^′=±1 ○ If q=q^′=−1, then d=−d^′ 0. ○ This is impossible since d and d′ are both positive ○ Therefore q=q^′=1 and d=d^′ Proposition 4 • Statement ○ Suppose a,b∈Z, where b≠0 ○ Choose q,r∈Z s.t. a=qb+r, and 0≤r |b| ○ If (b,r) exists, then (a,b) exists and (a,b)=(b,r) • Proof ○ Set d≔(b,r) ○ d|a and d|b § Choose q_1,q_2∈Z s.t. dq_1=b and dq_2=r § Then a=qb+r=qq_1 d+q_2 d=d(qq_1+q_2 ), so d|a § And we already know d|b ○ If e∈Z s.t. e|a and e|b, then e|d § Let e∈Z s.t. e|a and e|b § Choose q_3,q_4∈Z s.t. eq_3=a and eq_4=b § a=qb+r § ⇒a−qb=r § ⇒eq_3−qeq_4=r § ⇒e(q_3−qq_4 )=r § Thus e|r § Since e|b and d=(b,r) § We can conclude that e|d ○ By Proposition 3, (a,b)=(b,r) Proposition 5 • Statement ○ (a,0)=|a|,∀a∈Z • Proof ○ If a=0 § This is true by our convention ○ If a≠0 § Certainly ├ |a|┤|├ a┤, and ├ |a|┤|├ 0┤ § If e∈Z s.t. e|a and ├ e┤|├ 0┤, then ├ e┤|├ |a|┤ § Therefore (a,0)=|a|$

Math 541 – 1/26

$Induction • Prove that ∑_(i=1)^n▒i=n(n+1)/2, ∀n≥1 • Base case, n=1 ○ ∑_(i=1)^i▒i=1=(1×2)/2 • Induction step ○ For n 1 ○ Assume ∀k s.t. 1≤kn, ∑_(i=1)^k▒i=k(k+1)/2 ○ Then∑_(i=1)^n▒i=(∑_(i=1)^(n−1)▒i)+n=(n−1)(n)/2+n=n(n+1)/2 Proposition 1: Well-ordering of Z • Statement ○ Every nonempty set S of Z(≥0) has a unique minimum element ○ That is, ∃!m∈S s.t. m≤s, ∀s∈S • Proof (Existence) ○ Assume S is finite § We will argue by induction on |S| § Base case: |S|=1 □ This is clear § Assume |S| 1 □ Choose x∈S, then |S∖{x}|=|S|−1 □ By induction S∖\{x} has a minimum value: call it m □ Case 1: xm, then x is a minimum value of S □ Case 2: mx, then m is a minimum value of S ○ Now we prove the general case § Choose x∈S § Let S^′≔{s∈S│s≤x} § Then |S^′ |≤x+1∞ § Choose a minimum element of S: call it m § Let s∈S □ If s∈S^′, then m≤s □ If s∉S′, then m≤xs § In either case, m≤s, so m is a minimum element of S ○ This proves existence • Proof (Uniqueness) ○ Suppose m and m′ are both minimum elements of S ○ m≤m′, and m^′≤m ○ Thus, m=m^′ ○ This proves uniqueness Proposition 2: The Division Algorithm • Statement ○ Let a,b∈Z, where b 0 ○ Then ∃!q,r∈Z s.t. a=qb+r, and 0≤rb • Proof (Existence) ○ Let S≔{a−bq│q∈Za−bq≥0}⊆Z(≥0) ○ S is not empty § Let q∈Z s.t. q≤a/b § Then bq≤a § ⇒0≤a−bq § i.e. a−bq∈S ○ Thus S contains a unique minumum elemtent: call it r ○ Choose q∈Z s.t. § a−bq=r § ⇒a=bq+r ○ We still need to show 0≤rb § We know 0≤r, since r∈S, so we just need to show rb § If r≥b, then a−b(q+1)=a−bq−b=r−b≥0 § But a−b(q+1)∈S, and it is less than r § This is impossible, since r is minimum element of S § Thus, rb ○ Therefore we ve proven the existence of q and r$

Shawn Zhong

Shawn Zhong

Mathematics

1.2 Applications of Propositional Logic

1.1 Propositional Logic

0. Introductory Lecture

Math 541 – 1/29

Math 541 – 1/26

Search

WeChat Account