M1.pdf

Logika i teoria mnogości

Mirosław Kurkowski

Kierownik projektu: Joanna Opoka

Redaktor: Ilona Urbańska-Grzyb

Metodycy: Agnieszka Budzyńska, Ilona Urbańska-Grzyb

Grafik: Izabela Świątkowska-Wośko

Informatyk: Maciej Czerczak

Wstęp do rachunku zdań

Wstęp

1. Zdania. Zmienne zdaniowe. Wartościowania

2. Spójniki i formuły rachunku zdań. Notacja polska

3. Tabele wartości logicznych

4. Tautologie i kontrtautologie. Metody weryﬁkacjitautologiczności

5. Deﬁniowalnośćspójników.Układy pełne

6. Postaci normalne formuł rachunku zdań

Bibliograﬁa

Wstęp

Do precyzyjnego opisu jakiejkolwiek rzeczywistości niezbędny jest odpowiednio

sformalizowany język, który umożliwia wyrażanie (specyﬁkowanie) dowolnych

zjawisk (sytuacji, zdarzeń) zachodzących w danym świecie. Często — badając jakąś

rzeczywistość — nie chcemy poprzestać tylko na samym jej opisie. Potrzebujemy

narzędzi, pozwalających na odpowiednie przetwarzanie zapisanej w postaci sym-

bolicznej (sformalizowanej) informacji, w celu wyciągania z niej wniosków. Logika

jest nauką zajmującą się właśnie między innymi formalnym opisem świata i dostar-

czaniem narzędzi umożliwiających odpowiednie wnioskowanie.

W module tym przedstawimy elementy klasycznej logiki zdaniowej (rachunku

zdań), najprostszego i zarazem najbardziej rozpowszechnionego rachunku logicz-

nego. Wprowadzimy pojęcia zmiennej zdaniowej oraz wartościowania zmiennych.

Przedstawimy deﬁnicję oraz omówimy strukturę formuł rachunku zdań. Omówi-

my także polską notację formuł. Zdeﬁniujemy pojęcia tautologii oraz kontrtauto-

logii i podamy ich przykłady. Również na przykładach omówimy metody weryﬁ-

kacji tautologiczności/kontrtautologiczności formuł. Przedstawimy również posta-

ci normalne formuł logiki zdaniowej oraz ich związki z pojęciami tautologiczności

oraz kontrtautologiczności.

1. Zdania. Zmienne zdaniowe.

Wartościowania

Zdaniem w sensie logicznym nazywamy dowolne wyrażenie, o którym jesteśmy

w stanie orzec, czy jest prawdziwe, czy fałszywe. Intuicyjnie rozróżniamy wśród

zdań logicznych zdania proste i zdania złożone. Przykładem zdania prostego jest

zdanie: „Kot pĳe mleko”, aprzykładem zdania złożonego: „Kot pĳe mleko a mysz

je ser”. Nietrudno zauważyć, że przykładami prostych zdań logicznych są w języku

polskim zdania orzekające typu: „Słońce świeci”, „Zosia podlewa kwiatki”, „Robert

lubi Jana” lub znane wyrażenia matematyczne w rodzaju: „2 + 4 = 6”, „3 ≤ 4” itp.

Każdemu takiemu zdaniu przyporządkowujemy literę alfabetu, nazywaną dalej

zmienną zdaniową (możemy tutaj założyć, że mamy nieskończenie wiele liter do

dyspozycji lub indeksujemy je kolejnymi liczbami naturalnymi).

Dobrym przykładem jest następujące przyporządkowanie:

„Kot pĳe mleko” — p ,

„Słońce świeci” — q ,

„Zosia podlewa kwiatki” — r ,

„Robert lubi Jana” — s, itp.

Zmienne reprezentują więc po prostu jakieś zdania proste opisujące daną (dowol-

ną) rzeczywistość.

Zmiennym zdaniowym przyporządkowujemy jedną z dwóch liczb: 0 lub 1 (tzw.

wartości logiczne) — w zależności od tego, czy dana zmienna reprezentuje zdanie

fałszywe, czy prawdziwe. Przyporządkowania takie nazywamy wartościowaniami.

Kolejne kolumny w tabeli 1 reprezentują takie wartościowania.

v 1 v 2 v 3 v 4 …

p 1 0 0 1 …

q 0 1 1 0 …

r 0 1 1 1 …

s 1 0 0 1 …

… … … … … …

Tabela 1

Zauważmy, że wartościowania te określają pewne rzeczywistości. Odpowiednio:

— wartościowanie v 1 określa rzeczywistość, w której:

Kot pĳe mleko.

Słońce nie świeci.

Zosia nie podlewa kwiatków.

Robert lubi Jana.

.............

— wartościowanie v 2 określa rzeczywistość, w której:

Kot nie pĳe mleka.

Słońce świeci.

Zosia podlewa kwiatki.

Robert nie lubi Jana.

..............

I tak dalej.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: