Mam takie zadanie, z którym nie mogę sobie poradzić:
Definiujemy \(\displaystyle{ p^{0}=p}\) i \(\displaystyle{ p^{1}= \neg 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{ < i_{0},...,i_{n-1}>}\) powyższe wyrażenie jest tautologią?
Z góry dziękuję za pomoc.
kiedy wyrażenie tautologią
-
patry93
- Użytkownik
- Posty: 1251
- Rejestracja: 30 sty 2007, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Koziegłówki/Wrocław
- Podziękował: 352 razy
- Pomógł: 33 razy
kiedy wyrażenie tautologią
Podbijam.
Ponoć taki trik się tu przyda - przypisujemy prawdzie 0, a fałszu(-owi?) 1, wtedy wartość logiczna \(\displaystyle{ p \Rightarrow q}\) okazuje się być równa \(\displaystyle{ q(1-p)}\).
Zatem wartość całego naszego wyrażenia, albo po formalnej indukcji, albo po "popatrzmy, że to tak działa", będzie wynosić:
\(\displaystyle{ p^{i_{n-1}}(1 -p^{i_{n-2}}(1 - \ldots p^{i_{2}}(1-p^{i_{1}}(1-p^{i_{0}})) \ldots )}\)
Ale jeszcze nie widzę, jak stąd wyciągnąć pasujący ciąg (bo raczej nie wymnażać?!)
Ponoć taki trik się tu przyda - przypisujemy prawdzie 0, a fałszu(-owi?) 1, wtedy wartość logiczna \(\displaystyle{ p \Rightarrow q}\) okazuje się być równa \(\displaystyle{ q(1-p)}\).
Zatem wartość całego naszego wyrażenia, albo po formalnej indukcji, albo po "popatrzmy, że to tak działa", będzie wynosić:
\(\displaystyle{ p^{i_{n-1}}(1 -p^{i_{n-2}}(1 - \ldots p^{i_{2}}(1-p^{i_{1}}(1-p^{i_{0}})) \ldots )}\)
Ale jeszcze nie widzę, jak stąd wyciągnąć pasujący ciąg (bo raczej nie wymnażać?!)
-
royas
- Użytkownik
- Posty: 363
- Rejestracja: 24 sie 2012, o 09:27
- Płeć: Mężczyzna
- Lokalizacja: Cieszyn
- Pomógł: 80 razy
kiedy wyrażenie tautologią
Kończące się na \(\displaystyle{ 00}\) lub \(\displaystyle{ 11}\).
Tworzymy nieskończone drzewo binarne z pustym korzeniem, w każdym lewym synu wpisujemy \(\displaystyle{ p}\), w prawym \(\displaystyle{ \neg p}\). Każda ścieżka od korzenia do dowolnego węzła odpowiada jednemu z badanych wyrażeń/ciągów. Każdy węzeł (oprócz korzenia) etykietujemy parą, lewy element oznacza wartość danego wyrażenia gdy \(\displaystyle{ v(p)=1}\), drugi gdy \(\displaystyle{ v(p)=0}\). Zauważamy, że etykieta węzła zależy jedynie od etykiety ojca oraz od tego czy jest to prawy czy lewy syn. Etykieta \(\displaystyle{ (0,0)}\) nie występuje.
Jeśli ojciec \(\displaystyle{ (1,1)}\) to lewy syn \(\displaystyle{ (1,0)}\), a prawy \(\displaystyle{ (0,1)}\).
Jeśli ojciec \(\displaystyle{ (0,1)}\) to lewy syn \(\displaystyle{ (1,0)}\), a prawy \(\displaystyle{ (1,1)}\).
Jeśli ojciec \(\displaystyle{ (1,0)}\) to lewy syn \(\displaystyle{ (1,1)}\), a prawy \(\displaystyle{ (0,1)}\).
Wyrażenia z \(\displaystyle{ (1,1)}\) to tautologie.
Zauważmy, że każde \(\displaystyle{ (1,1)}\) musi być lewym synem lewego syna, lub prawym synem prawego syna. Co daje nam ciągi kończące się na \(\displaystyle{ 00}\) lub \(\displaystyle{ 11}\).
Tworzymy nieskończone drzewo binarne z pustym korzeniem, w każdym lewym synu wpisujemy \(\displaystyle{ p}\), w prawym \(\displaystyle{ \neg p}\). Każda ścieżka od korzenia do dowolnego węzła odpowiada jednemu z badanych wyrażeń/ciągów. Każdy węzeł (oprócz korzenia) etykietujemy parą, lewy element oznacza wartość danego wyrażenia gdy \(\displaystyle{ v(p)=1}\), drugi gdy \(\displaystyle{ v(p)=0}\). Zauważamy, że etykieta węzła zależy jedynie od etykiety ojca oraz od tego czy jest to prawy czy lewy syn. Etykieta \(\displaystyle{ (0,0)}\) nie występuje.
Jeśli ojciec \(\displaystyle{ (1,1)}\) to lewy syn \(\displaystyle{ (1,0)}\), a prawy \(\displaystyle{ (0,1)}\).
Jeśli ojciec \(\displaystyle{ (0,1)}\) to lewy syn \(\displaystyle{ (1,0)}\), a prawy \(\displaystyle{ (1,1)}\).
Jeśli ojciec \(\displaystyle{ (1,0)}\) to lewy syn \(\displaystyle{ (1,1)}\), a prawy \(\displaystyle{ (0,1)}\).
Wyrażenia z \(\displaystyle{ (1,1)}\) to tautologie.
Zauważmy, że każde \(\displaystyle{ (1,1)}\) musi być lewym synem lewego syna, lub prawym synem prawego syna. Co daje nam ciągi kończące się na \(\displaystyle{ 00}\) lub \(\displaystyle{ 11}\).