Matematyka.pl

Definiujemy \(\displaystyle{ p^0=p, p^1=\sim p}\). Rozważmy wyrażenie postaci

\(\displaystyle{ (...( p^{ i_{0} } \Rightarrow p^{ i_{1} }) \Rightarrow ...) \Rightarrow p^{ i_{n-1} }}\)

Dla jakich ciągów \(\displaystyle{ \left\langle i_{0}, i_{1},..., i _{n-1} \right\rangle}\) powyższe wyrażenie jest tautologią?

A kiedy implikacja jest prawdziwa? Rozpatrz dwa przypadki.

Jakie dwa przypadki?

A kiedy implikacja jest prawdziwa?
Załóż na razie mamy wyrażenie typu \(\displaystyle{ A \Rightarrow B}\).
Spróbuj rozwiązać ten przypadek, a potem to uogólnimy.

Wtedy, gdy \(\displaystyle{ A}\) i \(\displaystyle{ B}\) są jednocześnie prawdziwe bądź fałszywe oraz gdy \(\displaystyle{ A}\) jest fałszywe, a \(\displaystyle{ B}\) prawdziwe.

Czyli na dobrą sprawę mamy dwa przypadki - kiedy \(\displaystyle{ B}\) jest prawdziwe i kiedy nie.
Wypisz teraz możliwe ciągi. Spróbuj analogiczne rozumowanie zastosować do przykładu z zadania.

\(\displaystyle{ p \Rightarrow p}\) oraz \(\displaystyle{ \sim p \Rightarrow \sim p}\), zatem dopuszczalnymi ciągami są \(\displaystyle{ \left\langle 0,0 \right\rangle, \left\langle 1,1 \right\rangle}\).

Ok, rozpisz sobie jeszcze co będzie dla \(\displaystyle{ 3,4,5}\) a potem spróbuj uogólnić to dla dowolnego \(\displaystyle{ n}\).

Prawidłowe są też ciągi:
\(\displaystyle{ \left\langle 1,0,0 \right\rangle, \left\langle 0,1,1 \right\rangle, \left\langle 0,0,0,0 \right\rangle, \left\langle 1,1,1,1 \right\rangle, \left\langle 0,1,0,0 \right\rangle, \left\langle 1,1,0,0 \right\rangle, \left\langle 0,0,1,1 \right\rangle, \left\langle 1,0,1,1 \right\rangle}\)

ale nie wiem jak to uogólnić

To rozpisuj tak długo, aż coś zobaczysz...
Jeżeli nadal nie widzisz żadnej zależności, to powiem Ci, że wytropiłam funkcję tworzącą (przy liczeniu takich ciągów): \(\displaystyle{ \frac{2 x}{1 -x - 2x^2}}\). Odpowiada ona rekurencji \(\displaystyle{ a_n = a_{n-1} + 2 a_{n-2}}\). Jeżeli nadal nie masz pojęcia, o co chodzi, to zacznij czytać swoje ciągi od końca.

Czyli te ciągi mogą być postaci takiej, że dla \(\displaystyle{ i_{k} \in \left\{ 0,1\right\}, k \in \mathbb{N}}\):

\(\displaystyle{ i_{n-1}=i _{n-2}}\) oraz \(\displaystyle{ i _{n-j}=i _{n-1} \vee i _{n-j} \neq i _{n-1}}\) dla \(\displaystyle{ j \in \mathbb{ N^{+} } \setminus \left\{ 1,2\right\}}\), przy czym dla \(\displaystyle{ n}\) nieparzystych może być również \(\displaystyle{ i _{0}=...=i _{n-1}}\)?

Nie za bardzo rozumiem to, co do mnie napisałeś. Po prostu policz, ile na końcu stoi zer.

No dwa pierwsze wyrazy od prawej muszą być sobie równe, każdy następny na lewo może być równy 1 lub 0, przy czym dla \(\displaystyle{ n}\) nieparzystych wszystkie wyrazy mogą być sobie równe.