Equivalence of Logical and Boolean Expressions

Section 1.2 Equivalence of Logical and Boolean Expressions

Checkpoint 1.1.5 suggests that there is some kind of equivalence between logical expressions and Boolean expressions. This turns out to be true. Here are some facts.

🔗

Proposition 1.2.1. All Boolean functions are polynomial.

Let \(x_1,x_2,\ldots,x_n\) be Boolean variables, and let \(f\colon \B^n \to \B\) be a function. Then \(f(x_1,x_2,\ldots,x_n)\) may be written as a polynomial

\begin{equation} f(x_1,x_2,\ldots,x_n)=\sum_{I=(i_1,i_2,\ldots,i_n)\in \B^n}c_I x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}\tag{1.2.1} \end{equation}

for some constants \(c_I=c_{i_1,i_2,\ldots,i_n}\in \B\text{.}\)

🔗

Comment on terminology. A Boolean expression in \(n\) variables \(x_1,x_2,\ldots,x_n\) is a polynomial in those variables, with coefficients in \(\B\text{.}\) Polynomials are the expressions that can be made using only the variables \(x_1,x_2,\ldots,x_n\text{,}\) the constants \(0,1\text{,}\) and the operations of addition and multiplication. A consequence of Proposition 1.2.1 is that Boolean expressions account for all possible Boolean functions \(\B^n\to \B\text{.}\)

🔗

Checkpoint 1.2.2.

Identify all of the details for the Boolean functions in both parts of Checkpoint 1.1.5.

🔗

Proposition 1.2.3. All Boolean expressions are logical.

Let \(f\colon \B^n\to \B\) be a function. There exists a truth table in whose columns are \(n\) statements \(p_1,p_2,\ldots,p_n\) for a logical expression made using \(p_1,p_2,\ldots,p_n\) and the logical connectives \(\sim,\wedge,\vee\) whose corresponding Boolean expression is \(f(x_1,x_2,\ldots,x_n)\text{,}\) where \(x_k=v(p_k)\) for \(1\leq k\leq n\text{.}\)

🔗

Checkpoint 1.2.4.

Make three random strings 8 letter long using the letters \(T,H\text{.}\) Make a table whose columns are labeled \(p,q,r,L\text{,}\) and with 8 rows, filled in with the 8 3-letter logical possibilities \(TTT,TTH,THT,\ldots,HHH\) for columns \(p,q,r\text{,}\) and put one of your random 8-letter strings in the column for \(L\text{.}\) Find a logical expression made using \(p,q,r\) and the connectives \(\sim,\wedge,\vee\) so that your table is the truth table for that expression. Find the corresponding Boolean polynomial expression. Repeat for your remaining 8-letter strings.

🔗

Corollary 1.2.5. The connectives \(\sim,\wedge,\vee\) are universal.

Any truth table made from any number of logical variables \(p_1,p_2,\ldots,p_n\) is equivalent to the truth table for a logical expression that used only the logical connectives \(\sim,\wedge,\vee\text{.}\)

🔗

Prev Top Next