Dowód spełnialności formuły

[vicossess]

Chciałbym spytać o poprawność mojego dowodu - Zadanie brzmi tak: Które z poniższych zdań są prawdziwe dla dowolnych formuł zdaniowych \(\displaystyle{ \phi}\) i \(\displaystyle{ \psi}\):
Zdanie takie:
Jeśli \(\displaystyle{ \phi \Rightarrow \psi}\) oraz \(\displaystyle{ \neg \phi \Rightarrow \psi}\) są spełnialne, to \(\displaystyle{ \psi}\) jest spełnialna.

Dowód:

Ukryta treść:    

Załóżmy nie wprost, że teza jest fałszywa, czyli \(\displaystyle{ \psi}\) jest sprzeczne (innymi słowy fałszywe dla każdego wartościowania \(\displaystyle{ \sigma}\)). Doprowadzimy, że któraś z formuł \(\displaystyle{ \phi \Rightarrow \psi}\), \(\displaystyle{ \neg \phi \Rightarrow \psi}\) jest sprzeczna. W takim razie dla każdego wartościowania \(\displaystyle{ \sigma}\) zajdzie \(\displaystyle{ \hat{\sigma}(\psi) = F}\). Zauważmy także, że jedno ze zdań \(\displaystyle{ \phi, \neg \phi}\) musi być prawdziwe. W takim razie, bez straty ogólności uznajmy, że \(\displaystyle{ \hat{\sigma}(\phi) = T}\). Z tego wynika, że \(\displaystyle{ \hat{\sigma}(\phi \Rightarrow \psi) = F}\) dla każdego wartościowania \(\displaystyle{ \sigma}\) co kończy dowód nie wprost.

I mam jeszcze pytania teoretyczne (chcę się upewnić):
1. Czy jeśli formuła jest tautologią, to jest jednocześnie spełnialna? (Mniemam, że to działa tak, że każda tautologia jest spełnialna, ale nie każda formuła spełnialna jest tautologią oczywiście)
2. Zaprzeczenie, że 'formuła jest sprzeczna' oznacza, że formuła jest spełnialna, ale niekoniecznie jest tautologią, tak jest?
3. Jaka jest różnica, między oznaczeniem \(\displaystyle{ \hat{\sigma}(\phi) = T}\) a \(\displaystyle{ \sigma(\phi) = T}\)?

[Cytryn]

1. Tak. "Definicja tautologii w klasycznym rachunku zdań przedstawia się następująco: Wyrażenie W jest tautologią klasycznego rachunku zdań, wtedy i tylko wtedy, gdy przy każdym podstawieniu stałych za zmienne przechodzi w zdanie prawdziwe." - źródło: Wikipedia.

[Jan Kraszewski]

2. Tak.

3. Zapewne \(\displaystyle{ \sigma}\) jest wartościowaniem zmiennych zdaniowych, a \(\displaystyle{ \hat{\sigma}}\) jest rozszerzeniem tego wartościowania na zbiór wszystkich formuł rachunku zdań.

JK

[vicossess]

Dziękuję za odpowiedzi. Co prawda nikt mnie nie upewnił w sprawie poprawności dowodu w pierwszym poście, ale strzelam, że skoro moje przemyślenia teoretyczne były prawidłowe, to przemyślenia w dowodzie również

[Jan Kraszewski]

Prawidłowe, choć gdyby dowód miał być formalny, to zażądałbym uzasadnienia, dlaczego

Zauważmy także, że jedno ze zdań \(\displaystyle{ \phi, \neg \phi}\) musi być prawdziwe.

i

Z tego wynika, że \(\displaystyle{ \hat{\sigma}(\phi \Rightarrow \psi) = F}\) dla każdego wartościowania \(\displaystyle{ \sigma}\)

a uzasadnienie musiałoby się odwoła do formalnej definicji \(\displaystyle{ \hat{\sigma}.}\) Ale jak nie musimy być bardzo formalni, to jest OK.

JK

edit: To jednak nie jest poprawne rozumowanie - patrz niżej.

[vicossess]

Sprawa wygląda tak, że raczej muszę być bardzo formalny, więc spróbuję 'naprawić' dowód rozważając dwa przypadki:
Z faktu, że \(\displaystyle{ \hat{\sigma}}\) przypisuje wartości logiczne formułom zdaniowym, czyli przekształca je na zbiór dwuelementowy \(\displaystyle{ \left\{ T, F\right\}}\) to są dwa przypadki
1.
Jeśli \(\displaystyle{ \hat{\sigma}(\phi) = F}\), wtedy zachodzi \(\displaystyle{ \hat{\sigma}(\neg\phi) = T}\), czyli wtedy \(\displaystyle{ \hat{\sigma}(\neg\phi \Rightarrow \psi) = F}\) (mało formalnie rzecz ujmując z prawdy wynikać fałsz nie może, a formalniej: Implikacja jest fałszywa wtedy i tylko wtedy poprzednik implikacji jest prawdziwy i następnik implikacji jest fałszywy)
2.
Jeśli \(\displaystyle{ \hat{\sigma}(\phi) = T}\),wtedy \(\displaystyle{ \hat{\sigma}(\phi \Rightarrow \psi) = F}\)

W każdym z przypadków otrzymaliśmy żądaną sprzeczność, co kończy dowód nie wprost.

[Jan Kraszewski]

No nie, nie to miałem na myśli. To jest dalej dowód intuicyjny, tylko dokładniej zapisany. Choć być może na Twoje potrzeby zupełnie wystarczy.

Pisząc "dowód formalny" miałem na myśli taki, który odwołuje się do rekurencyjnej definicji \(\displaystyle{ \hat{\sigma}}\).

JK

[vicossess]

Czy definicja rekurencyjna w tym wypadku polega na takich zapisach jak poniżej?
\(\displaystyle{ \hat{\sigma}(\phi) = \sigma(\phi)}\)
\(\displaystyle{ \hat{\sigma}(\neg\phi) = \begin{cases} T \Leftrightarrow \hat{\sigma}(\phi) = F \\ F \Leftrightarrow \hat{\sigma}(\phi) = T \end{cases}}\)
\(\displaystyle{ \hat{\sigma}(\phi_1 \Rightarrow \phi_2) = \begin{cases} F \Leftrightarrow \hat{\sigma}(\phi_1) = T \wedge \hat{\sigma}(\phi_2) = T \\ T, w p.p. \end{cases}}\)

I jeszcze poprosiłbym o wskazówkę w wykazaniu takiego zdania (Polecenie do zadania takie jak w pierwszym poście)
Jeśli \(\displaystyle{ \phi \Rightarrow \psi}\) jest tautologią oraz \(\displaystyle{ \neg\phi \Rightarrow \psi}\) jest spełnialna, to \(\displaystyle{ \psi}\) jest spełnialna.

Czy w przypadku takiego zadania mogę rozważyć wszystkie możliwe wartościowania, które spełniają początek (ta pierwsza formuła jest tautologią, a druga spełnialna) i pokazać, że istnieje wśród tych wartościowań takie, dla którego formuła na końcu jest tautologią?

[Jan Kraszewski]

Czy definicja rekurencyjna w tym wypadku polega na takich zapisach jak poniżej?
\(\displaystyle{ \hat{\sigma}(\phi) = \sigma(\phi)}\)

Raczej \(\displaystyle{ \hat{\sigma}(p) = \sigma(p)}\) dla dowolnej zmiennej zdaniowej \(\displaystyle{ p}\).

\(\displaystyle{ \hat{\sigma}(\neg\phi) = \begin{cases} T \Leftrightarrow \hat{\sigma}(\phi) = F \\ F \Leftrightarrow \hat{\sigma}(\phi) = T \end{cases}}\)
\(\displaystyle{ \hat{\sigma}(\phi_1 \Rightarrow \phi_2) = \begin{cases} F \Leftrightarrow \hat{\sigma}(\phi_1) = T \wedge \hat{\sigma}(\phi_2) = T \\ T, w p.p. \end{cases}}\)

No cóż, ja definiuję wartościowanie jako funkcję zero-jedynkową i wtedy definiuję to arytmetycznie. Używając \(\displaystyle{ F,T}\) musisz robić tak, jak powyżej.

I jeszcze poprosiłbym o wskazówkę w wykazaniu takiego zdania (Polecenie do zadania takie jak w pierwszym poście)
Jeśli \(\displaystyle{ \phi \Rightarrow \psi}\) jest tautologią oraz \(\displaystyle{ \neg\phi \Rightarrow \psi}\) jest spełnialna, to \(\displaystyle{ \psi}\) jest spełnialna.

Czy w przypadku takiego zadania mogę rozważyć wszystkie możliwe wartościowania, które spełniają początek (ta pierwsza formuła jest tautologią, a druga spełnialna) i pokazać, że istnieje wśród tych wartościowań takie, dla którego formuła na końcu jest tautologią?

Jaką tautologią, jak formuła na końcu ma być spełnialna?

Możesz zrobić to rozumowanie nie wprost.

JK

[vicossess]

Oczywiście, że chodziło o bycie spełnialną - moje niedopatrzenie - istnieje wartościowanie, dla którego formuła jest prawdziwa. A rozpatrzenie 'tabelki', formalnie patrząc, jest prawidłowe?

Próbowałem nie wprost, ale nie jestem przekonany do tego. Nie wprost musimy wykazać, że jeśli \(\displaystyle{ \psi}\) jest formułą sprzeczną to \(\displaystyle{ \phi \Rightarrow \psi}\) nie jest tautologią (istnieje wartościowanie, że formuła ta jest fałszywa) lub \(\displaystyle{ \neg\phi \Rightarrow \psi}\) jest sprzeczna, dobrze myślę?

[Jan Kraszewski]

Oczywiście, że chodziło o bycie spełnialną - moje niedopatrzenie - istnieje wartościowanie, dla którego formuła jest prawdziwa. A rozpatrzenie 'tabelki', formalnie patrząc, jest prawidłowe?

Co rozumiesz przez "rozpatrzenie tabelki"?

Próbowałem nie wprost, ale nie jestem przekonany do tego. Nie wprost musimy wykazać, że jeśli \(\displaystyle{ \psi}\) jest formułą sprzeczną to \(\displaystyle{ \phi \Rightarrow \psi}\) nie jest tautologią (istnieje wartościowanie, że formuła ta jest fałszywa) lub \(\displaystyle{ \neg\phi \Rightarrow \psi}\) jest sprzeczna, dobrze myślę?[/quote]
Dobrze, przy czym sprzeczność z jednym z założeń otrzymujesz wykorzystując drugie z założeń.

JK

[vicossess]

I chciałbym wrócić do zadania na samym początku - okazuje się (na co mój znajomy zwrócił mi uwagę), że podstawiając za formułę \(\displaystyle{ \phi}\) wyrażenie \(\displaystyle{ p \vee q}\) a za wyrażenie \(\displaystyle{ \psi}\) formułę sprzeczną \(\displaystyle{ p \wedge \neg p}\) dostajemy wnioski następujące:
1. Formuły \(\displaystyle{ p \vee q \Rightarrow p \wedge \neg p}\) oraz \(\displaystyle{ \neg p \wedge \neg q \Rightarrow p \wedge \neg p}\) są jak najbardziej spełnialne. (Możemy rozpatrzeć dwa różne wartościowania, dla których formuła \(\displaystyle{ p \vee q}\) będzie dawała raz fałsz, raz prawdę i obie z implikacji będą spełnialne)
2. Formuła \(\displaystyle{ \psi = p \wedge \neg p}\) jest oczywiście formułą sprzeczną.

Czy ten kontrprzykład jest prawidłowy?

[Jan Kraszewski]

Prawidłowy. Zauważ, że wystarczy wziąć \(\displaystyle{ \phi=p}\).

JK

[vicossess]

A to jest sprzeczne z dowodem w pierwszym poście, że \(\displaystyle{ \psi}\) musi być spełnialne, czyli dowód musi mieć gdzieś błąd

[Jan Kraszewski]

Tak, zagalopowałem się potwierdzając jego poprawność.

Załóżmy nie wprost, że teza jest fałszywa, czyli \(\displaystyle{ \psi}\) jest sprzeczne (innymi słowy fałszywe dla każdego wartościowania \(\displaystyle{ \sigma}\)). Doprowadzimy, że któraś z formuł \(\displaystyle{ \phi \Rightarrow \psi}\), \(\displaystyle{ \neg \phi \Rightarrow \psi}\) jest sprzeczna. W takim razie dla każdego wartościowania \(\displaystyle{ \sigma}\) zajdzie \(\displaystyle{ \hat{\sigma}(\psi) = F}\). Zauważmy także, że jedno ze zdań \(\displaystyle{ \phi, \neg \phi}\) musi być prawdziwe. W takim razie, bez straty ogólności uznajmy, że \(\displaystyle{ \red\hat{\sigma}(\phi) = T}\). Z tego wynika, że \(\displaystyle{ \hat{\sigma}(\phi \Rightarrow \psi) = F}\) dla każdego wartościowania \(\displaystyle{ \sigma}\) co kończy dowód nie wprost.

Błąd jest czerwony - nie możesz bez straty ogólności uznać, że \(\displaystyle{ \hat{\sigma}(\phi) = T}\). Żeby dostać, że któraś z tych z implikacji jest formułą sprzeczną, musiałbyś wiedzieć, że zawsze, czyli dla każdego wartościowania masz \(\displaystyle{ \hat{\sigma}(\phi) = T}\). Tymczasem część wartościowań może wartościować \(\displaystyle{ \phi}\) na prawdę, a część na fałsz, jak w powyższym kontrprzykładzie.

JK