📐
Discrete Mathematics, Made by: Haneen Metwally
Created @October 8, 2023 11:11 PM
Class Maths for C.S
Type Lecture
Materials chapter-Logic1.pdf
Reviewed
Chapter 1: Logic
Propositions:
a statement (i.e., a declarative sentence) with some definite meaning (not vague or ambiguous)
having a truth value that’s either true (T) or false (F)
Examples: Not examples:
1. 1 + 2 = 3. (T) / equation. 1. x + 2 = 5 (declaration about semantic
tokens of non-constant value)
2. Beijing is the capital of China. (T) / natural language. 2. Who’s there? (interrogative, question)
Truth table:
An operator or connective combines one or more operand expressions into a larger expression. (e.g., “+” in numeric expressions.)
The number of rows in this table = n(power)2 {where n is the number of variables}
For the number of (T/F) we firstly divide number of rows by 2 to indicate after how many blocks the sign changes; then continue
dividing by 2 for the next column.
The Boolean domain is the set {T, F}. Either of its elements is called a Boolean value.
An n-operand truth table is a table that assigns a Boolean value to the set of all Boolean n-tuples: (number of variables).
The Negation Operator (NOT):
📌 The unary operator (meaning it only accepts one value), same as the logic gate; converts the sign (T/F) into the opposite value.
Symbol: ¬
The truth table for NOT:
Discrete Mathematics, Made by: Haneen Metwally 1
, p ¬p
T F
F T
The conjunction operator (AND):
📌 The binary operator (meaning it accepts two input variables), which is also similar to the logic gate as it only accepts when both
are true. Symbol: ∧
The truth table for AND:
p q p ∧q
T T T
T F F
F T F
F T F
The disjunction operator (OR):
📌 The binary operator (also called inclusive or because it includes the possibility of both being true) is also like the logic gate
where if one is true, the statement is also true.
Symbol: ∨
Truth table for inclusive OR:
p q p ∨q
T T T
T F T
F T T
F F F
The exclusive (OR) operator:
📌 The OR operator where the statement will be false if both are true.
Symbol: ⊕
Truth table for exclusive OR:
p q p ⊕q
T T F
T F T
F F T
F T F
The Implication Operator:
💡 The conditional statement p → q states that p implies q. (in other words: P is sufficient for Q \ Q is necessary for P/q whereas
p/p only if q). ⇒
P Hypothesis/Premise/Antecedent
Q ⇒ Conclusion/Consequence
Implication Truth Table and its inverse/converse/contrapositive:
Discrete Mathematics, Made by: Haneen Metwally 2
, Inverse: is the negation of p and q in (p→ q). / Converse is switching sides meaning (q→ p). / Contrapositive: is the negation
of both sides of the converse.
P ¬P Q ¬Q p→q q→p ¬ p →¬ q ¬ q → ¬
T F T F T T T T
T F F T F T T F
F T T F T F F T
F T F T T T T T
Equivalency:
The p → q is equivalent to the ¬q → ¬p (contrapositive).
The q → p is equivalent to the ¬ p →¬ q (inverse).
The Biconditional Operator:
💡 This operator means if and only if (iff) meaning that both conditions must be the same for the statement to be true (p is
necessary and sufficient for q). Symbol: p ↔ q
Truth table for biconditional The biconditional is the exact opposite for the XOR.
operator:
p q p↔q
T T T
T F F
F T F
F F T
Compound proposition:
The truth table for the compound proposition :(p ∨ ¬ q) → q.
p q ¬q p ∨¬ q (p ∨ ¬ q) → q
T T F T T
T F T T F
F T F F T
F F T T F
Logic and Bit Operations:
A bit is a binary (base 2) digit: 0 or 1.
Bits may be used to represent truth values, T= 1, F= 0.
E.g. 01 1011 0110
OR 11 0001 1101
11 1011 1111
Precedence Of Logical Operators:
1. Brackets
2. Negation
3. AND
4. OR
Discrete Mathematics, Made by: Haneen Metwally 3
, 5. Implication
6. Biconditional
7. XOR
Types Of Propositions Based on Truth Values:
Tautology: is a compound proposition that is always true no matter what the truth values of its atomic propositions are!
Contradiction: is a compound proposition that is always false no matter what!
Contingency: a compound proposition which contains both the values: true and false.
Logical Equivalence/Equivalence Laws:
Formally, two propositions p and q are said to be logically equivalent if compound proposition p ≅ q, or p↔ q is a Tautology.
1. De-Morgan Rule: ¬ ( p ٧ q) = ¬ p ٨ ¬ q / where the negation enters the whole bracket and also turns the AND into OR and vice versa.
2. Identity: p ∨ T is equivalent to T p ∧ T is equivalent to p
T T T T T T
F T T F T F
3. Domination: p ∨ F is equivalent to p p ∧ F is equivalent to F
T F T F F
T F F F
F F
F
4. Double Negation: ¬ ¬ p is equivalent to p.
5. p ∨ ¬ p is equivalent to T p ∧ ¬ p is equivalent to F
T F T T F F
F T T F T F
6. Commutative (Com.):2 +3 + 5 is the same as 3 + 5 + 2 as long as the operation between them is the same: p ∨ q ≅ q ∨ p.
7. Associative (Assoc.): 2 + (3+5) is the same as 3+ (5+2) as long as the operation between them in the same: p ∧ (q ∧ r) ≅ q ∧ (r ∧
p).
8. Distributive (dist.): 2 * (x + 3) = 2x + 6 is the same as: p∨ (r ∧q) ≅ (p ∧ r) ٧ (p ∧ q).
9. Implication: p⇒q≅¬p∨q 12. p ↔ q ≅ ¬ p⊕ q
10. Absorption: p ∨ (p ∧ q) ≅ p 13. p ⊕ q ≅ (p ∨ q) ∧ ¬ (p ∧ q).
11. p ⊕ q ≅ (p ∧ ¬q) ∨ (¬p ∧ q)
Predicate Logic (Propositional Functions):
The statement x > 3 which is equivalent to P(x), consists of two parts: a subject/variable x, the condition >3 is called a predicate.
Universe of discourse or domain of discourse: it is the domain of subjects or variables for a propositional function.
When x is assigned a value, it will become a proposition and we could assign it a truth value either T or F.
Quantifiers:
📌 Expresses the extent to which the predicate is true or false over a range of elements.
Types of quantifiers:
Universal ( ∀) Existential ( ∃) Uniqueness ( ∃!)
Discrete Mathematics, Made by: Haneen Metwally 4
, ∀xP(x) for all values of x in the ∃xP(x)There exists an element in the domain There exists a unique x where P(x) is true.
domain such that P(x)
For all x There exists an x.
Examples: Every student in this class has studied Calculus, x is subject (student) and the predicates as follows:
P(x): has studied Calculus / S(x): is in this class.
This statement can be expressed as: ∀(S(x)→ P(x)) / we used the universal quantifier due to the use of “For every student”.
calculus معني انه في الفصل انه درس, S implies P.
Translate from natural language: ∀x(C(x) ٧ ∃y(C(y) ٨ F(x, y) ) )
Where C(x) is “x has a computer”, F (x, y) is “x and y are friends”, and both x and y are the set of students in your school.
Every student (x) has a computer or, there exists a student (y) who owns a computer and is friends with (x) .
Answer: Every student in our school has a computer or has a friend who owns a computer..
Negation of quantifier in natural language: P(x) is the statement “x has taken a class in calculus” and the domain consists of students
in your class:
∀xP(x): Every student in my class has taken a class in calculus
True negation: There exists a student/there is at least one student in my class who hasn’t taken a class in calculus. (at least one false
∀
makes xP(x) false)
False negation: All students in my class haven’t taken a class in calculus.
This statement can be expressed as: ¬ ∀xP(x) ≅ ∃x¬P(x)/ ¬∃xP(x) ≅ ∀x¬P(x)
Precedence Of Quantifiers:
Quantifiers have higher precedence than all logical operators.
Logical Equivalence Among Quantifiers:
∀x(P(x) ٨ Q(x)) ≅ ∀xP(x) ٨ ∀xQ(x)
1. if we assume that all values for first predict are true then, due to the AND operator between P(x) and Q(x) they also must be true for
all values in the domain.
2. For second predicate, since all values in the domain for P(x) are true, that means for all x P(x) is also true AND same thing for Q(x).
3. That makes both values an equivalent tautology.
Free and Bound Variables:
An expression like P(x) is said to have a free variable x (meaning, x is undefined).
∀x P (x, y, z) has only one bound variable: x, and two free variables: y and z.
Chapter 2: Basic Structures:
Sets:
Definition: a set is a structure that contains un-ordered elements or members.
S = {a, b, c} is the set called S whose elements are a, b, and c where we can say that a ∈ (belongs to) S and x! ∈ S.
{x | P(x)} is the set of all x such that P(x) is true, | = ⇒ whereas.
Example: S = {1, 2, 3, 4} can be also expressed as: = {x | x is an integer where x > 0 and x < 5} OR {x ∈ Z | x > 0 and x > 5}
where Z (set of integer numbers).
You can repeat elements in a set but that doesn’t necessarily mean anything as elements are DISTINCT, (multiple listings make
no difference!).
Definition of Set Equality: if two sets contain exactly the same elements.
An empty set or NULL set is expressed as follows: Φ = { }.
Discrete Mathematics, Made by: Haneen Metwally 5
, Open intervals are represented by ( ), while closed intervals are represented by [ ].
Infinite Sets:
N = {0, 1, 2…} the set of Natural numbers. Q = {p/q | p,q ∈ Z, and q ≠ 0}
Z = {…, –2, –1, 0, 1, 2…} the set of integers. The set of Rational numbers. {p/q | p, q ∈ Z, and q ≠ 0}
Z+ = {1, 2, 3…} the set of positive integers. R = the set of “Real” numbers including decimals.
SUBSET: Set Forms:
⊆
S T (S is a subset of T) means that every element of S 1. Tabular form: {1, 2, 3}
is also an element of T and gives the possibility of equal
2. Descriptive form: S is a set of positive integer numbers more
(both have same elements).
than 5 and less than 10 = {6, 7, 8, 9}
∀x (x ∈ S → x ∈ T) 3. Builder form: {x| x ∈ Z+ and 5<x<10}
Either S = T or S is a small part in T.
4. Venn diagram:
For every set S: 1. Φ ∈S ⊆S
2. S
Proper subset: cancels the equal option, S ⊂ T, as:
{1, 2} ⊂ {1, 2, 3}
SUPERSET: T ⊇ S (T is a superset of S) means that T is a
big set that contains every element of set S and more or
may be equal to it.
Properties Of Sets:
Cardinality: Power Of Sets:
Represents the number of elements in a set. All the possible subsets of a set including the option of an
empty set: Φ and the option of the set itself.
S = {Φ, {}, {Φ} } then |S| = 2
S = {1, 2, 4} then P(S) = {Φ, {1}, {2}, {4}, {1,2}, {1,4},
where Φ and an empty set are the same element with different
{2,4}, {1,2,4} }
representation and {Φ} is a subset considered one element which
also contains 1 element. P(S) = 2 to the power of n / n = number of elements.
Cartesian Products of Sets:
For sets A and B, their Cartesian product denoted by A x B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B.
A = {1, 3, 5} / B = {2, 4}
A x B = {(1,2), (1,4), (3,2), (3,4), (5,2), (5,4)}
AxB≠BxA
Set Operators:
Set A = {1, 2, 3} Union operator: Intersection operator:
Set B = {1, 3, 5}
A ∪ B means all the elements in both sets A ∩ B means the elements common
without repetition. between both sets.
Difference operator: A ∪ B = {1, 2, 3, 5} A ∩ B = {1, 3}
A - B means all the elements that are in A A ∪ B = {x| x ∈ A ٧ x∈ B} A ∩ B = {x| x ∈ A ٨ x ∈ B}
but not in B while, B - A means the
elements in B which aren’t in A, where: A Disjoint sets: Set’s complement:
- B = {x| x ∈ A ٨ x ∉ B} We say two sets A and B are disjoined A` or A complement contains all the
A - B = {2} when: elements to complete A to be a universal
A∩B=Φ set.
B - A = {5}
Discrete Mathematics, Made by: Haneen Metwally 6
Discrete Mathematics, Made by: Haneen Metwally
Created @October 8, 2023 11:11 PM
Class Maths for C.S
Type Lecture
Materials chapter-Logic1.pdf
Reviewed
Chapter 1: Logic
Propositions:
a statement (i.e., a declarative sentence) with some definite meaning (not vague or ambiguous)
having a truth value that’s either true (T) or false (F)
Examples: Not examples:
1. 1 + 2 = 3. (T) / equation. 1. x + 2 = 5 (declaration about semantic
tokens of non-constant value)
2. Beijing is the capital of China. (T) / natural language. 2. Who’s there? (interrogative, question)
Truth table:
An operator or connective combines one or more operand expressions into a larger expression. (e.g., “+” in numeric expressions.)
The number of rows in this table = n(power)2 {where n is the number of variables}
For the number of (T/F) we firstly divide number of rows by 2 to indicate after how many blocks the sign changes; then continue
dividing by 2 for the next column.
The Boolean domain is the set {T, F}. Either of its elements is called a Boolean value.
An n-operand truth table is a table that assigns a Boolean value to the set of all Boolean n-tuples: (number of variables).
The Negation Operator (NOT):
📌 The unary operator (meaning it only accepts one value), same as the logic gate; converts the sign (T/F) into the opposite value.
Symbol: ¬
The truth table for NOT:
Discrete Mathematics, Made by: Haneen Metwally 1
, p ¬p
T F
F T
The conjunction operator (AND):
📌 The binary operator (meaning it accepts two input variables), which is also similar to the logic gate as it only accepts when both
are true. Symbol: ∧
The truth table for AND:
p q p ∧q
T T T
T F F
F T F
F T F
The disjunction operator (OR):
📌 The binary operator (also called inclusive or because it includes the possibility of both being true) is also like the logic gate
where if one is true, the statement is also true.
Symbol: ∨
Truth table for inclusive OR:
p q p ∨q
T T T
T F T
F T T
F F F
The exclusive (OR) operator:
📌 The OR operator where the statement will be false if both are true.
Symbol: ⊕
Truth table for exclusive OR:
p q p ⊕q
T T F
T F T
F F T
F T F
The Implication Operator:
💡 The conditional statement p → q states that p implies q. (in other words: P is sufficient for Q \ Q is necessary for P/q whereas
p/p only if q). ⇒
P Hypothesis/Premise/Antecedent
Q ⇒ Conclusion/Consequence
Implication Truth Table and its inverse/converse/contrapositive:
Discrete Mathematics, Made by: Haneen Metwally 2
, Inverse: is the negation of p and q in (p→ q). / Converse is switching sides meaning (q→ p). / Contrapositive: is the negation
of both sides of the converse.
P ¬P Q ¬Q p→q q→p ¬ p →¬ q ¬ q → ¬
T F T F T T T T
T F F T F T T F
F T T F T F F T
F T F T T T T T
Equivalency:
The p → q is equivalent to the ¬q → ¬p (contrapositive).
The q → p is equivalent to the ¬ p →¬ q (inverse).
The Biconditional Operator:
💡 This operator means if and only if (iff) meaning that both conditions must be the same for the statement to be true (p is
necessary and sufficient for q). Symbol: p ↔ q
Truth table for biconditional The biconditional is the exact opposite for the XOR.
operator:
p q p↔q
T T T
T F F
F T F
F F T
Compound proposition:
The truth table for the compound proposition :(p ∨ ¬ q) → q.
p q ¬q p ∨¬ q (p ∨ ¬ q) → q
T T F T T
T F T T F
F T F F T
F F T T F
Logic and Bit Operations:
A bit is a binary (base 2) digit: 0 or 1.
Bits may be used to represent truth values, T= 1, F= 0.
E.g. 01 1011 0110
OR 11 0001 1101
11 1011 1111
Precedence Of Logical Operators:
1. Brackets
2. Negation
3. AND
4. OR
Discrete Mathematics, Made by: Haneen Metwally 3
, 5. Implication
6. Biconditional
7. XOR
Types Of Propositions Based on Truth Values:
Tautology: is a compound proposition that is always true no matter what the truth values of its atomic propositions are!
Contradiction: is a compound proposition that is always false no matter what!
Contingency: a compound proposition which contains both the values: true and false.
Logical Equivalence/Equivalence Laws:
Formally, two propositions p and q are said to be logically equivalent if compound proposition p ≅ q, or p↔ q is a Tautology.
1. De-Morgan Rule: ¬ ( p ٧ q) = ¬ p ٨ ¬ q / where the negation enters the whole bracket and also turns the AND into OR and vice versa.
2. Identity: p ∨ T is equivalent to T p ∧ T is equivalent to p
T T T T T T
F T T F T F
3. Domination: p ∨ F is equivalent to p p ∧ F is equivalent to F
T F T F F
T F F F
F F
F
4. Double Negation: ¬ ¬ p is equivalent to p.
5. p ∨ ¬ p is equivalent to T p ∧ ¬ p is equivalent to F
T F T T F F
F T T F T F
6. Commutative (Com.):2 +3 + 5 is the same as 3 + 5 + 2 as long as the operation between them is the same: p ∨ q ≅ q ∨ p.
7. Associative (Assoc.): 2 + (3+5) is the same as 3+ (5+2) as long as the operation between them in the same: p ∧ (q ∧ r) ≅ q ∧ (r ∧
p).
8. Distributive (dist.): 2 * (x + 3) = 2x + 6 is the same as: p∨ (r ∧q) ≅ (p ∧ r) ٧ (p ∧ q).
9. Implication: p⇒q≅¬p∨q 12. p ↔ q ≅ ¬ p⊕ q
10. Absorption: p ∨ (p ∧ q) ≅ p 13. p ⊕ q ≅ (p ∨ q) ∧ ¬ (p ∧ q).
11. p ⊕ q ≅ (p ∧ ¬q) ∨ (¬p ∧ q)
Predicate Logic (Propositional Functions):
The statement x > 3 which is equivalent to P(x), consists of two parts: a subject/variable x, the condition >3 is called a predicate.
Universe of discourse or domain of discourse: it is the domain of subjects or variables for a propositional function.
When x is assigned a value, it will become a proposition and we could assign it a truth value either T or F.
Quantifiers:
📌 Expresses the extent to which the predicate is true or false over a range of elements.
Types of quantifiers:
Universal ( ∀) Existential ( ∃) Uniqueness ( ∃!)
Discrete Mathematics, Made by: Haneen Metwally 4
, ∀xP(x) for all values of x in the ∃xP(x)There exists an element in the domain There exists a unique x where P(x) is true.
domain such that P(x)
For all x There exists an x.
Examples: Every student in this class has studied Calculus, x is subject (student) and the predicates as follows:
P(x): has studied Calculus / S(x): is in this class.
This statement can be expressed as: ∀(S(x)→ P(x)) / we used the universal quantifier due to the use of “For every student”.
calculus معني انه في الفصل انه درس, S implies P.
Translate from natural language: ∀x(C(x) ٧ ∃y(C(y) ٨ F(x, y) ) )
Where C(x) is “x has a computer”, F (x, y) is “x and y are friends”, and both x and y are the set of students in your school.
Every student (x) has a computer or, there exists a student (y) who owns a computer and is friends with (x) .
Answer: Every student in our school has a computer or has a friend who owns a computer..
Negation of quantifier in natural language: P(x) is the statement “x has taken a class in calculus” and the domain consists of students
in your class:
∀xP(x): Every student in my class has taken a class in calculus
True negation: There exists a student/there is at least one student in my class who hasn’t taken a class in calculus. (at least one false
∀
makes xP(x) false)
False negation: All students in my class haven’t taken a class in calculus.
This statement can be expressed as: ¬ ∀xP(x) ≅ ∃x¬P(x)/ ¬∃xP(x) ≅ ∀x¬P(x)
Precedence Of Quantifiers:
Quantifiers have higher precedence than all logical operators.
Logical Equivalence Among Quantifiers:
∀x(P(x) ٨ Q(x)) ≅ ∀xP(x) ٨ ∀xQ(x)
1. if we assume that all values for first predict are true then, due to the AND operator between P(x) and Q(x) they also must be true for
all values in the domain.
2. For second predicate, since all values in the domain for P(x) are true, that means for all x P(x) is also true AND same thing for Q(x).
3. That makes both values an equivalent tautology.
Free and Bound Variables:
An expression like P(x) is said to have a free variable x (meaning, x is undefined).
∀x P (x, y, z) has only one bound variable: x, and two free variables: y and z.
Chapter 2: Basic Structures:
Sets:
Definition: a set is a structure that contains un-ordered elements or members.
S = {a, b, c} is the set called S whose elements are a, b, and c where we can say that a ∈ (belongs to) S and x! ∈ S.
{x | P(x)} is the set of all x such that P(x) is true, | = ⇒ whereas.
Example: S = {1, 2, 3, 4} can be also expressed as: = {x | x is an integer where x > 0 and x < 5} OR {x ∈ Z | x > 0 and x > 5}
where Z (set of integer numbers).
You can repeat elements in a set but that doesn’t necessarily mean anything as elements are DISTINCT, (multiple listings make
no difference!).
Definition of Set Equality: if two sets contain exactly the same elements.
An empty set or NULL set is expressed as follows: Φ = { }.
Discrete Mathematics, Made by: Haneen Metwally 5
, Open intervals are represented by ( ), while closed intervals are represented by [ ].
Infinite Sets:
N = {0, 1, 2…} the set of Natural numbers. Q = {p/q | p,q ∈ Z, and q ≠ 0}
Z = {…, –2, –1, 0, 1, 2…} the set of integers. The set of Rational numbers. {p/q | p, q ∈ Z, and q ≠ 0}
Z+ = {1, 2, 3…} the set of positive integers. R = the set of “Real” numbers including decimals.
SUBSET: Set Forms:
⊆
S T (S is a subset of T) means that every element of S 1. Tabular form: {1, 2, 3}
is also an element of T and gives the possibility of equal
2. Descriptive form: S is a set of positive integer numbers more
(both have same elements).
than 5 and less than 10 = {6, 7, 8, 9}
∀x (x ∈ S → x ∈ T) 3. Builder form: {x| x ∈ Z+ and 5<x<10}
Either S = T or S is a small part in T.
4. Venn diagram:
For every set S: 1. Φ ∈S ⊆S
2. S
Proper subset: cancels the equal option, S ⊂ T, as:
{1, 2} ⊂ {1, 2, 3}
SUPERSET: T ⊇ S (T is a superset of S) means that T is a
big set that contains every element of set S and more or
may be equal to it.
Properties Of Sets:
Cardinality: Power Of Sets:
Represents the number of elements in a set. All the possible subsets of a set including the option of an
empty set: Φ and the option of the set itself.
S = {Φ, {}, {Φ} } then |S| = 2
S = {1, 2, 4} then P(S) = {Φ, {1}, {2}, {4}, {1,2}, {1,4},
where Φ and an empty set are the same element with different
{2,4}, {1,2,4} }
representation and {Φ} is a subset considered one element which
also contains 1 element. P(S) = 2 to the power of n / n = number of elements.
Cartesian Products of Sets:
For sets A and B, their Cartesian product denoted by A x B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B.
A = {1, 3, 5} / B = {2, 4}
A x B = {(1,2), (1,4), (3,2), (3,4), (5,2), (5,4)}
AxB≠BxA
Set Operators:
Set A = {1, 2, 3} Union operator: Intersection operator:
Set B = {1, 3, 5}
A ∪ B means all the elements in both sets A ∩ B means the elements common
without repetition. between both sets.
Difference operator: A ∪ B = {1, 2, 3, 5} A ∩ B = {1, 3}
A - B means all the elements that are in A A ∪ B = {x| x ∈ A ٧ x∈ B} A ∩ B = {x| x ∈ A ٨ x ∈ B}
but not in B while, B - A means the
elements in B which aren’t in A, where: A Disjoint sets: Set’s complement:
- B = {x| x ∈ A ٨ x ∉ B} We say two sets A and B are disjoined A` or A complement contains all the
A - B = {2} when: elements to complete A to be a universal
A∩B=Φ set.
B - A = {5}
Discrete Mathematics, Made by: Haneen Metwally 6
