Discrete Mathematics — Key Definitions, Truth Tables & Laws

Binary operation

\(*\) is a binary operation on \(S\) if \(*\,:\,S\times S\to S\); i.e. \(a*b\in S\) for all \(a,b\in S\) (closure).

Properties (operation \(*\) on \(S\), identity \(e\))

Commutative: \(a*b=b*a\)
Associative: \((a*b)*c=a*(b*c)\)
Identity: \(a*e=e*a=a\)
Inverse: \(a*a'=a'*a=e\)

The identity, if it exists, is unique; the inverse (under associativity) is unique.

Boolean matrices (entries \(\in\{0,1\}\))

Join: \((A\lor B)_{ij}=\max(a_{ij},b_{ij})\). Meet: \((A\land B)_{ij}=\min(a_{ij},b_{ij})\). Identity for join \(=\) null matrix \(O\); identity for meet \(=\) all-ones matrix \(U\).

Modular arithmetic

\(a\equiv b\ (\mathrm{mod}\ n)\iff n\mid(a-b)\). On \(\mathbb{Z}_n\): \(a+_n b=\) remainder of \((a+b)\) mod \(n\); \(\quad a\times_n b=\) remainder of \((a\times b)\) mod \(n\).

Truth table — negation

\[\begin{array}{c|c} p & \lnot p\\ \hline T & F\\ F & T \end{array}\]

Truth tables — binary connectives

\[\begin{array}{c|c|c|c|c|c|c} p & q & p\land q & p\lor q & p\to q & p\leftrightarrow q & p\veebar q\\ \hline T & T & T & T & T & T & F\\ T & F & F & T & F & F & T\\ F & T & F & T & T & F & T\\ F & F & F & F & T & T & F \end{array}\]

Conditional and its consequences

Conditional: \(p\to q\)
Converse: \(q\to p\)
Inverse: \(\lnot p\to\lnot q\)
Contrapositive: \(\lnot q\to\lnot p\) — equivalent to the original

Classification

Tautology: always \(T\), e.g. \(p\lor\lnot p\)
Contradiction: always \(F\), e.g. \(p\land\lnot p\)
Contingency: neither of the above

Laws of logical equivalence

Idempotent: \(p\lor p\equiv p\), \(\quad p\land p\equiv p\)
Commutative: \(p\lor q\equiv q\lor p\), \(\quad p\land q\equiv q\land p\)
Associative: \(p\lor(q\lor r)\equiv(p\lor q)\lor r\), \(\quad p\land(q\land r)\equiv(p\land q)\land r\)
Distributive: \(p\lor(q\land r)\equiv(p\lor q)\land(p\lor r)\), \(\quad p\land(q\lor r)\equiv(p\land q)\lor(p\land r)\)
Identity: \(p\lor F\equiv p\), \(\ p\land T\equiv p\), \(\ p\lor T\equiv T\), \(\ p\land F\equiv F\)
Complement: \(p\lor\lnot p\equiv T\), \(\ p\land\lnot p\equiv F\), \(\ \lnot T\equiv F\), \(\ \lnot F\equiv T\)
Double negation: \(\lnot(\lnot p)\equiv p\)
De Morgan: \(\lnot(p\land q)\equiv\lnot p\lor\lnot q\), \(\quad \lnot(p\lor q)\equiv\lnot p\land\lnot q\)
Absorption: \(p\lor(p\land q)\equiv p\), \(\quad p\land(p\lor q)\equiv p\)

Duality

Swap \(\land\leftrightarrow\lor\) and \(T\leftrightarrow F\) (variables and negations unchanged) to obtain the dual of a statement.

Discrete Mathematics — Key Definitions, Truth Tables & Laws