[Points: 12.5; Issued: 2008/05/09; Deadline: 2008/05/30; Tutor:
Gerhard Neumann; Infohour: 2008/05/23, 15:30-16:30,
HS i11; Einsichtnahme: 2008/06/13, 15:30-16:30, HS i11; Download:
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
- Consider the case of the hypothesis class of axis parallel
rectangles. The VC-dimension 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 VC-dimension you can proof ?