Computational Intelligence, SS08
2 VO 442.070 + 1 RU 708.070 last updated:
General
Course Notes (Skriptum)
Online Tutorials
Practical Course Slides
Homework
Assignments
Scores
Guidelines
Archive
Exams
Animated Algorithms
Interactive Tests
Key Definitions
Downloads
Literature and Links
News
mailto:webmaster

Homework 1: Boolean Functions and threshold circuits



[Points: 10; Issued: 2003/03/13; Deadline: 2003/03/28; Tutor: Gerald Krammer; Infohour: 2003/03/26, 14:00-15:00, Seminarraum IGI; Einsichtnahme: 2003/04/09, 14:00-15:00, Seminarraum IGI; Download: pdf; ps.gz]





Prove that each Boolean function can be computed by a threshold circuit (Schwellenschaltkreis) of depth 2.

Remarks

  • You can use the fact (without proving it) that there exists for each Boolean function $ f:\{0,1\}^n \rightarrow \{0,1\}$ 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.