Back MAT 243 — Discrete Mathematical Structures Math
Download Open
Show description 2,401 chars · Math

MAT 243 — Discrete Mathematical Structures

MAT 243 — Discrete Mathematical Structures

MAT 243

Logic
Proofs
Sets
Functions
Big-O
Number Theory
Induction
Counting
Graphs
Formulas

ASU · Discrete Mathematical Structures

DISCRETEMATHSTRUCTURES

An interactive reference covering logic, proofs, sets, functions, number theory, induction, combinatorics, and graph theory — every formula, concept, and technique you need.

Propositional Logic
Proof Techniques
Set Theory
Big-O Notation
Modular Arithmetic
Mathematical Induction
Combinatorics
Graph Theory

01

PROPOSITIONAL LOGIC

Logical Operators

¬p

Negation

Reverses truth value. If p is T, ¬p is F.

T→F, F→T

p ∧ q

Conjunction (AND)

True only when BOTH p and q are true.

T∧T=T, all others=F

p ∨ q

Disjunction (OR)

True when AT LEAST ONE of p, q is true.

F∨F=F, all others=T

p ⊕ q

Exclusive OR

True when EXACTLY ONE of p, q is true — not both.

T⊕T=F, T⊕F=T, F⊕T=T, F⊕F=F

p → q

Implication (IF-THEN)

FALSE only when p is TRUE and q is FALSE. The most critical operator.

T→F=F, all others=T

p ↔ q

Biconditional (IFF)

True when p and q have IDENTICAL truth values.

T↔T=T, F↔F=T, else F

Conditional Relatives — Know All Four

Name
Form
Equivalent To
Key Fact

Implication
p → q
¬p ∨ q
Original statement

Converse
q → p
—
NOT equivalent to original

Inverse
¬p → ¬q
—
NOT equivalent; equivalent to converse

Contrapositive
¬q → ¬p
p → q
LOGICALLY EQUIVALENT to original ✓

Laws of Logic (Equivalences)

Identity Laws

p ∧ T ≡ pp ∨ F ≡ p

Domination Laws

p ∨ T ≡ Tp ∧ F ≡ F

Idempotent Laws

p ∨ p ≡ pp ∧ p ≡ p

Double Negation

¬(¬p) ≡ p

De Morgan's Laws ⚡

¬(p ∧ q) ≡ ¬p ∨ ¬q¬(p ∨ q) ≡ ¬p ∧ ¬q

Negate → flip AND/OR, distribute negation.

Distributive Laws

p ∧ (q ∨ r) ≡ (p∧q) ∨ (p∧r)p ∨ (q ∧ r) ≡ (p∨q) ∧ (p∨r)

Absorption Laws

p ∨ (p ∧ q) ≡ pp ∧ (p ∨ q) ≡ p

Negation Laws

p ∨ ¬p ≡ T (Tautology)p ∧ ¬p ≡ F (Contradiction)

Quantifiers — Predicate Logic

∀x

Universal Quantifier

"For ALL x in the domain, P(x) is true."To DISPROVE: find ONE counterexample.

Negation: ¬∀x P(x) ≡ ∃x ¬P(x)

∃x

Existential Quantifier

"There EXISTS at least one x such that P(x) is true."To DISPROVE: show P(x) is false for every x.

Negation: ¬∃x P(x) ≡ ∀x ¬P(x)

INTERACTIVE TRUTH TABLE

Select a compound proposition to generate its truth table:

p ∧ q
p ∨ q
p ⊕ q
p → q
p ↔ q
¬(p ∧ q)
¬p ∨ ¬q
¬q → ¬p
(p→q) ∧ (q→r)

02

METHODS OF PROOF

Rules of Inference

Rule
Given
Conclude
F…