474 CHAPTER 7 Counting and Combinatorics
(c) A self-dual, two-valued boolean function defined on an n-bit binary number whose
bits are a,, a2, ... , an is a function F where
F(al, a2 ..... an) = F(1 - a, 1 - a2. 1 -a,)
How many self-dual boolean functions of n variables are there?- In Section 2.5.3, we discussed formulas in CNF. A CNF formula, such as
(X13 V X17 V -X23) A (-X2 V X5) A (X2 V -X13 V -X17)
is a formula that is composed of a conjunction (A) of disjunctions (v) of literals (propo-
sition letters xi and their negations --xi). Note that if we assume a v applies to as few
literals as possible, reversing normal operator precedence rules, we can unambiguously
drop parentheses-for example,
X13 V X17 V -X23 A -X2 V X5 A X2 V -X13 V -X17
The CNF formulas are very convenient in computer representations of logic, but they
also tend to get exponentially long. Show that for any fixed k, for large enough n, there
are boolean functions of n variables that are not expressed by any CNF formula with lessthan or equal to n k literals. (Actually, allowing any mixing of A's and v's would still not
solve the exponential length problem.) (Hint: Count the number of CNF formulas with
less than or equal to nk literals. In fact, this overcounts the number of n-ary boolean
functions expressible by such CNF formulas, since several CNF formulas may express
the same boolean function-that is, be logically equivalent).8. A system encodes integers as strings of O's and l's, with no two consecutive O's. (Two
O's are used to indicate the end of one number and the start of the next.) Approximate,
as best you can, how many different integers can be represented in no more than 100
digits. Compute the maximum error of your approximation-and prove that your error
assertion is correct.