Discrete Math Chapter 1 Review Set

Proposition

A statement that has a truth value and is either true or false but not both

Truth Value

The value true or false assigned to a proposition

Negation (¬p)

¬p is true when p is false and false when p is true which means not p

Conjunction (p ∧ q)

(p ∧ q) is true if and only if both p and q are true which means p and q

Disjunction (p ∨ q)

(p ∨ q) is true if at least one of p or q is true which means p or q or both

Exclusive Or (p ⊕ q)

(p ⊕ q) is true if exactly one of p or q is true which means p or q but not both

Conditional (p → q)

(p → q) is false only when p is true and q is false which means if p then q

Biconditional (p ↔ q)

(p ↔ q) is true if p and q have the same truth value which means p if and only if q

Compound Proposition

A proposition formed by combining propositions using logical connectives

Logical Connective

A symbol used to connect propositions such as not and and or implies and if and only if

Truth Table

A table that shows the truth values of a compound proposition for all cases

Propositionally Equivalent (p ≡ q)

p ≡ q means p and q have identical truth tables which means they are logically the same

Tautology

A compound proposition that is true for all possible truth values

Contradiction

A compound proposition that is false for all possible truth values

Contingency

A proposition that is true in some cases and false in others

De Morgan’s Law not and

¬(p ∧ q) ≡ ¬p ∨ ¬q which means the negation of and becomes or with negations

De Morgan’s Law not or

¬(p ∨ q) ≡ ¬p ∧ ¬q which means the negation of or becomes and with negations

Double Negation Law

¬(¬p) ≡ p which means negating a statement twice gives the original statement

Identity Laws

p ∧ T ≡ p and p ∨ F ≡ p which means combining with true or false does not change the statement

Domination Laws

p ∨ T ≡ T and p ∧ F ≡ F which means true dominates or and false dominates and

Idempotent Laws

p ∨ p ≡ p and p ∧ p ≡ p which means repeating a statement changes nothing

Commutative Laws

p ∨ q ≡ q ∨ p and p ∧ q ≡ q ∧ p which means order does not matter

Associative Laws

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) which means grouping does not matter

Distributive Laws

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) which means or distributes over and

Absorption Laws

p ∨ (p ∧ q) ≡ p which means extra information does not change the result

Argument

A set of premises followed by a conclusion

Premise

A statement assumed to be true

Conclusion

A statement logically derived from the premises

Valid Argument

An argument where the conclusion must be true if all premises are true

Modus Ponens

p and p implies q therefore q which means if p is true then q is true

Modus Tollens

not q and p implies q therefore not p which means if q is false then p is false

Hypothetical Syllogism

p implies q and q implies r therefore p implies r which means chaining conditionals

Disjunctive Syllogism

p or q and not p therefore q which means if one option is false the other must be true

Addition

p therefore p or q which means adding another option

Simplification

p and q therefore p which means removing part of a conjunction

Conjunction

p and q therefore p and q which means combining statements

Resolution

p or q and not p or r therefore q or r which means eliminating a variable

Predicate

A statement with variables that becomes true or false when values are assigned

Domain

The set of all possible values a variable can take

Universal Quantifier (∀x)

∀x P(x) which means P of x is true for every element in the domain

Existential Quantifier (∃x)

∃x P(x) which means P of x is true for at least one element in the domain

Bound Variable

A variable that is controlled by a quantifier

Free Variable

A variable that is not controlled by any quantifier

Negation of Universal Quantifier

not for all x P of x is equivalent to there exists an x such that not P of x

Negation of Existential Quantifier

not there exists an x P of x is equivalent to for all x not P of x

Universal Instantiation

From for all x P of x infer P of a which means applying a universal statement to a specific element

Existential Instantiation

From there exists an x P of x infer P of a for some a which means choosing an example that makes the statement true