[go: up one dir, main page]
Scribd
Upload
117 views1 page

Logical Propositions and Proofs

This document provides solutions to 10 problems involving concepts in number theory and logic. The key steps are outlined for proving that: 1) If a divides b, a divides c, and b divides m, then a divides 91m - 433dc for some integer d. This is shown by writing b and c in terms of a, and m in terms of b, and then factoring the expression. 2) If n divides m and a is congruent to b modulo m, then a is congruent to b modulo n. This is proven by substituting the definition of modulo and dividing throughout by the common factor n. 3) Various logical statements and number equations are identified as true or false, with explanations

Uploaded by

marshadjafer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
117 views1 page

Logical Propositions and Proofs

This document provides solutions to 10 problems involving concepts in number theory and logic. The key steps are outlined for proving that: 1) If a divides b, a divides c, and b divides m, then a divides 91m - 433dc for some integer d. This is shown by writing b and c in terms of a, and m in terms of b, and then factoring the expression. 2) If n divides m and a is congruent to b modulo m, then a is congruent to b modulo n. This is proven by substituting the definition of modulo and dividing throughout by the common factor n. 3) Various logical statements and number equations are identified as true or false, with explanations

Uploaded by

marshadjafer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

SOLUTION

Concept 1 : Tell true or false : [ 2.5 ]


(i) (p ∨ ￢p ) ∧ q ≡ q TRUE As ( p ∨ ￢p ) ∧ q ≡ T ∧ q ≡ q
( Negation law ) ( Identity law )
(ii) If P( x ) = ' x+1 = 4 ' , x∈N then P(2) is a proposition. TRUE When we give variable a value
from the domain then the predicate becomes a proposition.
(iii)The quotient of -11 divided by 3 is -3. FALSE As -11 = 3(-4) + 1 so quotient is -4 not -3.
(iv)￢Ɐ x ( x + 2 > 7 ) ≡ ∃ x ( x+2 ≤7) TRUE Using De Morgan's law for quantifiers
￢Ɐ x ( x + 2 > 7 ) ≡ ∃ x ￢ ( x+2 >7) ≡ ∃ x ( x+2 ≤7)
(v) If p is false and ￢q is false, then ￢p ↔ q is true. TRUE
As p is false then ￢p is True and￢q is false then q is True so ￢p ↔ q becomes T ↔ T which is T.
(vi) ( 5 +7 12 ) *11 25 = -2 TRUE As ( 5 +7 12 ) *11 25 = [ ( 5 + 12 ) mod 7 ] * 25 mod 11
= [17 mod 7] * 25 mod 11 = 3*25 mod 11 = 75 mod 11 = 9 = -2
I realized that I did not tell you about negative form so I did not deduct any mark for this part.
(vii) A proof by contradiction of p → q starts with ￢q. TRUE As we start proof by contradiction by
supposing that q is false i.e￢q is true.
2 3 2 3
(viii) 4 ≡−2 ( mod 3 ) TRUE As 4 ≡−2 ( mod 3 ) => 16≡−8 ( mod 3 ) which is true as
3 | ( 16-(-8)) => 3 | ( 16+8) => 3 | 24
(ix) gcd ( 3 + 1 , 4 ) = ( ( 2 +1 ) mod 3 ) TRUE As gcd ( 3 + 1 , 4 ) = gcd (9+1,4)=gcd(10,4) =2 ,the largest
2 2 2

number which divides both 10 and 4 is 2 and ( 22 +1 ) mod 3 = 5 mod 3 = 2


(x) 1= 9 x + 7 y , where x , y ∈Z TRUE as gcd ( 9 , 7 ) = 1 so this is Bezout's identity which
says that gcd of two numbers can be written as a linear combination of the numbers.

Q # 7 : Let a, b, c ,m be integers, where a , b ≠ 0. [ 1.5 ]


Show if a | b , a | c and b | m, then a | (91m –433dc) for some integer d.
Given = a | b , a | c and b | m
To prove = a | ( 91 m – 433 dc )
We use direct proof :
As given a | b => b = ae --------> ( 1 ) for some integer e
a | c => c = af ---------> ( 2 ) for some integer f
and b | m => m = bg for some integer g
put value of b from ( 1 ) => m = aeg ---------> (3)
Now
91 m – 433 dc = 91 aeg – 433 d af putting values of m from (3) and c from (2)
= a ( 91 eg – 433 df )
91 m – 433dc = as where s = 91 eg – 433 df is an integer
So a | ( 91 m – 433 dc ) proved
Q # 10 : Show for n , m , a , b∈Z where n and m are integers greater than 1 ,
if n | m and if a ≡ b ( mod m ) , then a ≡ b ( mod n ). [ 1.5 ]
Given = ' n | m and a ≡ b ( mod m ) '
To prove = ' a ≡ b ( mod n ) '
We use direct proof : As given n | m => m = nc ---------> ( 1 ) for some integer c
and a ≡ b ( mod m ) => m | ( a – b)
=> a - b = mk for some integer k
put value of m from ( 1 )
=> a – b = nck = n(ck)
a – b = ns where s = ck is an integer
So n | ( a – b ) it means a ≡ b ( mod n ) proved

You might also like