EF Boolean polynomials

Section 3.1 Boolean polynomials

We can proceed more algebraically by assigning value

0

to represent false and value

1

to represent true.

🔗

Example 3.1.1. Boolean multiplication.

🔗

Comparing the two tables below, we see that Boolean multiplication is equivalent to logical conjunction.

$x$	$y$	$x y$
$1$	$1$	$1$
$1$	$0$	$0$
$0$	$1$	$0$
$0$	$0$	$0$

$p$	$q$	$p \land q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

🔗

Example 3.1.2. Boolean addition.

🔗

Comparing the following two tables, we see that Boolean addition is equivalent to exclusive or.

$x$	$y$	$x + y$
$1$	$1$	$0$
$1$	$0$	$1$
$0$	$1$	$1$
$0$	$0$	$0$

$p$	$q$	$\neg (p \leftrightarrow q)$
$T$	$T$	$F$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

🔗

Example 3.1.3. Boolean disjunction.

🔗

In Boolean arithmetic we may realize disjunction by combining both addition and multiplication.

$x$	$y$	$x + y + x y$
$1$	$1$	$1$
$1$	$0$	$1$
$0$	$1$	$1$
$0$	$0$	$0$

$p$	$q$	$p \lor q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

🔗

Example 3.1.4. Boolean negation.

🔗

In Boolean algebra, negation is just a matter of shifting one value to the next.

$x$	$x + 1$
$1$	$0$
$0$	$1$

$p$	$\neg p$
$T$	$F$
$F$	$T$

🔗

For notation, we borrow symbols

\land

and

\lor

from logic, but add new negation notation.

$x^{'}$: 🔗
Boolean negation

🔗

With this notation setup, we have

\begin{aligned} x \land y & = x y, & x \lor y & = x + y + x y, & x^{'} & = x + 1 . \end{aligned}

🔗

Boolean polynomial: 🔗
an expression involving variables $x_{1}, x_{2}, \dots, x_{m}$ representing Boolean values, and operations $\land, \lor,^{'},$ often written in function notation

🔗

Note 3.1.5.

🔗

Every Boolean polynomial can be interpreted as a logical statement.

🔗

Example 3.1.6.

🔗

There are two special constant Boolean polynomials, the zero polynomial and the unit polynomial:

\begin{aligned} 0 (x_{1}, x_{2}, \dots, x_{m}) & = 0, & 1 (x_{1}, x_{2}, \dots, x_{m}) & = 1 . \end{aligned}

🔗

Example 3.1.7.

🔗

The Boolean polynomials

p (x, y) = x^{'} \lor y

and

q (x, y) = (x \land y^{'})^{'}

have the same truth table.

$x$	$y$	$x^{'}$	$p (x, y)$	$y^{'}$	$x \land y^{'}$	$q (x, y)$
$1$	$1$	$0$	$1$	$0$	$0$	$1$
$1$	$0$	$0$	$0$	$1$	$1$	$0$
$0$	$1$	$1$	$1$	$0$	$0$	$1$
$0$	$0$	$1$	$1$	$1$	$0$	$1$

🔗

Using our knowledge of logical equivalence, we see that the truth tables are the same because as logical statements,

p

and

q

are equivalent by DeMorgan.

🔗

equivalent polynomials: 🔗
Boolean polynomials which represent equivalent logical statements

🔗

Fact 3.1.8. Recognizing equivalent Boolean polynomials.

🔗

Polynomials

p, q

are equivalent if and only if they have the same truth table.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: