Zasada indukcji strukturalnej na rachunku zdań

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
mattik
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 22 paź 2017, o 16:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Zasada indukcji strukturalnej na rachunku zdań

Post autor: mattik » 22 paź 2017, o 17:22

Pokaż przez indukcję, że każda formuła \(\displaystyle{ \phi}\) zbudowana ze zmiennych \(\displaystyle{ p}\) i \(\displaystyle{ q}\) oraz spójnika \(\displaystyle{ \Rightarrow}\) jest równoważna dokładnie jednej z formuł z poniższego zbioru:
\(\displaystyle{ \{T, p, q, (p \Rightarrow q , (q \Rightarrow p ), (p \vee q)\}}\)
Ostatnio zmieniony 22 paź 2017, o 17:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .

Jan Kraszewski
Administrator
Administrator
Posty: 27298
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4596 razy

Re: Zasada indukcji strukturalnej na rachunku zdań

Post autor: Jan Kraszewski » 22 paź 2017, o 17:35

No to najpierw konstruujesz rekurencyjnie zbiór takich formuł, a potem indukcyjnie pokazujesz co trzeba. W kroku indukcyjny będziesz miał formułę postaci \(\displaystyle{ (\psi_1) \Rightarrow (\psi_2)}\), gdzie \(\displaystyle{ \psi_1,\psi_2}\) są równoważne formułom ze zbioru \(\displaystyle{ \{T, p, q, (p \Rightarrow q , (q \Rightarrow p ), (p \vee q)\}}\). I teraz nie widzę innego wyjścia, niż rozpatrzenie 36 przypadków (część będzie prosta, więc to nie jest aż tak straszne).

JK

Jakub Gurak
Użytkownik
Użytkownik
Posty: 824
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 28 razy
Pomógł: 54 razy

Zasada indukcji strukturalnej na rachunku zdań

Post autor: Jakub Gurak » 24 paź 2017, o 02:52

Można to zrobić pomysłowo ( to nie mój pomysł, pomysł pochodzi z ważniaka). Pokażemy, że przy pomocy spójnika \(\displaystyle{ \Rightarrow}\) można zdefiniować, co najwyżej \(\displaystyle{ 6}\) różnych funkcji binarnych. Zbiór tych funkcji oznaczymy \(\displaystyle{ F _{ \Rightarrow }}\).

Niech \(\displaystyle{ R}\) będzie dowolną formułą o zmiennych wolnych \(\displaystyle{ \displaystyle p,q}\), zbudowaną jedynie przy pomocy spójnika \(\displaystyle{ \displaystyle \Rightarrow}\). Pokażemy najpierw indukcyjnie, że jeśli \(\displaystyle{ \displaystyle p}\) jest ostatnią zmienną występującą w \(\displaystyle{ R}\), to każde wartościowanie, które wartościuje \(\displaystyle{ \displaystyle p}\) na \(\displaystyle{ 1}\), wartościuje również całą formułę \(\displaystyle{ R}\) na \(\displaystyle{ 1}\). Dowód poprowadzimy indukcyjnie, ze względu na ilość wystąpień spójnika \(\displaystyle{ \Rightarrow .}\)

\(\displaystyle{ 1.}\) Baza indukcji. Jeśli \(\displaystyle{ \displaystyle \Rightarrow}\) ma zero wystąpień, to jedyną formułą w której ostatnią zmienną jest \(\displaystyle{ \displaystyle p}\) jest formuła \(\displaystyle{ \displaystyle p}\). Badana własność jest oczywiście spełniona.
\(\displaystyle{ 2.}\) Krok indukcyjny. Ustalmy dowolne \(\displaystyle{ n>0}\), i przypuśćmy, że wszystkie formuły o mniej niż \(\displaystyle{ n}\) wystąpień spójnika \(\displaystyle{ \Rightarrow}\) mają żądaną własność. Weźmy dowolną formułę \(\displaystyle{ R}\), w której jest \(\displaystyle{ n}\) wystąpień spójnika \(\displaystyle{ \Rightarrow}\), i której ostatnią zmienną jest \(\displaystyle{ p}\). Weźmy dowolne wartościowanie \(\displaystyle{ w}\), które wartościuje \(\displaystyle{ p}\) na prawdę. Pokażemy, że wtedy cała formuła \(\displaystyle{ R}\) jest wartościowana również na prawdę. Ponieważ \(\displaystyle{ n>0}\), to \(\displaystyle{ R}\) jest postaci \(\displaystyle{ R_{1} \Rightarrow R_{2}}\). Zmienna \(\displaystyle{ p}\) jako ostatnia w \(\displaystyle{ R}\), jest też ostatnia w \(\displaystyle{ R_{2}}\). Ponieważ w \(\displaystyle{ R_{2}}\) jest mniej niż \(\displaystyle{ n}\) wystąpień spójnika \(\displaystyle{ \Rightarrow}\), to na mocy założenia indukcyjnego wartościowanie \(\displaystyle{ p}\) na prawdę, wartościuje również \(\displaystyle{ R_{2}}\) na prawdę. Łatwo sprawdzić, że wtedy również \(\displaystyle{ R_{1} \Rightarrow R_{2}}\) jest wartościowana na prawdę, czyli \(\displaystyle{ R}\) jest wartościowana na prawdę, co należało pokazać.

Na mocy zasady indukcji twierdzenie jest prawdziwe.

Analogicznie pewnie można udowodnić analogiczne twierdzenie dla zmiennej \(\displaystyle{ q}\).

Wiemy teraz, że jeśli formuła zbudowana jedynie z implikacji kończy się jakąś zmienną, to wartościowania tej zmiennej na \(\displaystyle{ 1}\) wartościuje całą formułę na \(\displaystyle{ 1}\). Dla tabeli funkcji binarnej oznacza to, że ostatni wiersz jest stale równy \(\displaystyle{ 1}\), lub ostatnia kolumna jest stale równa \(\displaystyle{ 1}\). Nietrudno sprawdzić, że tabeli o takiej własności jest dokładnie \(\displaystyle{ 6}\). Wobec tego przy pomocy implikacji nie da się zdefiniować więcej niż \(\displaystyle{ 6}\) funkcji binarnych. Oznacza to, że funkcje \(\displaystyle{ \displaystyle f_p,f_q,f_T,f_{p \Rightarrow q},f_{q \Rightarrow p}, f_{p\vee q}}\), są wszystkimi funkcjami binarnymi, które da się zdefiniować przy pomocy samej implikacji.\(\displaystyle{ \square}\)

ODPOWIEDZ