Witam.
Mam takie zadanie ażeby sprawdzić czy wyrażenie jest tautologią.
Mój znajomy rozwiązał to w ten sposób, jednak nie jestem pewien czy jest to zrobione prawidłowo, mianowicie samemu wyszło mi coś innego.
Dlatego chciałbym prosić o weryfikację tego rozwiązania.
\(\displaystyle{ [ \forall x (p(x)) \implies \forall x (q(x)) ] \implies [ \forall x(p(x) \implies q(x))]}\)
"dowód nie wprost przez kontrapozycję"
Niech \(\displaystyle{ \forall x(p(x) \implies q(x))}\) jest fałszywe
Wtedy \(\displaystyle{ \exists x \neg (p(x) \implies q(x))}\)
Czyli jest \(\displaystyle{ \exists x (p(x) \wedge \neg q(x))}\)
Czyli jest taki x, że p(x) prawdziwe i q(x) nieprawdziwe.
Zatem \(\displaystyle{ \forall x (p(x)) \implies \forall x (q(x)) }\) nie jest prawdziwe
Czyli całość jest tautologią.
Sprawdź czy podane wyrażenie jest tautologią (kwantyfikatory)
-
- Użytkownik
- Posty: 3
- Rejestracja: 20 lis 2021, o 23:41
- Płeć: Mężczyzna
- wiek: 22
- Podziękował: 1 raz
-
- Użytkownik
- Posty: 22209
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Sprawdź czy podane wyrażenie jest tautologią (kwantyfikatory)
To za mało, żeby wyciągnąć taki wniosek.ColumbusTheBox pisze: ↑20 lis 2021, o 23:57
Czyli jest taki x, że p(x) prawdziwe i q(x) nieprawdziwe.
Zatem \(\displaystyle{ \forall x (p(x)) \implies \forall x (q(x)) }\) nie jest prawdziwe
Czyli całość jest tautologią.
-
- Administrator
- Posty: 34276
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Sprawdź czy podane wyrażenie jest tautologią (kwantyfikatory)
Niby dlaczego?ColumbusTheBox pisze: ↑20 lis 2021, o 23:57Czyli jest taki x, że p(x) prawdziwe i q(x) nieprawdziwe.
Zatem \(\displaystyle{ \forall x (p(x)) \implies \forall x (q(x)) }\) nie jest prawdziwe
Tym bardziej, że to nie jest tautologia.
JK
-
- Użytkownik
- Posty: 3
- Rejestracja: 20 lis 2021, o 23:41
- Płeć: Mężczyzna
- wiek: 22
- Podziękował: 1 raz
Re: Sprawdź czy podane wyrażenie jest tautologią (kwantyfikatory)
Też mi coś nie pasuje tutaj.
Dowód przez kontrapozycję wygląda tak:
\(\displaystyle{
(p \implies q) \Leftrightarrow (\neg q \implies \neg p)
}\)
Zatem wychodzi coś takiego:
\(\displaystyle{
\exists x (p(x) \wedge \neg q(x)) \implies \neg [ \forall x (p(x)) \implies \forall x (q(x))]
}\)
Po przekształceniu:
\(\displaystyle{
\exists x (p(x) \wedge \neg q(x)) \implies [ \forall x (p(x)) \wedge \exists x \neg (q(x))]
}\)
Czyli mamy tak:
istnieje jakiś 'x', który jednocześnie ma właściwość 'p' i nie ma właściwości 'q'
=>
każdy x ma właściwość 'p' i jednocześnie istnieje x, który nie ma właściwości 'q'
To co widać na przekształceniu nie ma chyba za bardzo sensu, sam fakt istnienia jakiegoś x który ma właściwość 'p' i nie ma właściwości 'q' nie implikuje przecież, że każdy x ma właściwość 'p', czy dobrze rozumuję?
Dodano po 16 minutach 26 sekundach:
EDIT:
W każdym razie chciałbym jeszcze zapytać czy mój kontrprzykład jest prawidłowy?
\(\displaystyle{
x \in \NN\\
p(x) = x > 5\\
q(x) = x < 5}\)
\(\displaystyle{
[( \forall x \in \NN (x > 5) \implies \forall x \in \NN (x<5)] \implies \forall x \in \NN (x > 5 \implies x < 5)
}\)
W skrócie (jeżeli dobrze myślę) poprzednik będzie wyglądał tak [0 => 0] czyli będzie miał wartość PRAWDA.
Następnik z kolei będzie miał wartość FAŁSZ, gdyż chociaż by dla x = 6, implikacja
\(\displaystyle{
\forall x \in \NN (x > 5 \implies x < 5)
}\)
przyjmuje wartość fałsz, więc nie zachodzi dla każdego x.
Postać całego wyrażenia przyjmie formę [1 => 0] czyli jego wartością jest FAŁSZ.
Zatem całość nie jest tautologią.
Dowód przez kontrapozycję wygląda tak:
\(\displaystyle{
(p \implies q) \Leftrightarrow (\neg q \implies \neg p)
}\)
Zatem wychodzi coś takiego:
\(\displaystyle{
\exists x (p(x) \wedge \neg q(x)) \implies \neg [ \forall x (p(x)) \implies \forall x (q(x))]
}\)
Po przekształceniu:
\(\displaystyle{
\exists x (p(x) \wedge \neg q(x)) \implies [ \forall x (p(x)) \wedge \exists x \neg (q(x))]
}\)
Czyli mamy tak:
istnieje jakiś 'x', który jednocześnie ma właściwość 'p' i nie ma właściwości 'q'
=>
każdy x ma właściwość 'p' i jednocześnie istnieje x, który nie ma właściwości 'q'
To co widać na przekształceniu nie ma chyba za bardzo sensu, sam fakt istnienia jakiegoś x który ma właściwość 'p' i nie ma właściwości 'q' nie implikuje przecież, że każdy x ma właściwość 'p', czy dobrze rozumuję?
Dodano po 16 minutach 26 sekundach:
EDIT:
O proszę, czyli chyba dobrze myślałem, a próbowałem już z 2/3 godziny dojść do tego dlaczego wyszła mu (znajomemu) ta tautologia. Tym bardziej, że jego rozwiązanie potwierdził student starszego roku...
W każdym razie chciałbym jeszcze zapytać czy mój kontrprzykład jest prawidłowy?
\(\displaystyle{
x \in \NN\\
p(x) = x > 5\\
q(x) = x < 5}\)
\(\displaystyle{
[( \forall x \in \NN (x > 5) \implies \forall x \in \NN (x<5)] \implies \forall x \in \NN (x > 5 \implies x < 5)
}\)
W skrócie (jeżeli dobrze myślę) poprzednik będzie wyglądał tak [0 => 0] czyli będzie miał wartość PRAWDA.
Następnik z kolei będzie miał wartość FAŁSZ, gdyż chociaż by dla x = 6, implikacja
\(\displaystyle{
\forall x \in \NN (x > 5 \implies x < 5)
}\)
przyjmuje wartość fałsz, więc nie zachodzi dla każdego x.
Postać całego wyrażenia przyjmie formę [1 => 0] czyli jego wartością jest FAŁSZ.
Zatem całość nie jest tautologią.
Ostatnio zmieniony 21 lis 2021, o 01:23 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Administrator
- Posty: 34276
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Sprawdź czy podane wyrażenie jest tautologią (kwantyfikatory)
Tak.ColumbusTheBox pisze: ↑21 lis 2021, o 01:08W każdym razie chciałbym jeszcze zapytać czy mój kontrprzykład jest prawidłowy?
JK
-
- Użytkownik
- Posty: 3
- Rejestracja: 20 lis 2021, o 23:41
- Płeć: Mężczyzna
- wiek: 22
- Podziękował: 1 raz