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ść.