Implikacja, dysjunkcja za pomocą alternatywy i koniunkcji

[xxDorianxx]

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

[Jan Kraszewski]

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

[xxDorianxx]

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?

[Jan Kraszewski]

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