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 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 on and define for every two nonempty lists and of examples with for all with the properties
1. for arbitrary examples
2. for arbitrary examples
for which you can prove that there exists a hypothesis defined by a single threshold gate (Schwellengatter) with the following properties:
1. .
2. .

[4 points]

B:
Prove or disprove that for every the Boolean function
 (1)

can be computed by a threshold gate (Schwellengatter).

[4 points]

C:
Prove or disprove that for every with every Boolean function 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 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.