C959: Discrete Mathematics 1 latest updated version with 100% correct answers 2026-2027

proposition

a statement that is either true or false

truth value

a value indicating whether the proposition is actually true or false

truth table

A table used as a convenient method for organizing the truth values of statements

compound proposition

created by connecting individual propositions with logical operations

logical operation

combines propositions using a particular composition rule

conjunction (^, and)

- p ∧ q is true if both p is true and q is true

- p ∧ q is false if p is false, q is false, or both are false

disjunction (v, inclusive or)

- p ∨ q is true if either one of p or q is true, or

- p V q is true if both are true

exclusive or (⊕)

p and q evaluate to true when p is true and q is false or when q is true and p is false.

negation operation (¬)

reverses the truth value of a proposition

order of operations (no parenthesis)

negation, conjunction (and), disjunction (or)

conditional operation (→)

The proposition p → q is false if p is true and q is false; otherwise, p → q is true.

biconditional operation (↔)

The proposition p ↔ q is true when p and q have the same truth value and is false when p and q have different truth values.

Converse Statement

q → p

the opposite of the conditional statement

inverse statement

¬p → ¬q

the negation of the conditional statement

contrapositive statement

¬q → ¬p

the opposite and negative of the conditional statement

tautology (t)

a statement that is always true

contradiction (c)

a statement that is always false

logical equivalence

Sentences p and q are logically equivalent if and only if it is not possible for one of these sentences to be true while the other sentence is false.

DeMorgan's Law

logical equivalences that show how to correctly distribute a negation operation inside a parenthesized expression

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

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

Idempotent Laws

p ∨ p ≡ p

p ∧ p ≡ p

Associative Laws

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

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

Commutative Laws

p ∨ q ≡ q ∨ p

p ∧ q ≡ q ∧ p

Distributive Laws

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

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

Identity Laws

p ∧ T ≡ p

p ∨ F ≡ p

Domination Laws

p ∨ T ≡ T

p ∧ F ≡ F

Double Negation Laws

¬(¬p) ≡ p

Complement Laws

p ∧ ¬p ≡ F

¬T ≡ F

p ∨ ¬p ≡ T

¬F ≡ T

Absorption Laws

p ∨ (p ∧ q) ≡ p

p ∧ (p ∨ q) ≡ p

Conditional Identities

p → q ≡ ¬p ∨ q

p ↔ q ≡ ( p → q ) ∧ ( q → p )

predicate P(x)

A logical statement whose truth value is a function of one or more variables

domain

the set of all possible values for the variable of a predicate

​

universal quantifier ∀x P(x)

asserts that P(x) is true for every possible value for x in its domain

existential quantifier ∃x P(x)

asserts that P(x) is true for at least one possible value for x in its domain