Matematyka.pl

Witam, jak rozwiązać tego typu zadanie?

"Rozważmy taki spójnik \(\displaystyle{ \oplus}\), że \(\displaystyle{ p \oplus q \equiv \neg p}\). Pokaż, że zbiór \(\displaystyle{ \{ \oplus \}}\) nie jest zupełny."

Dostałem radę, żeby zrobić to indukcją, nie wiem jednak do końca jak i proszę o pomoc.

Skonstruuj rekurencyjnie zbiór wszystkich formuł, które można zbudować za pomocą tego spójnika i zmiennych \(\displaystyle{ p,q}\). Potem indukcją po złożoności formuły udowodnij, że dla dowolnej takiej formuły \(\displaystyle{ \alpha(p,q)}\) i dowolnego wartościowania \(\displaystyle{ w}\) mamy \(\displaystyle{ w(\alpha(p,q))=w(\alpha(q,p))}\), co oznacza, że żadna taka formuła nie jest równoważna formule \(\displaystyle{ p \Rightarrow q}\).

JK

Co to znaczy, że zbiór spójników jest zupelny
Czy chodzi o to, że przy pomocy wyłącznie spójnika \(\displaystyle{ \oplus}\) oraz zmiennych można zdefiniować dowolny spójnik??

Jakub Gurak pisze: 12 lis 2022, o 16:04 Co to znaczy, że zbiór spójników jest zupelny
Czy chodzi o to, że przy pomocy wyłącznie spójnika \(\displaystyle{ \oplus}\) oraz zmiennych można zdefiniować dowolny spójnik??

Według definicji podanych nam na zajęciach, zbiór spójników jest zupełny, jeśli funkcję boolowską można opisać za pomocą formuły zawierającej jedynie spójniki z tego zbioru spójników i zmienne. Intuicyjnie wydaje mi się, że chodzi o to o czym piszesz, czyli pokazać jak zastąpić nasz spójnik dowolnym innym spójnikiem, sam jednak nie rozumiem do końca funkcji boolowskich i zupełności zbiorów.

Jan Kraszewski pisze: 12 lis 2022, o 16:00 Skonstruuj rekurencyjnie zbiór wszystkich formuł, które można zbudować za pomocą tego spójnika i zmiennych \(\displaystyle{ p,q}\). Potem indukcją po złożoności formuły udowodnij, że dla dowolnej takiej formuły \(\displaystyle{ \alpha(p,q)}\) i dowolnego wartościowania \(\displaystyle{ w}\) mamy \(\displaystyle{ w(\alpha(p,q))=w(\alpha(q,p))}\), co oznacza, że żadna taka formuła nie jest równoważna formule \(\displaystyle{ p \Rightarrow q}\).

JK

Nie do końca rozumiem, co masz na myśli przez skonstruuj rekurencyjnie? Jeśli dobrze myślę, chodzi o to, żeby po prostu sprawdzać po kolei formuły, które możemy utworzyć z tego spójnika i zmiennych p oraz q, i na ich podstawie spróbować wywnioskować, że nie ma formuły równoważnej którejś z tych formuł?

Carino pisze: 12 lis 2022, o 19:41Nie do końca rozumiem, co masz na myśli przez skonstruuj rekurencyjnie? Jeśli dobrze myślę, chodzi o to, żeby po prostu sprawdzać po kolei formuły, które możemy utworzyć z tego spójnika i zmiennych p oraz q, i na ich podstawie spróbować wywnioskować, że nie ma formuły równoważnej którejś z tych formuł?

Niby jak chcesz to zrobić, jeśli tych formuł jest nieskończenie wiele? Jeżeli chcesz mieć uczciwy dowód, to potrzebujesz uczciwej konstrukcji, która wygląda tak:

\(\displaystyle{ F_0=\{p,q\}}\)
Dla \(\displaystyle{ n\ge 1}\)
\(\displaystyle{ F_n=\left\{ (\alpha)\oplus(\beta):\alpha,\beta\in \bigcup_{k<n}F_k \right\}.}\)

Wtedy zbiór \(\displaystyle{ F= \bigcup_{n=0}^{\infty}F_n }\) jest pożądanym zbiorem formuł.

JK

Jan Kraszewski pisze: 12 lis 2022, o 16:00dla dowolnej takiej formuły \(\displaystyle{ \alpha(p,q)}\) i dowolnego wartościowania \(\displaystyle{ w}\) mamy \(\displaystyle{ w(\alpha(p,q))=w(\alpha(q,p))}\), co oznacza, że żadna taka formuła nie jest równoważna formule \(\displaystyle{ p \Rightarrow q}\).

To raczej nie wyjdzie. Można poszukać innego niezmiennika, ale proponuję tak: wypisywać z dokładnością do równoważności wszystkie formuły, które dają się otrzymać z podanego spójnika. Kiedy przestaną dochodzić nowe, wykazać indukcyjnie że w znalezionym zbiorze są istotnie wszystkie takie formuły, i znaleźć formułę której tym zbiorze nie ma. W zależności od tego, jaki jest wymagany poziom formalizmu, mniej lub bardziej jawne odniesienie do tej konstrukcji:

Jan Kraszewski pisze: 12 lis 2022, o 19:48\(\displaystyle{ F_0=\{p,q\}}\)
Dla \(\displaystyle{ n\ge 1}\)
\(\displaystyle{ F_n=\left\{ (\alpha)\oplus(\beta):\alpha,\beta\in \bigcup_{k<n}F_k \right\}.}\)

Wtedy zbiór \(\displaystyle{ F= \bigcup_{n=0}^{\infty}F_n }\) jest pożądanym zbiorem formuł.

też powinno się gdzieś pojawić.

Dasio11 pisze: 13 lis 2022, o 10:36To raczej nie wyjdzie.

Dlaczego? Wydawało mi się, że to sobie uzasadniłem, więc jestem ciekaw, gdzie oszukałem...

JK

Przecież już sam spójnik \(\displaystyle{ \oplus}\) nie jest przemienny, tj. \(\displaystyle{ p \oplus q \not \equiv q \oplus p}\).

Dasio11 pisze: 13 lis 2022, o 14:20 Przecież już sam spójnik \(\displaystyle{ \oplus}\) nie jest przemienny, tj. \(\displaystyle{ p \oplus q \not \equiv q \oplus p}\).

Ech, pomyślałem o czymś innym i wyszło jak wyszło...

JK

Dasio11 pisze: 13 lis 2022, o 10:36 Można poszukać innego niezmiennika, ale proponuję tak: wypisywać z dokładnością do równoważności wszystkie formuły, które dają się otrzymać z podanego spójnika. Kiedy przestaną dochodzić nowe, wykazać indukcyjnie że w znalezionym zbiorze są istotnie wszystkie takie formuły, i znaleźć formułę której tym zbiorze nie ma.

Wciąż nie do końca rozumiem wyżej wymienionych propozycji rozwiązania... Przez "wypisywać z dokładnością do równoważności wszystkie formuły, które dają się otrzymać z podanego spójnika" rozumiemy wypisanie co może być pod formułami \(\displaystyle{ \alpha}\) oraz \(\displaystyle{ \beta}\) w \(\displaystyle{ \alpha \oplus \beta}\) oraz \(\displaystyle{ \beta \oplus \alpha}\)? Czy takich opcji nie byłaby nieskończość?

Myślałem trochę nad tym zadaniem, nie moglibyśmy rozwiązać tego w następujący sposób?:
Skoro nasz spójnik jest równoważny negacji z pierwszej jego zmiennej, to udowadniając, że zbiór spójników składający się jedynie z negacji jest niezupełny, udowodnilibyśmy też to, że zbiór naszego spójnika jest niezupełny (bo przyjmuje te same wartości, co dla negacji pierwszej z jego zmiennych)? Czy jest to zbyt powierzchowny pomysł na rozwiązanie?

Carino pisze: 13 lis 2022, o 15:10Wciąż nie do końca rozumiem wyżej wymienionych propozycji rozwiązania... Przez "wypisywać z dokładnością do równoważności wszystkie formuły, które dają się otrzymać z podanego spójnika" rozumiemy wypisanie co może być pod formułami \(\displaystyle{ \alpha}\) oraz \(\displaystyle{ \beta}\) w \(\displaystyle{ \alpha \oplus \beta}\) oraz \(\displaystyle{ \beta \oplus \alpha}\)? Czy takich opcji nie byłaby nieskończość?

Źle rozumiesz. "Z dokładnością do równoważności" oznacza, że rozróżniamy tylko formuły, które mają różne tabelki.

Carino pisze: 13 lis 2022, o 15:10Skoro nasz spójnik jest równoważny negacji z pierwszej jego zmiennej, to udowadniając, że zbiór spójników składający się jedynie z negacji jest niezupełny, udowodnilibyśmy też to, że zbiór naszego spójnika jest niezupełny (bo przyjmuje te same wartości, co dla negacji pierwszej z jego zmiennych)?

A dlaczego uważasz, że udowodnilibyśmy to?

JK

Jan Kraszewski pisze: 13 lis 2022, o 15:14 Źle rozumiesz. "Z dokładnością do równoważności" oznacza, że rozróżniamy tylko formuły, które mają różne tabelki.

Ale skoro nie znamy tabelki naszego nowego spójnika, jak mamy ją odróżnić od znanych nam tabelek? Szczerze nie mogę dobrze tego sobie przyswoić.

Jan Kraszewski pisze: 13 lis 2022, o 15:14

Carino pisze: 13 lis 2022, o 15:10Skoro nasz spójnik jest równoważny negacji z pierwszej jego zmiennej, to udowadniając, że zbiór spójników składający się jedynie z negacji jest niezupełny, udowodnilibyśmy też to, że zbiór naszego spójnika jest niezupełny (bo przyjmuje te same wartości, co dla negacji pierwszej z jego zmiennych)?

A dlaczego uważasz, że udowodnilibyśmy to?

Ponieważ możemy udowodnić niezupełność zbioru spójnika negacji, a przynajmniej tak mi się wydaje. Intuicyjnie wydawało mi się, że nie każdy inny spójnik możemy zastąpić negacją, bo jest ona jednoargumentowa, a spójniki koniunkcji, alternatywy itd. są dwuargumentowe. Stąd mój wniosek.

Carino pisze: 13 lis 2022, o 17:25Ale skoro nie znamy tabelki naszego nowego spójnika, jak mamy ją odróżnić od znanych nam tabelek?

To przeczytaj uważnie:

Dasio11 pisze: 13 lis 2022, o 10:36ale proponuję tak: wypisywać z dokładnością do równoważności wszystkie formuły, które dają się otrzymać z podanego spójnika. Kiedy przestaną dochodzić nowe, ...

Tzn. wypisujesz kolejne tabelki, jak któraś się powtarza, to już nas nie interesuje. Zaczynasz od \(\displaystyle{ p\oplus q, q\oplus p}\) itd.

Carino pisze: 13 lis 2022, o 17:25Intuicyjnie wydawało mi się, że nie każdy inny spójnik możemy zastąpić negacją, bo jest ona jednoargumentowa, a spójniki koniunkcji, alternatywy itd. są dwuargumentowe.

Po pierwsze "intuicyjnie" to za mało. Po drugie tutaj masz spójnik dwuargumentowy.

JK