Elementy Logiki i Teorii Mnogości PDF
Document Details
Uploaded by EliteWisdom9597
Politechnika Poznańska
Piotr Formanowicz
Tags
Summary
This document provides an introduction to discrete mathematics, focusing on logic and set theory. It outlines basic concepts like propositional logic and its truth tables. It also discusses set theory, including operations, relationships between sets and diagrams.
Full Transcript
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