Logika zadanie

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
Awatar użytkownika
xxDorianxx
Użytkownik
Użytkownik
Posty: 413
Rejestracja: 1 paź 2016, o 17:06
Płeć: Mężczyzna
Lokalizacja: Rybnik
Podziękował: 88 razy
Pomógł: 22 razy

Logika zadanie

Post autor: xxDorianxx »

Witam, proszę o wskazówki do zadania bo nie wiem jak go ruszyć:
Rozważmy formuły zdaniowe zbudowane z \(\displaystyle{ \vee \wedge \neg }\) Dowolną funkcję \(\displaystyle{ v : V ars \rightarrow \mathcal{P}\left( \NN\right) }\) (przypisująca zmiennym podzbiory liczb naturalnych) rozszerzamy na wszystkie formuły w następujący sposób:
\(\displaystyle{ F_{v}\left( \phi\right) =\displaystyle{ \begin{cases} v\left( \phi \right) \ \ gdy \ \ \phi \ \ jest \ \ zmienną \\ F_{v}\left( \phi_{1}\right) \cup F_{v}\left( \phi_2\right) \ \ gdy \ \ \phi \ \ jest \ \ postaci \ \ \phi_1 \vee \phi_2 \\
F_{v}\left( \phi_{1}\right) \cap F_{v}\left( \phi_2\right) \ \ gdy \ \ \phi \ \ jest \ \ postaci \ \ \phi_1 \wedge \phi_2 \\
\mathbb{N} \setminus F_{v}\left( \phi_1\right) \ \ gdy \phi \ \ jest \ \ postaci \ \ \neg \phi_1
\end{cases}}}\)


Udowodnij, że jeśli \(\displaystyle{ F_{v}\left( \phi\right) \neq \mathbb{N}}\) dla pewnego wartościowania \(\displaystyle{ v: Vars \rightarrow \mathcal{P}\left(\mathbb{N} \right) }\) to \(\displaystyle{ \phi}\) nie jest tautologią logiki klasycznej.
Ostatnio zmieniony 20 sty 2021, o 15:14 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
matmatmm
Użytkownik
Użytkownik
Posty: 2280
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 88 razy
Pomógł: 351 razy

Re: Logika zadanie

Post autor: matmatmm »

Skoro \(\displaystyle{ F_{v}\left( \phi\right) \neq \mathbb{N}}\) dla pewnego \(\displaystyle{ v: Vars \rightarrow \mathcal{P}\left(\mathbb{N} \right) }\) to istnieje \(\displaystyle{ n\in\NN}\) takie, że \(\displaystyle{ n\notin F_{v}\left( \phi\right)}\). Określamy wartościowanie \(\displaystyle{ w:Vars\rightarrow\{0,1\}}\) wzorem
\(\displaystyle{ w(p)=\begin{cases}
0 & ,n\notin v(p) \\
1 & ,n\in v(p)
\end{cases}}\)


a następnie dowodzimy przez indukcję strukturalną, że dla każdej formuły \(\displaystyle{ \psi}\)

\(\displaystyle{ W(\psi)=1 \iff n\in F_{v}(\psi)}\)

, gdzie \(\displaystyle{ W}\) to rozszerzenie \(\displaystyle{ w}\) na wszystkie formuły zgodnie z tabelkami działań.
ODPOWIEDZ