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 .