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)\}}\)
Zasada indukcji strukturalnej na rachunku zdań
-
mattik
- 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ń
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 .
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
-
Jan Kraszewski
- Administrator
- Posty: 34281
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Zasada indukcji strukturalnej na rachunku zdań
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
JK
-
Jakub Gurak
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Zasada indukcji strukturalnej na rachunku zdań
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}\)
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}\)