
[Points: 12.5; Issued: 2008/05/09; Deadline: 2008/05/30; Tutor:
Gerhard Neumann; Infohour: 2008/05/23, 15:3016:30,
HS i11; Einsichtnahme: 2008/06/13, 15:3016:30, HS i11; Download:
pdf; ps.gz]
Prove that each Boolean function can be
computed by a threshold circuit (Schwellenschaltkreis) of depth 2.
 You can use the fact (without proving it) that there exists for
each Boolean function
a Boolean formula in
disjunctive normal form (DNF); see definition 1.1.5 of ``Grundbegriffe der Aussagenlogik'' for the precise
definition of the DNF.
 Hence you just have to prove that there exists for each Boolean
formula in DNF a circuit of threshold gates (of depth 2) which
outputs for each binary input vector 1 if the DNF formula is true
and outputs 0 if the DNF formulae is false for the corresponding
truth assignment.
 Consider the case of the hypothesis class of axis parallel
rectangles. The VCdimension of a single rectangle is 4. Find the
best lower bound if you can use 2 rectangles instead of one !
 Consider the case of the hypothesis class of a single, axis
parallel rectangle, where you can additionally choose wether to
classify class 1 inside or outside the rectangle. Whats the best
lower bound for the VCdimension you can proof ?

