Implikacja, dysjunkcja za pomocą alternatywy i koniunkcji
- xxDorianxx
- 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
Implikacja, dysjunkcja za pomocą alternatywy i koniunkcji
Witam, musze udowodnić w sposób bardzo formalny, że za pomocą alternatywy i koniunkcji nie pokażemy implikacji i dysjunkcji. Prosiłbym o jakieś wskazówki
-
- Administrator
- Posty: 34294
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Implikacja, dysjunkcja za pomocą alternatywy i koniunkcji
Konstruujesz rekurencyjnie zbiór wszystkich formuł (dwóch zmiennych \(\displaystyle{ p,q}\)), zbudowanych za pomocą koniunkcji i alternatywy, a następnie indukcyjnie pokazujesz, że każda taka formuła dla dowolnego wartościowania \(\displaystyle{ w}\), takiego że \(\displaystyle{ w(p)=w(q)=0}\) jest wartościowana na fałsz (zatem nie jest równoważna implikacji) oraz że dla dowolnego wartościowania \(\displaystyle{ w}\), takiego że \(\displaystyle{ w(p)=w(q)=1}\) jest wartościowana na prawdę (zatem nie jest równoważna dysjunkcji).
JK
JK
- xxDorianxx
- 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
Re: Implikacja, dysjunkcja za pomocą alternatywy i koniunkcji
Przeprowadzam dowód dla pierwszej części.
Tworzę zbiór wszystkich formuł zawierających tylko koniunkcje i alternatywę. Dla \(\displaystyle{ n=1}\) (formuła składająca się z jedego spójnika) :
\(\displaystyle{ p_1 \vee p_2: v\left( p_{i}\right)=0 }\) to \(\displaystyle{ v(p_1 \vee p_2)=0}\)
\(\displaystyle{ p_1 \wedge p_2: v\left( p_{i}\right)=0 }\) to \(\displaystyle{ v(p_1 \wedge p_2)=0}\)
\(\displaystyle{ T\left( n\right) }\) orzeka, że formuła \(\displaystyle{ \psi_n}\) zawierająca się w powyższym zbiorze dla \(\displaystyle{ v\left( p_i\right) =0}\) nadaje wartość formule w następujący sposób : \(\displaystyle{ v\left( \psi_n\right)=0 }\). Dla \(\displaystyle{ n+1}\)
\(\displaystyle{ 1^{\circ}}\) \(\displaystyle{ \psi_{n+1}=\psi_n \vee p_{n+1}}\) dla \(\displaystyle{ v\left( p_{n+1}\right) }\), \(\displaystyle{ v\left( \psi_{n+1}\right)=0 }\)
\(\displaystyle{ 2^{\circ}}\) \(\displaystyle{ \psi_{n+1}=\psi_n \wedge p_{n+1}}\) dla \(\displaystyle{ v\left( p_{n+1}\right) }\), \(\displaystyle{ v\left( \psi_{n+1}\right)=0 }\)
Zatem \(\displaystyle{ T\left( n\right) }\) zachodzi na mocy indukcji matematycznej. Zatem nie możemy uzyskać dla wartościowania każdej ze zmiennej na zero wartość jeden co zachodzi w przypadku implikacji. Co dowodzi zadaniu.
Czy dowód jest przeprowadzony poprawnie?
Tworzę zbiór wszystkich formuł zawierających tylko koniunkcje i alternatywę. Dla \(\displaystyle{ n=1}\) (formuła składająca się z jedego spójnika) :
\(\displaystyle{ p_1 \vee p_2: v\left( p_{i}\right)=0 }\) to \(\displaystyle{ v(p_1 \vee p_2)=0}\)
\(\displaystyle{ p_1 \wedge p_2: v\left( p_{i}\right)=0 }\) to \(\displaystyle{ v(p_1 \wedge p_2)=0}\)
\(\displaystyle{ T\left( n\right) }\) orzeka, że formuła \(\displaystyle{ \psi_n}\) zawierająca się w powyższym zbiorze dla \(\displaystyle{ v\left( p_i\right) =0}\) nadaje wartość formule w następujący sposób : \(\displaystyle{ v\left( \psi_n\right)=0 }\). Dla \(\displaystyle{ n+1}\)
\(\displaystyle{ 1^{\circ}}\) \(\displaystyle{ \psi_{n+1}=\psi_n \vee p_{n+1}}\) dla \(\displaystyle{ v\left( p_{n+1}\right) }\), \(\displaystyle{ v\left( \psi_{n+1}\right)=0 }\)
\(\displaystyle{ 2^{\circ}}\) \(\displaystyle{ \psi_{n+1}=\psi_n \wedge p_{n+1}}\) dla \(\displaystyle{ v\left( p_{n+1}\right) }\), \(\displaystyle{ v\left( \psi_{n+1}\right)=0 }\)
Zatem \(\displaystyle{ T\left( n\right) }\) zachodzi na mocy indukcji matematycznej. Zatem nie możemy uzyskać dla wartościowania każdej ze zmiennej na zero wartość jeden co zachodzi w przypadku implikacji. Co dowodzi zadaniu.
Czy dowód jest przeprowadzony poprawnie?
-
- Administrator
- Posty: 34294
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Implikacja, dysjunkcja za pomocą alternatywy i koniunkcji
Nie. Po pierwsze najpierw powinieneś zrobić porządną konstrukcję rekurencyjną, a dopiero potem dowód indukcyjny, a nie jedno z drugim równocześnie. po drugie, ważniejsze, Twoja konstrukcja jest niepoprawna.
JK
JK