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
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 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.