Niedefiniowalność alternatywy/koniunkcji
: 15 gru 2018, o 19:50
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?
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?