Problem z konkluzją w przejściu z FOL na CNF

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
edutomek
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 1 paź 2021, o 12:11
Płeć: Mężczyzna
wiek: 44
Podziękował: 1 raz

Problem z konkluzją w przejściu z FOL na CNF

Post autor: edutomek »

Napotkałem problem, żeby zamienić coś takiego:

\(\displaystyle{ \forall_x man(x) \Rightarrow strong(x) }\)

na CNF.

Wg

Kod: Zaznacz cały

https://april.eecs.umich.edu/courses/eecs492_w10/wiki/images/6/6b/CNF_conversion.pdf
, konkretnie wg punktu pierwszego (drugi podpunkt), jednym z kroków jest:
Eliminate \(\displaystyle{ ⇒}\), replacing \(\displaystyle{ α ⇒ β}\) with \(\displaystyle{ ¬α ∨ β}\).
Rzecz w tym, że wydaje mi się to być kompletnie bez sensu.

W oryginale mam przesłankę (\(\displaystyle{ α}\)) i konkluzję (\(\displaystyle{ β}\)). Po zamianie mam zwykłą alternatywę logiczną: gdzie się podziało wnioskowanie (konkluzja wynika z przesłanki)?

Przecież jeśli zamiast \(\displaystyle{ α ⇒ β}\) zapiszę \(\displaystyle{ ¬α ∨ β}\), to równie dobrze mógłbym napisać \(\displaystyle{ β ∨ ¬α}\). Jak z CNF-a miałbym przejść z powrotem na poprzedni zapis? Jak odtworzyć związki przyczynowo-skutkowe (przesłanki i konkluzje) z altenatywy logicznej?

Gwoli ścisłości: nie jestem logikiem, nie jestem matematykiem. A opisywaną regułę znalazłem chyba w jeszcze jednym miejscu, więc nie wydaje mi się, aby to była jakaś bzdura. Zakładam, że to ja czegoś nie rozumiem - i dlatego tu pytam.
Ostatnio zmieniony 1 paź 2021, o 15:13 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
matmatmm
Użytkownik
Użytkownik
Posty: 2280
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 88 razy
Pomógł: 351 razy

Re: Problem z konkluzją w przejściu z FOL na CNF

Post autor: matmatmm »

edutomek pisze: 1 paź 2021, o 12:30 W oryginale mam przesłankę (\(\displaystyle{ α}\)) i konkluzję (\(\displaystyle{ β}\)). Po zamianie mam zwykłą alternatywę logiczną: gdzie się podziało wnioskowanie (konkluzja wynika z przesłanki)?
Implikacja sama w sobie to jeszcze nie wnioskowanie. Spójnik implikacji \(\displaystyle{ \implies}\) pozwala na łączenie dwóch zdań lub funkcji zdaniowych tak, że w rezultacie otrzymujemy nowe zdanie lub funkcję zdaniową.

W przypadku zdań sprawa jest prostsza. Wartość logiczna implikacji zależy jedynie od wartości logicznej zdań składowych i formalnie jest to opisane za pomocą tabelki (mam nadzieję, że ją znasz). Tabelka ta ma oddawać intuicję konstrukcji językowej "jeśli ..., to ...".

W przypadku funkcji zdaniowych sprawa jest bardziej skomplikowana (Akurat tutaj mamy do czynienia z funkcjami zdaniowymi), ale zasada jest podobna.


Okazuje się, że identyczny efekt jaki daje spójnik implikacji uzyskamy za pomocą alternatywy i negacji. Krótko mówiąc \(\displaystyle{ \neg \alpha \vee \beta}\) daje taką samą tabelkę jak \(\displaystyle{ \alpha\implies \beta}\), a to już wystarcza, żeby zastępować jedno przez drugie w formułach równoważnych.

Przecież jeśli zamiast \(\displaystyle{ α ⇒ β}\) zapiszę \(\displaystyle{ ¬α ∨ β}\), to równie dobrze mógłbym napisać \(\displaystyle{ β ∨ ¬α}\). Jak z CNF-a miałbym przejść z powrotem na poprzedni zapis? Jak odtworzyć związki przyczynowo-skutkowe (przesłanki i konkluzje) z altenatywy logicznej?
Na przykład tak (Ostatnie przejście to prawo kontrapozycji):

\(\displaystyle{ \beta\vee\neg\alpha\quad \equiv\quad \neg\neg\beta\vee \neg\alpha\quad \equiv\quad \neg \beta\implies \neg \alpha \quad\equiv\quad \alpha\implies \beta}\)

Dodano po 26 minutach 4 sekundach:
Dodam jeszcze, że takie zdanie
edutomek pisze: 1 paź 2021, o 12:30 \(\displaystyle{ \forall_x man(x) \Rightarrow strong(x) }\)
znaczy w języku potocznym "Każdy mężczyzna jest silny", a to jest to samo jakbyśmy powiedzieli "Każdy obiekt nie jest mężczyzną lub jest silny" (przepraszam za słowo obiekt w odniesieniu do ludzi, nie miałem pomysłu jak to wypowiedzieć).
edutomek
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 1 paź 2021, o 12:11
Płeć: Mężczyzna
wiek: 44
Podziękował: 1 raz

Re: Problem z konkluzją w przejściu z FOL na CNF

Post autor: edutomek »

Bardzo dziękuję za odpowiedź.

Drugą połowę przeczytałem kilka razy. Piewszą połowę raz, albo dwa razy - i nie było sensu czytać więcej. Potem przeczytałem to żonie i jest możliwe, że jej podejrzenie jest słuszne - używamy tych samych słów, ale w innych znaczeniach. Dlatego mam takie trudności ze zrozumieniem.

Bo dla mnie implikacja jest równoważna z wnioskowaniem (takie synonimy).

Kiedy przeczytałem o tych tabelkach prawdy (skądinąd nienawidzę ich; reguły są dla mnie znacznie bardzej czytelne), zrozumiałem, skąd wzięła się ta problematyczna (w moim prywatnym odczuciu) równoważność.
rafal3006
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 11 mar 2007, o 19:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 1 raz

Re: Problem z konkluzją w przejściu z FOL na CNF

Post autor: rafal3006 »

edutomek pisze: 3 paź 2021, o 05:33 Bo dla mnie implikacja jest równoważna z wnioskowaniem (takie synonimy).
Kiedy przeczytałem o tych tabelkach prawdy (skądinąd nienawidzę ich; ...
Tabelki zero-jedynkowe są bardzo dobre pod warunkiem fundamentalnie innego ich rozumienia.

Przykład:
Zdefiniujmy sobie zero-jedynkowo dwa znaczki inaczej niż to jest we współczesnej matematyce (to nam wolno) i zobaczmy jak pięknie pasują do otaczającej nas rzeczywistości.

1.
Definiujemy zero-jedynkowo znaczek warunku wystarczającego \(\displaystyle{ \Rightarrow }\)
\(\displaystyle{ p \Rightarrow q = \neg p+q}\)
Gdzie:
\(\displaystyle{ \Rightarrow}\) = warunek wystarczający, zajście \(\displaystyle{ p}\) jest wystarczające \(\displaystyle{ \Rightarrow}\) dla zajścia \(\displaystyle{ q}\)

2.
Definiujemy zero-jedynkowo znaczek warunku koniecznego \(\displaystyle{ \rightarrow }\)
\(\displaystyle{ p \rightarrow q = p+ \neg q}\)
Gdzie:
\(\displaystyle{ \rightarrow }\) = warunek konieczny, zajście \(\displaystyle{ p}\) jest konieczne \(\displaystyle{ \rightarrow }\) dla zajścia \(\displaystyle{ q}\)

Stąd w rachunku zero-jedynkowym łatwo wyprowadzamy matematyczny związek między warunkiem wystarczającym \(\displaystyle{ \Rightarrow }\) i koniecznym \(\displaystyle{ \rightarrow }\) z zamianą poprzednika \(\displaystyle{ p}\) z następnikiem \(\displaystyle{ q}\)

Prawo Rachunku zero-jedynkowego:
\(\displaystyle{ p \Rightarrow q = q \rightarrow p}\)

Powyższe prawo można też udowodnić bez tabel zero-jedynkowych korzystając z definicji warunku wystarczającego \(\displaystyle{ \Rightarrow }\) i koniecznego \(\displaystyle{ \rightarrow }\):
\(\displaystyle{ p \Rightarrow q = \neg p + q = q \rightarrow p}\)
Na mocy definicji znaczków \(\displaystyle{ \Rightarrow i \rightarrow}\)
cnd

Teraz zobaczmy jak wyprowadzony związek między warunkiem wystarczającym \(\displaystyle{ \Rightarrow}\) i koniecznym \(\displaystyle{ \rightarrow }\) absolutnie genialnie pasuje do otaczającej nas rzeczywistości.

Wypowiedzmy zdanie ze spełnionym warunkiem wystarczającym \(\displaystyle{ \Rightarrow }\):
\(\displaystyle{ A1}\).
Jeśli jutro będzie padało \(\displaystyle{ (P)}\) to na 100% \(\displaystyle{ \Rightarrow }\) będzie pochmurno \(\displaystyle{ (CH)}\)
\(\displaystyle{ P \Rightarrow CH =1}\)
Padanie jest (=1) warunkiem wystarczającym \(\displaystyle{ \Rightarrow }\) dla istnienia chmur, bo zawsze gdy pada, są chmury

Skorzystajmy z wyprowadzonego wyżej prawa rachunku zero-jedynkowego.
\(\displaystyle{ A1: P \Rightarrow CH = A3: CH \rightarrow P}\)
Na mocy prawa rachunku zero-jedynkowego prawdziwe zdanie \(\displaystyle{ A1}\) (co udowodniliśmy) wymusza prawdziwe zdanie \(\displaystyle{ A3}\) (albo odwrotnie).

Wypowiedzmy prawdziwe zdanie \(\displaystyle{ A3}\):
\(\displaystyle{ A3}\).
Jeśli jutro będzie pochmurno \(\displaystyle{ (CH)}\) to może \(\displaystyle{ \rightarrow }\) padać \(\displaystyle{ (P)}\)
\(\displaystyle{ CH \rightarrow P =1}\)
Chmury są (=1) warunkiem koniecznym \(\displaystyle{ \rightarrow }\) dla padania, bo padać może wyłącznie z chmury
cnd

Prawda, że proste?

Dodano po 15 godzinach 14 minutach 30 sekundach:

UWAGA:
W nawiązaniu do mojego postu wyżej podaję rozpiskę warunku wystarczającego \(\displaystyle{ \Rightarrow}\) i koniecznego \(\displaystyle{ \rightarrow }\) na tabele zero jedynkowe.

1.
Definicja warunku wystarczającego \(\displaystyle{ \Rightarrow }\):
\(\displaystyle{ p \Rightarrow q = \neg p+q}\)

Definicja warunku wystarczającego \(\displaystyle{ \Rightarrow }\) w tabeli zero-jedynkowej wygląda tak:
\(\displaystyle{ \begin{array}{ccc}
p&q&p \Rightarrow q\\
1&1&1 \\
1&0&0\\
0&0&1\\
0&1&1\\
\end{array}}\)


2.
Definicja warunku koniecznego \(\displaystyle{ \rightarrow }\):
\(\displaystyle{ p \rightarrow q = p+ \neg q}\)

Definicja warunku koniecznego \(\displaystyle{ \rightarrow}\) w tabeli zero-jedynkowej wygląda tak:
\(\displaystyle{ \begin{array}{ccc}
p&q&p \rightarrow q\\
1&1&1 \\
1&0&1\\
0&0&1\\
0&1&0\\
\end{array}}\)


Prawo rachunku zero-jedynkowego zapisane w moim poście wyżej:
\(\displaystyle{ p \Rightarrow q = q \rightarrow p}\)

Mam nadzieję, że po tej podpowiedzi każdy, kto zna rachunek zero-jedynkowy bez problemu udowodni powyższe prawo.

Definicja znaczka różne na mocy definicji ##:
Dwie funkcje logiczne (na przykład \(\displaystyle{ p \Rightarrow q}\) i \(\displaystyle{ p \rightarrow q}\)) są różne na mocy definicji ## wtedy i tylko wtedy gdy nie są tożsame i żadna z nich nie jest zaprzeczeniem drugiej

Oczywistym jest, że na mocy definicji zachodzi:
\(\displaystyle{ p \Rightarrow q = \neg p+q}\) ## \(\displaystyle{ p \rightarrow q = p+ \neg q}\)
Gdzie:
## - różne na mocy definicji
Ławo sprawdzić, że definicja znaczka różne na mocy definicji ## jest tu spełniona.

Innymi słowy:
Warunek wystarczający \(\displaystyle{ \Rightarrow }\) to fundamentalnie co innego niż warunek konieczny \(\displaystyle{ \rightarrow }\)
ODPOWIEDZ