Matematyka dyskretna – dr Marcin Raniszewski

Matematyka Dyskretna – ćw. 1

Elementy logiki

Zdania, wartości logiczne zdań, funktory zdaniotwórcze, tautologie

Niech zdania

będą dowolnymi zdaniami wypowiadanymi w matematyce. Będziemy im

przyporządkowywać dwie wartości logiczne: prawdę (oznaczaną symbolem 1) lub fałsz (oznaczaną symbolem
0). Dla zdań

, niech oznaczają wartości logiczne tych zdań. Zatem:



czytamy: „zdanie p jest zdaniem prawdziwym”



czytamy: „zdanie q jest zdaniem fałszywym”

Zdania możemy łączyć funktorami zdaniotwórczymi w nowe zdania. Funktory zdaniotwórcze to:



koniunkcja („… i …”): symbol



alternatywa („… lub …”): symbol



implikacja („jeśli … to …”): symbol



równoważność („… wtedy i tylko wtedy, gdy …”): symbol



negacja („nie prawda, że …”): symbol

0

0

0

0

1

1

1

0

1

0

1

1

0

1

1

0

0

1

0

0

0

1

1

1

1

1

1

0

Tautologią będziemy nazywać każde zdanie, które jest zawsze prawdziwe, niezależnie od wartości logicznych
zdań je tworzących.

Niektóre znane tautologie:



(prawo tożsamości)



(prawo wyłączonego środka)



(prawo podwójnej negacji)



(prawo De Morgana dla koniunkcji)



(prawo De Morgana dla alternatywy)



(prawo przeczenia implikacji)



(prawo kontrapozycji)

Kilka faktów o implikacji

:



nazywamy poprzednikiem, zaś nazywamy następnikiem implikacji



jeśli

jest twierdzeniem, to nazywamy warunkiem wystarczającym na to by , zaś

nazywamy warunkiem koniecznym na to by



implikację

nazywamy odwrotną do implikacji prostej

Zad. 1. Określ wartość logiczną zdań:

(a) Jestem kobietą i jechałam dziś tramwajem

Matematyka dyskretna – dr Marcin Raniszewski

(b) Jestem mężczyzną lub jestem kobietą
(c) Moje imię zaczyna się na M i świat jest płaski
(d) Jeśli świat jest płaski to 3 < 7
(e) Jeśli 3 < 7, to świat jest płaski
(f) Jestem kobietą wtedy i tylko wtedy, gdy mam pomalowane paznokcie
(g) Jeśli 2 + 3 = 4 to 2 + 2 = 3

Zad. 2. Zapisz negacje poniższych zdań, nie stosując symbolu negacji:

(a)

(b)

(c)

(d)

(e)

Zad. 3. Dla każdego z poniższych twierdzeń: napisz twierdzenie równoważne, wypisz
warunek konieczny i wystarczający oraz napisz twierdzenie odwrotne i stwierdź czy jest
prawdziwe:

(a)

(b) jeżeli funkcja jest różniczkowalna w punkcie, to jest ciągła w tym punkcie

(c) jeśli

jest zbieżny, to

(d)

Zad. 4. Sprawdź metodą zero-jedynkową czy podane schematy są tautologiami:

(a) prawa de Morgana
(b) dowolny schemat dwuargumentowy
(c) prawo przeczenia implikacji

(d)

(e)

Zad. 5. Sprawdź bez użycia metody zero-jedynkowej czy podane schematy są tautologiami:

(a)

(b)

(c)

Zad. 6. Sprawdź w którym momencie dalsze przetwarzanie instrukcji if nie jest konieczne:

(a)

a = 3, b = 8, c = -1
if (b > a and b > c) or (c < a):

(b)

x = y = 6, z = -x, v = -z
if (y % 2 == 0 and x % 2 == 1) or (v != z):

(c)

napis = ‘123456’, x = 54.3, y = 0.22
if (len(napis) == 5 or x - y > 60 or y < 1) and (len(napis) > 0):

(d)

a = 3, b = 4, c = 2, d = -1
if a - b < 0 and c * d > b - 1 and b - c > -1: