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 14: Boolean circuits



[Points: 8; Issued: 2004/03/04; Deadline: 2004/04/28; Tutor: Stefan Klampfl; Infohour: 2004/04/26, 12:00-13:00, Seminarraum IGI; Einsichtnahme: 2004/05/17, 12:00-13:00, Seminarraum IGI; Download: pdf; ps.gz]





Prove or disprove that for arbitrary large $ n \in \mathbf{N}$ every Boolean function $ f:\{0,1\}^n \rightarrow \{0,1\}$ can be calculated by a Boolean circuit consisting of $ \leq 5n^4 + 100$ gates $ \neg$, $ \wedge$ ,$ \vee$ (with at most 2 inputs).