Dowodzenie twierdzeń

[blade]

Dostałem na zajęciach dwa poniższe twierdzenia (czy jakkolwiek się to nazywa) i muszę dowieść za pomocą aksjomatów, nie mam zupełnie pojęcia od czego zacząć i na czym to polega, dlatego proszę o jakiekolwiek wskazówki :
1) \(\displaystyle{ (p \Rightarrow q \wedge r) \Rightarrow (p \Rightarrow q) \wedge (p \Rightarrow r)}\)
2) \(\displaystyle{ \neg (p \vee q) \Rightarrow ( \neg p) \wedge ( \neg q)}\)
Bardzo proszę o jakąkolwiek pomoc.

[musialmi]

Proponuję tabeleczkę, którą pewnie już widziałeś na wykładzie lub ćwiczeniach.

[blade]

Zapewne masz na myśli tabelę wartości logicznych (

Kod: Zaznacz cały

http://images.slideplayer.pl/2/824661/slides/slide_4.jpg

) ?
Ja w miarę rozumiem kiedy zachodzi która wartość (nie wiem jak to określić), ale nie potrafię przedstawić tego w postaci aksjomatów, tak jak to było na ćwiczeniach.

[kropka+]

To sprawdź, czy podano Wam ten sam zestaw aksjomatów co tu (str.3-4, Ax.1-Ax.14)

[blade]

Tak są to te same aksjomaty, które dostaliśmy na ćwiczeniach. Przeanalizuję te przykłady, które zostały tam umieszczone, może uda mi się coś zrobić.

@EDIT: Jednak nadal nie wiem od czego zacząć.

[norwimaj]

1. Z prawa mnożenia następników masz:

\(\displaystyle{ ((p\Rightarrow q \wedge r)\Rightarrow(p\Rightarrow q))
\Rightarrow\\
((p\Rightarrow q \wedge r)\Rightarrow(p\Rightarrow r))
\Rightarrow \\
((p \Rightarrow q \wedge r) \Rightarrow (p \Rightarrow q) \wedge (p \Rightarrow r)),}\)

co po dwukrotnym oderwaniu daje tezę. Musisz jeszcze tylko udowodnić przesłanki.

[blade]

Ad. 1) Postanowiłem jednak zrobić to metodą nie wprost z użyciem Reguł wnioskowania i mam pytanie:

\(\displaystyle{ (p \Rightarrow q \wedge r) \Rightarrow (p \Rightarrow q) \wedge (p \Rightarrow r)}\)

Czy robię to dobrze ?:
\(\displaystyle{ \alpha_{0}}\) \(\displaystyle{ \neg \left[ (p \Rightarrow q \wedge r) \Rightarrow (p \Rightarrow q) \wedge (p \Rightarrow r)\right]}\) [zaprzeczam tezie]

\(\displaystyle{ \alpha_{1}}\) \(\displaystyle{ (p \Rightarrow q \wedge r) \wedge \neg \left[ (p \Rightarrow q) \wedge (p \Rightarrow r)\right]}\) Tutaj użyłem R2

\(\displaystyle{ \alpha_{2}}\) \(\displaystyle{ p \Rightarrow q \wedge r}\) R6 do \(\displaystyle{ \alpha_{1}}\)
\(\displaystyle{ \alpha_{3}}\) \(\displaystyle{ p \wedge \neg (q \wedge r)}\) R2 do \(\displaystyle{ \alpha_{2}}\)
\(\displaystyle{ \alpha_{4}}\) \(\displaystyle{ p}\) R6 do \(\displaystyle{ \alpha_{3}}\)
\(\displaystyle{ \alpha_{5}}\) \(\displaystyle{ \neg \left[ (p \Rightarrow q) \wedge (p \Rightarrow r)\right]}\) R7 do \(\displaystyle{ \alpha_{1}}\)
\(\displaystyle{ \alpha_{6}}\) \(\displaystyle{ \neg (p \Rightarrow q) \vee \neg (p \Rightarrow r)}\) R8 do \(\displaystyle{ \alpha_{5}}\)

No i dotąd doszedłem i nie wiem za bardzo co dalej, nie wiem też czy dobrze zrobiłem to dotąd, dlatego chciałbym zapytać czy dobrze to rozumiem i jeśli tak to poprosiłbym o jakąś wskazówkę na kolejny 'krok'

Reguły wnioskowania, które tutaj użyłem :
R2 : \(\displaystyle{ \neg (p \Rightarrow q) \Rightarrow p \wedge \neg q}\)
R6: \(\displaystyle{ p \wedge q \Rightarrow p}\)
R7: \(\displaystyle{ p \wedge q \Rightarrow q}\)
R8: \(\displaystyle{ \neg (p \wedge q) \Rightarrow \neg p \vee \neg q}\)

Mam nadzieje, że wszystko dobrze i czytelnie przepisałem.

[norwimaj]

Dowodząc \(\displaystyle{ \alpha_3}\) popełniasz błąd. Stosujesz prawo zaprzeczenia implikacji, podczas gdy implikacja nie jest zaprzeczona.

Poza tym już się nie orientuję, w jakim systemie dowodowym masz to udowodnić.

[blade]

Dowodząc \(\displaystyle{ \alpha_3}\) popełniasz błąd. Stosujesz prawo zaprzeczenia implikacji, podczas gdy implikacja nie jest zaprzeczona.

Rzeczywiście źle popatrzyłem.

więc będzie tak :
\(\displaystyle{ \alpha_{0}}\) \(\displaystyle{ \neg \left[ (p \Rightarrow q \wedge r) \Rightarrow (p \Rightarrow q) \wedge (p \Rightarrow r)\right]}\) [zaprzeczam tezie]

\(\displaystyle{ \alpha_{1}}\) \(\displaystyle{ (p \Rightarrow q \wedge r) \wedge \neg \left[ (p \Rightarrow q) \wedge (p \Rightarrow r)\right]}\) Tutaj użyłem R2

\(\displaystyle{ \alpha_{2}}\) \(\displaystyle{ p \Rightarrow q \wedge r}\) R6 do \(\displaystyle{ \alpha_{1}}\)
\(\displaystyle{ \alpha_{3}}\) \(\displaystyle{ \neg \left[ (p \Rightarrow q) \wedge (p \Rightarrow r)\right]}\) R7 do \(\displaystyle{ \alpha_{1}}\)
\(\displaystyle{ \alpha_{4}}\) \(\displaystyle{ \neg (p \Rightarrow q) \vee \neg (p \Rightarrow r)}\) R8 do \(\displaystyle{ \alpha_{3}}\)

I nadal nie wiem co teraz zrobić

chyba, że mogę zastosować regułę odrywania (R0) do \(\displaystyle{ \alpha_{2}}\) ?
wtedy byłoby :

\(\displaystyle{ \alpha_{5}}\) \(\displaystyle{ q \wedge r}\) R0 dla \(\displaystyle{ \alpha_{2}}\)
\(\displaystyle{ \alpha_{6}}\) \(\displaystyle{ q}\) R6 dla \(\displaystyle{ \alpha_{5}}\)
\(\displaystyle{ \alpha_{7}}\) \(\displaystyle{ r}\) R7 dla \(\displaystyle{ \alpha_{5}}\)

Lecz nadal nie wiem jak pozbyć się alternatywy z \(\displaystyle{ \alpha_{4}}\) i wykazać sprzeczność ~q lub ~r.

Poza tym już się nie orientuję, w jakim systemie dowodowym masz to udowodnić.

Na ćwiczeniach dzisiaj pokazano nam reguły wnioskowania, a dowód robię sam dla siebie, żeby dobrze to zrozumieć, system dowodzenia nie ma już znaczenia, a wydaję mi się, że dowód nie wprost jest łatwiejszy do przeprowadzenia.

[norwimaj]

chyba, że mogę zastosować regułę odrywania (R0) do \(\displaystyle{ \alpha_{2}}\) ?

Ale musiałbyś udowodnić \(\displaystyle{ p}\), co jest niewykonalne. Raczej powinieneś rozpatrzeć przypadki: \(\displaystyle{ p}\) prawdziwe albo fałszywe. Nie znam dopuszczalnego zestawu reguł, więc nie napiszę szczegółowo, jak to się robi, ale przypuszczam, że możesz udowodnić \(\displaystyle{ (p\vee \neg p) \wedge\alpha_1}\), następnie \(\displaystyle{ (p\wedge \alpha_1) \vee (\neg p\wedge \alpha_1)}\), itd.

a wydaję mi się, że dowód nie wprost jest łatwiejszy do przeprowadzenia.

Nie sądzę, żeby tak było.