Klasy abstrakcji relacji określonej na zbiorze formuł

[angus_parvis]

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

Proszę o pomoc w drugiej części zadania, ustaleniu liczby klas abstrakcji podanej relacji.

[bartek118]

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 \(\displaystyle{ 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?

[Dasio11]

Innymi słowy, dwie formuły są w relacji \(\displaystyle{ R}\) wtedy i tylko wtedy, gdy zadają te same funkcje boolowskie \(\displaystyle{ \{ 0, 1 \}^{n+1} \to \{ 0, 1 \}.}\) A ponieważ każda funkcja boolowska pochodzi od pewnej formuły, więc klas abstrakcji relacji \(\displaystyle{ R}\) jest tyle co takich funkcji boolowkisch.

[angus_parvis]

Czyli będzie to \(\displaystyle{ |\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.

[Jan Kraszewski]

Czyli będzie to \(\displaystyle{ |\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 \(\displaystyle{ n}\) zmiennych.

JK