Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweise das der logische Ausdruck eine Tautologie

Beweise das der logische Ausdruck eine Tautologie

Universität / Fachhochschule

Sonstiges

Tags: Logikaufgabe

karl3333 aktiv_icon

23:37 Uhr, 20.11.2018

Weiß leider nicht wie ich da vorgehen soll

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

karl3333 aktiv_icon

12:43 Uhr, 21.11.2018

Der logische Ausdruck müsste dann immer wahr sein um eine Tautologie zu sein kann einer helfen?

anonymous

17:23 Uhr, 23.11.2018

Roboter-Mensch-Kontakter anschalt...

Es steht dort, verbal intoniert, räusper:

I inklusives Oder II

mit

I: Für jedes

x

gilt, dass

q

von

x

impliziert,
dass für alle

y

gilt, dass

p

von

x

und

y

nicht gilt.

II: Es gibt ein

y,

für dass es ein

x

gibt,
sodass

p

von

x

und

y

gilt.

Genau wenn I gilt, gilt II nicht,
daher gilt

(I

oder II) immer.

Ja, und I könnte auch schlichter gefasst werden als

I: Für jedes

x

gilt, dass für alle

y

gilt, dass

p

von

x

und

y

nicht gilt.

Es sei denn, man möchte dieses "q von

x

impliziert"
irgendwie betonen...

ermanus aktiv_icon

21:18 Uhr, 23.11.2018

Hallo,
nun zum formalen Teil ;-)
Wir wollen zeigen, dass der Gesamtausdruck vom Typ

A \lor \neg A

ist.
Dazu negieren wir den linken Teil und zeigen,
dass er äquivalent zum rechten Partner der Disjunktion ist:

\neg (\forall x : (q (x) \to \forall y : \neg p (x, y))) \equiv

Implikation auflösen:

\neg (\forall x : (\neg q (x) \lor \forall y : \neg p (x, y))) \equiv

All-Quantor über Terme, die durch ihn nichtgebundene Variablen enthalten, nach vorne ziehen:

\neg (\forall x \forall y : \neg q (x) \lor \neg p (x, y)) \equiv

deMorgan bzgl.

\forall x

\exists x (\neg \forall y : \neg q (x) \lor \neg p (x, y)) \equiv

deMorgan bzgl.

\forall y

:
...
und nun du weiter ...

Gruß ermanus

anonymous

00:00 Uhr, 24.11.2018

. .

karl3333 aktiv_icon

01:18 Uhr, 24.11.2018

Müsste genau die Rechte Seite raus kommen dann

anonymous

01:41 Uhr, 24.11.2018

Oder Negieren per Faustregel: All-Quantoren mit Es-gibt-Quantoren
tauschen und umgekehrt und die Kernaussage negieren.

Aus

\neg (\forall x \forall y : \neg q (x) \lor \neg p (x, y))

wird dann

\exists x \exists y : q (x) \land p (x, y)

.

(Beachte

\neg (\neg A \lor \neg B) \Leftrightarrow A \land B .)

Diese Aussage ist allerdings stärker als

\exists x \exists y : p (x, y)

.

Ob das der Tautologie im Wege steht, weiß ich nicht.

karl3333 aktiv_icon

17:19 Uhr, 24.11.2018

Danke für die Lösung

1448955

1448291

	Status: nicht eingeloggt	Noch nicht registriert?