[Logika] Tautologia rachunku zdań, funkcje zdaniowe :: Kompendium / Polski Serwis Naukowy

Polecamy również:

List- przykładowe zdania

[F.wielomianowa] Rozkład na czynniki, dodawanie, mnożenie, dzielenie wielomianów

[Stężenia] Stężenia procentowe i molowe

[Funkcje] Pojęcie funkcji

[Funkcje] Przebieg zmienności funkcji

[Funkcje] Ciągi liczbowe

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

jest prawdziwe, to zdanie $\sim p$ jest fałszywe. Jeśli zaś zdanie

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

oraz

.
Jeśli więc w(p)=1

i

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

i

Dla wartościowań w(p)=1

oraz

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).

$\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline \\ 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ą.

$\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline \\ 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 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline \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.

komentuj publikację