Niedefiniowalność alternatywy/koniunkcji

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
nicniewiem+
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 15 gru 2018, o 17:28
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 1 raz

Niedefiniowalność alternatywy/koniunkcji

Post autor: nicniewiem+ »

Mam udowodnić, że za pomocą równoważności i negacji nie można zdefiniować alternatywy ani koniunkcji.
Zaczynam tak:
Niech A będzie zbiorem wszystkich zdań logicznych zbudowanych na zmiennych p,q, przy pomocy spójnika negacji lub równoważności, tj.
\(\displaystyle{ A= \bigcup_{n \in N} A_n{}}\) ,gdzie n-stopień złożoności formuły
\(\displaystyle{ A_{0} =\left\{ p,q\right\}}\) , \(\displaystyle{ A_{1} = \left\{ \neg p, \neg q, p\Leftrightarrow q\right\}}\) , \(\displaystyle{ A_{n+1} = \left\{ \neg\varphi : \varphi\in A_{n} \right\} \cup \left\{ \varphi \Leftrightarrow \psi : \varphi,\psi \in A_{n} \right\}}\)
W definicji alternatywy i koniunkcji występuje nieparzysta ilość jedynek, odpowiednio 3 i 1. Zatem, trzeba pokazać, że dowolna formuła \(\displaystyle{ \varphi\in A}\) przy dowolnym wartościowaniu zmiennych zdaniowych p,q przyjmuje parzystą ilość wartości logicznej 1 ( tj. 0,2 lub 4)
Indukcyjnie:
dla n=0 jest oczywiste
Zakładamy, że jest tak dla dowolnej l.naturalnej \(\displaystyle{ n \ge 0}\). Dla n+1 zachodzi jedna z dwóch możliwości. Niech \(\displaystyle{ \varphi \in A_{n+1}}\), wówczas:
1 \(\displaystyle{ \varphi= \neg \varphi _{1}}\), gdzie \(\displaystyle{ \varphi _{1} \in A _{n}}\) Skoro formuła \(\displaystyle{ \varphi _{1}}\) przyjmuje parzystą liczbę jedynek (0,2 lub 4) to jej negacja również (odpowiednio 4,2 lub 0).
2 \(\displaystyle{ \varphi=\varphi _{1} \Leftrightarrow \varphi _{2}}\), gdzie \(\displaystyle{ \varphi _{1},\varphi _{2} \in A _{n}}\) i teraz nie wiem jak to pakazać. Czy jest jakiś inny sposób niż sporządzenie tabelek zero-jedynkowych?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Niedefiniowalność alternatywy/koniunkcji

Post autor: Dasio11 »

Rozważ nieznany (czerwony) fragment tabelki prawdy:

\(\displaystyle{ \begin{array}{|c|c|c|c|c|} \hline
p & q & \varphi_1 & \varphi_2 & \varphi_1 \Leftrightarrow \varphi_2 \\ \hline
0 & 0 & \textcolor{red}{?} & \textcolor{red}{?} & \textcolor{red}{?} \\ \hline
0 & 1 & \textcolor{red}{?} & \textcolor{red}{?} & \textcolor{red}{?} \\ \hline
1 & 0 & \textcolor{red}{?} & \textcolor{red}{?} & \textcolor{red}{?} \\ \hline
1 & 1 & \textcolor{red}{?} & \textcolor{red}{?} & \textcolor{red}{?} \\ \hline
\end{array}}\)


Z definicji równoważności, w każdym z czterech wierszy jest nieparzysta liczba jedynek, zatem we wszystkich czterech wierszach łącznie - czyli w całym rozważanym fragmencie tabelki - będzie ich parzysta liczba. Ponadto z założenia indukcyjnego otrzymujemy, że w każdej z dwóch pierwszych kolumn jest parzysta liczba jedynek. Stąd w ostatnim wierszu też musi być parzysta liczba jedynek.


Nawiasem mówiąc, Twoja rekurencyjna definicja zbiorów \(\displaystyle{ A_n}\) jest niepełna, bo na przykład nie umożliwia skonstruowania formuły \(\displaystyle{ p \Leftrightarrow \neg q}\). Powinno być:

\(\displaystyle{ A_0 = \{ p, q \} \\
A_{n+1} = \textcolor{red}{A_n \: \cup} \: \{ \neg \varphi : \varphi \in A_n \} \cup \{ \varphi \Leftrightarrow \psi : \varphi, \psi \in A_n \}.}\)
ODPOWIEDZ