
[Points: 10; Issued: 2003/03/13; Deadline: 2003/03/28; Tutor:
Gerald Krammer; Infohour: 2003/03/26, 14:0015:00,
Seminarraum IGI; Einsichtnahme: 2003/04/09, 14:0015:00,
Seminarraum IGI; 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.
