szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 18:53 
Użytkownik

Posty: 4
Lokalizacja: polska
Niech p_{0},...,p_{n} będą zmiennymi zdaniowymi. Definiujemy relację R na zbiorze Form(p_{0},...,p_{n}) (formuł o zmiennych p_{0},...,p_{n}):
xRy wtw. x\leftrightarrow y jest tautologią.
Pokaż, że relacja R jest relacją równoważności. Ile jest klas abstrakcji tej relacji (w zależności od n)?

Proszę o pomoc w drugiej części zadania, ustaleniu liczby klas abstrakcji podanej relacji.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 19:25 
Gość Specjalny

Posty: 5774
Lokalizacja: Toruń
Jest ich tyle, ile jest możliwych "kombinacji wyników".

Pomyśl o tym jak o funkcji, która przyjmuje jako argument ciąg długości n zer i jedynek, a zwraca liczbę zero lub jeden.

Lub patrząc inaczej - wyobraź sobie tabelę wartościowania dla takiej formuły -- ile jest możliwości ustawienia wyników w ostatniej kolumnie?
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 21:41 
Moderator
Avatar użytkownika

Posty: 7745
Lokalizacja: Wrocław
Innymi słowy, dwie formuły są w relacji R wtedy i tylko wtedy, gdy zadają te same funkcje boolowskie \{ 0, 1 \}^{n+1} \to \{ 0, 1 \}. A ponieważ każda funkcja boolowska pochodzi od pewnej formuły, więc klas abstrakcji relacji R jest tyle co takich funkcji boolowkisch.
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 22:37 
Użytkownik

Posty: 4
Lokalizacja: polska
Czyli będzie to |\lbrace 0,1\rbrace^{\lbrace 0,1\rbrace^{n+1}}|=2^{2^{n+1}}. Dzięki za pomoc, potraktowanie formuł zdaniowych jako funkcji logicznych bardzo pomogło.
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 23:07 
Administrator

Posty: 22534
Lokalizacja: Wrocław
angus_parvis napisał(a):
Czyli będzie to |\lbrace 0,1\rbrace^{\lbrace 0,1\rbrace^{n+1}}|=2^{2^{n+1}}.

Tylko pamiętaj, że ten wynik nie oznacza liczby klas abstrakcji dla n zmiennych.

JK
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Relacje i klasy abstrakcji - zadanie 2  Petermus  0
 Znaleźć moc klasy abstrakcji  act  23
 Zasada abstrakcji - dowód  Ingao  1
 Wykazać równość relacji, z jej odwrotnością.  Urbiacz  5
 Rodzina relacji  mathac  13
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl