Disjunction#

Definition: Disjunction

The disjunction function is the Boolean function \(\mathop{\operatorname{OR}}: \{0, 1\}^n \to \{0,1\}\) defined in the following way:

\[ \mathop{\operatorname{OR}}(x_1, \dotsc, x_n) \overset{\text{def}}{=} \begin{cases} 0 \qquad \text{if } x_1 = \cdots = x_n = 0 \\ 1 \qquad \text{otherwise}\end{cases} \]

Notation

It is much more common to write \(\mathop{\operatorname{OR}}(x, y)\) in one of the following ways:

\[ x \lor y \qquad x + y \]

Definition: Maxterm

A logical connective \(f: \{0,1\}^n \to \{0,1\}\) is a maxterm if it can be expressed as the disjunction of a combination of \(n\) negations and identity functions

\[ f(x_1, \dotsc, x_n) = \mathop{\operatorname{OR}}(x_1', \dotsc, x_n'), \]

where \(x_k'\) is either equal to \(x_k\) or to its negation \(\neg x_k\).

Theorem: Commutativity of Conjunction

The disjunction \(\mathop{\operatorname{OR}}: \{0, 1\}^n \to \{0,1\}\) is commutative - if \(y_1, \dotsc, y_n\) is any permutation of \(x_1, \dotsc, x_n\), then

\[ \mathop{\operatorname{OR}}(y_1, \dotsc, y_n) = \mathop{\operatorname{OR}}(x_1, \dotsc, x_n) \]

Tip: Binary Disjunction

In particular, we have:

\[ x_1 \lor x_2 = x_2 \lor x_1 \]

Proof

TODO

Theorem: Associativity of Conjunction

The disjunction \(\mathop{\operatorname{OR}}: \{0,1\}^2 \to \{0,1\}\) is associative:

\[ (x \lor y) \lor z = x \lor (y \lor z) \]

Proof

TODO

Theorem: General Disjunction from Binary Disjunction

Any disjunction \(\mathop{\operatorname{OR}}: \{0, 1\}^n \to \{0,1\}\) can be obtained via composition of binary disjunctions \(\mathop{\operatorname{OR}}: \{0,1\}^2 \to \{0,1\}\):

\[ \mathop{\operatorname{OR}}(x_1, \dotsc, x_n) = \mathop{\operatorname{OR}}(x_1, \mathop{\operatorname{OR}}(x_2, \mathop{\operatorname{OR}}(\cdots))) \]

Proof

TODO