How To Prove It - Chapter 4 - 4.1

Relations - Ordered Pairs and Cartesian Products

1.

(a) T = {(a, b) ∈ P x P | a is a parent of b).
(b) T = {(c, u) ∈ C x U | there is someone who lives in c and attends u}

2.

(a) T = {(p, c) ∈ P x C | p lives in c}
(b) T = {(p, n) ∈ C x N | the population of p is n}

3.
(a) Samples (x, y) = (0, -2), (1, -2), (-1, 0)
(b) Samples (x, y) = (1, 0), (2, 1), (1000, 100)
(c) Samples (x, y) = (0, -2), (1, 1)
(d) Samples (x, y) = (0, -2), (6, 4)

4.
A = {1, 2, 3}, B = {1, 4}, C = {3, 4}, and D = {5}
(1)
A × (B ∩ C) = {(1,1), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,3), (3,4) }
(A × B) ∩ (A × C) = {(1,1), (2,1), (3,1), (1,3), (1,4), (2,3), (2,4), (3,3), (3,4)}

A × (B ∩ C) = (A × B) ∩ (A × C)

(5)
A×∅= ∅×A = ∅
A×∅ = {}
∅×A = {}

Both are = ∅



6.

Proof given for (A ∪ C) × (B ∪ D) ⊆ (A × B) ∪ (C × D)

The cases are not exhaustive. Missing cases are
(3) x ∈ A and y ∈ D
(4) x ∈ C and y ∈ B


7. m

8.
To prove A×(B \C) = (A× B)\(A×C)
-->

Given
For arbitrary x, y
(x, y) ∈ A x (B\C)
x ∈ A
y ∈ B\C

or,
Givens
x ∈ A
y ∈ B
y ∉ C

From the first 2 givens,
(x, y) ∈ A x B
From the 1st and 3rd givens,

(x, y) ∉ A x C

Combining these two,
the Cartesian product (x, y) for arbitrary x and y must is an element of A x B, but not of A x C. Hence,
(x, y) ∈ (A× B)\(A×C)

or,
(x, y) ∈ A x (B\C) -> (x, y) ∈ (A× B)\(A×C)
This completes the forward proof.

<--
Given,
for arbitrary x, y
suppose (x, y) ∈ (A× B)\(A×C)

or,
(x, y) ∈ (A× B)
(x, y) ∉ (A x C)

or,
x ∈ A
y ∈ B
Since we already have x ∈ A, so it's only possible when
y ∉ C (second given above)

Revised givens,
x ∈ A
y ∈ B
y ∉ C

From the 2nd and 3rd givens,
y ∈ B\C

Hence,
(x, y) ∈ A x (B\C)

Or, (x, y) ∈ (A× B)\(A×C) -> (x, y) ∈ A x (B\C)
This completes the reverse proof.

10.
(A x B) ∩ (C x D) = ∅

To prove,
A ∩ C = ∅ ∨B ∩ D = ∅
or,
(x ∈ A -> x ∉ C) ∨ (y ∈ B -> y ∉ D)

Suppose x ∈ A, y ∈ B
Then,
(x, y) ∈ A x B -> (x, y) ∉ C x D

The RHS can be expressed as
(x ∉ C ∧ y ∉ D) ∨ (x ∈ C ∧ y ∉ D) ∨ (x ∉ C ∧ y ∈ D)

Or,
(x ∈ A ∧ y ∈ B) -> (x ∉ C ∧ y ∉ D) ∨ (x ∈ C ∧ y ∉ D) ∨ (x ∉ C ∧ y ∈ D)

Taking the 3 cases -
1.
x ∈ A
y ∈ B
x ∉ C
y ∉ D

This implies A ∩ C = ∅ and B ∩ D = ∅
Since both are true, this is an inclusive case of the required proof.

2.
x ∈ A
y ∈ B
x ∈ C
y ∉ D

This implies A ∩ C ≠ ∅ and B ∩ D = ∅, or one of them is true. Hence,
A ∩ C = ∅ ∨B ∩ D = ∅

3.
x ∈ A
y ∈ B
x ∉ C
y ∈ D

This implies A ∩ C = ∅ and B ∩ D ≠ ∅, or one of them is true. Hence,
A ∩ C = ∅ ∨B ∩ D = ∅

From the 3 cases, A ∩ C = ∅ ∨B ∩ D = ∅

How To Prove It - Chapter 3 - 3.4

Proofs involving Conjunctions and Biconditionals

Note: A lot of the first few problems are of the same type. Skipped the similar ones.

1.
-->
Given
∀x(P(x) ∧ Q(x))

Goal
∀x P(x) ∧ ∀x Q(x)

Let ∀x(P(x) ∧ Q(x))
So for an arbitrary y, P(y) ∧ Q(y).
Hence, P(y). So ∀x P(x) is true. So is ∀x Q(x)

So, for arbitrary x, P(x) and Q(x) are true.
Hence,
∀x P(x) ∧ ∀x Q(x)

<--
Given
∀x P(x) ∧ ∀x Q(x)

Goal
∀x(P(x) ∧ Q(x))

Let ∀x P(x) ∧ ∀x Q(x)
For arbitrary y, ∀y P(y) ∧ ∀y Q(y)

Since P(y), and also Q(y), hence P(y) ∧ Q(y) is also true.
Since y was arbitrary, P(x) ∧ Q(x) is true for any value of x.
Hence, ∀x(P(x) ∧ Q(x))

2.

Givens
A ⊆ B
A ⊆ C

Goal
A ⊆ B ∩ C

Revised
Givens
x ∈ A
x ∈ A -> x ∈ B
x ∈ A -> x ∈ C

Goal
x ∈ B
x ∈ C

From the givens, x ∈ A is true. Hence, so is x ∈ B (first goal) and x ∈ C (second goal)

3.

Givens
x ∈ A -> x ∈ B

Goal
x ∈ C \ B ⊆ x ∈ C \ A

Let x be an arbitrary element of an arbitrary set C.

Revised Givens
x ∈ A -> x ∈ B
x ∈ C ∧ x ∉ B

Goal
x ∈ C \ A

The first given can be expressed as (modus tollens)
x ∉ B -> x ∉ A
x ∈ C
x ∉ B

Goals
x ∈ C
x ∉ A

From the givens,
x ∉ B, hence x ∉ A as well, which is one of the goals
From the second given, x ∈ C, which is the second goal.

9.

Given
x and y are odd integers

Goal
xy is odd

Since x and y are odd integers, they can be expressed as
x = 2k +1
y = 2m + 1,

where k and m are integers

Hence, xy = (2k + 1) (2m + 1)
= 2(2km + k + m) + 1

2km + k + m is an integers, and 2(2km + k + m) is even. Hence, 2(2km + k + m) + 1 is odd.

10.

n³ is even iff n is even

-->
We'll prove by contradiction.

Givens
n³ is even
n is odd

Goal
Contradiction

n³ is even, so
n³ = 2k, where k is an integer.

n is odd, so n = 2m + 1, m being an integer.

Hence, (2k)³ = (2m + 1)³
or,
2.4k³ = 2(4m³ + 6m² + 3m) + 1

which is impossible as the number of the left is even, while the one on the right is odd.

Hence, n has to be even if n³ is odd.

<---

Given
n is even
n³ is odd

Goal
Contradiction

n is even, so n = 2k, k being an integer
n³ is odd, so n³ = 2m + 1, m being an integer

Hence, (2k)³ = 2m + 1
=> 2(4.k³) = 2m + 1

Which is impossible, as the left expression evaluates to an even integer, while the right one to an odd integer.

Hence, n³ is even when n is even.

Combining the two, n³ is even iff n is even.

11.

(a) The same 'k' cannot be chosen, as it translates that m = n+1, which is not an assumption that is given.

(b) The theorem is incorrect.
Counterexample - m = 4, n =7

How To Prove It - Chapter 3 - 3.3

Proofs involving Quantifiers

1.
Givens
∃x(P(x) → Q(x))

Goal
∀x P(x) → ∃x Q(x)

Revised givens
∃x(P(x) → Q(x))
∀x P(x)

Goals
∃x Q(x)

Let y be an arbitrary value of x, so that
P(y) -> Q(y)
Since P(x) is true for all x, then P(y) must also be true.

Hence, Q(y) must also be true.
So for some arbitrary value of x called y, Q(x) is true. Hence, there exists some x so that Q(x) is true, i.e., ∃x Q(x)

2.
Givens
A and B \ C are disjoint

Goal
A ∩ B ⊆ C

Revised
Givens
x ∈ A -> x ∉ B \ C
x ∈ A
x ∈ B

Goal
x ∈ C

From the givens,
x ∈ A, hence x ∉ B \ C is also true.
Hence, x must be an element of C since it's not an element of (in B but not in C).
Or,
x ∈ C

3.

Givens
A ⊆ B \ C, or
for some arbitrary x,
x ∈ A -> x ∈ B \ C, or
x ∈ A -> (x ∈ B ∧ x ∉ C)

Goal
A and C are disjoint, or
x ∈ A -> x ∉ C

Revised givens
x ∈ A -> (x ∈ B ∧ x ∉ C)
x ∈ A

Revised goals
x ∉ C

From the givens, since x ∈ A is true, so x ∈ B is also true, and so is x ∉ C, which is the desired goal.

6.

(a)
Givens,
x is real
x ≠ 1

Goal
∃y (y+1 / y -2 = x)

Assume that y = -1.
Then, (y+1 / y -2 = x)
=> -1 +1 = x (-3)
=> x= 0

Thus, there exists a real number y so that x ≠ 1 and the equation is satisfied.

(b)
Using contradiction,

Givens,
there is a real number y so that y + 1 / y -2 = x
x = 1

Goal
Contradiction

From the givens,

y + 1 = y - 2
or, 1 = -2, which is a contradiction. Hence, if there is a real number y so that the equation is satisfied, then x cannot be 1.

How To Prove It - Chapter 3 - 3.2

Proofs involving negations and conditionals

1.
(a) Givens
P → Q - i
Q → R - ii

Goals
P → R

Suppose P. Then from (i), Q.
Since Q, from (ii), we have R.
Hence if P then R. P → R

(b)Given
¬R → (P → ¬Q)

Goal
P → (Q → R)

Suppose P.
From the given,
¬R → (P → ¬Q)
suppose ¬R.
Then,
(P → ¬Q)
Since we know P, we also know now that ¬Q.
Hence, ¬R led to ¬Q.
or,
¬R → ¬Q
or
Q → R
Hence,
P led to Q → R,
or,
P → (Q → R)

2.
(a)
Givens
P → Q
R → ¬Q

Goal
P → ¬R

Revised givens
P → Q
R → ¬Q
P
Q (because of the first given)

Revised goal
¬R

From the givens using modus tollens
Q→ ¬R

Since we already have Q as a given, we can conclude ¬R.

(b)
Givens
P

Goals
Q → ¬(Q → ¬P)
can be written as
(Q → ¬P) → ¬ Q

Revised Givens
P
Q → ¬P or written as
P → ¬Q

Revised goals
¬Q

From the revised givens we know P.
One of the givens also implies that ¬Q, which is the desired goal.

3.
Givens
A ⊆ C
x ∈ A
x ∈ C → x ∉ B

Goal
x ∉ B

From the givens,
Since x ∈ A and A ⊆ C, then x ∈ C also.
From the third given, this implies x ∉ B which is the desired conclusion.

x ∉ B

4.

Givens
x ∈ A
x ∈ C → x ∉ A \ B

Goal
If x ∈ C then x ∈ B

Revised givens
x ∈ A
x ∈ C → x ∉ A \ B
x ∈ C

Revised goal
x ∈ B

From the 2nd and 3rd givens, we can conclude x ∉ A \ B
or,
¬(x ∈ A ∧ x ∉ B)
From the given we know x ∈ A, hence the truth value of the expression becomes
¬(x ∉ B)
or,
x ∈ B, which is the desired goal.

7.

Givens
y + x = 2y − x
or,
y = 2x
x and y are not both 0

Goal
y is not 0

Revised givens
y = 2x
x and y are not both 0
x = 0

Hence, y cannot be 0

8.

Givens
a, b are non zero real numbers
a < 1/a < b < 1/b

Goal
a < -1

Revised givens
a, b are non zero real
a < 1/a
or a² < 1
or a < +1 or -1

b < 1/b
or
or b² < 1
or b < +1 or -1

1/a < 1/b
or a > b
But, it's already given a > b.
Hence, 1/a < 1/b is possible only when a and b are both < 0

Revised givens
a and b are non zero real
a < 1/a < 1/b < b
a and b are both < 0
a, b < + 1 or < -1

Since a and b are < 0, hence they have to be < -1 (and not just < 1)
Hence b < -1

9.

Givens
x and y are real
x * x = 2x + y
y ≠ 0

Goal
x ≠ 0

Revised givens, assuming contradiction that x = 0
x and y are real
x * x * y = 2x + y
y ≠ 0
x = 0

Goal
Contradiction

From the givens now,
0 = 0 + y
or y = 0
This is a contradiction to one of the givens.

Hence, the assumption that x = 0 is false.
Or x ≠ 0

10.

Givens
x and y are real
x ≠ 0
y = (3x² +2y) / (x² + 2)

Goal
y = 3

Revised givens
x²y + 2y = 3x² +2y
or
x² (y - 3) = 0

Since x is not 0, y - 3 has to be = 0

or y = 3, which is the desired goal.

11.

(a) "x = 3 and y = 8" is incorrect, as x and y may be any other real numbers too.
(b) x = 2, y = 8

How To Prove It - Chapter 1 - 1.2

1.2 Sentential Logic

1.
(a)

P	Q	-P	∨	Q
T	T	F	F	F
T	F	F	T	T
F	T	T	T	F
F	F	T	T	T

(b)

S	G	(S	∨	G)	∧	(-S	∨	-G)
T	T	T	T	T	T	F	F	F
T	F	T	T	F	T	F	T	T
F	T	F	T	T	T	T	T	F
F	F	F	F	F	T	T	T	T

2.
(a)

P	Q	-[	P	∧	(Q	∨	-P)]
T	T	F	T	T	T	T	F
T	F	T	T	F	F	F	F
F	T	T	F	F	T	T	T
F	F	T	F	F	F	T	T

3.
(a)

P	Q	P+Q
T	T	F
T	F	T
F	T	T
F	F	F

(b)
P + Q = (P ∧ ¬Q) ∨ (¬P ∧ Q)
Truth table -

P	Q	P+Q	(P	∧	¬Q)	∨	(¬P	∧	Q)
T	T	F	T	F	F	F	F	F	T
T	F	T	T	T	T	T	F	F	F
F	T	T	F	F	F	T	T	T	T
F	F	F	F	F	T	F	T	F	F

4.
P ∨ Q
= ¬¬P ∨ ¬¬Q
= ¬ (¬ P ∧ ¬ Q) (De Morgan's Law)
Truth table -

P	Q	P	∨	Q	¬ (	¬	P	∧	¬	Q)
T	T	T	T	T	T	F	T	F	F	T
T	F	T	T	F	T	F	T	F	T	F
F	T	F	T	T	T	T	F	F	F	T
F	F	F	F	F	F	T	F	T	T	F

5.
(a)

P	Q	P ↓ Q
T	T	F
T	F	F
F	T	F
F	F	T

(b)
P ↓ Q = ¬ P ∧¬ Q
= ¬ (P ∨ Q)

Truth table verification -

P	Q	P ↓ Q	¬	(P	∨	Q)
T	T	F	F	T	T	T
T	F	F	F	T	T	F
F	T	F	F	F	T	T
F	F	T	T	F	F	F

(c)
(i) ¬P = ¬P ∧ ¬P
= P ↓ P

(ii) P ↓ Q
= (from the previous ones) ¬ (P ∨ Q)

So, (P ∨ Q) = ¬ (P ↓ Q)
= (P ↓ Q) ↓ (P ↓ Q) (from c(i))

(iii) ¬ (P ∧ Q)
= ¬ P ∨ ¬ Q

Hence, (P ∧ Q) = ¬(¬ P ∨ ¬ Q)
= ¬ ((¬P ↓ ¬Q) ↓ (¬P ↓ ¬Q)) (from the previous one)
= ¬ (¬ (¬P ↓ ¬Q)) (from c(i))
= ¬P ↓ ¬Q
= (P ↓ P) ↓ (Q ↓ Q)

6.
(a)

P	Q	P | Q
T	T	F
T	F	T
F	T	T
F	F	T

(b)
P | Q = ¬ P ∨ ¬ Q
Truth table -

P	Q	P | Q	¬	P	∨	¬	Q
T	T	F	F	T	F	F	T
T	F	T	F	T	T	T	F
F	T	T	T	F	T	F	T
F	F	T	T	F	T	T	F

(c)
(i)
¬P = ¬ (P ∧ P)
= ¬ P ∨ ¬P
= P | P

(ii)
P ∨ Q
= ¬P | ¬ Q (from (b))
= (P | P) | (Q | Q) (from c(i)

(iii)
P ∧ Q
= ¬ (¬P ∨ ¬Q)
= ¬ ((P|P) ∨ (Q|Q))
= ¬ (((P|P) | (P|P)) | ((Q|Q) | (Q|Q)) ) (from ii)
= (((P|P) | (P|P)) | ((Q|Q) | (Q|Q)) ) | (((P|P) | (P|P)) | ((Q|Q) | (Q|Q)) ) (from i)

7. Boring stuff. Skipping.
8. Ditto!

9.
(a)

(P	∨	Q)	∧	(¬	P	∨	¬	Q)
T	T	T	F	F	T	F	F	T
T	T	F	T	F	T	T	T	F
F	T	T	T	T	F	T	F	T
F	F	F	F	T	F	T	T	F

Neither.
(b)

(P	∨	Q)	∧	(¬	P	∧	¬	Q)
T	T	T	F	F	T	F	F	T
T	T	F	F	F	T	F	T	F
F	T	T	F	T	F	F	F	T
F	F	F	F	T	F	T	T	F

A contradiction.

(c)

(P	∨	Q)	∨	(¬	P	∨	¬	Q)
T	T	T	T	F	T	F	F	T
T	T	F	T	F	T	T	T	F
F	T	T	T	T	F	T	F	T
F	F	F	T	T	F	T	T	F

A tautology.

12.
(a) ¬(¬P ∨ Q) ∨ (P ∧ ¬R)
= (¬¬P ∧ ¬Q) ∨ (P ∧ ¬R)
= (P ∧ ¬Q) ∨ (P ∧ ¬R)
= P ∧ (¬Q ∨ ¬R)

(b) ¬(¬P ∧ Q) ∨ (P ∧ ¬R)
= ( ¬¬P ∨ ¬Q)) ∨ (P ∧ ¬R)
= (P ∨ ¬Q) ∨ (P ∧ ¬R)

(c) (P ∧ R) ∨ [¬R ∧ (P ∨ Q)]
= (P ∧ R) ∨ [(¬R ∧ P) ∨ (¬R ∧ Q)]
= (P ∧ R) ∨ (¬R ∧ P) ∨ (¬R ∧ Q)

13.
First DM law -> ¬(P ∧ Q) is equivalent to ¬P ∨ ¬Q
Double negation -> ¬¬P = P

¬(P ∨ Q)
= ¬ (¬ (¬ P ∧ ¬Q)) (First)
= (¬ P ∧ ¬Q)) (double neg)

which is the second law.

14.
[P ∧ (Q ∧ R)] ∧ S
= [P ∧ (Q ∧ R)] ∧ S
= P ∧ [(Q ∧ R) ∧ S]
= P ∧ [Q ∧ (R ∧ S)]
= (P ∧ Q) ∧ [(R ∧ S)

15.
2^n

16.
It's true if either both are false or both are true, or P is true.
Can be expressed as
[(P ∧ Q) ∨ (¬P ∧ ¬Q)] ∨ P
Truth table -

P	Q	Desired	[(P ∧ Q)	∨	(¬P ∧ ¬Q)]	∨	P
F	F	T	F	T	T	T	F
F	T	F	F	F	F	F	F
T	F	T	F	F	F	T	T
T	T	T	T	T	F	T	T

17.
True when they have different values.
Can be expressed as (P ∧ ¬Q) ∨ (¬P ∧ Q)
Truth table -

(P	∧	¬	Q)	∨	(¬	P	∧	Q)
F	F	T	F	F	T	F	F	F
F	F	F	T	T	T	F	T	T
T	T	T	F	T	F	T	F	F
T	F	F	T	F	F	T	F	T

How To Prove It - Chapter 1 - 1.1

1.1. Deductive Reasoning and Logical Connectives

1.
(a) A = We will have a reading assignment
B = We will have a test
C = We will have homework problems

(A ∨ C) ∧ ¬ (C ∧ B)

(b) A = you will go skiiing
B = There will be snow

¬ A ∨ (A ∧ ¬B)

(c) ¬ [(√ 7 < 2) ∨ (√ 7 = 2)]

2.
(a) A = Bill is telling the truth
B = John is telling the truth

[(A ∧ B) ∨ ¬(A ∧ B)]

(b) F = I'll have fish
C = I'll have chicken
P = I'll have mashed potatoes

(F ∧ C) ∨ (F ∧ P)

(c) S = 3 is a divisor of 6
N = 3 is a divisor of 9
F = 3 is a divisor of 15

S ∧ N ∧ F

3.
A = Alice is in the room
B = Bob is in the room
(a) (A ∧ ¬B) ∨ (¬A ∧ B)
(b) ¬(A ∧ B)
(c) ¬A ∨ ¬B
(d) ¬A ∧ ¬B

4.
(a) Yes
(b) No
(c) Yes
(d) No

5.
P = I will buy the pants
S = I will buy the shirt

(a) I will not buy the pants without the shirt
(b) I will buy neither the pants nor the shirt
(c) Either I will not buy the pants or I'll not buy the shirt

6.
S = Steve is happy
G = George is happy

(a) (S ∨ G) ∧ (¬S ∨ ¬G) - One of S and G is happy, and one of S and G is unhappy.
Simplified, One of S and G is happy and the other is unhappy.

(b) [S ∨ (G ∧ ¬S)] ∨ ¬G - Either G is unhappy, or either G is happy but S is not or S is happy.
Another form (multisentence) -
Either G is unhappy, or one of the following is true -
a) G is happy but S is not
b) S is happy.

(c) S ∨ [G ∧ (¬S ∨ ¬G)]
Either S is happy, or G is happy and one of them is unhappy.

Note: I'm not satisfied with my answers here.

7.
(a) JC = Jane will win the chem prize
PC = Pete will win the chem prize
JM = Jane will win the math prize
PM = Pete will win the math prize

(JM ∧ ¬PM) ∨ (¬JM ∧ PM)
PM ∨ PC
JM
Conclusion : PC

Reasoning is valid.

(b) B = beef main course
F = fish main course
P = peas
C = corn

B ∨ F
P ∨ C
¬(F ¬(B ∧ P) C)
Conclusion : ¬(B ∧ P)

Reasoning is invalid. For P = B = true, C = F = false, the arguments are true but ¬(B ∧ P) is false.

(c)
J ∨ B
¬S ∨ ¬B

Conclusion : J ∨ ¬S

Reasoning is valid.

(d) (S ∧ B) ∨ (E ∧ ¬B)

Conclusion : ¬(E ∧ S)

For S = B = E = true, the argument is valid, but the conclusion is not. Hence, reasoning is not valid.

How To Prove It - Introduction

Chapter : Intro

1.
(a) 2^15 - 1 = 32767
4681×7 is a possible answer, trying out divisors from 3 onwards.

2.

n	Is n prime?	3^n – 1	Prime?	3^n – 2^n	Prime?
2	Yes	8	No	5	Yes
3	Yes	28	No	19	Yes
4	No	80	No	65	No
5	Yes	242	No	211	Yes
6	No	728	No	665	No
7	Yes	2186	No	2059	No
8	No	6560	No	6305	No
9	No	19682	No	19171	No

Conjectures -
(a) 3^n - 1 is not a prime irrespective of what n is
(b) If n is a prime, so is 3^n - 2^n, and if n is not, neither is 3^n - 2^n

3.
(a) m = 2 * 3 * 5 * 7 = 210
From the above table, we know 211 (m + 1) is a prime!

(b) m = 2 * 5 * 11 = 110
m + 1 = 111, which is divisible by 3 (as the sum of the digits is divisible by 3)
m + 1 = 37 * 3, both of which are primes.


4.
For n = 5,
x = (n + 1)! + 2 = 6! + 2 = 722
Non primes are - 722, 723, 724, 725, 726

5.
If 2^n − 1 is prime, then 2^(n−1) (2^n − 1) is perfect (Euclid).

Using the table in the book, 2^n - 1 is prime for n = 5, 7

P1 = 16 * 31 = 496
P2 = 64 * 127 = 8128

6. There are no more such triplets - http://en.wikipedia.org/wiki/Prime_triplet

And next...

Finished the Ross book's intro probability chapter today. I've decided not to do the next chapters yet (random variables, etc), but start with a book on mathematical proofs instead. Post that, I might do the remaining chapters, or do the Bertsekas book

Now I think this blog should have been named "math stuff". directly.

Sheldon Ross Introductory Statistics - Probability Chapter Review Problems

Review Problems

1.
(a) P(first is good) = 9/12 = 3/4 = 0.75

(b) G1 = first is good
B1 = first is bad
G2 = second is good
P(G2) = P(G2|G1) + P(G2|B1)
= 9/12 * 8/11 + 3/12 * 9/11
= 0.75

(c) P(both are good) = P(G2|G1)
= 9 / 12 * 8/11
= 6/11

(d) P(both are bad) = P(not G2 | not G1)
= P(first is bad) * P(second is bad | first is bad)
= 3/12 * 2/11 = 1/22

(e) P(one is good and one is bad)
= P(G1 ∩ B2) + P(B1 ∩ G2)
= P(B2|G1). P(G1) + P(G2|B1).P(B1)
= 3/11 * 9/12 + 9/11 * 3/12
= 0.409090909

2.
(a) 0.64
(b) 0.04
(c) 0.04

3.
F1 = makes the first shot
F2 = makes the second shot

(a) P(F1 ∩ F2) = P(F2|F1) * P(F1)
= 0.85 * 0.8 = 0.68

(b) P(not F1 ∩ not F2) = P(not F2|not F1) * P(not F1)
= 0.3 * 0.2 = 0.06

(c) P(F1 ∩ not F2) = P(not F2|F1) * P(F1)
= 0.15 * 0.8 = 0.12

4.
M = person is a man
W = person is a woman
L = voted in the last election

(a) P(W ∩ L) = P(L|W) * P(W)
= 0.68 * 0.54
= 0.3672

(b) P(M ∩ not L) = P(not L|M) * P(M)
= 0.38 * 0.46
= 0.1748

(c) P(M|L) = P(M ∩ L) / P(L)
= 0.62 / (0.68 * 0.54 + 0.62 * 0.46)
= 0.950337216 (seems too high!)

5.
(a) P(first is a boy) = 11/24

(b) P(second is a girl ∩ first is a boy)
= 13/23

6.
(a) P(both aces)
= P(first is ace ∩ second is ace)
= P(second is an ace| first is an ace) * P(first is an ace)
= 3/52 * 4/52 = 0.00443787

(b) P(both are spades) = same as above = 0.00443787

(c) Once the first card is chosen, there are 51 - 12 = 39 cards of other suits.
P(choosing another suit) = 39/52

(d) Once the first card is chosen, there are 51 - 3 = 48 cards of other denominations.
P(choosing another card) = 48/52

7.
(a) 1/2 * 1/2 * 1/2 * 1/2 * 1/2 * 1/2 = 1/64

(b) 1/64 (independent events)

(c) 1/64 (independent events)

8.
(a) 1/2 * 1/2 = 1/4

(b) 1/2 * 1/2 * 1/2 = 1/8

(c) (1/2) ^ 10 = 1/1024

9. Repeat question from one of the earlier sections.

10.
Total pop = 48.8 + 50.4 + 74.5 + 66.6 = 240.3 (million)

(a) P(A) = (50.4 + 66.6) / 240.3 = 0.486891386
P(not A) = 1 - P(A) = 0.513108614

(b) P(B) = (48.8 + 50.4 ) / 240.3 = 0.412817312

P(not B) = 0.587182688

(c) P(A ∩ B) = P(A).P(B) = 0.200997193

(d) P(A ∩ not B) = P(A). P(not B) = 0.301288495

(e) P(A|B) = P(A ∩ B) / P (B) = 0.200997193 / 0.412817312 = 0.486891386

(f) P(B|A) = P(B ∩ A) / P(A) = 0.200997193/0.486891386 = 0.412817312

11.
(a)P(The successful key is the first one tried) = 1/3
(b)P(The successful key is the second one tried) = 1/3
(c)P(The successful key is the third one tried) = 1/3
(d)P(The second key works given that the first one did not) = 1/2

13.
P(neither is faulty)
= P(first is not faulty) * P(second is not faulty|first is not faulty)
= 8/12 * 7 /11
= 14/33

14.
Note : P(B) = 0.6 and P(not A) = 0.2

(a) P(A ∩ B) = 0.8 * 0.6 = 0.48

(b) P(A ∪ B) = 0.8 + 0.6 - 0.48 = 0.92

(c) P(B) = 0.6

(d) P(not A ∩ B)

We have, P(not A) = P(not A ∩ B) + P(not A ∩ not B )
=> P(not A ∩ B) = P(not A) - P(not A ∩ not B ) (the second exp's two events are independent, so it's equal to the product of the probabilities of the events)

= P(not A) - P(notA).P(not B)
= 0.2 - 0.2 * 0.4
= 0.12

15.
(a) 1/52

(b)
A = 1st card is not ace of spades
B = 2nd card is ace of spades

P(A∩B) = P(A). P(B|A)
= (1 - 1/52) * (1/51)
= 1/52

(c) equally

(d) 1/52 - see (c)

16.
M = manual check detects
E = electronic check detects

P(not M ∩ not E) = P(not E| not M) * P(not M)
= 0.20 * 0.30 = 0.06

So, 6 % of defective disks are not detected.

17.
TG = this year is good
NG = next year is good

(a) Business conditions both this year and next will be good.
P = (TG ∩ NG) = P(NG | TG) * P(TG)
= 0.7 * 0.6 = 0.42

(b) Business conditions will be good this year and bad next year.
P = P(TG ∩ not NG) = P(not NG|TG) * P(TG)
= 0.3 * 0.6 = 0.18

(c) Business conditions will be bad both years.
P = P(not TG ∩ not NG) = P(not NG|not TG) * P(not TG)
= 0.6 * 0.4 = 0.24

(d) Business conditions will be good next year.
P(NG) = P(NG|TG)P(TG) + P(NG|not TG )P(not TG ) (Form. 4.1 on page 185)
= 0.7 * 0.6 + 0.4 * 0.4
= 0.58

(e) Given that business conditions are good next year, what is the
conditional probability that they were good this year?
P(TG|NG) = P(TG ∩ NG) / P(NG)
= 0.42 / 0.58
= 0.724137931

18.
J = child receives a blue gene from John
M = child receives a blue gene from Maureen

From the questions, it looks like once a gene is given to a child, it cannot be given again to another from that parent. But is that how it really works?

19.
A = person is above ideal weight
B = person has high BP

P(A∩B) = P(A) + P(B) - P(A ∪ B)
= 0.55 + 0.20 - 0.60
= 0.15

P(A) * P(B)
= 0.55 * 0.20
= 0.11

Since the values are different, they are not independent.

21.
(a) What is the probability that the husband earns less than $75,000?
P = (212 + 36)/500 = 0.496

(b) What is the conditional probability that the wife earns more than
$75,000 given that the husband earns more than this amount?
P = P(w> | h>) = P(h> ∩ w>) / P(h>)
= (54/500) / ((198 + 54)/500) = 0.214285714

(c) What is the conditional probability that the wife earns more than
$75,000 given that the husband earns less than this amount?
P = P(w> | h<) = P(w> ∩ h<) / P(h<)
= (36/500) / (248/500) = 0.14516129

(d) Are the salaries of the wife and husband independent?
P(h> ∩ w>) = 54/500 = 0.108
P(h>) = ((198 + 54)/500) = 0.504
P(w>) = 90/500 = 0.18

P(h>) * P(w>) = 0.09072 != 0.108
Hence, the salaries are not independent.

23.
G = purchases gasoline
O = purchases oil

(a) P(G ∩ O) = P(G) + P(O) - P(G ∪ O)
= 0.86 + 0.08 - 0.9
= 0.04
= 4%

(b)
(i) P(O | G) = P(O ∩ G) / P(G)
= 0.04 / 0.86 = 0.046511628

(ii) P(G | O) = P(O ∩ G) / P(O)
= 0.04 / 0.08 = 0.5

(iii) P(O ∩ G) = 0.04
P(O) * P(G) = 0.86 * 0.08 = 0.0688
Hence, not independent.

24.
(a) P(18-24jazz ∩ 35-44jazz)
= P(18-24jazz) * P(35-44jazz)
= 0.14 * 0.10
= 0.014

(b) P(18-24jazz) + P(35-44jazz)
= 0.24

25.
(a) P(M ∩ not W) + P(W ∩ not M)
= P(M)*P(not W) + P(W)*P(not M)
= 3/100 * 95/100 + 97/100 * 5/100
= 0.077

(b) P(M ∪ W)
= P(M) + P(W) - P (M ∩ W)
= P(M) + P(W) - P(M)*P(W)
= (2 + 3)/100 - 2*3/10000
= 0.0494

(c) P(M) * P(W) = 15 * 19/10000 = 0.0285

26.
No, it's not enough as we don't know the overlaps.

27.
(a) P(A ∪ B)
= P(A) + P(B) - P (A ∩ B)
= P(A) + P(B) - P(B|A)*P(A)

and,
P(B) = P(B|A)P(A) + P(B|not A)P(not A) (Form. 4.1 on page 185)
Combining,
P(A ∪ B)
= P(A) + P(B|A)P(A) + P(B|not A)P(not A) - P(B|A)*P(A)
= P(A) + P(B|not A)P(not A)
= 0.6 + 0.1 * 0.4
= 0.64

(b) Assumption being that they are independent,
P(A ∩ B) = P(A) * P(B)
= 0.06

29.
(a) P(A ∪ B)
= P(A) + P(B) - 0 (mut. excl.)
= 0.5

(b) P(A ∪ B)
= P(A) + P(B) - P(A).P(B)
= 0.2 + 0.3 - 0.06
= 0.44

(c) P(A ∩ B ∩ C)
= P(A).P(B).P(C)
= 0.024

(d) P(A ∩ B ∩ C)
= 0 (mutually excl, so they cannot occur together).

30.
B = has breast cancer
M = has positive mammography

P(B|M) = P(M|B)*P(B) / ( P(M|B)*P(B) + P(M|not B)*P(not B) )

= (0.9 * 0.02) / ((0.9 * 0.02) + (0.1 * 0.98) )
= 0.155172414

31.
Note: Identical does not mean it has to be monozygotic. Did not realize this simple fact at first! Also, same sex != identical

Struggled with this for half an hour, and then got the pointer from here - http://www.math.wustl.edu/~feres/Math450Lect02.pdf

BB, GG, BG -> events that the pair has only boys, only girls and mixed.
M, D -> zygoticness

For a given pair,
P(BB|M) = P(GG|M) = 1/2 (equally likely that the pair has both boys, or both girls)
P(GB|M) = 0 (always same sex)
P(GB|D) = 1/2 (sample space - BB, GG, GB, BG, fulfilling events = 2)
P(GG|D) = 1/4 = P(BB|D)

P(GG) = P(GG|M). P(M) + P(GG|D).P(D) (M = !D)
= 1/2 * P(M) + 1/4 * (1 - P(M))
=> 4P(GG) = 2P(M) + 1 - P(M)
=> P(M) = 4P(GG) - 1

Given P(GG) + P(BB) = 0.64
Also, P(M) = 4P(BB) - 1 (assuming equal number of boys and girls)

2P(M) = 4 (P(GG) + P(BB) ) -2
=> P(M) = 2 * 0.64 - 1
= 0.28

Sheldon Ross Introductory Statistics - Probability Section 4.6

Bayes' Theorem

1.
F-> event that the fair coin is selected
B-> event that the biased coin is selected

(a) P(Heads) = P(H|F).P(F) + P(H|B).P(B)
= 0.5 * 0.5 + 0.6 * 0.5
= 0.55

(b) P(F|T) = P(F∩T)/P(T) = P(T|F)P(F)/P(T)

= P(T|F).P(F) / (P(T|F).P(F) + P(T|not F).P(not F))

= (0.5 * 0.5) / (0.5 * 0.5 + 0.4 * 0.5) = 0.555555556

2.
K-> event that the student knew the answer
C-> event that the student answered it correctly

P(K|C) = P(C|K). P(K) / (P(C|K). P(K) + P(C|not K). P(not K))

= (1 * 0.6) / (1 * 0.6 + 0.2 * 0.4 ) = 0.882352941

3.
L -> event that the suspect is left handed
G -> event that the suspect is guilty

(a) P(L) = P(L|G). P(G) + P(L|not G).P(not G)
= 1 * 0.6 + 0.18 * 0.4 = 0.672

(b) P(G|L) = P(L|G).P(G) / (P(L|G).P(G) + P(L|not G).P(not G))

= (1 * 0.6 ) / ( 1 * 0.6 + 0.18 * 0.4 ) = 0.892857143

4.
U1 - 4R 3B
U2 - 2R 2B
R1 -> event that the ball drawn from urn 1 was red
B1 -> event that the ball drawn from urn 1 was blue
R2 -> event that the ball drawn from urn 2 is red
B2 -> event that the ball drawn from urn 2 is blue

If R1 happened, there are 3R 2B in U2. Note that, R1 = not B1

(a) P(R2) = P(R2|R1).P(R1) + P(R2|not R1).P(not R1)
= (3/5)*(4/7) + (2/5)*(3/7)
= 0.514285714

(b) P(R1|B2) = (B2|R1) . P(R1) / ((B2|R1) . P(R1) + P(B2|not R1) . P(not R1) )
= (2/5)* (4/7) / ( (2/5)* (4/7) + (3/5) * (3/7) )
= 0.470588235

5.
P-> person's diagnosis is positive
D-> person has the disease

P(D|P) = P(P|D).P(D)/( P(P|D).P(D) + P(P|not D).P(not D) )

= (0.97 * 0.02) / (0.97 * 0.02 + 0.03 * 0.98)
= 0.397540984

6.
R -> this side of the card is red
M -> this is the mixed card (bi coloured)

P(M|R) = P(R|M).P(M) / (P(R|M).P(M) + P(R|not M).P(not M))

= (0.5 * 1/3) / ( (0.5 * 1/3) + (0.5 * 2/3) )
= 0.333333333

7.
(a) P(in favour) = P(A|D) + P(A|R) (A, D, R self explanatory)

= 0.42 * 0.48 + 0.64 * 0.52 = 0.5344

(b) P(R|not A) = P(not A|R) * P(R)/( P(not A|R) * P(R) + P(not A|not R) * P(not R) )

= (0.36 * 0.52) / (0.36 * 0.52 + 0.58 * 0.48)
= 0.402061856

9.
C-> it's a California household
T-> earns over 250k/year

(a) Let x be the total no of households in the US

No of households in Cal = 0.12x
No of households in Cal earning over 250k/year = 3.3 % of 0.12x
= 0.00396x

No of households in the US earning over 250k/year = 0.013x

Hence, no of households in non-Cal earning over 250k/year = 0.013x - 0.00396x
= 0.00904x

The same thing as a percentage = 0.00904x/total non-Cal households
= 0.00904x/0.88x
= 0.010272727
~ 0.0103

(b) P(C|T) = P(T|C). P(C) / (P(T|C). P(C) + P(T|not C). P(not C))

= 0.033 * 0.12 / (0.033 * 0.12 + 0.0103 * 0.88)

= 0.304054054
~ 0.3046

Sheldon Ross Introductory Statistics - Probability Section 4.5

Conditional Probability and Independence

1.
(a) A -> obese
B -> diabetes

P(B|A) = P(A ∩ B) / P(A)
= 0.02/0.3 = 0.067

(b) P(A|B) = P(A ∩ B) / P(B)
= 0.02/0.03 = 0.67

2.
A -> first flip is heads
B -> second flip is heads

P(B|A) = P(A ∩ B) / P(A) = 1/4 / 2/4 = 1/2 = 0.5

3.
Mistake in q? There's no bracket for >25k

5.
Total = 28900
(a) Less than 10 years old = 4200/28900 = 0.14532872
(b) Between 10 and 20 years old = 5100 / 28900 = 0.176470588
(c) Between 20 and 30 years old = 6200/28900 = 0.214532872
(d) Between 30 and 40 years old = 4400 / 28900 = 0.152249135

6.
(a) Between 10 and 20 years old, given that the resident is less than 30 years old
A -> between 10 and 20
B -> less than 30

P(A|B) = P(A ∩ B) / P(B) = (5100/28900) / (15500/28900) = 0.329032258

(b) Between 30 and 40 years old, given that the resident is older than 30

A -> between 30 and 40
B -> older than 30

P(A|B) = P(A ∩ B) / P(B) = (4400/28900)/(13400/28900) = 0.328358209

7.
(a)
A -> plays chess
B -> plays bridge

P(A|B) = P(A ∩ B) / P(B) = (26/120) / (56/120) = 0.464285714

(b)
A -> plays bridge
B -> plays chess

P(A|B) = P(A ∩ B) / P(B) = (26/120)/(40/120) = 0.65

Most problems after this are copies with the situations changed. Skipping till I find something interesting.

27.
(a) S = {(U, D), (D, U), (U, U), (D,D)} (move up, then down, or the reverse, over two days)

P(reach original after 2 days) = 2/4 = 1/2

(b) S = {(u,u,u), (u,u,d), (u,d,d), (d,d,d), (d,d,u), (d, u, u), (d,u,d), (u,d,u)}
Risen by 1 after 3 = {(u,u,d), (d, u, u), (u,d,u)}
P(rise by 1 after 3 days) = 3/8

(c) P (went up on first | risen by 1 after 3 days) = P (went up on first ∩ risen by 1 after 3 days) / P (risen by 1 after 3 days)
= (2/8) / (3/8) = 2/3

28.
(a) Independent
(b) Ind
(c) Ind

33.
A = ace
B = spade

P(A) = 4/52
P(B) = 13/52

P(A).P(B) = 1/52

P(A ∩ B) = P(A|B). P(B) = (1/13).(13/52) = 1/52

The probabilities are the same - hence, they are independent.

34.
A = {(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)}
P(A) = 6/36 = 1/6
------------------------------------
B(first die on 1) = {(1,1),(1,2),(1,3),(1,4),(1,5),(1,6)}
P(B) = 6/36 = 1/6

P(A∩B) = 1/36

P(A).P(B) = P(A∩B). Hence A is independent of the fact that the first die lands on 1.
------------------------------------
C(first die on 2) = {(2,1),(2,2),(2,3),(2,4),(2,5),(2,6)}
P(C) = 1/6

P(A∩C) = 1/36

Independent
------------------------------------
D(first die on 4) = {(4,1),(4,2),(4,3),(4,4),(4,5),(4,6)}
P(D) = 1/6

P(A∩D) = 1/36

Independent
------------------------------------
E(first die on 5) = {(4,1),(4,2),(4,3),(4,4),(4,5),(4,6)}
Same. Ind

------------------------------------
F(first die on 6) = {(6,1),(6,2),(6,3),(6,4),(6,5),(6,6)}
Same.

Actually, because the sum is constant in all these cases, there is only one possibility for the second die to make the sum 7. Hence, the prob of that and A is always 1/36. And the prob of that _one_ event is of course 1/6. Hence, they are all independent

35.
Let's say the first person has a birthday on day 1. For the other person to have the same birthday, he has only one choice - day 1. 1 out of 365 possible days - 1/365

37.
(a) P(current flowing) = P(both relays closing) = P(A). P(B) = 0.8 * 0.8 = 0.64

(b) P(current flowing) = P(first relay closing) or P(second relay closing) = P(A) + P(B) + P(A∩B) = 0.8 + 0.8 - 0.64 = 0.96

(c) P(current flowing) = P(both upper relays close) or P(both lower relays close)
= (P(upper1).P(upper2)) or (P(upper1).P(upper2))
= 0.8 * 0.8 + 0.8 * 0.8 - (0.8 * 0.8 * 0.8 * 0.8) = 0.8704

38.
No, they are not independent.
Intuitively, P(B) changes once A has happened.


39.
Yes, they will be. In this case, P(A) is alway 1/2, and so is P(B)
P(A∩B) = 1/4 = P(A).P(B)

40.
(a) P(all 4 yes or all 4 no) = 0.7 * 0.7 * 0.7 * 0.7 + 0.3 * 0.3 * 0.3 * 0.3 = 0.2401 + 0.0081 = 0.2482

(b) P(first 2 no, last 2 yes) = 0.9 * 0.49 = 0.441

(c) P(atleast one no) = 1 - P(no nos) = 1 - (all yes) = 1 - 0.2482 = 0.7518

(d) 4 cases where exactly three answer yes.
P(3 yes) = (0.7 cubed * 0.3) quadrupled = 0.000112114

41.
(a) Rain on all 3 = 4/31 * 3/30 * 16/31 = 0.006659729
(b) Dry on all 3 = (1-4/31) * (1-3/30) * (1-16/31) = 0.379292404
(c) P(Ph, Mo, not LA) = 4/31 * (1-3/30) * 16/31 = 0.059937565
(d) ... same stuff.
(f) Sum of c,d,e

42.
(a) P(both are defective) = P(A).P(B) = 0.005
(b) P(both are not defective) = (1-P(A)). P(1-P(B)) = 0.0855
(c) P(exactly one) = P(A).P(not B) + P(not A).P(B) = 0.1 * 0.95 + 0.9 * 0.05 = 0.14
(d) P(A|defective) = P(A and defective) / P(defective)
= 0.10/(0.10 + 0.05) = 0.666666667
(e) P(B|defective) = P(B and defective) / P(defective)
= 0.05/(0.10 + 0.05) = 0.333333333

43.
(a) P(CF) = 1/2 + 1/2 = 1/4 (one from each parent)
(b) Q Not clear.

Sheldon Ross Introductory Statistics - Probability Section 4.4

1. P(did not sleep) = (216-128)/216 = 0.407

2.
(a) Gained weight = 5/32 = 0.15625
(b) Lost weight = 18/32 = 0.5625
(c) Neither lost nor gained weight = 9/32 = 0.28125

3.
(a) An ace = 4/52 = 0.076923077
(b) Not an ace = 0.923076923
(c) A spade = 13/52 = 0.25
(d) The ace of spades = 1/52 = 0.019230769

4.
(a) Exceeds 10,000 = 3/10 = 0.33
(b) Is under 3500 = 5/10 = 0.2
(c) Is between 4000 and 6000 = 0
(d) Is less than 2000 = 0

5.
TBD

6.
4/5

7.
(a) P (not in the program) = 56/100 = 0.56
(b) Addition rule - P(A ∩ B) = (26 + 28 - 44)/100 = 0.1

8. P(either dog or cat) = 20+32 -12 = 40
So P (neither) = 60/100 = 0.6

9.
(a) Either ring or necklace=40%, 0.4
(b) P(ring and necklace) = 20+30 - 40 = 10, 0.1

10.
(a) Does not play tennis = 120 - 44 = 76
(b) Does not play squash = 120 - 30 = 90
(c) Plays neither tennis nor squash - 0.64

11. Addition rule = 44 + 30 - 18 = 56

12.
(a) Either 7 or 11 = {(1,6), (6,1), (2,5), (5,2), (3,4), (4,3), (5,6), (6,5)}
P(Either 7 or 11) = 8/36 = 0.22

(b) One of the values 2, 3, or 12 = {(1,1), (1,2), (2,1), (6,6)}
P(One of the values 2, 3, or 12) = 4/36 = 0.11

(c) An even number = {(1,1), (1,3), (1,5), (3,1), (5,1), (2,2), (2,4), (2,6), (3,3), (3,5), ( 4,2), (6,2), (5,3)}
P(an even number) = 0.36

13. 1/19

14.
(a) Earns under $15,000 = 3936 / 81018 = 0.048581797
(b) Is a woman who earns between $20,000 and $40,000 = P(woman). P(range) = 0.386827619 x 0.300093806 = 0.116084573
(c) Earns under $50,000 = (22138(w) + 21364(m))/81018 = 0.54

15.
(a) The first key opens the door = 0.1
(b) All 10 keys are tried = 1/10
Here, prob that 1st key is not = 9/10
Once this is out of the way, prob that 2nd key is not = 8/9 (total 9 left)
And so on....
So P = 9/10 x 8/9 x 7/8 x .... 1/2 = 1/10 = 0.1

16.
(a) P(2nd) = 4/9 (position does not matter)
(b) P(charles is second) = P(second is boy). P(boy is charles) = 4/9 x 1/4 = 1/9

17.
(a) January 5 - 10/31
(b) August 12 - 9/31
(c) April 15 - 10/30
(d) May 15 - 11/31
(e) October 12 - 7/31