Math Homework: Propositional Logic, Sets, and Mathematical Induction

This document provides solutions to a math homework assignment. The assignment covers several key concepts in discrete mathematics, including propositional logic, set theory, and mathematical induction. The solutions include truth tables to evaluate logical expressions, demonstrating the principles of logical equivalence and implication. For set theory, the solutions involve identifying set operations such as union and intersection and proving set identities. Finally, the assignment presents proof by mathematical induction, demonstrating the ability to prove statements for all positive integers. The solutions are detailed and step-by-step, making them useful for students studying these concepts. The solutions are contributed by a student and published on Desklib, a platform that offers AI-based study tools for students.

Ans:
a)
P Q (P V
Q)
!P (!P -> Q) (P V Q) <-> (!P -> Q)
T T T F T T
T F T F T T
F T T T T T
F F F T F T
b)
P Q (P -> Q) !P !Q !Q -> !P (P -> Q) ^ (!Q->!P) (Q ->
P)
((P -> Q) ^ (!Q->!P) )-> (Q ->
P)
T T T F F T T T T
T F F F T F F T T
F T T T F T T F F
F F T T T T T T T
c)
P Q (P V
Q)
!Q (P V Q) ^ !Q ((P V Q) V^!Q ) - > P
T T T F F T
T F T T T T
F T T F F T
F F F T F T

d)
P Q (P -> Q) (P -> Q) ^ P ((P -> Q ) ^ P )-> Q
T T T T T
T F F F T
F T T F T
F F T F T
Ans: a)
P Q R P V Q (P V Q) -> R !P (Q V R) !P <-> (Q V R) ((P V Q) -> R) ^ (!P <-> (Q
V R))
T T T T T F T F F
T T F T F F T F F
T F T T T F T F F
T F F T F F F T F
F T T T T T T T T
F T F T F T T T T
F F T F T T T T T
F F F F T T F F F

b)
P Q R Q V R P ^ (QV R) P ^ Q P ^ R (P ^ Q) V (P ^ R) ((P^(Q V R)) <->
((P^Q V (P ^ R))
T T T T T T T T T
T T F T T T F T T
T F T T T F T T T
T F F F F F F F T
F T T T F F F F T
F T F T F F F F T
F F T T F F F F T
F F F F F F F F T
Ans:

Ans 4:
= { a,d}
= {b,d,e,f,a,c}
= {e,f}

Ans 5:
1- A ∩ (B UC) = (A ∩ B) U (A ∩ C)
A B C B U C A ∩ (B UC)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
A B C A ∩ B A ∩ C (A ∩ B) U (A ∩ C)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F

2-
A B C B∩C A U (B ∩ C)
T T T T T
T T F F T
T F T F T
T F F F T
F T T T T
F T F F F
F F T F F
F F F F F
A B C A U B A U C (A U B) ∩ (A U C)
T T T T T T
T T F T T T
T F T T T T
T F F T T T
F T T T T T
F T F T F F
F F T F T F
F F F F F F

Ans:
____ _ _
1- A U B = A ∩ B
A B A U B
____
A U B
T T T F
T F T F
F T T F
F F F T
A B
__
A
__
B
__ __
A ∩ B
T T F F F
T F F T F
F T T F F
F F T T T

____ _ _
2- A ∩B = A U B
A B A∩B
____
A ∩ B
T T T F
T F F T
F T F T
F F F T
A B
__
A
__
B
__ __
A U B
T T F F F
T F F T T
F T T F T
F F T T T

Ans:
S1: 1 = 12 this is true
S2: 1+3 = 22 this is true
S3: 1+3+5= 32
S4: 1+3+5+7= 42
.
.
Suppose that it will also true for n = k
Sk: 1+3+5+7+……+(2k – 1) = k2
It is assumed that if it is true for k then it should true for n = k+1
Sk+1: 1+3+5+7+……+(2(k+1) – 1) = (k+1)2
1 + 3 + 5 + · · · + [2(k + 1) − 1] = (k + 1)2
1 + 3 + 5 + · · · + (2k − 1) + [2(k + 1) − 1] = (k+1)2
[1 + 3 + 5 + · · · + (2k − 1)] + [2(k + 1) − 1] = k 2 + [2(k + 1) − 1]
= k 2 + 2k + 1
= (k + 1)2

As we can see the left hand side and right hand side are equal so this proves the inductive step.
So this is proved that this is true for every positive integer n.
Ans: S1: 1 + 2 = 3 ( 3 is equal to 3)
S2: 1 + 2 * 2 = 5 ( 5 is less than 9)
So let assume that Sk: 1 + 2 * k is also less than 3k
S(k+1): 1 + 2 * (k + 1) <= 3k+1
1 + 2k + 2 <= 3k * 3
1 + 2k <= 3k * 3 – 2
3k * 3 – 2 >=1 + 2k
3k * 3 – 2 >= 3k >= 1 + 2k
We know that 3k is greater than 1+2k and 3k * 3 – 2 is greater than 3k
So 3k * 3 -2 will also greater or equal to 3k. This is proved that 3k * 3 -2 will also greater than or
equal to 1 + 2k.

Ans:
S1: 13 – 1 = 0 this is divisible by 6
S2: 23 - 2 = 8 – 2 = 6 this is also divisible by 6
Now assume that Sk where n = k, k3 - k is true for every non negative integer n.
Now test it with k+1 where n = k+1
S(k+1): ( k+1)3 – (k+1) = ( k3+3k2+3k+1 )-k -1
= k3+3k2+2k
= k3-k+3k2+3k
= (k3-k)+3k(k+1)
3k(k+1) can be divided by 6. This shows that S(k+1) is true for every non negative integer n.
This completes the inductive step and completes the proof.
Ans 2:
S1: 12– 1 = 0 this is clearly divisible by 8
S3: 32 – 1 = 9 – 1 = 8 this is clearly divisible by 8
.
.
.
Sk: k3 – 1
S(k+2): (k+2)2– 1 = k2 + 4 + 4 k -1
= (k2 – 1) + 4(1 + k )
We already know that (k2 – 1) is divisible by 8. 4(1 + k ) this term can divide by 8. This
completes the inductive step and completes the proof.