Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
1
Matematyka dyskretna składa się z działów
matematyki, które zajmują się badaniem
struktur zawierających zbiory przeliczalne (czyli
dyskretne).
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
1
Matematyka dyskretna składa się z działów
matematyki, które zajmują się badaniem
struktur zawierających zbiory przeliczalne (czyli
dyskretne).
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
2
Dwa zbiory i nazywamy równolicznymi,
jeśli istnieje bijekcja .
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
3
Zbiór przeliczalny to zbiór skończony lub
równoliczny ze zbiorem liczb naturalnych .
Przyjmujemy, że .
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
4
Zbiory przeliczalne:
zbiór liczb naturalnych ,
zbiór liczb parzystych ,
zbiór liczb nieparzystych ,
…
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
5
Suma dwóch zbiorów przeliczalnych jest
zbiorem przeliczalnym.
Zbiór liczb całkowitych jest zbiorem
przeliczalnym.
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
6
Iloczyn kartezjański zbiorów przeliczalnych jest
zbiorem przeliczalnym.
Zbiór
liczb
wymiernych
jest
zbiorem
przeliczalnym.
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
7
Zbiór nieprzeliczalny to zbiór, który nie jest
przeliczalny.
Zbiór
liczb
rzeczywistych
jest
zbiorem
nieprzeliczalnym.
Zbiór liczb niewymiernych jest zbiorem
nieprzeliczalnym.
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
8
Niech będą dowolnymi zdaniami
wypowiadanymi w matematyce.
Będziemy przypisać im dwie wartości logiczne:
prawdę lub fałsz. Prawdę będziemy oznaczać
symbolem 1, zaś fałsz symbolem 0.
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
9
- wartości logiczne zdań i
- zdanie jest prawdziwe
- zdanie jest fałszywe
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
10
Funktory zdaniotwórcze – służą do łączenia
zdań lub funkcji zdaniowych w większe zdania
lub funkcje zdaniowe (tzw. schematy).
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
11
Funktory zdaniotwórcze dwuargumentowe:
- koniunkcja („i”),
- alternatywa („lub”),
- implikacja („jeśli …, to …”),
- równoważność („… tylko i tylko wtedy,
gdy …”).
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
12
Funktor zdaniotwórczy jednoargumentowy:
- negacja („nie prawda, że …”).
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
13
0 0
1
0
0
1
1
0 1
1
0
1
1
0
1 0
0
0
1
0
0
1 1
0
1
1
1
1
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
14
Tautologią (prawem rachunku funkcyjnego)
nazywamy dowolny schemat, który jest zawsze
prawdziwy (niezależnie od wartości logicznych
tworzących go zdań lub funkcji zdaniowych).
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
15
Znane tautologie:
1. Prawo tożsamości:
2. Prawa przemienności:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
16
3. Prawa łączności:
4. Prawa rozdzielności:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
17
5. Prawo wyłączonego środka:
6. Prawa idempotentności:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
18
7. Prawo podwójnej negacji:
8. Prawa De Morgana:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
19
9. Prawo kontrapozycji:
10. Prawo sylogizmu:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
20
11. Prawa pochłaniania:
12. Prawo odrywania:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
21
13.
14. Prawo eliminacji implikacji
15. Prawo przeczenia implikacji
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
22
Sprawdź bez użycia metody zero-jedynkowej
czy podane schematy są tautologiami:
jedno z praw De Morgana
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
23
– poprzednik implikacji (założenie
twierdzenia)
– następnik implikacji (teza twierdzenia)
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
24
Implikacja prosta:
Implikacja przeciwstawna:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
25
Implikacja odwrotna:
Implikacja przeciwna:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
26
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
27
Kwadrat logiczny:
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
28
jest warunkiem wystarczającym na to by .
jest warunkiem koniecznym na to by .
Matematyka Dyskretna – wykład 1
dr Marcin Raniszewski
29
jest
warunkiem
koniecznym
i wystarczającym na to by .
jest
warunkiem
koniecznym
i wystarczającym na to by .