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 stwierdz
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. Sprawdz
metodÄ… zero-jedynkowÄ… czy podane schematy sÄ… tautologiami:
(a) prawa de Morgana
(b) dowolny schemat dwuargumentowy
(c) prawo przeczenia implikacji
(d)
(e)
Zad. 5. Sprawdz
bez użycia metody zero-jedynkowej czy podane schematy są tautologiami:
(a)
(b)
(c)
Zad. 6. Sprawdz
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:
Matematyka dyskretna  dr Marcin Raniszewski