Discrete math logic 1

Proposition

A statement with a truth value of true or false, not both

Truth Value

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)

true iff both p q are true which means p and q

Disjunction (p ∨ q)

(p ∨ q) is true if at least 1 of p or q is true ; p or q or both

Exclusive Or (p ⊕ q)

(p ⊕ q) true if exactly 1 p or q is true ; 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 with truth values of a compound proposition for all cases

Propositionally Equivalent (p ≡ q)

p ≡ q means p q have identical truth tables; 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’s true in some cases and false in others

De Morgan’s Law not and

¬(p ∧ q) ≡ ¬p ∨ ¬q which means 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 or 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 order doesnt 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 info doesnt change result (got absorbed)

Argument

A set of propositions (premises) followed by a conclusion

Premise

A statement assumed to be true

Conclusion

A statement logically derived from the premises

valid condition

iff premise imply conclusion; iff whenever all premise is true; conclusion true