Back MAT 243 — Discrete Math Structures — The Complete Galaxy Guide Math
Download Open
Show description 2,329 chars · Math

MAT 243 — Discrete Math Structures — The Complete Galaxy Guide

MAT 243 — Discrete Math Structures — The Complete Galaxy Guide

↑

ASU · MAT 243 · Spring 2026

DISCRETE MATH STRUCTURES

The complete course — every concept, every formula, every proof technique — condensed into one galaxy-class reference.

✦ Navigation

01 Propositional Logic
02 Logical Equivalences
03 Predicates & Quantifiers
04 Rules of Inference
05 Proof Techniques
06 Sets
07 Functions
08 Sequences & Summation
09 Growth of Functions (Big-O)
10 Divisibility & Modular Arithmetic
11 Number Systems & Representations
12 Primes & GCD
13 Mathematical Induction
14 Structural Induction
15 Recurrence Relations
16 Combinatorics & Counting
17 Inclusion-Exclusion
18 Relations

01

Propositional Logic

Propositions

A proposition is a declarative sentence that is either true (T) or false (F), but not both. Questions, commands, and opinions are NOT propositions.

Examples

Proposition: "2 + 3 = 5" → T
Proposition: "The moon is made of cheese" → F
NOT a proposition: "What time is it?" / "Close the door."

Logical Operators (Connectives)

Name
Symbol
Read As
True When

Negation
¬p
"not p"
p is false

Conjunction
p ∧ q
"p and q"
both true

Disjunction
p ∨ q
"p or q"
at least one true

Exclusive Or
p ⊕ q
"p xor q"
exactly one true

Conditional
p → q
"if p then q"
¬p or q (false only when p=T, q=F)

Biconditional
p ↔ q
"p if and only if q"
both same truth value

The Conditional (p → q) — Most Tested!

p
q
p → q

T
T
T

T
F
F

F
T
T

F
F
T

Key Insight

p → q is only false when the hypothesis (p) is true and the conclusion (q) is false. A false hypothesis makes the whole conditional vacuously true.

Variations of Conditionals

Given the conditional p → q:

Name
Form
Equivalent To

Converse
q → p
NOT equivalent to p → q

Inverse
¬p → ¬q
equivalent to converse

Contrapositive
¬q → ¬p
equivalent to p → q

Remember

The contrapositive is always logically equivalent to the original. The converse and inverse are equivalent to each other but NOT to the original.

"Only If" Statements

"p only if q" means p → q (NOT q → p!).

Think of it as: p can be true ONLY IF q is also true. If q is false, p must be false.

Example

"You pass only if you study" = "If you pass, then you studied" = pass → studied

Tautologies, Contradictions & Contingencies

Definitions

Tautology: Always true for all truth value assignments.…