
[Points: 12.5; Issued: 2006/03/22; Deadline: 2006/05/10; Tutor:
Karin Schoefegger; Infohour: 2006/05/08,
13:0014:00, HSi13; Einsichtnahme: 2006/05/22, 13:0014: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

for arbitrary examples

for arbitrary examples
for which you can prove that there exists a hypothesis
defined by a
single threshold gate (Schwellengatter) with the following
properties:

.

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