Predikatlogik - kontraposition

Ax[P(x)->Q(x)]

Bevisa

Ax[notP(x)->notQ(x)]

Bevisa

Rent logiskt så är det väl rätt självklart, men jag måste skriva formellt bevis i med linjereferens.

Så hur är det bäst att börja. Är det Ok om jag börjar så här_ Jag är osäker på om jag helt sonika kan ange att det finns ett element a och anta notQ(a), eller om jag måste börja med att anta notQ(x) och därefter namnge elementet a....

1. Ax[P(x)->Q(x)]
2. (a) not Q(a)
3. P(a)
4. P(a)->Q(a) A Elim 1
5. Q(a) -> Elim 4
6. Contradiction Contra intro 2,5
7. notP(a) not intro 3,6
8. notQ(a)->notP(a) -> intro 2,7

9. Ax[notP(x)->notQ(x)] A intro 8

Prövat trädmetoden?

http://www.google.se/url?sa=t&source...h6P1Ng&cad=rja

Ett sätt att bevisa en sats genom att försöka hitta motsägelser till att den är sann.

Förstår jag rätt att du från "för alla x gäller att P(x) implicerar Q(x)" skall visa "för alla x gäller att icke P(x) implicerar icke Q(x)"? Detta går inte eftersom det inte är sant.

Exempel:
Låt vår universalmängd vara mängden av alla människor på jorden.
Låt P(x) betyda att x bor i Skåne.
Låt Q(x) betyda att x bor i Sverige.
Eftersom Skåne är en del av Sverige gäller att alla personer som bor i Skåne även bor i Sverige. Alltså "för alla x gäller att P(x) implicerar Q(x)".
Däremot gäller inte "för alla x gäller att icke P(x) implicerar icke Q(x)", vilket i detta fall skulle innebära att alla som inte bor i Skåne inte heller bor i Sverige. Jag är ett exempel på att påståendet inte är sant; jag bor i Stockholmsregionen, så jag bor inte i Skåne. Ändå bor jag i Sverige.

Men inte undra på att ingen svarar... när jag skriver av uppgiften fel. Nedan är den rätta. manne1973 har helt rätt, som jag skrev funkar inte.

Nedan i fetstil är den rätta.


Ax[P(x)->Q(x)]

Bevisa

Ax[notQ(x)->notP(x)]


Så vi har alltså:
Ax[P(x)->Q(x)]

Bevisa

Ax[notQ(x)->notP(x)]

Bevisa

Rent logiskt så är det väl rätt självklart, men jag måste skriva formellt bevis i med linjereferens.

Så hur är det bäst att börja. Är det Ok om jag börjar så här_ Jag är osäker på om jag helt sonika kan ange att det finns ett element a och anta notQ(a), eller om jag måste börja med att anta notQ(x) och därefter namnge elementet a....

1. Ax[P(x)->Q(x)]
2. (a) not Q(a)
3. P(a)
4. P(a)->Q(a) A Elim 1
5. Q(a) -> Elim 4
6. Contradiction Contra intro 2,5
7. notP(a) not intro 3,6
8. notQ(a)->notP(a) -> intro 2,7

9. Ax[notQ(x)->notP(x)] A intro 8[/quote]

Trodde att det skulle vara så.



Du kan namnge elementet a, men du kan inte säga att det finns. Universalmängden (som ∀ kvantifierar över) kan nämligen vara tom.


Ungefär så här skulle jag skriva:
1. Antag ∀x (P(x) → Q(x)).
2. Då P(a) → Q(a) för godtyckligt a genom ∀-elimination (1).
3. Antag P(a).
4. Då Q(a) genom →-elimination (2 och 3).
5. Antag ¬Q(a).
6. Då ⊥ (dvs motsägelse) genom →-elimination (4 och 5).
7. Alltså, ¬P(a) (egentligen P(a) → ⊥) genom →-introduktion (3 och 6).
8. Alltså, ¬Q(a) → ¬P(a) genom →-introduktion (5 och 7).
9. Då ∀x (¬Q(x) → ¬P(x)) genom ∀-introduktion (8) eftersom a var godtyckligt.

Och det är väl ungefär så du har skrivit...

Perfekt! Hur fick du så fina symboler?

Kopierat från andra sidor.