Logic and Set – Typed Notes
1. Logic
Statement
A declarative sentence which is either true or false but not both is called a statement.
Types of Statement
- Simple statement
- Compound statement
2. Logical Connectives
1) Conjunction (AND, ∧)
Two simple statements which are combined by the word “and” to form a compound statement is called conjunction of given statements.
It is denoted by ∧.
If p and q are two simple statements, then conjunction of p and q is denoted by:
If p ∧ q is true when p is true and q is true; otherwise p ∧ q is false.
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
2) Disjunction (OR, ∨)
Two simple statements which are combined by the word “or” to form a compound statement is called disjunction of given statements.
It is denoted by ∨.
If p and q are two simple statements, then disjunction of p and q is denoted by:
If p ∨ q is false when p is false and q is false; otherwise p ∨ q is true.
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
3) Condition (If … then, ⇒)
Two simple statements which are combined by the words “if … then” to form a compound statement is called condition of given statements.
It is denoted by ⇒.
If p and q are two simple statements, then condition of p and q is denoted by:
p ⇒ q is false when p is true and q is false; otherwise it is true.
| p | q | p ⇒ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
4) Bi-condition (“If and only if”, ⇔)
Two simple statements which are combined by the words “if and only if” to form a compound statement is called bi-condition of given statements.
It is denoted by ⇔.
p ⇔ q is true when p is true and q is true, and also when p is false and q is false; otherwise it is false.
| p | q | p ⇔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
5) Negation (~)
If p is a given statement, then negative or denial of p is called negation.
It is denoted by ~p.
| p | ~p |
|---|---|
| T | F |
| F | T |
3. Types of Condition
- Condition: p ⇒ q
- Converse: q ⇒ p
- Inverse: ~p ⇒ ~q
- Contrapositive: ~q ⇒ ~p
4. Some Laws of Logic
A. Associative Laws
| p | q | r | q ∧ r | p ∧ q | p ∧ (q ∧ r) | (p ∧ q) ∧ r |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | F | T | F | F |
| T | F | T | F | F | F | F |
| T | F | F | F | F | F | F |
| F | T | T | T | F | F | F |
| F | T | F | F | F | F | F |
| F | F | T | F | F | F | F |
| F | F | F | F | F | F | F |
| p | q | r | q ∨ r | p ∨ q | p ∨ (q ∨ r) | (p ∨ q) ∨ r |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | T | T | T |
| T | F | T | T | T | T | T |
| T | F | F | F | T | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | T | T | T |
| F | F | T | T | F | T | T |
| F | F | F | F | F | F | F |
B. Idempotent Laws
C. Commutative Laws
D. Distributive Laws
E. De Morgan’s Laws
5. Exercise 1.1
1. Which of the following sentences are statements?
- Laxmi Prasad Devkota was a great poet.
- 2 + 3 = 5
- Rara Tal is in Nepal.
- 5 = √2
- Any natural number is positive.
- 5 ≥ 3 + 2
- (25 + 5) ÷ 10 = 3
- 2 > 3
3. If p and q are the statements such that:
p: “5 is a divisor of 125”
q: “It is raining”
Then give the meaning of the statements:
- ~p: “125 is not divisible by 5.” — False
- ~q: “It is not raining.” — True
- p ∨ q: “5 is a divisor of 125 or it is raining.” — True
- p ∧ q: “5 is a divisor of 125 and it is raining.” — False
- p ⇒ q: “If 5 is a divisor of 125 then it is raining.” — False
- ~p ⇒ q: “If 5 is not a divisor of 125 then it is raining.” — True
- p ⇔ q: “5 is a divisor of 125 if and only if it is raining.” — False
4. If p is true, q is false, r is true and s is false, find the truth values:
- p ∧ q = F
- ~p ∧ ~q = F
- p ∨ (~q) = T
- (p ∨ q) ∧ (r ∨ s) = T
- q ∧ (p ∧ s) = F
5. Identify the hypothesis and conclusion
| Hypothesis | Conclusion |
|---|---|
| A person lives in Delhi Bazar. | He lives in Kathmandu. |
| Two angles are right angles. | They are equal. |
| A figure is a parallelogram. | Its diagonals bisect each other. |
| A student does not study. | He may fail. |
6. State whether the given statements are true or false. Also give the negation.
-
15 > 13 and 3 is odd.
Truth value: T
Negation: 15 is not greater than 13 or 3 is not odd. -
3 is odd and 22 = 5.
Truth value: F
Negation: 3 is not odd or 22 ≠ 5. -
2 is prime or 1 < 5.
Truth value: T
Negation: 2 is not prime and 1 is not less than 5. -
7 is even or 5 × 2 = 10.
Truth value: T
Negation: 7 is not even and 5 × 2 ≠ 10.
7. State whether the given statements are true or false. Also give the negation and contrapositive.
a. If 3 ≤ 7 then 2 + 3 = 5.
Negation: 3 ≤ 7 and 2 + 3 ≠ 5.
Contrapositive: If 2 + 3 ≠ 5 then 3 is not less than or equal to 7.
b. If 5 is a prime then 13 is even.
Negation: 5 is a prime and 13 is not even.
Contrapositive: If 13 is not even then 5 is not prime.
c. If 2 < 3 implies that 3 > 7, then 4 is odd.
Negation: 2 < 3 implies that 3 > 7 and 4 is not odd.
Contrapositive: If 4 is not odd then 2 < 3 and 3 is not greater than 7.
d. If 10 is odd or 12 is even, then 5 > 7.
Negation: 10 is odd or 12 is even and 5 is not greater than 7.
Contrapositive: If 5 is not greater than 7 then 10 is not odd and 12 is not even.
8. Write converse and inverse of the statement
Statement: If 3 is an odd number and 6 is not an odd number.
Converse: If 6 is not an odd number then 3 is an odd number.
Inverse: If 3 is not an odd number then 6 is an odd number.
9. Construct truth tables for the following statements
a. (~p) ∧ q
| p | q | ~p | (~p) ∧ q |
|---|---|---|---|
| T | T | F | F |
| T | F | F | F |
| F | T | T | T |
| F | F | T | F |
b. ~(p ∧ q)
| p | q | p ∧ q | ~(p ∧ q) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
c. p ∨ (~q)
| p | q | ~q | p ∨ (~q) |
|---|---|---|---|
| T | T | F | T |
| T | F | T | T |
| F | T | F | F |
| F | F | T | T |
d. (p ∧ q) ⇒ (p ∨ q)
| p | q | p ∧ q | p ∨ q | (p ∧ q) ⇒ (p ∨ q) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | F | T |
e. ~(p ⇒ ~q)
| p | q | ~q | p ⇒ ~q | ~(p ⇒ ~q) |
|---|---|---|---|---|
| T | T | F | F | T |
| T | F | T | T | F |
| F | T | F | T | F |
| F | F | T | T | F |
f. ~[(~p) ∧ q]
| p | q | ~p | (~p) ∧ q | ~[(~p) ∧ q] |
|---|---|---|---|---|
| T | T | F | F | T |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | T | F | T |
g. ~(p ⇔ q)
| p | q | p ⇔ q | ~(p ⇔ q) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | T | F |
h. (p ∨ q) ⇒ (p ∧ q)
| p | q | p ∨ q | p ∧ q | (p ∨ q) ⇒ (p ∧ q) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | T | F | F |
| F | T | T | F | F |
| F | F | F | F | T |
i. (p ⇒ ~q) ∧ (p ⇒ r)
| p | q | r | ~q | p ⇒ r | p ⇒ ~q | (p ⇒ ~q) ∧ (p ⇒ r) |
|---|---|---|---|---|---|---|
| T | T | T | F | T | F | F |
| T | T | F | F | F | F | F |
| T | F | T | T | T | T | T |
| T | F | F | T | F | T | F |
| F | T | T | F | T | T | T |
| F | T | F | F | T | T | T |
| F | F | T | T | T | T | T |
| F | F | F | T | T | T | T |
10. If p and q be two statements, prove that the following statements are tautologies.
a. (p ∨ q) ∨ (~p)
| p | q | p ∨ q | ~p | (p ∨ q) ∨ (~p) |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | T | F | T |
| F | T | T | T | T |
| F | F | F | T | T |
Proved: (p ∨ q) ∨ (~p) is a tautology.
b. (p ∧ q) ⇒ (p ∨ q)
| p | q | p ∧ q | p ∨ q | (p ∧ q) ⇒ (p ∨ q) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | F | T |
Proved: (p ∧ q) ⇒ (p ∨ q) is a tautology.
11. Prove that for any statements p and q:
| p | q | p ∧ q | p ∨ q | ~(p ∨ q) | (p ∧ q) ∧ ~(p ∨ q) |
|---|---|---|---|---|---|
| T | T | T | T | F | F |
| T | F | F | T | F | F |
| F | T | F | T | F | F |
| F | F | F | F | T | F |
Proved: (p ∧ q) ∧ ~(p ∨ q) is a contradiction.
6. Introduction of Sets
A well-defined collection or list of objects is known as a set.
7. Operations of Sets
1) Union of Two Sets
If A and B are two sets, then union of two sets A and B is denoted by A ∪ B and defined by the set of all elements belonging to set A and set B or both.
2) Intersection of Two Sets
The intersection of two sets A and B is denoted by A ∩ B and defined by the set of all elements which are common to both A and B.
3) Difference of Two Sets
The difference of two sets A and B is denoted by A – B and defined by the set of all elements of A which do not belong to B.
4) Complement of a Set
If U is a universal set and A ⊂ U, then complement of A is defined by the set of all elements which belong to U and do not belong to A. It is denoted by A̅ or Ac.
Example: If U = {1, 2, 3, 4, 5} and A = {1, 3, 4}, then A̅ = {2, 5}.
5) Symmetric Difference
The symmetric difference of any two sets A and B is the union of the differences (A – B) and (B – A).
8. Set Identities
1. Idempotent Laws
2. Commutative Laws
3. Domination Law
4. Absorption Law
5. Associative Law
6. Distributive Law
7. Complementation Law
8. De Morgan’s Laws
Proof of De Morgan’s First Law
= {x : x ∉ (A ∪ B)}
= {x : x ∉ A and x ∉ B}
= {x : x ∈ A̅ and x ∈ B̅}
= A̅ ∩ B̅
Proof of De Morgan’s Second Law
= {x : x ∉ (A ∩ B)}
= {x : x ∉ A or x ∉ B}
= {x : x ∈ A̅ or x ∈ B̅}
= A̅ ∪ B̅
9. Exercise 1.2
10. For any sets A, B and C, prove that:
a. A – B = A – (A ∩ B) = A ∩ overline(A ∩ B)
A ∩ overline(A ∩ B)
= {x : x ∈ A and x ∉ (A ∩ B)}
= {x : x ∈ A and (x ∉ A or x ∉ B)}
= {x : (x ∈ A and x ∉ A) or (x ∈ A and x ∉ B)}
= ∅ ∪ (A ∩ B̅)
= A ∩ B̅
= A – B
Proved.
b. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
= {x : x ∈ A or x ∈ (B ∩ C)}
= {x : x ∈ A or (x ∈ B and x ∈ C)}
= {x : (x ∈ A or x ∈ B) and (x ∈ A or x ∈ C)}
= {x : x ∈ (A ∪ B) and x ∈ (A ∪ C)}
= (A ∪ B) ∩ (A ∪ C)
Proved.
c. A – (B ∪ C) = (A – B) ∩ (A – C)
= {x : x ∈ A and x ∉ (B ∪ C)}
= {x : x ∈ A and (x ∉ B and x ∉ C)}
= {x : (x ∈ A and x ∉ B) and (x ∈ A and x ∉ C)}
= {x : x ∈ (A – B) and x ∈ (A – C)}
= (A – B) ∩ (A – C)
Proved.
d. A – (B – C) = (A – B) ∪ (A ∩ C)
= {x : x ∈ A and x ∉ (B – C)}
= {x : x ∈ A and x ∈ overline(B ∩ C̅)}
= {x : x ∈ A and x ∈ (B̅ ∪ C)}
= {x : (x ∈ A and x ∉ B) or (x ∈ A and x ∈ C)}
= {x : x ∈ (A – B) or x ∈ (A ∩ C)}
= (A – B) ∪ (A ∩ C)
Proved.
e. A ∩ (B – C) = (A ∩ B) – (A ∩ C)
= {x : x ∈ A and x ∈ (B ∩ C̅)}
= {x : x ∈ A and (x ∈ B and x ∉ C)}
= {x : (x ∈ A and x ∈ B) and (x ∈ A and x ∉ C)}
= {x : x ∈ (A ∩ B) and x ∉ (A ∩ C)}
= (A ∩ B) – (A ∩ C)
Proved.
f. A △ B = (A ∪ B) – (A ∩ B)
= {x : x ∈ (A – B) or x ∈ (B – A)}
= {x : (x ∈ A and x ∉ B) or (x ∈ B and x ∉ A)}
= {x : x ∈ (A ∪ B) and x ∉ (A ∩ B)}
= (A ∪ B) – (A ∩ B)
Proved.
Typed from the supplied handwritten “Logic and Set” PDF and formatted for easier reading on a web page.
Discussion
Share a helpful question, idea, or explanation with other students.