Elementy Logiki i Teorii Mnogości PDF

c Piotr Formanowicz Standardowe spójniki logiczne: v. 1.1.2, 2023.10.03 ¬ – negacja ∧ – koniunkcja (iloczyn logiczny) ELEMENTY LOGIKI I TEORII MN...

c Piotr Formanowicz Standardowe spójniki logiczne: v. 1.1.2, 2023.10.03 ¬ – negacja ∧ – koniunkcja (iloczyn logiczny) ELEMENTY LOGIKI I TEORII MNOGOŚCI ∨ – alternatywa (suma logiczna) Materialy pomocnicze do wykladu z Matematyki Dyskretnej → – implikacja ↔ – równoważność Piotr Formanowicz ⊕ – alternatywa wykluczajaca , Jeżeli zdanie sklada sie, z innych zdań polaczonych , za pomoca, spójników logicznych, to jego wartość WSTEP logiczna jest wyznaczona przez wartości logiczne zdań , skladowych. Matematyka dyskretna jest dzialem matematyki, na gruncie którego rozważane sa, zagadnienia dotyczace Wlasności spójników logicznych , zbiorów skończonych oraz przeliczalnych. negacja Znaczenie matematyki dyskretnej bardzo wzroslo wraz p ¬p z rozwojem informatyki, ponieważ pojecia i metody 0 1 , matematyki dyskretnej sa, wykorzystywane do opisu i 1 0 analizy problemów i obiektów rozważanych w wielu koniunkcja obszarach informatyki. p q p∧q Podstawe, calej matematyki stanowia, logika oraz 0 0 0 teoria mnogości. Pelnia, one też bardzo ważna, role, 0 1 0 w matematyce dyskretnej. 1 0 0 1 1 1 LOGIKA alternatywa Logika jest nauka, o ogólnych prawach poprawnego p q p∨q wnioskowania. 0 0 0 0 1 1 Rachunek zdań jest dzialem logiki zajmujacym , sie, 1 0 1 badaniem zwiazków , logicznych miedzy , zdaniami. 1 1 1 Definicja implikacja Zdaniem jest dowolne stwierdzenie, które jest albo p q p→q prawdziwe, albo falszywe i które nie może być 0 0 1 jednocześnie prawdziwe i falszywe.  0 1 1 1 0 0 (Znajomość wartości logicznej zdania nie jest ko- 1 1 1 nieczna do tego, by sie, nim zajmować.) równoważność Przyklady sformulowań, które sa, zdaniami: p q p↔q xy = yx dla wszystkich x, y ∈ N. 0 0 1 3 > 5. 0 1 0 Jeżeli 2 + 2 = 4, to 4 + 4 = 10. 1 0 0 |x| ≥ x dla każdego x ∈ R. 1 1 1 Przyklady sformulowań, które nie sa, zdaniami: alternatywa wykluczajaca , Cóż za piekny , poranek! p q p⊕q Wylacz, komputer. 0 0 0 Czy dzisiaj jest poniedzialek? 0 1 1 x jest liczba, wymierna. , 1 0 1 1 1 0 W rachunku zdań malymi literami alfabetu lacińskiego oznacza sie, zazwyczaj zdania proste. Zdania takie laczy , sie, za pomoca, spójników logicznych, by otrzymać Zdanie odwrotne, zdanie przeciwstawne (kon- zdania zlożone. trapozycja) 1 Definicja (Zamiast symbolu ⇒ stosuje sie, również symbol .) Zdanie q → p jest zdaniem odwrotnym do zdania p → q.  P ⇒ Q wtedy i tylko wtedy, gdy zdanie zlożone P → Q jest tautologia. , Definicja Zdanie ¬q → ¬p jest zdaniem przeciwstawnym Funkcja zdaniowa (lub kontrapozycja) , zdania p → q i jest mu równoważne.  Definicja Funkcja zdaniowa jednej zmiennej, określona w dziedzinie U , jest to wyrażenie zawierajace , te, zmien- p q p → q ¬p ¬q ¬q → ¬p na, które staje sie zdaniem, gdy na miejsce zmiennej , , 0 0 1 1 1 1 podstawiony zostanie dowolny element zbioru U.  0 1 1 1 0 1 1 0 0 0 1 0 Funkcja zdaniowa nazywana jest też forma, zdaniowa, 1 1 1 0 0 1 lub predykatem. Przykladowo, wyrażenie “x jest liczba, parzysta”, , Tautologia, zdanie sprzeczne, zdania logicznie gdzie x należy do zbioru liczb calkowitych, stanie sie, równoważne, implikacje logiczne zdaniem prawdziwym, gdy za x podstawimy liczbe, 2, a jeśli za x podstawimy liczbe, 3, wyrażenie to stanie Definicja sie, zdaniem falszywym. Zdanie zlożone jest tautologia, , jeżeli jest ono praw- dziwe niezależnie od wartości logicznych jego zdań Każde równanie jest funkcja zdaniowa. , , skladowych (zmiennych zdaniowych).  Kwantyfikatory p p→p 0 1 Zasady laczenia , zdań za pomoca, spójników w ra- 1 1 chunku zdań nie dopuszczaja, takich konstrukcji, w których wystepuje , wiecej , niż skończona liczba zdań, Definicja badź , zawierajacych , sformulowania takie jak “dla Jeżeli zdanie zlożone jest falszywe niezależnie od każdego” lub “dla pewnego”. wartości logicznych jego zdań skladowych, to jest ono zdaniem sprzecznym.  W rachunku predykatów wystepuj , a, dwa sformulowania, które pozwalaja, na przedstawie- nie w sposób symboliczny takich zdań jak: p ¬p p ∧ ¬p 0 1 0 p1 ∧ p2 ∧ p3 ∧... ∧ pn 1 0 0 Niech {p(x) : x ∈ U } bedzie , rodzina, zdań, gdzie U jest Definicja zbiorem, być może nieskończonym, czyli p jest funkcja, Jeżeli zdania zlożone P i Q maja, takie same wartości zdaniowa, określona, na zbiorze U. logiczne dla wszystkich możliwych sposobów przypisa- nia wartości logicznych ich zmiennym zdaniowym, to Definicja sa, zdaniami logicznie równoważnymi.  Kwantyfikator ogólny ∀ jest używany do tworzenia zdań zlożonych postaci ∀x p(x), które czytamy, “dla Jeżeli zdania P i Q sa, logicznie równoważne, to każdego x, p(x)”.  piszemy P ⇐⇒ Q. (Zamiast symbolu ⇐⇒ stosuje sie, również symbol ≡.) Zdanie zlożone ∀x p(x) ma przypisana, wartość logiczna, w nastepuj , acy , sposób: zdanie ∀x p(x) jest prawdziwe, P ⇐⇒ Q wtedy i tylko wtedy, gdy zdanie P ↔ Q jeżeli zdanie p(x) jest prawdziwe dla każdego x ∈ U ; jest tautologia. , w przeciwnym przypadku zdanie ∀x p(x) jest falszywe. Definicja Definicja Dla danych dwóch zdań zlożonych P i Q mówimy, że Kwantyfikator szczególowy (egzystencjalny) ∃ zdanie P implikuje logicznie zdanie Q, jeżeli zdanie jest używany do formulowania zdań postaci ∃x p(x), Q ma wartość logiczna, prawdy zawsze wtedy, gdy które czytamy “istnieje x taki, że p(x)”.  zdanie P ma wartość logiczna, prawdy.  Zdanie zlożone ∃x p(x) ma nastepuj , ace , wartości logicz- Jeżeli zdanie P implikuje logicznie zdanie Q, to ne: zdanie ∃x p(x) jest prawdziwe, jeżeli zdanie p(x) piszemy P ⇒ Q. jest prawdziwe dla co najmniej jednego x ∈ U ; zdanie 2 ∃x p(x) jest falszywe, jeśli zdanie p(x) jest falszywe dla (p ∧ T0 ) ⇐⇒ p każdego x ∈ U. prawa odwrotności: Zdanie ∀x p(x) jest falszywe, jeżeli co najmniej jedno (p ∨ ¬p) ⇐⇒ T0 za zdań p(x) jest falszywe. Aby wykazać, że zdanie (p ∧ ¬p) ⇐⇒ F0 ∀x p(x) jest falszywe, wystarczy pokazać, że dla jednej wartości x zdanie p(x) jest falszywe. Innymi slowy, prawa De Morgana: wystarczy pokazać jeden przyklad zaprzeczajacy , ¬(p ∨ q) ⇐⇒ (¬p ∧ ¬q) zdaniu ogólnemu, tzw. kontrprzyklad. ¬(p ∧ q) ⇐⇒ (¬p ∨ ¬q) Funkcja zdaniowa poprzedzona kwantyfikatorem staje prawo kontrapozycji: sie, zdaniem. (p → q) ⇐⇒ (¬q → ¬p) Reguly podstawiania określenie implikacji za pomoca, alternatywy: (p → q) ⇐⇒ (¬p ∨ q) Regula pierwsza Jeżeli zdanie zlożone P jest tautologia, i wszystkie określenie implikacji za pomoca, koniunkcji: wystapienia , pewnej zmiennej p (zdania skladowego) (p → q) ⇐⇒ ¬(p ∧ ¬q) wystepuj , acej , w zdaniu P zastapimy , zdaniem R, to otrzymane zdanie zlożone P1 bedzie , również tauto- określenie równoważności: logia. ,  (p ↔ q) ⇐⇒ [(p → q) ∧ (q → p)] Regula druga prawo eksportacji: Jeżeli zdanie zlożone P zawiera zdanie Q, R jest [(p ∧ q) → r] ⇐⇒ [p → (q → r)] zdaniem takim, że Q ⇐⇒ R i jeśli w P zastapimy , jedno lub wiecej , wystapień , Q przez R, to otrzymamy reductio ad absurdum: zdanie zlożone P2 takie, że P ⇐⇒ P2.  (p → q) ⇐⇒ [(p ∧ ¬q) → F0 ] Prawa rachunku zdań IMPLIKACJE LOGICZNE Niech T0 bedzie , dowolna, tautologia, , a F0 dowolnym wprowadzanie alternatywy: zdaniem sprzecznym. p ⇒ (p ∨ q) ZDANIA LOGICZNIE RÓWNOWAŻNE opuszczanie koniunkcji (p ∧ q) ⇒ p prawo podwójnego przeczenia: (¬¬p) ⇐⇒ p sprowadzenie do sprzeczności: (p → F0 ) ⇒ ¬p prawa przemienności: (p ∨ q) ⇐⇒ (q ∨ p) przechodniość równoważności: (p ∧ q) ⇐⇒ (q ∧ p) [(p ↔ q) ∧ (q ↔ r)] ⇒ (p ↔ r) (p ↔ q) ⇐⇒ (q ↔ p) przechodniość implikacji: prawa laczności: , [(p → q) ∧ (q → r)] ⇒ (p → r) [(p ∨ q) ∨ r] ⇐⇒ [p ∨ (q ∨ r)] [(p ∧ q) ∧ r] ⇐⇒ [p ∧ (q ∧ r)] TEORIA MNOGOŚCI prawa rozdzielności: Teoria mnogości jest dzialem matematyki zaj- [p ∨ (q ∧ r)] ⇐⇒ [(p ∨ q) ∧ (p ∨ r)] mujacym , sie, analiza, pojecia , zbioru oraz ogólnych [p ∧ (q ∨ r)] ⇐⇒ [(p ∧ q) ∨ (p ∧ r)] pojeć , matematycznych definiowanych przez pojecie , zbioru. prawa idempotentności: (p ∨ p) ⇐⇒ p Teoria ta zajmuje sie, wlasnościami zbiorów, które sa, (p ∧ p) ⇐⇒ p niezależne od natury przedmiotów tworzacych , zbiory. prawa identyczności: Twórca, teorii mnogości jest Georg Cantor. (p ∨ F0 ) ⇐⇒ p (p ∨ T0 ) ⇐⇒ T0 Pojecie , zbioru oraz pojecie , należenia do zbioru (p ∧ F0 ) ⇐⇒ F0 przyjmujemy za pojecia , pierwotne. 3  Różnica symetryczna zbiorów Jeżeli obiekt a należy do zbioru A, to piszemy a ∈ A ⊕ B ⇐⇒ [a ∈ (A ∪ B)] ∧ [a ∈ / (A ∩ B)] (czyli A ⊕ B = (A ∪ B) \ (A ∩ B)). a∈A Do zbioru A ⊕ B należa, zatem wszystkie te i tylko te i mówimy, że obiekt a jest elementem zbioru A. Jeżeli elementy, które należa, do zbioru A lub do zbioru B, obiekt a nie jest elementem zbioru A, to piszemy ale nie należa, do obu tych zbiorów jednocześnie. a∈ /A Równość zbiorów Jeżeli a ∈ A oraz b ∈ A, to równość a = b oznacza, że a i b sa, symbolami tego samego elementu zbioru A. Definicja Równość elementów zbioru jest: Dwa zbiory A i B sa, równe, co zapisujemy A = B, jeżeli zawieraja, dokladnie te same elementy.  zwrotna: a = a, symetryczna: (a = b) ⇒ (b = a), Inkluzja przechodnia: [(a = b) ∧ (b = c)] ⇒ (a = c). Istotnym pojeciem w teorii mnogości jest inkluzja, Zbiór określamy podajac, wszystkie jego elementy lub czyli zawieranie sie zbioru w zbiorze, oznaczana , podajac , warunek, który spelniaja, wszystkie (i tylko) symbolem ⊆. , elementy tego zbioru. A ⊆ B ⇐⇒ [(a ∈ A) ⇒ (a ∈ B)] Przyklad: A = {x : x ∈ N ∧ x ≤ 20} oznacza zbiór wszystkich Jeżeli A ⊆ B, to A nazywamy podzbiorem zbioru liczb naturalnych nie wiekszych , niż 20. B, natomiast B nazywamy nadzbiorem zbioru A i możemy napisać B ⊇ A. Pewne szczególne zbiory Z określenia inkluzji i równości zbiorów wynika, że: P – zbiór liczb calkowitych dodatnich (1, 2, 3,...) A = B ⇐⇒ [(A ⊆ B) ∧ (B ⊆ A)]. N – zbiór liczb naturalnych (0, 1, 2, 3,...) Z – zbiór liczb calkowitych (... , −2, −1, 0, 1, 2,...) Jeżeli A ⊆ B i A 6= B, to A nazywamy podzbiorem Q – zbiór liczb wymiernych wlaściwym zbioru B i piszemy A ⊂ B. R – zbiór liczb rzeczywistych C – zbiór liczb zespolonych Inkluzja jest przechodnia, tzn. prawdziwa jest + implikacja [(A ⊆ B) ∧ (B ⊆ C)] ⇒ A ⊆ C. (Zbiór P oznaczany jest też jako Z.) Przestrzeń i dopelnienie zbioru Dzialania na zbiorach Zalóżmy, że wszystkie rozpatrywane przez nas zbiory Niech bed , a, dane dwa zbiory: A i B. sa, podzbiorami pewnego ustalonego zbioru U. Każdy rozpatrywany przez nas zbiór A ma zatem te, wlasność, Suma zbiorów że A ⊆ U. Zbiór U nazywamy w takim przypadku a ∈ (A ∪ B) ⇐⇒ [(a ∈ A) ∨ (a ∈ B)]. przestrzenia. , Do zbioru A ∪ B należa, zatem wszystkie i tylko te Dopelnienie zbioru A do przestrzeni U , które elementy, które należa, do zbioru A lub do zbioru B. oznaczymy symbolem A, określone jest jako A = U \A. Iloczyn zbiorów Zbiór pusty i zbiór potegowy a ∈ (A ∩ B) ⇐⇒ [(a ∈ A) ∧ (a ∈ B)]. , Definicja Do zbioru A ∩ B należa, zatem wszystkie i tylko te Zbiór nie majacy żadnych elementów jest zbiorem elementy, które należa, jednocześnie do zbioru A i do , pustym i oznaczany jest symbolem ∅.  zbioru B. Zbiór pusty jest podzbiorem każdego zbioru, gdyż Różnica zbiorów zdanie “jeżeli x ∈ ∅, to x ∈ A” jest logicznie prawdziwe. a ∈ (A \ B) ⇐⇒ [(a ∈ A) ∧ (a ∈ / B)]. Definicja Do zbioru A \ B należa, zatem wszystkie te i tylko te Zbiór wszystkich podzbiorów zbioru A nazywamy elementy, które należa, do zbioru A, ale nie należa, do zbiorem potegowym zbioru A i oznaczamy symbo- zbioru B. , lem P(A).  4  rozdzielność dodawania wzgledem , mnożenia: |P(A)| = 2|A| , gdzie |A| oznacza moc zbioru A. (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C) Przedzial, alfabet, slowo, jezyk , prawa idempotentności: A∪A=A Przedzialy A∩A=A Można określić pewne szczególne podzbiory zbioru R nazywane przedzialami. prawa identyczności: Dla a, b ∈ R, gdzie a < b określamy: A∪∅=A [a, b] = {x ∈ R : a ≤ x ≤ b} A∩U =A (a, b) = {x ∈ R : a < x < b} [a, b) = {x ∈ R : a ≤ x < b} prawa dominacji: (a, b] = {x ∈ R : a < x ≤ b} A∪U =U A∩∅=∅ Definicja Alfabet jest to skończony niepusty zbiór Σ, którego prawo podwójnego dopelnienia: elementami sa, symbole, nazywane literami alfabetu A = A Σ.  prawa odwrotności: Definicja A∪A=U Slowem danego alfabetu Σ nazywamy dowolny A ∩ A = ∅ skończony ciag , liter zbioru Σ.  prawa De Morgana: Zbiór Σ∗ A∪B =A∩B Zbiór wszystkich slów zbudowanych z liter alfabetu Σ A ∩ B = A ∪ B oznaczany jest przez Σ∗. prawa pochlaniania: Definicja A ∪ (A ∩ B) = A Dowolny podzbiór zbioru Σ∗ nazywany jest jezykiem , A ∩ (A ∪ B) = A nad alfabetem Σ.  U =∅ Przyklad ∅=U Σ = {A, C, G, T } Slowa alfabetu Σ to dowolne ciagi, liter A, C, G, T. Diagramy Venna sluża, do graficznego ilustrowania Σ∗ zawiera wszystkie ciagi , zbudowane z liter A, C, G, T zwiazków pomiedzy zbiorami. , , oraz slowo puste λ. Zbiór L = {A, AT, AT T T, AT T T T T, CGC} jest jed- nym z nieskończenie wielu jezyków , nad alfabetem Σ.  Prawa algebry zbiorów Niech A, B i C bed , a, podzbiorami pewnej ustalonej przestrzeni U. przemienność dodawania: A∪B =B∪A przemienność mnożenia: A∩B =B∩A Rysunek 1: Diagramy Venna dla dwóch zbiorów laczność , dodawania: (A ∪ B) ∪ C = A ∪ (B ∪ C) Literatura R.P. Grimaldi. Discrete and Combinatorial Ma- laczność , mnożenia: thematics. An Applied Introduction. Addison Wesley (A ∩ B) ∩ C = A ∩ (B ∩ C) Publishing Company, New York 1994. K.A. Ross, Ch.R.B. Wright. Matematyka dyskretna. rozdzielność mnożenia wzgledem , dodawania: PWN, Warszawa 1996. (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) W. Żakowski, G. Decewicz. Matematyka t. I. WNT, Warszawa 1992. 5