logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Logika, zadanie nr 3738

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

moonlighter11
postów: 48
2015-10-31 14:39:35

Zdecyduj, jakie własności odpowiadają relacji S$\subset$XxX (zwrotna, symetryczna, przechodnia, antysymetryczna, całkowita):
a) xSy$\iff$|x-y|=0
b) xSy$\iff$x < y
c) xSy$\iff$|y-2|=|2-x|
d) xSy$\iff$|x-y|$\le$1


tumor
postów: 8070
2015-10-31 17:14:54

Więcej się na raz nie dało?
Po pierwsze należy w przypadku relacji podać $X$

a) zwrotna, symetryczna, przechodnia, antysymetryczna jest. Całkowita nie.
Zwrotność to oczywisty warunek $\mid x-x \mid =0$ prawdziwy dla każdego $x$,
Symetria wynika z tego, że $\mid x-y \mid = \mid y-x \mid$
Antysymetria z tego, że $\mid x-y \mid=0 \Rightarrow x=y$
i stąd także przechodniość.

b) zwrotna nie, symetryczna nie, antysymetryczna nie, całkowita nie, jest za to przechodnia

Rozumiesz w ogóle sprawdzane warunki?
Jak definiowaliście relację całkowitą?


moonlighter11
postów: 48
2015-10-31 19:22:13

Siedzę nad tym już długo i powoli zaczynam dopiero czaić o co chodzi z tym sprawdzaniem warunków.

Relację całkowitą definiowaliśmy jako:
Dla każdego x,y $\in$ X: [x=y $\vee$ xSy $\vee$ ySx]

Wiadomość była modyfikowana 2015-10-31 19:27:58 przez moonlighter11

tumor
postów: 8070
2015-10-31 21:17:32

b) to jednak jest "całkowita", dobrze, że się upewniłem. W literaturze ten warunek nazywa się raczej spójność.

Dla dowolnych x,y rzeczywistych prawdą jest co najmniej jedno ze zdań:
x<y
y<x
x=y

Zrób następne przykłady to sprawdzę. Wyręczać tak całkiem to nie będę.
-------

I powtórzę, że należy dla każdej relacji podać zbiór X, bo własności czasem od tego zbioru zależą.


moonlighter11
postów: 48
2015-11-01 10:49:27

c) zwrotna - tak, symetryczna - tak, antysymetryczna - tak, spójna - tak, przechodnia - nie wiem


d) zwrotna - tak, symetryczna - tak, antysymetryczna - nie, spójna - tak, przechodnia - nie wiem

Niestety mam problem z przechodniością, nie za bardzo ten warunek przechodniości rozumiem.

Wiadomość była modyfikowana 2015-11-01 11:48:42 przez moonlighter11

tumor
postów: 8070
2015-11-02 11:01:14

c)
Nie jest antysymetryczna. Na przykład
4S0 oraz 0S4

Przechodnia jest, bo
jeśli założymy $\mid y-2 \mid=\mid 2-x\mid $
oraz $\mid z-2 \mid=\mid 2-y\mid$
to mamy
$\mid z-2 \mid=\mid 2-y\mid =\mid y-2 \mid=\mid 2-x\mid $
czyli
$xSz$

Spójna nie jest. Spójna mówi, że dla dowolnych x,y zachodzi co najmniej jeden z trzech warunków
xSy
ySx
y=x

Tu dla x=100, y=2 nie zachodzi żaden z nich.


------------------

Warunek przechodniości działa jak "bycie potomkiem". Jeśli X jest potomkiem Y, a Y jest potomkiem Z, to chyba rozumiesz, że X musi być także potomkiem Z.

Tak samo działa "bycie większym". Jeśli X jest większy od Y i Y jest większy od Z, to X musi być większy od Z.

Nie w każdej relacji mamy przechodniość. Możemy mieć drużyny piłkarskie takie, że X pokonuje Y, Y pokonuje Z, ale niekoniecznie X jest w stanie pokonać Z.

-----

d)
jest zwrotna i symetryczna.
Nie jest antysymetryczna, co potwierdzamy jakimś przykładem
x=1, y=0
Spójna nie jest. Na przykład x=3, y=0 nie jest prawdą ŻADEN z warunków
x=y
xSy
ySx
Przechodnia nie jest.
Na przykład x=0,y=1,z=2.
Mamy xSy oraz ySz, ale nie jest prawdą xSz.


moonlighter11
postów: 48
2015-11-03 20:05:11

Obawiam się, że jednak nie do końca te sprawdzane warunki rozumiem. Byłbym wdzięczny, gdybyś mógł mi je wszystkie zdefiniować.



moonlighter11
postów: 48
2015-11-03 20:26:57

Mam jeszcze takie 2 problemy. Podam je na przykładzie d):

xSy$\iff$|x-y|<=1

1. problem
Mam do sprawdzenia np. relację przechodniości, czyli zapisuję:
[(|x-y|<=1 $\wedge$ |y-z|<=1) $\Rightarrow$ |x-z|<=1]

I teraz nie rozumiem tego dowolnego podstawiania liczb. Dla każdego x,y,z mogę podstawić dowolną liczbę. Ale czy jeśli podstawię np. x=1, y=6, z=-15 to |x-y|<=1 już się nie będzie zgadzało, a przecież było podane na początku, że xSy$\iff$|x-y|<=1, czyli musi się zgadzać.

2. problem
Jeśli sprawdzam np. warunek przechodniości dla xSy$\iff$|x-y|<=1, czyli piszę [(|x-y|<=1 $\wedge$ |y-z|<=1) $\Rightarrow$ |x-z|<=1], to czy jeśli podstawię dowolne wartości x=1, y=6, z=-15, to jestem zmuszony zastosować je dla każdego działania? Czy mogę przykładowo dla |y-z|<=1 podstawić z=100, a dla |x-z|<=1 mogę już podstawić np. z=45?

Wiadomość była modyfikowana 2015-11-03 20:27:50 przez moonlighter11

tumor
postów: 8070
2015-11-03 21:46:53

1. Masz implikację.
$p \Rightarrow q$

Implikacja jest FAŁSZYWA gdy p jest prawdą, a q jest fałszem. W każdym innym przypadku jest prawdziwa. Badanie przechodniości to sprawdzanie, czy implikacja może być fałszywa (wtedy relacja nie jest przechodnia), czy musi być prawdziwa.

Zatem relacja NIE JEST przechodnia wtedy, jeśli znajdujemy x,y,z, że warunki po lewej stronie implikacji są spełnione, a warunek po prawej stronie jest niespełniony (czyli ten jedyny przypadek, gdy implikacja jest fałszywa).

W przypadku relacji d) można podać x=1, y=2, z=3.
Mamy $\mid 1-2\mid \le 1$ (czyli prawdą jest xSy)
$\mid 2-3\mid \le 1$ (czyli prawdą jest ySz)
ale zarazem nie jest prawdą
$\mid 1-3\mid \le 1$ (czyli nie jest prawdą xSz).
Znalezienie takiej trójki oznacza, że przechodnia nie jest. Jeśli natomiast niemożliwe jest znalezienie takiego przykładu, to przechodnia by była.

-----

Dalej do problemu 1:
xSy oznacza, że x,y są w relacji S. Nie każde dwie liczby muszą być w relacji. W tym przypadku prawdą jest 1S2 (bo spełniony jest warunek $\mid 1-2\mid \le 1$, ale nieprawdą jest 1S3 (co się zapisuje $\neg 1S3$ albo $(1,3)\notin S$, niespełniony jest warunek $\mid 1-3\mid \le 1$).

Sprawdzając na przykład zwrotność sprawdzasz, czy zawsze musi być xSx.
Sprawdzając przechodniość sprawdzasz, czy JEŚLI jest xSy i ySz, to musi być także xSz.
Jeśli chcesz pokazać, że nie jest zwrotna, wystarczy pojedynczy przykład x, dla którego nieprawdą jest, że xSx.
Jeśli chcesz pokazać, że nie jest przechodnia, potrzebujesz już takich x,y,z że spełnione są warunki xSy i ySz, a jednocześnie niespełniony jest warunek xSz (co daje fałszywą implikację).

-----

2. W obrębie jednej formuły, na przykład
$ [(\mid x-y\mid \le 1 \wedge \mid y-z\mid \le 1) \Rightarrow \mid x-z\mid \le 1]$,
zmienne x,y,z mają tylko jedno znaczenie. Czyli jeśli sobie obierasz za przykład $x=1,y=2,z=3$, to takie podstawienie obowiązuje w całej formule.

Wiadomość była modyfikowana 2015-11-03 22:15:10 przez tumor

moonlighter11
postów: 48
2015-11-03 21:55:32

Chyba nareszcie to zrozumiałem, bardzo dziękuję za pomoc!

Jeszcze tylko jedno drobne pytanie: czy mogę za x,y,z podstawić tą samą wartość, np. x=1, y=1, z=1?

Wiadomość była modyfikowana 2015-11-03 21:56:26 przez moonlighter11
strony: 1 2

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt online: 20 drukuj