Discrete Mathematics Exam 1

p v q

This is a disjunction: p or q, or p and q. This is an inclusive or.

p ^ q

This is a conjunction: p and q

p ⊕ q

This is an exclusive or: either p or q

p → q

This is an implication. If p, then q

Converse conditional statements

q → p

Contrapositive conditional statements

¬q → ¬p (has the same truth values as p → q)

Inverse conditional statement

¬p → ¬q

p ↔ q

This is a biconditional statement, also known as bi-implications. It means p if and only if q. True if both p and q have the same truth values. Also written as "p is necessary and sufficient for q", "if p then q, and conversely", and "p iff q".

Precedence of logical operators in 1st to 5th

1. ¬ 2. ^ 3. v 4. → 5. ↔

Bit

This is a symbol with two possible values, specifically 0 (zero) and 1 (one). 1 represents the True value and 0 represents a False value.

De Morgan's law

When you distribute a "¬", then you flip the conjunction or disjunction sign that you are distributing to.

p ∧ T ≡ p
p ∨ F ≡ p

Identity laws

p ∨ T ≡ T
p ∧ F ≡ F

Domination laws

p ∨ p ≡ p
p ∧ p ≡ p

Idempotent laws

¬(¬p) ≡ p

Double negation law

p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p

Commutative laws

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

Associative laws

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

Distributive laws

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

De Morgan's laws (1st and 2nd)

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

Absorption laws

p ∨ ¬p ≡ T
p ∧ ¬p ≡ F

Negation laws

Predicate

refers to a property that the subject of the statement can have (e.g. is greater than 3)

Propositional function

P at x or P(x); the function

Functionally Complete

Every compound proposition is logically equivalent to a compound proposition composed of only these logical operators

Satisfiability

Occurs when there is an assignment of truth values to its variables that makes it true

Set N

natural numbers = {0,1,2,3...}

Set Z

integers = {....-3,-2,-1,0,1,2,3....}

Set Z+

positive integers = {1,2,3.....}

Set R

real numbers

set R+

positive real numbers

set C

complex numbers

Q

set of rational numbers

Injection

Every single input into A (the domain) has a single output in B (the codomain). However, all of the codomain values do not have to be matched up. "One-to-one"

Surjection

Every element of the codomain is matched up with a value from the domain.

Bijection

It is both injective and surjective. In other words, every one of the domain has a single single output and every one of the codomain values is matched up with a value of the domain.

א

The Hebrew symbol aleph. |S| is equal to the cardinality "aleph null"

Join of matrices

A v B

The meet of matrices

A ^ B

Boolean Product

^ between terms and then v between the two deciding terms

Boolean Powers of zero-one matrices

for all positive integers n with n >=5, the matrix becomes all ones