Informatyka MIMUW

Wprowadzenie

---

Logika zdaniowa jest językiem, który pozwala opisywać zależności pomiędzy zdaniami. Przykładem może być zdanie:


Jeśli $\mathrm {n}$ jest liczbą pierwszą to $\mathrm {n}$ jest liczbą nieparzystą lub $\mathrm {n}$ jest równe 2. W powyższym zdaniu spójniki jeśli [..] to, lub mówią o związkach które zachodzą pomiędzy zdaniami:

1. $\mathrm {n}$ jest liczbą pierwszą,
2. $\mathrm {n}$ jest liczbą nieparzystą,
3. $\mathrm {n}$ jest równe 2.

Oznaczmy powyższe zdania przez $p,q,r$ (w takiej właśnie kolejności). Używając symboli, które zwyczajowo odpowiadają potocznemu rozumieniu spójników jeśli [..] to, lub oraz powyższych oznaczeń, otrzymamy formułę

$p \Rightarrow (q \vee r).$

Jeśli powyższą formułę uznamy za prawdziwą, to może nam ona posłużyć do otrzymania nowych wniosków. Na przykład, jeśli o jakiejś liczbie $\mathrm {n}$ będziemy wiedzieć, że jest liczbą pierwszą oraz że nie jest nieparzysta, to klasyczny rachunek zdań pozwoli nam formalnie wywnioskować fakt, że liczba $\mathrm {n}$ jest równa 2. Podsumowując, jeśli uznamy za prawdziwe następujące zdania:

1. $p \Rightarrow (q \vee r)$,
2. $p$,
3. $\neg q$ (przez $\neg$ oznaczamy negację)

to zgodnie z klasycznym rachunkiem zdań powinniśmy uznać za prawdziwe zdanie $\mathrm {r}$, czyli $\mathrm {n}$ jest równe 2. Powyższy schemat wnioskowania można również opisać formułą

$((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q))\Rightarrow q.$

W powyższej formule symbol $\wedge$ odpowiada spójnikowi $\mathrm {i}$ (oraz).

Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy wnioskowania i zdania złożone oraz oceniać ich prawdziwość.