Naukowy.pl

Ścisłe => Matematyka => Kompendium => Wątek zaczęty przez: lemon w Czerwiec 21, 2008, 11:30:37 am

Tytuł: [Logika] Tautologia rachunku zdań, funkcje zdaniowe
Wiadomość wysłana przez: lemon w Czerwiec 21, 2008, 11:30:37 am
DEFINICJE


Logika nie należy do najtrudniejszych działów matematyki. Dlatego też postanowiłem ją nieco przybliżyć każdemu, pomimo tego, że nie jest ona w programie szkoły średniej.

Zdanie - każde zdanie oznajmujące, o którym można jednoznacznie powiedzieć, że jest prawdziwe lub fałszywe. Zdanie prawdziwe ma wartość 1, a fałszywe 0. Zdania na ogół oznacza się literami: p, q, r, ...

Negacja (zaprzeczenie) - zapisuje się symbolicznie \sim p lub \neg p. Jeżeli zdanie p jest prawdziwe, to zdanie\sim p jest fałszywe. Jeśli zaś zdanie p jest fałszywe, to zdanie\sim p jest prawdziwe.

Koniunkcję zdań p i q zapisuje się symbolicznie p \wedge q. Zdanie p \wedge q jest prawdziwe wtedy i tylko wtedy, gdy oba zdania są prawdziwe.

Alternatywa - zapisywana symbolicznie p \vee q (p lub q). Jeśli przynajmniej jedno ze zań jest prawdziwe to ich alternatywa także jest prawdziwa.

Implikacja (wynikanie) - zapisywana symbolicznie  p \Rightarrow q (jeżeli p, to q). Implikacja jest fałszywa tylko wtedy, gdy zdanie poprzednie jest prawdziwe, a następne fałszywe.

Równoważność - zapisywana symbolicznie  p \Leftrightarrow q (p wtedy i tylko wtedy, gdy q). Równoważność jest prawdziwa, gdy oba zdania mają wartość logiczną.




PRAWA RACHUNKU ZDAŃ


Zdania określone mianem praw rachunku zdań - to zdania, których wartość logiczna jest równa 1. Innymi słowy są to zdania prawdziwe.

p \wedge q \quad \Leftrightarrow \quad q \wedge p - prawo przemienności koniunkcji

p \vee q \quad \Leftrightarrow \quad  q \vee p - prawo przemienności alternatywy

(p \wedge q) \wedge r\quad \Leftrightarrow \quad  p \wedge (q \wedge r) - prawo łączności koniunkcji

(p \vee q) \vee r \quad \Leftrightarrow \quad  p \vee (q \vee r) - prawo łączności alternatywy

p \wedge (q \vee r)\quad \Leftrightarrow \quad (p \wedge q) \vee(p \wedge r) - prawo rozdzielności koniunkcji względem alternatywy

p \vee (q \wedge r)\quad \Leftrightarrow \quad (p\vee q) \wedge (p \vee r) - prawo rozdzielności alternatywy względem koniunkcji

[(p \Rightarrow q) \wedge (q \Rightarrow r)] \quad \Rightarrow \quad (p \Rightarrow r) - prawo przechodniości implikacji

\sim(\sim p) \quad \Leftrightarrow \quad p - prawo podwójnego zaprzeczenia

[(p \wedge (p \Rightarrow q)] \quad \Rightarrow \quad q - prawo odrywania

\sim(p \Rightarrow q)\quad \Leftrightarrow \quad (p \wedge \sim q) - prawo zaprzeczenia implikacji

(p \Rightarrow q) \quad \Leftrightarrow \quad (\sim q \Rightarrow \sim p) - prawo kontrapozycji

Nie ma potrzeby uczenia się tych wzorów na pamięć. Najważniejsze to umieć z nich sprawnie korzystać.




FUNKCJE ZDANIOWE


Funkcję zdaniową (formułę zdaniową) zmiennej x określonej na zbiorze M, nazywamy wyrażenie zawierające zmienną x, które staje się zdaniem, gdy w miejsce tej zmiennej wstawimy dowolny element ze zbioru M.

Element spełnia funkcję zdaniową, jeżeli po podstawieniu tego elementu w miejsce zmiennej otrzymamy zdanie prawdziwe.

Zbiór elementów, które możemy podstawić ze zmienne, nazywamy dziedziną funkcji zdaniowej.


Przykładowe funkcje zdaniowe:

\bigwedge_{x} \quad x^2 + 2 > 0 - zdanie prawdziwe

\bigvee_{x} \quad x^2 + 2 < 0 - zdanie fałszywe




PRAWA DE MORGANA


\sim (p \wedge q) \quad \Leftrightarrow \quad (\sim p) \vee (\sim q)

\sim (p \vee q) \quad \Leftrightarrow \quad (\sim p) \wedge (\sim q)

\sim(\bigwedge_{x} p(x)) \quad \Leftrightarrow \quad \bigvee_{x} \sim p(x)

\sim(\bigvee_{x} p(x)) \quad \Leftrightarrow \quad \bigwedge_{x} \sim p(x)




Przykład 1 (zakres akademicki):
Sprawdź, czy następujące zdania są tautologiami:
a) (p \Rightarrow q) \quad \Rightarrow \quad [p \Rightarrow (q \vee r)]
b)  p \Rightarrow [(\sim p) \vee q)]

a) Przypuśćmy, że wyrażenie w((p \Rightarrow q) \quad \Rightarrow \quad [p \Rightarrow (q \vee r)]) = 0 , stąd w(p \Rightarrow q)=1 oraz w(p \Rightarrow (q \vee r))=0 to w(p \Rightarrow q)=1 oraz  w(p)=1 oraz  w(p \vee q)=0 to w(p \Rightarrow q)=1 oraz w(p)=1 oraz w(q)=0 oraz w(r)=0.
Jeśli więc w(p)=1 i  w(q)=0 to w(p \Rightarrow q)=0

Otrzymana sprzeczność dowodzi, że powyższe wyrażenie jest tautologią.

b) Przypuśćmy, że wyrażenie w(p \Rightarrow [(\sim p) \vee q)])=0 stąd w(p)=1 i w(( \sim p) \vee q)=0 stąd w(p)=1 i w(\sim p)=0 i w(q)=0 stąd  w(p)=1 i w(q)=0

Dla wartościowań w(p)=1 oraz w(q)=0 wyrażenie ma wartość 0, a więc nie jest tautologią.


Powyższą metodę możemy stosować tylko do implikacji. Co więcej, ten sposób pojawia sie dopiero na studiach. Jeśli jednak zamiast implikacji będzie np. równoważność? W takim przypadku niezbędne jest przedstawienie wyrażenia za pomocą tabeli. Aby poprawnie narysować tabelę niezbędna będzie umiejętność wyodrębniania poszczególnych części wyrażenia.



Przykład 2:
Sprawdź, czy wyrażenie [p \vee (q \vee r)] \Leftrightarrow [(p \vee q) \vee r] jest tautologią.

Najpierw sprawdzamy jakie zdania pojawiają się w wyrażeniu. W tym przypadku są to: p, q, r. Następnie wyznaczamy odpowiednie części wyrażeń (pierwszeństwo mają te w nawiasach).

<br />\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline \\ <br />p & q & r & (q \vee r) & \overbrace{p \vee (q \vee r)}^A & (p \vee q) & \overbrace{(p \vee q) \vee r}^B &  A \Leftrightarrow B \\ \hline  \end{tabular}

Jak widać na początku zapisujemy zdania, a następnie poszczególne częsci wyrażenia. Na końcu zapisujemy całe wyrażenie. Następnie zapisujemy każde możliwe relacje, jakie mogą istnieć pomiędzy zdaniami p, q i r. Na koniec rozwiązujemy resztę tabeli. Jeżeli w ostatniej kolumnie będą same 1, to wyrażenie jest tautologią. Jeśli zaś pojawi się chociaż jedne 0, to wyrażenie nie jest tautologią.

<br />\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline \\<br />p & q & r & (q \vee r) & \overbrace{p \vee (q \vee r)}^A & (p \vee q) & \overbrace{(p \vee q) \vee r}^B &  A \Leftrightarrow B \\ \hline<br />1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline<br />1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline<br />1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline<br />1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline<br />0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline<br />0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ \hline<br />0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline<br />0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline<br /> \end{tabular}

Jak widać w ostatniej kolumnie są tylko 1, a więc wyrażenie jest tautologią.

Bardzo ciężko jest skomentować powyższą tabelę. Jeśli zna się zależności zdań w alternatywie, implementacji, koniunkcji, itd., to całość powinna być zrozumiała. (Każdy wiersz rozpatrujemy z osobna, od lewej do prawej).

Najwięcej trudności może sprawić wyodrębnienie poszczególnych części wyrażenia. Jestem jednak przekonany, że po kilku rozwiązanych przykłądach wszystko będzie wyglądało na łatwe, wręcz oczywiste.