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. ♦
1
0
0
1
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
q
p ∧ q
„ p ∧ q”. Wartość logiczną koniunkcji definiuje tabela. ♦
1
1
1
1
0
0
Koniunkcja jest prawdziwa tylko wtedy, gdy obydwa zdania są prawdziwe.
0
1
0
0
0
0
DEFINICJA 1.4 (alternatywa - suma logiczna).
Alternatywą zdań p oraz q nazywamy zdanie „ p lub q”, które zapisujemy symbo-p
q
p ∨ q
1
1
1
licznie „ p ∨ q”. Wartość logiczną alternatywy definiuje tabela. ♦
1
0
1
Alternatywa jest fałszywa tylko wtedy, gdy obydwa zdania s
0
1
1
ą fałszywe.
0
0
0
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. ♦
1
1
0
Alternatywa wykluczaj
1
0
1
ąca jest zdaniem prawdziwym tylko wtedy, gdy jedno zdanie jest
0
1
1
prawdziwe, a drugie fałszywe. RóŜni się ona od alternatywy zwykłej.
0
0
0
DEFINICJA 1.6 (implikacja).
p
q
Implikacj
p ⇒ q
ą nazywamy zdanie postaci „JeŜeli p, to q”, które zapisujemy symbolicznie 1
1
1
„ p ⇒ q”. Wartość logiczną implikacji definiuje tabela. Zdanie p nazywamy poprzedni-
1
0
0
kiem, a zdanie q nastę pnikiem implikacji. ♦
0
1
1
0
0
1
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
1
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
p ⇔ q
lub zdanie „ p jest równowaŜne q”, które zapisujemy symbolicznie „ p ⇔ q”. Wartość 1
1
1
1
0
0
logiczną równowaŜności definiuje tabela. ♦
0
1
0
0
0
1
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
p
q
~ q p ∨ ~ q ( p ∨ ~ q) ∧ p
z formuły rachunku zdań
1
1
0
1
1
( p ∨ ~ q) ∧ p,
1
0
1
1
1
0
1
0
0
0
dla kaŜdego z moŜliwych podstawień, wygodnie jest posłu-
0
0
1
1
0
Ŝ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
2
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
~ ( p ⇒ q)
~ q
p ∧ ~ q
~ ( p ⇒ q) ⇔ ( p ∧ ~ q)
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
1
0
0
0
1
0
0
1
0
1
0
1
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
1
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,
1
pn .
q
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 .
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) .
T
♦
dr Dymitr Słezion
3
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
4
Matematyka