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 35: Threshold circuits and Boolean functions



[Points: 12.5; Issued: 2006/03/22; Deadline: 2006/05/10; Tutor: Karin Schoefegger; Infohour: 2006/05/08, 13:00-14:00, HSi13; Einsichtnahme: 2006/05/22, 13:00-14:00, HSi13; Download: pdf; ps.gz]





A:
Construct a probability measure $ P$ on $ \mathbb{R}^2\times\{-1,1\}$ and define for every $ i\in\mathbb{N}$ two nonempty lists $ L_i$ and $ L'_i$ of examples $ \langle \mathbf{a},b\rangle \in \mathbb{R}^2 \times \{-1,1\}$ with $ P(\langle \mathbf{a},b\rangle )>0$ for all $ \langle \mathbf{a},b\rangle $ with the properties
  1. $ L_{i+1} = \langle L_{i}, \langle {\bf c},d\rangle \rangle $ for arbitrary examples $ \langle {\bf c},d\rangle \in \mathbb{R}^2 \times \{-1,1\}$
  2. $ L'_{i+1} = \langle L'_{i}, \langle {\bf c}',d'\rangle \rangle $ for arbitrary examples $ \langle {\bf c}',d'\rangle \in \mathbb{R}^2 \times \{-1,1\}$
for which you can prove that there exists a hypothesis $ H:\mathbb{R}^2\rightarrow \{-1,1\}$ defined by a single threshold gate (Schwellengatter) with the following properties:
  1. $ error_{P}(H) > error_{L_i}(H) > error_{L_{i+1}}(H)$.
  2. $ error_{P}(H) < error_{L'_i}(H) < error_{L'_{i+1}}(H)$.

[4 points]

B:
Prove or disprove that for every $ n\in\mathbb{N}$ the Boolean function
$\displaystyle \bigvee(x_1,...,x_n) = \begin{cases}+1, & \mbox{if } x_i = 1 \mbox{ for at least one } i \in \{1,...,n\} \\ -1, & \mbox{otherwise} \end{cases}$ (1)


can be computed by a threshold gate (Schwellengatter).

[4 points]

C:
Prove or disprove that for every $ n\in\mathbb{N}$ with $ n \ge 5$ every Boolean function $ f:\{-1,1\}^n \rightarrow \{-1,1\}$ that can be computed by a single threshold gate (Schwellengatter) can be defined by a Boolean function in disjunctive normal form (DNF) with less than $ n$ conjunctions (Konjuktionen); see definition 1.1.5 of ''Grundbegriffe der Aussagenlogik'' for the precise definition of the DNF.

[4.5 points]

All proofs should be clearly structured, and consist of complete sentences in perspicuous logical relationship.