szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta
PostNapisane: 15 gru 2018, o 20:50 
Użytkownik

Posty: 3
Lokalizacja: Warszawa
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.
A=  \bigcup_{n \in N}  A_n{} ,gdzie n-stopień złożoności formuły
A_{0} =\left\{  p,q\right\} , A_{1} = \left\{  \neg p, \neg q, p\Leftrightarrow q\right\} , 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 \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 n \ge 0. Dla n+1 zachodzi jedna z dwóch możliwości. Niech \varphi \in  A_{n+1}, wówczas:
1 \varphi= \neg \varphi _{1}, gdzie \varphi _{1}  \in A _{n} Skoro formuła \varphi _{1} przyjmuje parzystą liczbę jedynek (0,2 lub 4) to jej negacja również (odpowiednio 4,2 lub 0).
2 \varphi=\varphi _{1} \Leftrightarrow \varphi _{2}, gdzie \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?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 15 gru 2018, o 21:54 
Moderator
Avatar użytkownika

Posty: 8341
Lokalizacja: Wrocław
Rozważ nieznany (czerwony) fragment tabelki prawdy:

\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 A_n jest niepełna, bo na przykład nie umożliwia skonstruowania formuły p \Leftrightarrow \neg q. Powinno być:

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 \}.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 wyznacz zbiór spełnienia alternatywy, koniunkcji, implikacji  kony03  3
 Prawo alternatywy dwóch zdań!  mareek1993  1
 koniunkcja względem alternatywy  ellam  1
 Czy zachodzi prawo rozdzielności względem alternatywy  MultiGumis  4
 Def. alternatywy za pomocą implikacji i negacji  Garbula  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl