Angenommen, es gibt zwei Formeln, X und Y. Diese Formeln werden als Äquivalenz bezeichnet, wenn X ↔ Y eine Tautologie ist. Wenn zwei Formeln X ↔ Y eine Tautologie sind, können wir sie auch als X ⇔ Y schreiben und diese Beziehung als Äquivalenz von X zu Y lesen.
Hinweis: Es gibt einige Punkte, die wir bei der linearen Äquivalenz der Formel beachten sollten. Diese werden wie folgt beschrieben:
- ⇔ wird nur als Symbol verwendet, ist jedoch nicht konnektiv.
- Der Wahrheitswert von X und Y ist immer gleich, wenn X ↔ Y eine Tautologie ist.
- Die Äquivalenzrelation enthält zwei Eigenschaften, nämlich symmetrisch und transitiv.
Methode 1: Wahrheitstabellenmethode:
Bei dieser Methode erstellen wir die Wahrheitstabellen einer beliebigen Formel mit zwei Aussagen und prüfen dann, ob diese Aussagen äquivalent sind.
Beispiel 1: In diesem Beispiel müssen wir X ∨ Y ⇔ ¬(¬X ∧ ¬Y) beweisen.
Lösung: Die Wahrheitstabelle von X ∨ Y ⇔ ¬(¬X ∧ ¬Y) wird wie folgt beschrieben:
| X | UND | X ∨ Y | ¬X | ¬Und | ¬X ∧ ¬Y | ¬(¬X ∧ ¬Y) | X ∨ Y ⇔ ¬(¬X ∧ ¬Y) |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | T | T |
| T | F | T | F | T | F | T | T |
| F | T | T | T | F | F | T | T |
| F | F | F | T | T | T | F | T |
Wie wir sehen können, ist X ∨ Y und ¬(¬X ∧ ¬Y) eine Tautologie. Daher X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Beispiel 2: In diesem Beispiel müssen wir (X → Y) ⇔ (¬X ∨ Y) beweisen.
Lösung: Die Wahrheitstabelle von (X → Y) ⇔ (¬X ∨ Y) wird wie folgt beschrieben:
| X | UND | X → Y | ¬X | ¬X ∨ Y | (X → Y) ⇔ (¬X ∨ Y) |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
Wie wir sehen können, sind X → Y und (¬X ∨ Y) eine Tautologie. Daher (X → Y) ⇔ (¬X ∨ Y)
Äquivalenzformel:
Es gibt verschiedene Gesetze, die zum Beweis der Äquivalenzformel verwendet werden, die wie folgt beschrieben wird:
Idempotentes Gesetz: Wenn es eine Anweisungsformel gibt, enthält diese die folgenden Eigenschaften:
X ∨ X ⇔ X X ∧ X ⇔ X
Assoziatives Recht: Wenn drei Anweisungsformeln vorhanden sind, enthält sie die folgenden Eigenschaften:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Kommutativgesetz: Wenn zwei Anweisungsformeln vorhanden sind, enthält sie die folgenden Eigenschaften:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Verteilungsrecht: Wenn drei Anweisungsformeln vorhanden sind, enthält sie die folgenden Eigenschaften:
Java einschalten
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Identitätsrecht: Wenn es eine Anweisungsformel gibt, enthält diese die folgenden Eigenschaften:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Komplementgesetz: Wenn es eine Anweisungsformel gibt, enthält diese die folgenden Eigenschaften:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorptionsgesetz: Wenn zwei Anweisungsformeln vorhanden sind, enthält sie die folgenden Eigenschaften:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Aus Morgans Gesetz: Wenn zwei Anweisungsformeln vorhanden sind, enthält sie die folgenden Eigenschaften:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Methode 2: Austauschprozess
Bei dieser Methode gehen wir von einer Formel A : X → (Y → Z) aus. Die Formel Y → Z kann als Teil der Formel bezeichnet werden. Wenn wir diesen Teil der Formel, also Y → Z, mit Hilfe der Äquivalenzformel ¬Y ∨ Z in A ersetzen, dann erhalten wir eine andere Formel, also B : X → (¬Y ∨ Z). Es ist ein einfacher Prozess, zu überprüfen, ob die angegebenen Formeln A und B zueinander äquivalent sind oder nicht. Mit Hilfe des Ersetzungsprozesses können wir B aus A erhalten.
Beispiel 1: In diesem Beispiel müssen wir beweisen, dass {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Lösung: Hier nehmen wir den linken Seitenteil und versuchen, den rechten Seitenteil zu bekommen.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Jetzt verwenden wir das Assoziativgesetz wie folgt:
⇔ (¬X ∨ ¬Y) ∨ Z
Jetzt verwenden wir das Gesetz von De Morgan wie folgt:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Somit bewiesen
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Beispiel 2: In diesem Beispiel müssen wir beweisen, dass {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Lösung: Hier nehmen wir den linken Seitenteil und versuchen, den rechten Seitenteil zu bekommen.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Somit bewiesen
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Beispiel 3: In diesem Beispiel müssen wir beweisen, dass X → (Y → X) ⇔ ¬X → (X → Y).
Lösung: Hier nehmen wir den linken Seitenteil und versuchen, den rechten Seitenteil zu bekommen.
X → (Y → X) ⇔ ¬X ∨ (Y → X) ⇔ ¬X ∨ (¬Y ∨ X) ⇔ (¬X ∨ X) ∨ ¬Y ⇔ T ∨ ¬Y ⇔ T and ¬X → (X → Y) ⇔ ¬(¬X) ∨ (X → Y) ⇔ X ∨ (¬X ∨ Y) ⇔ (X ∨ ¬X) ∨ Y ⇔ T ∨ Y ⇔ T
Somit bewiesen
X → (Y → X) ⇔ ¬X → (X → Y)
Beispiel 4: In diesem Beispiel müssen wir beweisen, dass (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Lösung: Hier nehmen wir den linken Seitenteil und versuchen, den rechten Seitenteil zu bekommen.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Jetzt verwenden wir die assoziativen und distributiven Gesetze wie folgt:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Jetzt verwenden wir das Gesetz von De Morgan wie folgt:
Shehzad Poonawala
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Jetzt verwenden wir das Distributivgesetz wie folgt:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Somit bewiesen
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Beispiel 5: In diesem Beispiel müssen wir zeigen, dass ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) eine Tautologie ist.
Lösung: Hier werden wir kleine Teile nehmen und sie lösen.
Zuerst verwenden wir das Gesetz von De Morgan und erhalten Folgendes:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Daher,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Auch
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Somit
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Daher
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Daher können wir sagen, dass die gegebene Formel eine Tautologie ist.
Beispiel 6: In diesem Beispiel müssen wir zeigen, dass (X ∧ Y) → (X ∨ Y) eine Tautologie ist.
Lösung: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Jetzt verwenden wir das Gesetz von De Morgan wie folgt:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Jetzt verwenden wir das Assoziativgesetz und das Kommutativgesetz wie folgt:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Jetzt verwenden wir das Negationsgesetz wie folgt:
⇔ (T ∨ T) ⇔ T
Daher können wir sagen, dass die gegebene Formel eine Tautologie ist.
Beispiel 7: In diesem Beispiel müssen wir die Negation einiger Aussagen schreiben, die wie folgt beschrieben werden:
- Marry wird ihre Ausbildung abschließen oder den Beitrittsbrief der Firma XYZ annehmen.
- Harry wird morgen reiten oder laufen gehen.
- Wenn ich gute Noten bekomme, wird mein Cousin eifersüchtig sein.
Lösung: Zunächst lösen wir die erste Aussage wie folgt:
1. Angenommen, X: Marry wird ihre Ausbildung abschließen.
Y: Akzeptieren Sie das Beitrittsschreiben der Firma XYZ.
Wir können die folgende symbolische Form verwenden, um diese Aussage auszudrücken:
X ∨ Y
Die Negation von X ∨ Y wird wie folgt beschrieben:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Zusammenfassend lautet die Negation der gegebenen Aussage:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Angenommen, X: Harry macht eine Fahrt
Y: Harry wird morgen laufen
Wir können die folgende symbolische Form verwenden, um diese Aussage auszudrücken:
X ∨ Y
Die Negation von X ∨ Y wird wie folgt beschrieben:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Zusammenfassend lautet die Negation der gegebenen Aussage:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Angenommen, X: Wenn ich gute Noten bekomme.
Y: Mein Cousin wird eifersüchtig sein.
Wir können die folgende symbolische Form verwenden, um diese Aussage auszudrücken:
X → Y
Die Negation von X → Y wird wie folgt beschrieben:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Zusammenfassend lautet die Negation der gegebenen Aussage:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Beispiel 8: In diesem Beispiel müssen wir die Negation einiger Aussagen mit Hilfe des Gesetzes von De Morgan schreiben. Diese Aussagen werden wie folgt beschrieben:
- Ich brauche einen Diamantenbesatz und einen Goldring im Wert.
- Du bekommst einen guten Job oder du bekommst keinen guten Partner.
- Ich nehme viel Arbeit in Anspruch und kann damit nicht umgehen.
- Mein Hund macht einen Ausflug oder macht im Haus Chaos.
Lösung: Die Negation aller Aussagen mit Hilfe des Gesetzes von De Morgan wird einzeln wie folgt beschrieben:
- Ich brauche keinen Diamantenbesatz oder keinen Goldring.
- Einen guten Job bekommt man nicht, dafür bekommt man einen guten Partner.
- Ich nehme mir nicht viel Arbeit, sonst kann ich damit umgehen.
- Mein Hund macht keinen Ausflug und macht im Haus kein Chaos.
Beispiel 9: In diesem Beispiel haben wir einige Aussagen und müssen die Negation dieser Aussagen schreiben. Die Aussagen werden wie folgt beschrieben:
- Wenn es regnet, wird der Plan, an den Strand zu gehen, gestrichen.
- Wenn ich fleißig lerne, werde ich bei der Prüfung gute Noten bekommen.
- Wenn ich bis spät in die Nacht auf eine Party gehe, werde ich von meinem Vater bestraft.
- Wenn Sie nicht mit mir sprechen möchten, müssen Sie meine Nummer sperren.
Lösung: Die Negation aller Aussagen wird einzeln wie folgt beschrieben:
- Wenn der Plan, an den Strand zu gehen, gestrichen wird, dann regnet es.
- Wenn ich bei der Prüfung gute Noten bekomme, lerne ich fleißig.
- Wenn ich von meinem Vater bestraft werde, gehe ich auf eine Late-Night-Party.
- Wenn du meine Nummer sperren musst, dann willst du nicht mit mir reden.
Beispiel 10: In diesem Beispiel müssen wir prüfen, ob (X → Y) → Z und X → (Y → Z) logisch äquivalent sind oder nicht. Wir müssen unsere Antwort mit Hilfe von Wahrheitstabellen und mit Hilfe von Regeln der Logik begründen, um beide Ausdrücke zu vereinfachen.
Lösung: Zunächst prüfen wir mit Methode 1, ob (X → Y) → Z und X → (Y → Z) logisch äquivalent sind, was wie folgt beschrieben wird:
Java-Webdienste
Methode 1: Dabei gehen wir von Folgendem aus:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
Und
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Methode 2: Jetzt verwenden wir die zweite Methode. Bei dieser Methode verwenden wir die Wahrheitstabelle.
| X | UND | MIT | X → Y | (X → Y) → Z | Y → Z | X → (Y → Z) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | T | T | T |
| T | F | F | F | T | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | F | F | T |
| F | F | T | T | T | T | T |
| F | F | F | T | F | T | T |
In dieser Wahrheitstabelle können wir sehen, dass die Spalten von (X → Y) → Z und X → (Y → Z) keine identischen Werte enthalten.