[go: up one dir, main page]
Scribd
Upload
25 views7 pages

Descrete Mathematics For Computer Science

The notes cover core concepts of logic and sets, including logical operators, truth tables, and set operations such as union and intersection. It discusses applications of sets in computer science, including programming, databases, and combinatorics, highlighting the importance of permutations and combinations. Additionally, a combinatorics challenge is presented, focusing on generating codes with at least one digit, with a detailed breakdown of the calculations involved.

Uploaded by

kofi76419
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
25 views7 pages

Descrete Mathematics For Computer Science

The notes cover core concepts of logic and sets, including logical operators, truth tables, and set operations such as union and intersection. It discusses applications of sets in computer science, including programming, databases, and combinatorics, highlighting the importance of permutations and combinations. Additionally, a combinatorics challenge is presented, focusing on generating codes with at least one digit, with a detailed breakdown of the calculations involved.

Uploaded by

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

Discrete Math for Computer Science – Notes

1. Logic & Sets: Core Concepts

Statements can be true or false.

Example: “It is raining.” = True or False

Logical operators:

AND (∧)

OR (∨)

NOT (¬)

IMPLIES (→)

IFF (↔)

Truth tables show how compound statements behave.

Example: If A = True, B = False, then A AND B = False

Quantifiers:
∀x (for all x): universal quantifier

∃x (there exists x): existential quantifier

Sets: unordered collections of elements

Union: A ∪ B

Intersection: A ∩ B

Difference: A – B

Complement: NOT A

Subsets: A ⊆ B means every element of A is in B

Membership: x ∈ A means x is in set A

Set Identities (like logic laws):

A∪A=A

A∩A=A

A∩B=B∩A
De Morgan’s Laws:

NOT (A ∪ B) = NOT A ∩ NOT B

NOT (A ∩ B) = NOT A ∪ NOT B

2. Set Applications in CS

Programming:

Sets used in Python, Java, etc.

Efficient lookup: if x in my_set

Set operations: union, intersection, difference

Databases (SQL):

UNION, INTERSECT, EXCEPT = set operations


Example: “Find users in both tables” → INTERSECT

Graphs:

Use sets to track visited nodes in DFS/BFS

Search Filters:

Likes cats AND dogs → intersection

Likes cats OR dogs → union

Permissions/Roles:

Check if a permission is in a user’s permission set

3. Combinatorics

Rule of Product: Multiply choices across stages


Permutations (order matters):

nPr = n! / (n – r)!

Combinations (order doesn’t matter):

nCr = n! / (r!(n – r)!)

With repetition:

Ordered with repeats: n^r

Example: 6-character password using a–z

With repeats: 26^6 = 308,915,776

Without repeats: 26P6 = 165,765,600

CS Applications:

Estimate password strength

Calculate brute-force difficulty


Plan data storage needs

4. Combinatorics Challenge: Codes with At Least One Digit

Characters: 26 letters + 10 digits = 36 options

Total 8-character codes (with repeats): 36^8

Codes with only letters (no digits): 26^8

Valid codes (with at least one digit):

36^8 – 26^8

Detailed Breakdown (optional):

For each digit count k = 1 to 8:

Choose k positions for digits: C(8, k)

Fill digits: 10^k

Fill letters: 26^(8 – k)


Total for that k: C(8, k) * 10^k * 26^(8 – k)

Final formula:

Sum from k = 1 to 8 of:

C(8, k) * 10^k * 26^(8 – k)

You might also like