Udowodnij tautologię - dwa zadania

[FanOfMath]

1. Przyporządkujemy wartości logicznej \(\displaystyle{ 0}\) liczbę naturalną \(\displaystyle{ 0}\) , zaś wartości logicznej \(\displaystyle{ 1}\) liczbę naturalną \(\displaystyle{ 1}\), wtedy funktory logiczne mogą być wyrażone w następujący sposób:

\(\displaystyle{ \neg p = 1-p \\
p \wedge q = \min (p,q) = pq \\
p \vee q = \max (p,q) = p+q-pq \\
p \Rightarrow q=1 - p + pq}\)

Udowodnić,że przy takiej interpretacji wyrażenie jest tautologią wtedy i tylko wtedy,gdy przy każdym układzie wartości przyjmuje wartość \(\displaystyle{ 1}\).

2.Udowodnić, że jeżeli wyrażenie \(\displaystyle{ \Psi}\) jest tautologią, to wyrażenie
\(\displaystyle{ \Phi_{1} \Rightarrow ( \Phi_{2} \Rightarrow ... \Rightarrow (\Phi_{n} \Rightarrow \Psi)...)}\)
także jest tautologią.

Jak tutaj będzie wyglądał formalny , indukcyjny dowód?
Indukcję umiem stosować w dziedzinach związanymi z liczbami naturalnymi, tutaj niestety nie wiem jak pokazać dowód indukcyjny.

[Jan Kraszewski]

Jak tutaj będzie wyglądał formalny , indukcyjny dowód?

Tak samo. Najpierw krok początkowy \(\displaystyle{ n=1}\), potem krok indukcyjny.

JK

[FanOfMath]

Jak tutaj będzie wyglądał formalny , indukcyjny dowód?

Tak samo. Najpierw krok początkowy \(\displaystyle{ n=1}\), potem krok indukcyjny.

JK

A co oznaczają te trzy kropki za nawiasem na końcu tego wyrażenia(za literką Psi)?

A więc :
1) dla \(\displaystyle{ n=1}\) mamy
\(\displaystyle{ \Phi_{1} \Rightarrow ( \Phi_{2} \Rightarrow ... \Rightarrow (\Phi_{1} \Rightarrow \Psi)...)}\)
Żeby to wyrażenie nie było tautologią ,to wartość logiczna wyrażenia \(\displaystyle{ \Phi_{1}}\) musiałaby wynosić 1 , natomiast wartość logiczna tego wyrażenia \(\displaystyle{ \Phi_{2} \Rightarrow ... \Rightarrow (\Phi_{1} \Rightarrow \Psi)...}\)musiałaby wynosić 0. Ale wartość logiczna \(\displaystyle{ (\Phi_{1} \Rightarrow \Psi)...)}\) wynosi 1 więc wartość logiczna tego wyrażenia \(\displaystyle{ ( \Phi_{2} \Rightarrow ... \Rightarrow (\Phi_{1} \Rightarrow \Psi)...)}\) nie może być równa 0 ,jako,że wartość logiczna następnika wynosi 1. Pokazaliśmy zatem , że to wyrażenie jest tautologią dla n=1.
2) Zakładam , że to wyrażenie jest prawdziwe dla \(\displaystyle{ k=n}\) , gdzie \(\displaystyle{ k\in \mathbb{ N^{+} }}\)
3)Teza:twiedzenie dla \(\displaystyle{ k+1}\)

\(\displaystyle{ \Phi_{1} \Rightarrow ( \Phi_{2} \Rightarrow ... \Rightarrow (\Phi_{k+1} \Rightarrow \Psi)...)}\)

4) Krok indukcyjny:
Wartość logiczna \(\displaystyle{ (\Phi_{k+1} \Rightarrow \Psi)...)}\) wynosi 1 więc wartość logiczna tego wyrażenia \(\displaystyle{ ( \Phi_{2} \Rightarrow ... \Rightarrow (\Phi_{k+1} \Rightarrow \Psi)...)}\) wynosi 1 . Zatem wartość naszego wyrażenia \(\displaystyle{ \Phi_{1} \Rightarrow ( \Phi_{2} \Rightarrow ... \Rightarrow (\Phi_{k+1} \Rightarrow \Psi)...)}\) wynosi 1 , jako , że następnik jest prawdziwy.



Ad 1
Nie wiem czy dobrze rozumiem to zadanie:
Należy tu pokazać , że to wyrażenie nie jest tautologią ,kiedy przyjmuje wartość 0. A dzieje się to gdy:
w wyrażeniu \(\displaystyle{ \ p \Rightarrow q}\) wartość \(\displaystyle{ p}\) przyjmuje wartość 1 natomiast \(\displaystyle{ q}\) przyjmuje wartosc 0 , ale wtedy pozostałe wyrażenia też się zgadzają.

[Jan Kraszewski]

A co oznaczają te trzy kropki za nawiasem na końcu tego wyrażenia(za literką Psi)?

Nawiasy.

1) dla \(\displaystyle{ n=1}\) mamy
\(\displaystyle{ \Phi_{1} \Rightarrow ( \Phi_{2} \Rightarrow ... \Rightarrow (\Phi_{1} \Rightarrow \Psi)...)}\)

Nie, nie tak. Dla \(\displaystyle{ n=1}\) mamy

\(\displaystyle{ \Phi_{1} \Rightarrow \Psi}\).

Krok indukcyjny też inaczej.

JK

[FanOfMath]

Mógłby Pan rzucić okiem na zadanie 1?

Nie, nie tak. Dla \(\displaystyle{ n=1}\) mamy
\(\displaystyle{ \Phi_{1} \Rightarrow \Psi}\).
JK

racja.

Co do kroku indukcyjnego to nie mam pomysłu , dopiero zaczynam swoją przygodę z udawadnianiem/dowodzeniem (problem wydaje się trywialny , no ale jednak w matematyce wszystko musi być uściślone) .

[Jan Kraszewski]

Co do kroku indukcyjnego to nie mam pomysłu , dopiero zaczynam swoją przygodę z udawadnianiem/dowodzeniem (problem wydaje się trywialny , no ale jednak w matematyce wszystko musi być uściślone) .

Wprowadź formułę pomocniczą \(\displaystyle{ \overline{\Psi}=\left( \Phi_{k+1} \Rightarrow \Psi\right)}\), skorzystaj względem niej z kroku pierwszego, a potem z zał indukcyjnego względem całości.

JK