Tautologia i ciągi

[kuba7687]

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ą?

[musialmi]

A kiedy implikacja jest prawdziwa? Rozpatrz dwa przypadki.

[kuba7687]

Jakie dwa przypadki?

[wiedzmac]

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.

[kuba7687]

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.

[wiedzmac]

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.

[kuba7687]

\(\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}\).

[wiedzmac]

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

[kuba7687]

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ć

[Medea 2]

To rozpisuj tak długo, aż coś zobaczysz...

Kod: Zaznacz cały

# n = 4
{0, 0, 0, 1, 1}
{0, 0, 1, 0, 0}
{0, 1, 0, 1, 1}
{0, 1, 1, 0, 0}
{0, 1, 1, 1, 1}
{1, 0, 0, 0, 0}
{1, 0, 0, 1, 1}
{1, 0, 1, 0, 0}
{1, 1, 0, 1, 1}
{1, 1, 1, 0, 0}

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.

[kuba7687]

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}}\)?

[Medea 2]

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

[kuba7687]

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.