Logo
BrainRecally Memory Master
Mathematics 20 flashcards ~10 min

Discrete Mathematics and Logic

Twenty flashcards covering discrete mathematics foundations. Includes set operations, propositional logic and truth tables, logical equivalences, permutations and combinations, basic graph theory terminology, and proof by induction. Suited to computer science...

Study this deck View all cards

About this deck

Twenty flashcards covering discrete mathematics foundations. Includes set operations, propositional logic and truth tables, logical equivalences, permutations and combinations, basic graph theory terminology, and proof by induction. Suited to computer science coursework, A-Level Further Maths and discrete maths modules.

Ready to test yourself?

Flip through all 20 cards in interactive study mode.

Launch study mode

All flashcards

Click any question to reveal the answer.

A set is an unordered collection of distinct elements. βˆ… βˆ… represents the empty set, containing no elements.
Union 𝐴 βˆͺ 𝐡 AβˆͺB: all elements in 𝐴 A or 𝐡 B (or both). Intersection 𝐴 ∩ 𝐡 A∩B: only elements in both 𝐴 A and 𝐡 B.
𝐴 β€² A β€² (or 𝐴 𝑐 A c ) contains all elements in the universal set that are not in 𝐴 A.
𝐴 A is a subset of 𝐡 B β€” every element of 𝐴 A is also an element of 𝐡 B. If additionally 𝐴 β‰  𝐡 A ξ€  =B, it's a proper subset ( 𝐴 βŠ‚ 𝐡 AβŠ‚B).
∣A∣, the number of distinct elements in a finite set 𝐴 A.
( 𝐴 βˆͺ 𝐡 ) β€² = 𝐴 β€² ∩ 𝐡 β€² (AβˆͺB) β€² =A β€² ∩B β€² and ( 𝐴 ∩ 𝐡 ) β€² = 𝐴 β€² βˆͺ 𝐡 β€² (A∩B) β€² =A β€² βˆͺB β€² .
A statement that is definitively either true or false, but not both β€” the basic unit of propositional logic.
𝑝 ∧ π‘ž p∧q is true only when both 𝑝 p and π‘ž q are true; false in all other cases.
𝑝 ∨ π‘ž p∨q is true when at least one of 𝑝 p or π‘ž q is true; false only when both are false.
𝑝 βŠ• π‘ž pβŠ•q is true when exactly one of 𝑝 , π‘ž p,q is true, but false when both are true β€” unlike inclusive OR.
The conditional 𝑝 β†’ π‘ž pβ†’q ("if p then q") is false only when 𝑝 p is true and π‘ž q is false. The converse is π‘ž β†’ 𝑝 qβ†’p, not logically equivalent to the original.
𝑝 ↔ π‘ž p↔q ("p if and only if q"), true when 𝑝 p and π‘ž q have the same truth value (both true or both false).
Β¬ ( 𝑝 ∧ π‘ž ) ≑ Β¬ 𝑝 ∨ Β¬ π‘ž Β¬(p∧q)≑¬p∨¬q and Β¬ ( 𝑝 ∨ π‘ž ) ≑ Β¬ 𝑝 ∧ Β¬ π‘ž Β¬(p∨q)≑¬p∧¬q.
A permutation counts arrangements where order matters. A combination counts selections where order does not matter.
𝑃 ( 𝑛 , π‘Ÿ ) = 𝑛 ! ( 𝑛 βˆ’ π‘Ÿ ) ! P(n,r)= (nβˆ’r)! n! ​ .
𝐢 ( 𝑛 , π‘Ÿ ) = ( 𝑛 π‘Ÿ ) = 𝑛 ! π‘Ÿ ! ( 𝑛 βˆ’ π‘Ÿ ) ! C(n,r)=( r n ​ )= r!(nβˆ’r)! n! ​ .
If one task can be done in π‘š m ways and a second independent task in 𝑛 n ways, both together can be done in π‘š Γ— 𝑛 mΓ—n ways.
A structure consisting of vertices (nodes) connected by edges (links), used to model relationships and networks β€” not related to coordinate graphs.
The number of edges incident to (connected to) that vertex.
Base case: prove the statement holds for the first value (e.g. 𝑛 = 1 n=1). Inductive step: assume it holds for 𝑛 = π‘˜ n=k, then prove it holds for 𝑛 = π‘˜ + 1 n=k+1.