Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Aussagenlogik » Beweisen, dass ein n-stelliger Junktor mit "AND" und "NEGATION" dargestellt werden kann.
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Beweisen, dass ein n-stelliger Junktor mit "AND" und "NEGATION" dargestellt werden kann.
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-12-18


Stellen Sie sich folgende Situation vor: Sie unterhalten sich auf einer Party mit einem Informatik-Studenten aus einem
höheren Semester. Dieser erzählt Ihnen stolz von seiner neuesten Entdeckung im Rahmen seiner Bachelorarbeit: einen
völlig neuen k-stelligen Junktor in der Aussagenlogik, genannt Humbug-Junktor. Um seine Forschungsergebnisse bis zur
Veröffentlichung geheim zu halten, erzählt er Ihnen allerdings nicht die genaue Semantik. Um Ihren enthusiastischen
Kommilitonen etwas den Wind aus den Segeln zu nehmen, beweisen Sie ihm folgendes:
Der Humbug-Junktor lässt sich ausdrücken als eine Formel, welche ausschließlich die Junktoren ∧ und ¬ verwendet.

Mein Ansatz wäre jetzt, dass dies schon allein deswegen so sein, muss, weil sich alle anderen Junktoren in der Form darstellen lassen.

Jemand Vorschläge?
Packe das leider nicht ohne Hilfe



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1802
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-12-18

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
Im Prinzip musst du zeigen, dass für beliebige $k$ alle *Funktionen* $\mathbf B^k \to \mathbf B$ mittels $\land$ und $\lnot$ (und eigentlich noch $\top$ oder $\bot$, außer, man fordert $k>0$) ausgedrückt werden können.

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-12-19


könnte mir bei dem Beweis jemand helfen?
Weiß nicht wie ich da jetzt anfangen sollen, was da für Schritte sind, um zum Beweis zu kommen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3610
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-12-19


Hallo rapiz,

du kannst es mit vollständiger Induktion versuchen. Angenommen, du könntest alles 2-stelligen Junktoren auf die gewünschte Art darstellen. Hast du dann vielleicht eine Idee, wie du bei einem 3-stelligen Junktor vorgehen könntest? Dann könntest du das Vorgehen auf den Fall k+1 bei bekanntem Vorgehen bei k-stelligem Junktor verallgemeinern.

Grüße aus dem Harz
Gerhard/Gonz


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-12-19


Nicht wirklich.

Ein n stelliger Junktor wäre doch ein Junktor der n Junktoren beinhaltet, oder?
Dann müsste man doch nur immer den letzten Junktor in diesem n stelligen Junktor für die "normale Version" am Ende hinzufügen ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3610
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-12-20


Hm, nicht wirklich. Ein n-stelliger Junktor hat n Eingänge, die man mit einem Ausgang verbindet. Es gibt also 2^n Möglichkeiten, die Eingänge zu belegen. Der Junktor ist dadurch beschrieben, wie er für jede dieser Kombinationen am Ausgang reagiert (dh. eine Wahrheitstabelle mit 2^n Zeilen). Vielleicht schaust du dir mal ein Beispiel für einen zweistelligen oder dreistelligen Junktor an, und erstellst die entsprechenden Wahrheitstabellen.


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-12-21


Also {0,1}^n -> {0,1}


Da für n <= 2 gilt, dass ich jede dieser Abbildungen mit AND und NEGATION darstellen kann, hat man für n+1 doch lediglich ein n=1 das angehängt wird, für das ja dies bereits gilt, also gilt dies auch für alle n ?

(Kann man nicht auch mit DNF und KNF argumentieren, dass dies möglich ist?)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6186
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-12-21


Hallo rapiz,

deinem Induktionsschritt kann ich nicht folgen.

Und DNF und KNF benutzen außer AND und NOT noch OR. Also klappt es damit nicht.

Zum Induktionsschritt:

Für eine Funktion \(f(x_1,...,x_n,x_{n+1})\) gilt ja:

\(f(x_1,...,x_n,x_{n+1})\equiv (f(x_1,...,x_n,0)\wedge (x_{n+1}=0)) \vee (f(x_1,...,x_n,1)\wedge (x_{n+1}=1))\)

Wie kannst du das nun nur mit AND und NOT schreiben?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-12-22


Zu DNF und KNF : Wenn ich vor den AND's ein NOT setze habe ich doch OR

Das Gleiche tritt doch hier auf?


So?

f(x1,...,xn,xn+1)=(f(x1,...,xn,0)∧(xn+1=0))∧NOT(f(x1,...,xn,1)∧(xn+1=1))


Danke nochmal für die Hilfe



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6186
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-12-22


2019-12-22 07:51 - rapiz in Beitrag No. 8 schreibt:
Zu DNF und KNF : Wenn ich vor den AND's ein NOT setze habe ich doch OR

Das Gleiche tritt doch hier auf?


So?

f(x1,...,xn,xn+1)=(f(x1,...,xn,0)∧(xn+1=0))∧NOT(f(x1,...,xn,1)∧(xn+1=1))

Meinst du \(x\vee y\equiv x\wedge\neg y\)?

Das stimmt leider nicht. Überzeuge dich durch eine Wahrheitstabelle davon.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-12-22


f(x1,...,xn,xn+1)≡¬(¬(f(x1,...,xn,0)∧(xn+1=0))∧¬(f(x1,...,xn,1)∧(xn+1=1)))

So meinte vor das AND ein Negationssymbol, damit es wieder zum or wird

a ¬∧ bist ja so nicht zulässig oder?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6186
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-12-22


2019-12-22 17:34 - rapiz in Beitrag No. 10 schreibt:
a ¬∧ b ist ja so nicht zulässig oder?

Natürlich nicht. Was sollte das auch sein?

Das andere sieht schon ganz gut aus. Du hast die De Morgansche Regel angewendet. Das solltest du dazu schreiben. Außerdem "nach IV gilt ...".

Aber: in der Formel sind noch zwei =, welche es zu eliminieren gilt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2020-01-18


Habe dazu nun folgenden Beweis gefunden.

Sei B = {0, 1}, k ≥ 2 und f : Bk+1 → B eine k + 1 -stellige Funktion.
Sei Gi ={(a1, . . . , ak) ∈ Bk|f (a1, . . . , ak, i) = 1}
für jedes i ∈ B
Sei gi: Bk → B mit gi(a) = 1 ⇐⇒ a ∈ Gi
für jedes i ∈ B
Dann ist
f (v1, . . . , vk+1) = (g0 (v1, . . . , vk) ∧ ¬vk+1) ∨ (g1 (v1, . . .
, vk) ∧ vk+1)

Kann mir den Beweis jemand erklären? Oder mir helfen, diesen verständlicher zu formulieren?

Mir ist auch nicht so ganz ersichtlich, wieso nur mit = 1 bewiesen wird.

Danke



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3610
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-01-19


Hallo rapiz,

es geht wieder um die vollständige Induktion. Für einen (k+1)-stelligen Junktor f werden hier zwei k-stellige Junktoren G0 und G1 konstruiert, aus denen er dargestellt werden soll. Diese entstehen aus f, indem man die k+1.Stelle in dem einen Fall auf 0 festlegt und in dem anderen Fall auf 1.

Versuch dir vielleicht besser, selber mit diesen Hinweisen eine Lösung zu entwickeln. So formale Konstruktionen, die du "gefunden" hast, zu verstehen, ist nicht eben einfach, wenn du die Idee dahinter nicht verstehst.

Oder mach dir das mal an einem Beispiel klar, zB nimm dir einen 3-stelligen Junktor her, schreib dir die Tabelle auf die ihn definiert, und sieh dann, wie daraus die 2-stelligen Junktoren entstehen...

Grüße
Gerhard/Gonz


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2020-01-19


Also Gi ist ja die Menge der Variablen, die jeweils 0|1 annehmen

1. Wieso setzt man f(Gi, i) = 1 ?


So gi ist nun die Abbildung auf 0|1 der gesamten Fkt| des Junktors

Jetzt wieder nur auf 1 abgebildet mit a € Gi



Dann ist
f (v1, . . . , vk+1) = (g0 (v1, . . . , vk) ∧ ¬vk+1) ∨ (g1 (v1, . . .
, vk) ∧ vk+1)

Also der k+1 stellige Junktor = (1 ∧ ¬vk+1 ) ∨ (1 ∧ vk+1)

Also k stelliger Junktor und 0 oder k stelliger Junktor und 1 ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3610
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2020-01-20


Ja genau, und zwar zwei unterschiedliche k-stellige Junktoren, je nachdem, ob man den k+1.ten Input auf 0 oder auf 1 "festgenagelt" hat.

Das ist der Rekursionsschritt. Wenn wir k-stellige Junktoren aus AND und NOT darstellen können, (und auch das OR), dann haben wir hiermit eine Methode, wie wir einen k+1 stelligen Junktor darstellen können.


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2020-01-20


Und was hat es mit Sei gi: Bk → B mit gi(a) = 1 ⇐⇒ a ∈ Gi auf sich?

gi(a) = 1 ⇐⇒ a ∈ Gi Der Teil?


Checke immer noch nicht die gesamte Vorgehensweise dieser rekursiven Funktion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3610
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2020-01-21


2020-01-20 18:12 - rapiz in Beitrag No. 16 schreibt:
Checke immer noch nicht die gesamte Vorgehensweise dieser rekursiven Funktion

Pass auf, wir spielen das mal an einem Beispiel durch. Angenommen, wir haben einen "beliebigen" 3-Junktor. Ich habe mal einen "ausgewürfelt". Er ist ja durch eine Tabelle definiert, die für jede der 2^3=8 Kombinationen der Inputs den entsprechenden Output beinhaltet. Tatsächlich habe ich gewürfelt, und hier ist der "Gonz-Junktor":



Wir sollen ihn also aus AND und NOT Elementen darstellen. Das trauen wir uns direkt nicht zu, aber wir können ihn in zwei zweistellige Junktoren zerlegen, je nachdem, wie der erste Input steht. Diese sind in der Tabelle in rot und grün hinterlegt, wir nennen sie je nachdem, ob IN-1 auf 0 oder auf 1 stehen soll g0 und g1.



Mal angenommen wir hätten diese zur Hand, dann hätten wir für f folgende nette Darstellung (die ist ja in deinem Beispiel auch angegeben):


f(IN-1,IN-2,IN-3) = ( IN-1 AND g1(IN-2,IN-3) OR ( (NOT IN-1) AND g0(IN-2,IN-3))

Das ist so zu verstehen: entweder muss IN-1 gesetzt sein, dann werten wir die beiden übrigen Eingänge mit Hilfe der Funktion g1 aus, oder IN-1 ist nicht gesetzt, dann ermitteln wir den Funktionswert mit Hilfe der Funktion g0. Dabei sind g0 und g1 zweistellige Funktionen, die wir einfacher auswerten können (das ist quasi der Induktionsschritt). Wir haben außerdem noch die Aufgabe, das OR aus der obigen Formel auch durch AND und NOT darzustellen.

Soweit -

Grüße
Gerhard/Gonz




-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]