Strona 1 z 1

Niedefiniowalność alternatywy/koniunkcji

: 15 gru 2018, o 19:50
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?

Re: Niedefiniowalność alternatywy/koniunkcji

: 15 gru 2018, o 20:54
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 \}.}\)