Elementy logiki - rachunek zda«
Dowody i algorytmy zawieraj¡ stwierdzenia takie jak:
• je»eli q to p
• je»eli p1 i p2 to q1 lub q2
• dla ka»dego x, y, p(x, y) > 5
• itd.
Dlatego konieczne jest poznanie metod, które umo»liwi¡
wyznaczenie kiedy stwierdzenia tego typu s¡ prawdziwe (T) lub faªszywe (F).
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 1
Def.: Zdaniem logicznym nazywamy dowolne stwierdzenie, które jest prawdziwe lub faªszywe, ale nie jest jednocze±nie prawdziwe i faªszywe.
Nast¦puj¡ce stwierdzenia s¡ zdaniami logicznymi:
• Japonia le»y w Europie.
• 1+1 = 2
• 1+1 = 3
• n ≥ 0, ∀n ∈ N
natomiast poni»sze nie s¡:
• Id¹cie do domu.
• Jaki jest kolor tego samochodu?
• x + y = y − x
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 2
Def.: Zdanie logiczne, które jest poª¡czeniem wielu zda«
logicznych za pomoc¡ odpowiednich spójników (operacji logicznych) nazywamy zdaniem zªo»onym.
Np.: Je»eli Polska le»y w Azji, to Francja le»y w Ameryce Póªnocnej i Chiny le»¡ w Europie
Def.: Zdanie logiczne, które nie jest zdaniem zªo»onym, jest zdaniem prostym.
Np.: Polska le»y w Azji
Uwaga: Podstawow¡ wªasno±ci¡ zdania zªo»onego jest to,
»e jego warto±¢ (czy zdanie jest prawdziwe, czy faªszywe) zale»y wyª¡cznie od warto±ci zda« prostych z których si¦
skªada oraz od sposobu w jaki te zdania proste s¡ poª¡czone.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 3
1. Iloczyn logiczny (koniunkcja). ¡czy dwa zdania logiczne za pomoc¡ spójnika 'i'.
Symbolicznie zapisujemy jako p ∧ q, gdzie p, q to dowolne zdania logiczne.
Np.: Polska le»y w Europie i Francja le»y w Azji
Tabela warto±ci dla operacji koniunkcji jest nast¦puj¡ca: p
q
p ∧ q
F F
F
F T
F
T F
F
T T
T
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 4
2. Alternatywa logiczna (dysjunkcja). ¡czy dwa zdania logiczne za pomoc¡ spójnika 'lub'.
Symbolicznie zapisujemy jako p ∨ q, gdzie p, q to dowolne zdania logiczne.
Np.: Polska le»y w Europie lub Francja le»y w Azji
Tabela warto±ci dla operacji dysjunkcji jest nast¦puj¡ca: p
q
p ∨ q
F F
F
F T
T
T F
T
T T
T
Uwaga: W j¦zyku potocznym znaczenie sªowa 'lub' mo»e by¢ inne, np. zdanie: Pójd¦ do kina lub pójd¦ do teatru
zwykle odbierane jest jako alternatywa wykluczaj¡ca.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 5
3. Negacja. Dla danego zdania logicznego p, negacj¦
zdania formuªujemy doª¡czaj¡c
Nieprawd¡ jest, »e . . . .
Symbolicznie zapisujemy jako ¬p, gdzie p to dowolne zdanie logiczne.
Np.: Nieprawd¡ jest, »e Polska le»y w Europie
Tabela warto±ci dla operacji negacji jest nast¦puj¡ca: p
¬p
F
T
T
F
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 6
Rozpatrzmy zdanie logiczne P (p, q, . . .), które skªada si¦
ze zmiennych p, q, . . . (przyjmuj¡ one warto±¢ prawda (T) lub faªsz (F)) oraz operacji logicznych ∧, ∨, ¬. Warto±¢ (T
lub F) zdania P mo»emy wyznaczy¢ za pomoc¡ tzw. tabeli prawdy (matrycy logicznej, tablicy warto±ci logicznych), np.:
P (p, q) = ¬(p ∧ ¬q)
p
q
¬q
p ∧ ¬q
¬(p ∧ ¬q)
F F
T
F
T
F T
F
F
T
T F
T
T
F
T T
F
F
T
Uwaga: Operacja ¬ ma pierwsze«stwo nad operacj¡ ∧
która z kolei ma pierwsze«stwo nad operacj¡ ∨.
Alternatywn¡ metod¡ konstruowania tabeli prawdy jest: Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 7
p
q
¬
(p
∧
¬
q)
F
F
F
F
F
T
F
T
T
F
T
F
T
T
T
T
p
q
¬
(p
∧
¬
q)
F
F
F
T
F
F
T
F
F
T
T
F
T
T
F
T
T
T
F
T
p
q
¬
(p
∧
¬
q)
F
F
F
F
T
F
F
T
F
F
F
T
T
F
T
T
T
F
T
T
T
F
F
T
p
q
¬
(p
∧
¬
q)
F
F
T
F
F
T
F
F
T
T
F
F
F
T
T
F
F
T
T
T
F
T
T
T
T
F
F
T
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 8
Istniej¡ zdania logiczne, które przyjmuj¡ warto±¢ T dla dowolnych warto±ci zmiennych, np.:
P (p, q) = (p ∨ q) ∨ ¬(p ∧ q)
p
q
p ∨ q
p ∧ q
¬(p ∧ q)
(p ∨ q) ∨ ¬(p ∧ q)
F F
F
F
T
T
F T
T
F
T
T
T F
T
F
T
T
T T
T
T
F
T
Zdanie takie nazywamy tautologi¡.
Istniej¡ równie» zdania logiczne, które przyjmuj¡ warto±¢ F
dla dowolnych warto±ci zmiennych, np.:
P (p, q) = (p ∧ q) ∧ ¬(p ∨ q)
Zdanie takie nazywamy sprzeczno±ci¡.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 9
Dwa zdania P (p, q, . . .) i Q(p, q, . . .) s¡ logicznie równowa»ne je»eli maj¡ identyczne tabele prawdy.
Równowa»no±¢ zda« zapisujemy w nast¦puj¡cy sposób: P (p, q, . . .) ≡ Q(p, q, . . .) (P (p, q, . . .) ⇔ Q(p, q, . . .)) Rozwa»my nast¦puj¡cy przykªad:
P (p, q) = ¬(p ∧ q),
Q(p, q) = ¬p ∨ ¬q
p
q
p ∧ q
¬(p ∧ q)
F F
F
T
F T
F
T
T F
F
T
T T
T
F
p
q
¬p
¬q
¬p ∨ ¬q
F F
T
T
T
F T
T
F
T
T F
F
T
T
T T
F
F
F
Czyli w powy»szym przykªadzie P (p, q) ≡ Q(p, q).
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 10
Idempotentno±¢
p ∨ p ≡ p
p ∧ p ≡ p
¡czno±¢
(p ∨ q) ∨ r ≡
(p ∧ q) ∧ r ≡
p ∨ (q ∨ r)
p ∧ (q ∧ r)
Przemienno±¢
p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p
Rozdzielno±¢
p ∨ (q ∧ r) ≡
p ∧ (q ∨ r) ≡
(p ∨ q) ∧ (p ∨ r)
(p ∧ q) ∨ (p ∧ r)
Identyczno±ci
p ∨ F ≡ p
p ∧ T ≡ p
p ∨ T ≡ T
p ∧ F ≡ F
Podwójna negacja
¬¬p ≡ p
Dopeªnienie
p ∨ ¬p ≡ T
p ∧ ¬p ≡ F
¬T ≡ F
¬F ≡ T
Prawa DeMorgan'a
¬(p ∨ q) ≡
¬(p ∧ q) ≡
¬p ∧ ¬q
¬p ∨ ¬q
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 11
Implikacja i równowa»no±¢ logiczna Wiele stwierdze« w matematyce ma posta¢: Je»eli p to q.
Stwierdzenie takie nazywamy implikacj¡ i symbolicznie zapisujemy jako: p → q.
Mo»emy je odczyta¢ równie» jako: p implikuje q.
Je»eli p → q i jednocze±nie q → p to zapisujemy to jako p ↔ q.
Tabele prawdy dla operacji → oraz ↔ s¡ nast¦puj¡ce: p
q
p → q
p
q
p ↔ q
F F
T
F F
T
F T
T
F T
F
T F
F
T F
F
T T
T
T T
T
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 12
Implikacja i równowa»no±¢ logiczna Uwaga: Symbol ⇔ (czyli ≡) oraz ↔ maj¡ inne znaczenie!
Wyznaczmy tabel¦ prawdy dla nast¦puj¡cego zdania
logicznego: P (p, q) = (p → q) ↔ (¬p ∨ q)
p
q
p → q
¬p
¬p ∨ q
(p → q) ↔ (¬p ∨ q)
F F
T
T
T
T
F T
T
T
T
T
T F
F
F
F
T
T T
T
F
T
T
Czyli zdanie logiczne P (p, q) jest tautologi¡. Oznacza to, »e zdania p → q oraz ¬p ∨ q s¡ równowa»ne, czyli: (p → q) ⇔ (¬p ∨ q) (lub inaczej (p → q) ≡ (¬p ∨ q)) Oczywi±cie inne zdanie logiczne tego typu nie musz¡ by¢
tautologiami, np.:
P (p, q) = (p → q) ↔ (p ∨ q) nie jest tautologi¡, czyli: (p → q) < (p ∨ q)
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 13
Def.: Niech dany b¦dzie zbiór A. Predykatem (funkcj¡
zdaniow¡) na zbiorze A nazywamy wyra»enie
p(x)
które ma tak¡ wªasno±¢, »e p(a) jest prawd¡ lub faªszem dla ka»dego a ∈ A.
Oznacza to, »e p(x) staje si¦ zdaniem logicznym (które mo»e by¢ T lub F) za ka»dym razem, gdy za x podstawimy dowoln¡ warto±¢ a ∈ A.
Zbiór A nazywamy dziedzin¡ funkcji zdaniowej p(x).
Zbiór wszystkich elementów a ∈ A dla których p(a) jest prawd¡ nazywamy zbiorem prawdy dla p(x) i zapisujemy jako:
Tp = {x|x ∈ A, p(x) jest prawd¡} lub
Tp = {x ∈ A : p(x) = T } lub
Tp = {x|p(x)}
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 14
Rozwa»my przykªad.
Znale¹¢ zbiory prawdy dla predykatu p(x) okre±lonego na zbiorze liczb naturalnych w nast¦puj¡cy sposób:
1. p(x) = x + 3 > 9
zbiorem prawdy jest zbiór {7, 8, 9, 10, 11, . . .}, czyli liczby naturalne wi¦ksze od 6.
2. p(x) = x + 7 < 2
zbiorem prawdy jest pusty zbiór ∅; nie istnieje liczba naturalna dla której ten predykat przyjmuje warto±¢ T.
3. p(x) = x + 3 > 1
zbiorem prawdy jest zbiór liczb naturalnych; dla ka»dej liczby naturalnej ten predykat przyjmuje warto±¢ T.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 15
Nich p(x) b¦dzie funkcj¡ zdaniow¡ okre±lon¡ na zbiorze A.
Rozwa»my nast¦puj¡ce wyra»enie:
(∀x ∈ A)p(x) lub
∀x p(x)
które odczytujemy dla ka»dego x nale»¡cego do A, p(x) jest zdaniem prawdziwym, lub dla ka»dego x, p(x).
Symbol ∀ (dla ka»dego) jest nazywany kwantykatorem uniwersalnym.
Stwierdzenie ∀x p(x) jest równowa»ne stwierdzeniu Tp = {x|x ∈ A, p(x) jest prawd¡} = A
Oczywi±cie nie mo»na stwierdzi¢, czy predykat p(x) jest prawd¡ czy faªszem. Jednak»e wyra»enie ∀x p(x) jest zdaniem logicznym, czyli mo»emy mu przypisa¢ warto±¢ T
lub F.
Je»eli Tp = {x|x ∈ A, p(x)} = A to ∀x p(x) jest prawd¡, w przeciwnym przypadku ∀x p(x) jest faªszem.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 16
Rozwa»my przykªad.
Stwierdzi¢, czy poni»sze zdania logiczne s¡ prawdziwe czy faªszywe.
1. (∀n ∈ N)(n + 7 > 2)
jest zdaniem prawdziwym, gdy»
Tp = {n|n + 7 > 2} = N
2. (∀n ∈ N)(n + 2 > 7)
jest zdaniem faªszywym, gdy»
Tp = {n|n + 2 > 7} = {6, 7, 8, . . .} 6= N
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 17
Nich p(x) b¦dzie funkcj¡ zdaniow¡ okre±lon¡ na zbiorze A.
Rozwa»my nast¦puj¡ce wyra»enie:
(∃x ∈ A)p(x) lub
∃x p(x)
które odczytujemy istnieje x nale»¡ce do A, takie »e p(x) jest zdaniem prawdziwym, lub dla pewnego x, p(x).
Symbol ∃ (istnieje) jest nazywany kwantykatorem szczegóªowym.
Stwierdzenie ∃x p(x) jest równowa»ne stwierdzeniu Tp = {x|x ∈ A, p(x) jest prawd¡} 6= ∅
Wyra»enie ∃x p(x) jest zdaniem logicznym, czyli mo»emy mu przypisa¢ warto±¢ T lub F.
Je»eli Tp = {x|x ∈ A, p(x)} 6= ∅ to ∃x p(x) jest prawd¡, w przeciwnym przypadku ∃x p(x) jest faªszem.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 18
Rozwa»my przykªad.
Stwierdzi¢, czy poni»sze zdania logiczne s¡ prawdziwe czy faªszywe.
1. (∃n ∈ N)(n + 3 < 6)
jest zdaniem prawdziwym, gdy»
Tp = {n|n + 3 < 6} = {0, 1, 2} 6= ∅
2. (∃n ∈ N)(n + 8 < 7)
jest zdaniem faªszywym, gdy»
Tp = {n|n + 8 < 7} = ∅
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 19
kwantykatorami
Rozwa»my zdanie:
Nie jest prawd¡, »e wszyscy studenci wydziaªu ETI to m¦»czy¹ni
Zdanie to równowa»ne jest nast¦puj¡cemu:
Przynajmniej jedna kobieta studiuje na wydziale ETI
Niech S b¦dzie zbiorem wszystkich studentów wydziaªu ETI, natomiast predykat p(x) = x jest m¦»czyzn¡.
U»ywaj¡c powy»szych symboli równowa»no±¢ przykªadowych zda« mo»emy zapisa¢ nast¦puj¡co:
¬(∀x ∈ S)p(x) ≡ (∃x ∈ S)¬p(x)
Powy»sze stwierdzenie jest prawdziwe dla dowolnego p(x).
Analogicznie:
¬(∃x ∈ S)p(x) ≡ (∀x ∈ S)¬p(x)
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 20
kwantykatorami
Rozpatrzmy przykªad.
Podane ni»ej zdania zapisa¢ symbolicznie. Sformuªowa¢
negacj¦ podanych zda«.
1. Dla wszystkich liczb naturalnych n, n + 4 > 9
∀(n ∈ N)(n + 4 > 9)
negacja:
¬∀(n ∈ N)(n + 4 > 9) ≡ ∃(n ∈ N)(n + 4 ≤ 9)
2. Istnieje liczba naturalna n, n < 10
∃(n ∈ N)(n < 10)
negacja:
¬∃(n ∈ N)(n < 10) ≡ ∀(n ∈ N)(n ≥ 10)
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 21
Aby pokaza¢, »e zdanie
∀(x ∈ A)p(x)
jest faªszywe. Wystarczy pokaza¢, »e zdanie
¬∀(x ∈ A)p(x) ≡ ∃(x ∈ A)¬p(x)
jest prawdziwe.
Element x0 ∈ A dla którego p(x0) jest faªszem nazywamy kontrprzykªadem.
Rozpatrzmy przykªadowe zdanie logiczne:
∀x ∈ R, x2 ≥ x
Aby pokaza¢, »e to zdanie jest faªszywe, mo»emy pokaza¢,
»e zdanie
∃x ∈ R, x2 < x
jest prawdziwe.
Np.: x = 1 jest kontrprzykªadem ( 12 < (1) jest prawd¡) 2
2
2
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 22
Funkcje logiczne wielu zmiennych
Funkcj¡ logiczn¡ n zmiennych, zdeniowan¡ na iloczynie kartezja«skim zbiorów A = A1×A2×. . .×An nazywamy wyra»enie
p(x1, x2, . . . , xn)
które jest zdaniem prawdziwym lub faªszywym dla dowolnej n-krotki (a1, a2, . . . , an).
Np.: x + 2y + 3z < 24 jest funkcj¡ logiczn¡ trzech zmiennych, zdeniowan¡ na 3
N = N × N × N.
Rozpatrzmy nast¦puj¡cy przykªad:
Niech B = {1, 2, 3, . . . , 9} oraz p(x, y) oznacza predykat
x + y = 10 (zdeniowany na zbiorze A = B × B).
∀x∃y, p(x, y)
jest zdaniem logicznym, które jest prawdziwe.
∃y∀x, p(x, y)
jest zdaniem logicznym, które jest faªszywe.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 23
Negacja funkcji logicznych wielu
zmiennych z kwantykatorami
Aby zanegowa¢ stwierdzenie:
¬ [∀x∃y∃z, p(x, y, z)]
wykonujemy negacje krok po kroku zgodnie z poznanymi wcze±niej reguªami, czyli:
¬ [∀x∃y∃z, p(x, y, z)] ≡
∃x¬ [∃y∃z, p(x, y, z)] ≡
∃x∀y¬ [∃z, p(x, y, z)] ≡
∃x∀y∀z, ¬p(x, y, z)
Np.: Ka»dy student przynajmniej z jednego przedmiotu otrzymaª ocen¦ 5
Negacj¡ tego zdania jest:
Istnieje student, który ze wszystkich przedmiotów otrzymaª
ocen¦ ró»n¡ od 5
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 24