Monotone Boolesche Funktion < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe eine Frage bezüglich einer monotonen Booleschen Funktion.
Die Definition ist laut Internet:
dass aus (b1..... bn) [mm] \le [/mm] (c1.....cn) f(b1....bn) [mm] \le [/mm] f(c1....cn) folgt.
Wie kann ich mir das jetzt vorstellen ? Wenn ich für (b1...bn) Belegungen einsetze , z.B. : (000) und für (c1...cn) (111) einsetze.
Dann ist (000) [mm] \le [/mm] (111). Und das gilt ja dann auch für f(000) [mm] \le [/mm] f(111). Also ist das jetzt monoton ? Und es ist auch eine AUfgabe , zu prüfen, ob zweistellige Boolesche Funktionen für eine Konjunktion monoton sind. Wie prüfe ich das bzw. wie gehe ich dort vor ?
Vielen Dank im Voraus.
|
|
| |
|
Hallo,
> Hallo,
> ich habe eine Frage bezüglich einer monotonen Booleschen
> Funktion.
> Die Definition ist laut Internet:
> dass aus (b1..... bn) [mm]\le[/mm] (c1.....cn) f(b1....bn) [mm]\le[/mm]
> f(c1....cn) folgt.
>
> Wie kann ich mir das jetzt vorstellen ? Wenn ich für
> (b1...bn) Belegungen einsetze , z.B. : (000) und für
> (c1...cn) (111) einsetze.
> Dann ist (000) [mm]\le[/mm] (111).
Ja, es muss komponentenweise [mm]\le[/mm] gelten, also [mm]b_i\le c_i[/mm] für [mm]i=1,...,n[/mm]
> Und das gilt ja dann auch für
> f(000) [mm]\le[/mm] f(111). Also ist das jetzt monoton ?
Wenn das gilt, dann ja; aber das hängt ja davon ab, wie f definiert ist ...
> Und es ist
> auch eine AUfgabe , zu prüfen, ob zweistellige Boolesche
> Funktionen für eine Konjunktion monoton sind. Wie prüfe
> ich das bzw. wie gehe ich dort vor ?
Teste im Zweifel alle Fälle durch ...
Hier ist [mm]f:(a,b)\to a\wedge b[/mm]
>
> Vielen Dank im Voraus.
Gruß
schachuzipus
|
|
|
| |
|
Danke für die Antwort.
Also ich habe jetzt zum Beispiel Folgendes:
Ich soll untersuchen ob zweistellige Boolsche Funktionen für die Disjunktion monoton sind.
Ich bin wie folgt vorgegangen:
(1,0) [mm] \le [/mm] ( 0,1) -- hier schon die erste Frage, reicht das ? Oder muss ich mehrere Kombinationen ausprobieren ?
Weiter:
(1,0) [mm] \le [/mm] ( 0,1) --> das ist zum Beispiel falsch (1,0) ist nicht kleiner gleich (0,1)
Und jetzt das als Funktion:
f(1,0) [mm] \le [/mm] f(0,1) , das trifft auch nichtzu ?
Und das ganze für die Disjunktion:
(1,0) [mm] \vee [/mm] (0,1)
1 oder 0 = 1
1 oder 1 = 1
0 oder 0 = 0
0 oder 1 = 1
Das kann es doch nicht gewesen sein ? Weiß nicht so recht , wie ich bei dieser Aufgabe vorgehen soll... Wäre nett, wenn mir gesagt wird , was falsch ist.
Vielen Dank im Voraus.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:44 So 03.11.2013 | | Autor: | pc_doctor |
Ich habs nochmal versucht für die Disjunktion:
(b1,b2) = (0,0) [mm] \vee [/mm] (1,0) = (c1,c2)
(b1,b2) [mm] \vee [/mm] (c1,c2 ) = 1
f(b1,b2) = 0
f(c1,c2) = 1
f(b1,b2) [mm] \vee [/mm] f(c1,c2) = 0 [mm] \vee [/mm] 1 = 1
Also monoton.
Ist das so richtig ?
|
|
|
| |
|
Hallo nochmal,
> Danke für die Antwort.
>
> Also ich habe jetzt zum Beispiel Folgendes:
> Ich soll untersuchen ob zweistellige Boolsche Funktionen
> für die Disjunktion monoton sind.
>
> Ich bin wie folgt vorgegangen:
>
> (1,0) [mm]\le[/mm] ( 0,1)
?? Das gilt doch nicht! In der ersten Komponente geht das doch schief, es ist doch [mm]1>0[/mm] und nicht [mm]1\le 0[/mm]
> -- hier schon die erste Frage, reicht das
> ? Oder muss ich mehrere Kombinationen ausprobieren ?
>
> Weiter:
> (1,0) [mm]\le[/mm] ( 0,1) --> das ist zum Beispiel falsch (1,0) ist
> nicht kleiner gleich (0,1)
>
> Und jetzt das als Funktion:
> f(1,0) [mm]\le[/mm] f(0,1) , das trifft auch nichtzu ?
>
> Und das ganze für die Disjunktion:
>
> (1,0) [mm]\vee[/mm] (0,1)
>
> 1 oder 0 = 1
> 1 oder 1 = 1
> 0 oder 0 = 0
> 0 oder 1 = 1
>
> Das kann es doch nicht gewesen sein ? Weiß nicht so recht
> , wie ich bei dieser Aufgabe vorgehen soll... Wäre nett,
> wenn mir gesagt wird , was falsch ist.
Ich glaube, du hast das mit dem f noch nicht ganz verstanden.
Es ist f eine Abbildung von [mm]\{0,1\}^2\to\{0,1\}[/mm], die ein [mm](a,b)[/mm] abbildet auf [mm]a\vee b[/mm].
Es ist zB. [mm]f((0,0))=0\vee 0=0[/mm] [mm], f((0,1))=0\vee 1=1[/mm] usw.
Nun schaue dir alle Urbildpaare [mm](a,b),(c,d)[/mm] an mit [mm](a,b)\le (c,d)[/mm] und schaue, ob f die Monotonie erhält oder nicht.
ZB. [mm](0,0)\le (0,1)[/mm] und [mm]f((0,0))=0\vee 0=\red{0 \ \le \ 1}=0\vee 1=f((0,1))[/mm] - passt!
Nun für alle anderen möglichen [mm](a,b),(c,d)[/mm] mit [mm](a,b)\le (c,d)[/mm] ...
So viele sind das ja nicht, das kannst du locker durchprobieren.
>
> Vielen Dank im Voraus.
>
>
Gruß
schachuzipus
|
|
|
|
