1 rachunek zdan

Temat 1

RACHUNEK ZDAŃ

Język potoczny nie jest dostatecznie dobrym narzędziem do budowania i opisu teorii matematycznych. Do tego celu służy język logiki matematycznej. Podamy podstawowe informacje o tym języku.

DEFINICJA 1.1 (zdanie, wartość logiczna zdania).

Zdaniem w sensie logiki nazywamy wypowiedź, która jest prawdziwa albo fałszywa.

Przyjmujemy, że wartoś cią logiczną zdania prawdziwego jest liczba 1, a wartością logiczną zdania fałszywego jest liczba 0. Zdania oznaczamy małymi literami. ♦

Z danych zdań budujemy zdania złożone za pomocą spójników logicznych. Podamy ich definicje.

DEFINICJA 1.2 (negacja − zaprzeczenie).

Negacją ( zaprzeczeniem) zdania p nazywamy zdanie „Nie p” lub „Nieprawda, że p”, które p

~ p

zapisujemy symbolicznie „~ p ”. Wartość logiczną negacji definiuje tabela. ♦

Negacja zdania prawdziwego jest zdaniem fałszywym, a fałszywego prawdziwym.

DEFINICJA 1.3 (koniunkcja − iloczyn logiczny).

Koniunkcją zdań p oraz q nazywamy zdanie „ p i q”, które zapisujemy symbolicznie p

p ∧ q

„ p ∧ q”. Wartość logiczną koniunkcji definiuje tabela. ♦

Koniunkcja jest prawdziwa tylko wtedy, gdy obydwa zdania są prawdziwe.

DEFINICJA 1.4 (alternatywa - suma logiczna).

Alternatywą zdań p oraz q nazywamy zdanie „ p lub q”, które zapisujemy symbo-p

p ∨ q

licznie „ p ∨ q”. Wartość logiczną alternatywy definiuje tabela. ♦

Alternatywa jest fałszywa tylko wtedy, gdy obydwa zdania s

ą fałszywe.

DEFINICJA 1.5 (alternatywa wykluczająca).

Alternatywą wykluczają cą zdań p oraz q nazywamy zdanie „ p albo q”, które zapisujemy p

q p ∨ q

symbolicznie „ p ∨ q”. Wartość logiczną alternatywy wykluczającej definiuje tabela. ♦

Alternatywa wykluczaj

ąca jest zdaniem prawdziwym tylko wtedy, gdy jedno zdanie jest

prawdziwe, a drugie fałszywe. Różni się ona od alternatywy zwykłej.

DEFINICJA 1.6 (implikacja).

Implikacj

p ⇒ q

ą nazywamy zdanie postaci „Jeżeli p, to q”, które zapisujemy symbolicznie 1

„ p ⇒ q”. Wartość logiczną implikacji definiuje tabela. Zdanie p nazywamy poprzedni-

kiem, a zdanie q nastę pnikiem implikacji. ♦

Implikacja jest zdaniem fałszywym tylko wtedy, gdy poprzednik jest zdaniem prawdziwym, a następnik fałszywym. Implikacji nie można utożsamiać z wnioskowaniem, które polega na tym, że ze zdania prawdziwego p − założ enia, wyprowadzamy nowe zdanie prawdziwe q − tezę.

dr Dymitr Słezion

Matematyka

DEFINICJA 1.7 (równoważność).

Równoważ noś cią zdań p oraz q nazywamy zdanie „ p wtedy i tylko wtedy, gdy q”

p ⇔ q

lub zdanie „ p jest równoważne q”, które zapisujemy symbolicznie „ p ⇔ q”. Wartość 1

logiczną równoważności definiuje tabela. ♦

Równoważność jest prawdziwa tylko wtedy, gdy obydwa zdania mają jednakową war-

tość logiczną.

DEFINICJA 1.8 (zmienna zdaniowa, formuła rachunku zdań).

1. Literę, w miejsce której możemy wstawić dowolne zdanie, nazywamy zmienną zdaniową.

2. Wyrażenie zbudowane ze zmiennych zdaniowych i spójników logicznych, które po podstawieniu za zmienne dowolnych zdań staje się zdaniem, nazywamy formułą rachunku zdań. ♦

Aby zagwarantować jednoznaczność zapisów zdań złożonych i formuł rachunku zdań ustalamy kolejność działania spójników logicznych oraz używamy nawiasów.

UMOWA 1.1 (kolejność działania spójników logicznych).

Jeżeli nie ma nawiasów, to obowiązuje następująca kolejność działania spójników logicznych: ~ , ∧ , ∨ oraz

∨ , ⇒ , ⇔. Kolejność działania ∨ oraz ∨ ustalają nawiasy. ♦

UWAGA 1.1 (sprawdzanie zerojedynkowe).

Jeżeli wyznaczamy wartość logiczną zdania złożonego, to nie jest dla nas ważna treść zdań, z których jest ono zbudowane, a jedynie ich wartości logiczne. Zatem, aby wyznaczyć wartość logiczną zdania, które powstaje z formuły rachunku zdań, po podstawieniu konkretnych zdań za zmienne zdaniowe, należy wykonać operacje zdefiniowane w tabelach spójników logicznych na wartościach logicznych wstawianych zdań. Jest to sprawdza-

nie zerojedynkowe wartości logicznych zdań złożonych. ♦

PRZYKŁAD 1.1 (sprawdzanie zerojedynkowe).

Aby określić wartość logiczną zdania, które powstaje

~ q p ∨ ~ q ( p ∨ ~ q) ∧ p

z formuły rachunku zdań

( p ∨ ~ q) ∧ p,

dla każdego z możliwych podstawień, wygodnie jest posłu-

żyć się przedstawioną obok tabelą. ♦

DEFINICJA 1.9 (tautologia − prawo rachunku zdań).

Tautologią albo prawem rachunku zdań nazywamy danie złożone, która jest prawdziwe niezależnie od tego jakimi zdaniami są wchodzące w jego skład zdania. ♦

Podamy najważniejsze tautologie.

TWIERDZENIE 1.1 (tautologie − prawa rachunku zdań).

1. ~ (~ p) ⇔ p,

podwójna negacja.

2. p ∧ q ⇔ q ∧ p,

przemienność koniunkcji.

3. p ∨ q ⇔ q ∨ p,

przemienność alternatywy.

dr Dymitr Słezion

Matematyka

4. ~ ( p ∧ q) ⇔ (~ p ∨ ~ q),

zaprzeczenie koniunkcji − prawo de Morgana.

5. ~ ( p ∨ q) ⇔ (~ p ∧ ~ q),

zaprzeczenie alternatywy − prawo de Morgana.

6. ~ ( p ⇒ q) ⇔ ( p ∧ ~ q),

zaprzeczenie implikacji.

7. [( p ⇒ q) ∧ ( q ⇒ r)] ⇒ ( p ⇒ r),

przechodniość implikacji.

8. [( p ⇒ q) ∧ ( q ⇒ p)] ⇔ ( p ⇔ q),

zwią zek implikacji z równoważ noś cią . ♦

Aby wykazać, że formuła rachunku zdań jest tautologią należy wykazać, stosując sprawdzenie zerojedynkowe, że przy dowolnym podstawieniu zdań w miejsce zmiennych zdaniowych otrzymujemy z formuły zdanie prawdziwe. Dla przykładu wykażemy, że formuła 6 jest tautologią.

p ⇒ q

~ ( p ⇒ q)

~ q

p ∧ ~ q

~ ( p ⇒ q) ⇔ ( p ∧ ~ q)

UWAGA 1.2 (schemat wnioskowania, dowód wprost).

Schematem wnioskowania nazywamy postępowanie w wyniku którego, mając pewien zbiór zdań prawdziwych: p ,

K p

n , które nazywamy przesłankami albo założ eniami, i korzystając z definicji pojęć oraz praw rachunku zdań, dołączamy do nich nowe zdanie prawdziwe q, które nazywamy wnioskiem albo tezą. Schemat wnioskowania zapisujemy symbolicznie w postaci:

p ,K,

pn .

Ciąg schematów wnioskowania, który pozwala na dołączenie zdania q do zbioru zdań prawdziwych nazywamy dowodem wprost zdania q. ♦

Typowe schematy wnioskowania formułuje się w postaci reguł wnioskowania. Podamy przykład najczęściej stosowanej reguły wnioskowania.

UWAGA 1.3 (reguła odrywania).

Z definicji implikacji (Def. 1.6) wynika, że jeżeli prawdziwe są zdania p oraz p ⇒ q, to prawdziwe jest zdanie q i można je dołączyć do zbioru zdań prawdziwych. Ten schemat wnioskowania nazywamy regułą

odrywania i zapisujemy symbolicznie w postaci:

p, p ⇒ q .

♦

UWAGA 1.4 (dowód nie wprost).

Jeżeli przy założeniu, że twierdzenie T jest fałszywe, uzyskamy sprzeczność, czyli zdanie i jego zaprzeczenie, to T jest prawdziwe. Jest to dowód nie wprost twierdzenia T. W zapisie symbolicznym:

~ T ⇒ ( r∧ ~ r) .

♦

dr Dymitr Słezion

Matematyka

UWAGA 1.5 (teoria dedukcyjna).

Poję ciami pierwotnymi nazywamy najprostsze pojęcia, które przyjmujemy jako oczywiste i nie podajemy ich definicji (opisu).

Aksjomatami albo pewnikami nazywamy stwierdzenia, które przyjmujemy jako prawdziwe (nie dowodzi-my ich prawdziwości).

Definicją pojęcia nazywamy opis tego pojęcia za pomocą pojęć pierwotnych lub pojęć wcześniej zdefiniowanych wraz z ustaleniem jego nazwy.

Twierdzeniem nazywamy zdanie prawdziwe, które dołączamy do zbioru zdań prawdziwych podając jego dowód, w którym przesłankami są pewniki lub wcześniej dołączone (udowodnione) twierdzenia.

Jeżeli dane są pojęcia pierwotne oraz aksjomaty, to zbiór zdefiniowanych na tej bazie pojęć i udowodnio-nych twierdzeń nazywamy teorią dedukcyjną. ♦

Matematyka jest nauką dedukcyjną. Przykładami pojęć pierwotnych mogą być: punkt, prosta, płaszczyzna, liczby naturalne, zbiór; przykładami aksjomatów mogą być zdania: „Przez dwa różne punkty przechodzi dokładnie jedna prosta”, „Przez trzy różne punkty, nie leżące na jednej prostej, przechodzi dokładnie jedna płaszczyzna”.

ZADANIA 1

1.1 Stwierdzić, która z następujących wypowiedzi jest zdaniem w sensie logiki, w przypadku zdania podać jego wartość logiczną:

a) Góry są piękne.

b) Wisła wpada do Bałtyku.

c) x 2 = 4.

d) 13 > 28.

1.2. Stosując odpowiednie tautologie zapisać zaprzeczenia zdań oraz wypowiedzi, które w konkretnej sytuacji są zdaniami.

a) Gram na skrzypcach lub śpiewam.

b) 3

( < − )

5 ∧ 3

( > )

0 .

c) 8 jest liczbą parzysta i mniejszą od 3.

d) (4

)

2 ⇒

(4 > 10) .

1.3. Stosując sprawdzanie zerojedynkowe wykazać, że formuły 1 − 5 z Tw. 1.1. są prawami rachunku zdań.

Odpowiedzi, wskazówki.

1.1. b) 1. d) 0. 1.2. a) Nieprawda, że gram na skrzypcach lub śpiewam. Nie gram na skrzypcach i nie śpiewam.

b) [∼(3 < −5)∧(3 > 0)]⇔ [ 3

( ≥ − )

5 ∨ 3

( ≤ )

0 ] . c) Nieprawda, że 8 jest liczbą parzystą i mniejszą od 3. 8 nie jest liczbą parzystą lub jest większe albo równe 3. d) ~[(4 > 2) ⇒ (4 > 10)] ⇔ [(4 > 2) ∧ (4 ≤ 10)] .

WYMAGANE WIADOMOŚCI I UMIEJĘTNOŚCI

1. Definicje spójników logicznych, zmiennej zdaniowej i formuły rachunku zdań, tautologi − prawa logicznego.

2. Sprawdzanie zerojedynkowe wartości logicznej zdania złożonego.

dr Dymitr Słezion

Matematyka