Udowodnić że to tautologia

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
Abstract
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 21 lut 2019, o 21:42
Płeć: Mężczyzna
Podziękował: 18 razy

Udowodnić że to tautologia

Post autor: Abstract »

Zad. Które spośród zdań są tautologiami: \(\displaystyle{ p \Rightarrow p, (p \Rightarrow p) \Rightarrow p, ((p \Rightarrow p) \Rightarrow p) \Rightarrow p, ...}\)

Tautologiami będą te zdania których ilość implikacji jest nieparzysta czyli \(\displaystyle{ 2n + 1}\)
Staram się to udowodnić za pomocą indukcji:
1. \(\displaystyle{ (p \Rightarrow p) \Leftrightarrow 1}\) bez względu na wartość p.
2. Zakładam, że dla nieparzystej ilość implikacji zdanie to jest tautologią a następnie implikuje zdanie z założenia(\(\displaystyle{ 1 \Rightarrow 0 \Leftrightarrow 0}\)) a potem jeszcze raz więc znów otrzymuje zdanie prawdziwe dla \(\displaystyle{ 2n+3}\) czyli \(\displaystyle{ 2(n+1) + 1}\).
Czy tak ma wyglądać ta indukcja? Z góry dziękuje.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Udowodnić że to tautologia

Post autor: Dasio11 »

Pomysł dobry, ale wykonanie kiepskie. Żeby udowodnić coś indukcyjnie, trzeba najpierw dokładnie sformułować tezę indukcyjną. W tym przypadku jest ona taka:

Dla każdej liczby naturalnej \(\displaystyle{ n \ge 1}\), jeśli \(\displaystyle{ n}\) jest nieparzyste, to formuła \(\displaystyle{ \varphi_n = \underbrace{(\ldots(((p \Rightarrow p) \Rightarrow p) \Rightarrow p)\ldots) \Rightarrow p}_{n \text{ implikacji}}}\) jest tautologią, jeśli zaś \(\displaystyle{ n}\) jest parzyste, to owa formuła jest równoważna \(\displaystyle{ p}\).

W szczególności zwróć uwagę, że żeby dowód indukcyjny wyszedł, musimy przypadek parzyście wielu implikacji scharakteryzować dokładniej, niż tylko stwierdzając, że formuła nie jest tautologią - potrzebujemy wiedzieć, że formuła jest równoważna \(\displaystyle{ p}\), co jest stwierdzeniem mocniejszym.

Następnie trzeba naszą tezę porządnie uzasadnić:

1. Dla \(\displaystyle{ n = 1}\) formuła \(\displaystyle{ \varphi_1 = p \Rightarrow p}\) jest oczywiście tautologią.
2. Ustalmy dowolną liczbę naturalną \(\displaystyle{ n \ge 1}\) i przypuśćmy, że teza indukcyjna jest prawdziwa dla \(\displaystyle{ n}\). Potrzebujemy wykazać, iż jest ona prawdziwa dla \(\displaystyle{ n+1}\). Rozważmy w tym celu dwa przypadki: \(\displaystyle{ n}\) jest liczbą parzystą bądź liczbą nieparzystą.

Jeśli \(\displaystyle{ n}\) jest liczbą nieparzystą, to \(\displaystyle{ n+1}\) jest parzyste, chcemy zatem wykazać, że \(\displaystyle{ \varphi_{n+1}}\) jest równoważne \(\displaystyle{ p}\). Jednak \(\displaystyle{ \varphi_{n+1} = \varphi_n \Rightarrow p}\), skoro zaś - na mocy założenia indukcyjnego - \(\displaystyle{ \varphi_n}\) jest tautologią, to tabelka formuły \(\displaystyle{ \varphi_n \Rightarrow p}\) przedstawia się następująco:

\(\displaystyle{ \begin{array}{|c|c|c|} \hline
p & \varphi_n & (\varphi_n \Rightarrow p) \\ \hline
0 & 1 & 0 \\ \hline
1 & 1 & 1 \\ \hline
\end{array}}\)


a zatem \(\displaystyle{ \varphi_{n+1}}\) jest równoważna \(\displaystyle{ p}\).

Załóżmy w takim razie, że \(\displaystyle{ n}\) jest liczbą parzystą, a więc \(\displaystyle{ n+1}\) jest nieparzyste. Wykażemy, że \(\displaystyle{ \varphi_{n+1}}\) jest tautologią. Znów \(\displaystyle{ \varphi_{n+1} = \varphi_n \Rightarrow p}\) oraz - na mocy założenia indukcyjnego - formuła \(\displaystyle{ \varphi_n}\) jest równoważna \(\displaystyle{ p}\), zatem tym razem tabelka \(\displaystyle{ \varphi_{n+1}}\) wygląda tak:

\(\displaystyle{ \begin{array}{|c|c|c|} \hline
p & \varphi_n & (\varphi_n \Rightarrow p) \\ \hline
0 & 0 & 1 \\ \hline
1 & 1 & 1 \\ \hline
\end{array}}\)


i w konsekwencji: \(\displaystyle{ \varphi_{n+1}}\) jest tautologią, co kończy dowód indukcyjny.
Ostatnio zmieniony 21 cze 2019, o 22:28 przez Dasio11, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Abstract
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 21 lut 2019, o 21:42
Płeć: Mężczyzna
Podziękował: 18 razy

Re: Udowodnić że to tautologia

Post autor: Abstract »

Dasio11 pisze:

W szczególności zwróć uwagę, że żeby dowód indukcyjny wyszedł, musimy przypadek parzyście wielu implikacji scharakteryzować dokładniej, niż tylko stwierdzając, że formuła nie jest tautologią - potrzebujemy wiedzieć, że formuła jest równoważna \(\displaystyle{ p}\), co jest stwierdzeniem mocniejszym.
Tego nie rozumiem. Dlaczego mocniejszym ?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Udowodnić że to tautologia

Post autor: Dasio11 »

Dlatego że z faktu, że formuła zmiennej \(\displaystyle{ p}\) nie jest tautologią, nie wynika jeszcze, że jest ona równoważna \(\displaystyle{ p}\). Tautologią jest formuła o tabelce:

\(\displaystyle{ \begin{array}{|c|c|} \hline p & \varphi \\ \hline 0 & 1 \\ \hline 1 & 1 \\ \hline \end{array}}\)

zatem formuła niebędąca tautologią może mieć dowolną z trzech pozostałych tabelek:

\(\displaystyle{ \begin{array}{|c|c|} \hline p & \varphi \\ \hline 0 & 0 \\ \hline 1 & 0 \\ \hline \end{array} \quad
\begin{array}{|c|c|} \hline p & \varphi \\ \hline 0 & 1 \\ \hline 1 & 0 \\ \hline \end{array} \quad
\begin{array}{|c|c|} \hline p & \varphi \\ \hline 0 & 0 \\ \hline 1 & 1 \\ \hline \end{array}}\)


ale tylko w jednym z tych przypadków \(\displaystyle{ \varphi}\) jest równoważna \(\displaystyle{ p}\).
ODPOWIEDZ