Rachunek zdań i dowody: zadania z rozwiązaniami krok po kroku
Darmowe zadania z tematu Rachunek zdań i dowody z rysunkami, podpowiedziami i pełnymi rozwiązaniami. Za każdym razem nowe wartości, na trzech poziomach: tablice prawdy, równoważności i metody dowodzenia, kwantyfikatory i wnioskowania.
Darmowe zadanieŁatwy
Uzupełnij tablicę prawdy (1 = prawda, 0 = fałsz). W ilu wierszach N formuła (p → r) ↔ (r ∨ q) jest prawdziwa?
(p → r) ↔ (r ∨ q)
Dokładna odpowiedź: liczba całkowita, bez zaokrąglania.
Zdanie logiczne to wypowiedź, która jest prawdziwa albo fałszywa, na przykład „7 jest liczbą pierwszą”. Zapisujemy je literą, p lub q, a jego wartość logiczną jako 1 (prawda) lub 0 (fałsz).
Spójniki budują większe formuły z mniejszych:
¬p (nie p) odwraca wartość.
p ∧ q (i) jest równe 1 tylko wtedy, gdy oba są równe 1.
p ∨ q (lub) jest równe 0 tylko wtedy, gdy oba są równe 0. To alternatywa nierozłączna: oba mogą być prawdziwe.
p → q (jeśli p, to q) jest równe 0 tylko wtedy, gdy p = 1 i q = 0.
p ↔ q (wtedy i tylko wtedy) jest równe 1, gdy p i q mają tę samą wartość.
Implikacja zaskakuje wielu studentów: gdy p jest fałszywe, p → q jest prawdziwe niezależnie od q. Obietnica „jeśli będzie padać, wezmę parasol” jest złamana tylko w deszczowy dzień bez parasola.
Samosprawdzenie p = 0 i q = 1. Jaka jest wartość p → q?
0
1
Nieokreślona
Zależy od kontekstu
Odpowiedź: 1. Implikacja jest fałszywa tylko wtedy, gdy warunek zachodzi, a wniosek nie (p = 1, q = 0). Dla p = 0 jest prawdziwa niezależnie od q.
2Tablice prawdy
Tablica prawdy wypisuje każdą kombinację wartości logicznych zmiennych. Przy n różnych zmiennych jest 2ⁿ wierszy: 4 dla dwóch zmiennych, 8 dla trzech, 16 dla czterech. Zmienna, która występuje dwa razy, liczy się raz.
Pracuj od wewnątrz na zewnątrz. Każdej podformule daj osobną kolumnę, by do każdej nowej kolumny wystarczył jeden spójnik zastosowany do już gotowych kolumn.
Wypisz zmienne i zapisz wszystkie 2ⁿ kombinacji, zaczynając od samych jedynek.
Dodaj kolumnę dla każdej podformuły, zaczynając od najbardziej wewnętrznej.
Wypełnij każdą kolumnę regułą jej głównego spójnika.
Odczytaj odpowiedź z ostatniej kolumny: policz jedynki lub znajdź żądany wiersz.
Samosprawdzenie Ile wierszy ma tablica prawdy formuły (p ∧ q) → (r ∨ p)?
16
4
6
8
Odpowiedź: 8. Formuła ma trzy różne zmienne, p, q i r, więc 2³ = 8 wierszy. Zmienna p występuje dwa razy, ale to jedna zmienna; 16 to 2⁴ dla czterech wystąpień.
3Przykład krok po kroku
Przejdź przez każdy krok. Spróbuj przewidzieć następny, zanim go odsłonisz.
Przykład krok po kroku
W ilu wierszach jej tablicy prawdy formuła (p → q) ∧ ¬q jest prawdziwa?
1
Zmienne i wiersze
Dwie zmienne, p i q, więc 4 wiersze: (1, 1), (1, 0), (0, 1), (0, 0).
2
Kolumna p → q
Jest równa 0 tylko w wierszu p = 1, q = 0:
p → q: 1, 0, 1, 1
3
Kolumna ¬q
¬q: 0, 1, 0, 1
4
Koniunkcja
Obie kolumny muszą być równe 1. Dzieje się tak tylko w ostatnim wierszu, p = 0 i q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Odpowiedź
Formuła jest prawdziwa w 1 wierszu, tym z p = 0, q = 0. Dlatego p → q razem z ¬q dają ¬p (modus tollens).
4Równoważności i metody dowodzenia
Dwie formuły są równoważne (≡), gdy ich kolumny w tablicy prawdy są identyczne. Tautologia jest równa 1 w każdym wierszu, kontradykcja 0 w każdym wierszu, a formuła kontyngentna nie jest ani jednym, ani drugim.
Prawa, których używasz najczęściej:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Te prawa są podstawą metod dowodzenia. Dowód p → q przez kontrapozycję dowodzi zamiast tego ¬q → ¬p, co jest równoważne. Dowód nie wprost zakłada p ∧ ¬q, jedyny sposób, w jaki implikacja może zawieść, i wyprowadza coś niemożliwego.
Uwaga: implikacja odwrotna q → p oraz przeciwna ¬p → ¬q nie są równoważne p → q.
Samosprawdzenie Która formuła jest równoważna ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Odpowiedź: ¬p ∨ ¬q. Według praw de Morgana ∧ zamienia się w ∨, a obie części są zanegowane. ¬p ∧ ¬q to zaprzeczenie p ∨ q, czyli inne zdanie: jest fałszywe, gdy dokładnie jedno z p i q jest prawdziwe, a ¬(p ∧ q) wtedy jest prawdziwe.
5Kwantyfikatory i poprawne wnioskowania
Przy zmiennych przebiegających dziedzinę ∀x P(x) mówi „P zachodzi dla każdego x”, a ∃x P(x) mówi „P zachodzi dla co najmniej jednego x”. Negacja zamienia kwantyfikator:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Przesuwaj negację do środka krok po kroku; wewnątrz używaj praw rachunku zdań. Na przykład ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): „nie każde P jest Q” oznacza „pewne P nie jest Q”.
Wnioskowanie jest poprawne, gdy wniosek jest równy 1 w każdym wierszu, w którym wszystkie przesłanki są równe 1. Klasyczne poprawne schematy to modus ponens (p → q, p, więc q), modus tollens (p → q, ¬q, więc ¬p) i sylogizm hipotetyczny (p → q, q → r, więc p → r).
Wiersz, w którym wszystkie przesłanki są równe 1, a wniosek 0, to kontrprzykład. Stwierdzenie następnika (p → q, q, więc p) jest niepoprawne: wiersz p = 0, q = 1 jest kontrprzykładem.
Samosprawdzenie Jaka jest negacja zdania „każdy student zdał”, ∀x P(x)?
¬P(x) dla jednego ustalonego studenta x
∀x ¬P(x): żaden student nie zdał
∃x P(x): jakiś student zdał
∃x ¬P(x): jakiś student nie zdał
Odpowiedź: ∃x ¬P(x): jakiś student nie zdał. Jeden student, który nie zdał, wystarczy, by „każdy student zdał” było fałszywe. „Żaden student nie zdał” jest znacznie mocniejsze niż negacja.
6Typowe błędy
Uznawanie p → q za fałszywe, gdy p jest fałszywe. Jest fałszywe tylko wtedy, gdy p = 1 i q = 0.
Liczenie powtarzającej się zmiennej dwa razy przy wyznaczaniu liczby wierszy.
Mylenie kontrapozycji ¬q → ¬p z implikacją odwrotną q → p lub przeciwną ¬p → ¬q.
Zapisanie zaprzeczenia ∀x P(x) jako ∀x ¬P(x): kwantyfikator musi zmienić się na ∃.
Zapisanie ¬(p ∧ q) jako ¬p ∧ ¬q: prawa de Morgana zamieniają też spójnik.
Samosprawdzenie Które zdanie jest kontrapozycją zdania „jeśli n² jest parzyste, to n jest parzyste”?
Jeśli n jest nieparzyste, to n² jest nieparzyste
Jeśli n jest parzyste, to n² jest parzyste
Jeśli n² jest nieparzyste, to n jest nieparzyste
n² jest parzyste i n jest nieparzyste
Odpowiedź: Jeśli n jest nieparzyste, to n² jest nieparzyste. Zamień obie części i zaneguj obie: nie (n parzyste) → nie (n² parzyste). „Jeśli n jest parzyste, to n² jest parzyste” to implikacja odwrotna; ostatnia opcja to założenie dowodu nie wprost.
7Jak wyglądają zadania egzaminacyjne
Łatwe: tablice prawdy. Znajdujesz liczbę wierszy, liczysz wiersze, w których formuła jest prawdziwa, albo klikasz jedyny wiersz, który czyni formułę prawdziwą lub fałszywą.
Średnie: równoważności i metody dowodzenia. Rozstrzygasz, czy formuła jest tautologią, kontradykcją czy kontyngencją, wybierasz formułę równoważną albo zdanie do udowodnienia w dowodzie przez kontrapozycję lub nie wprost.
Trudne: kwantyfikatory i wnioskowania. Negujesz zdania z kwantyfikatorami, wybierasz wniosek wynikający z przesłanek, klikasz wiersz kontrprzykładu niepoprawnego wnioskowania albo liczysz wiersze prawdziwe w tablicy czterech zmiennych.
Dokładnie jeden wiersz tablicy prawdy czyni ¬(p ∨ q) → q fałszywym. Kliknij ten wiersz.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Pokaż podpowiedzi
a → b jest równe 0 tylko wtedy, gdy a = 1 i b = 0. ¬a odwraca wartość. a ∨ b jest równe 0 tylko wtedy, gdy oba są równe 0.
Najpierw ustal główny spójnik: jakie muszą być jego dwie strony, aby cała formuła była 0?
Każdej części daj osobną kolumnę: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Pokaż odpowiedź i wyjaśnienie
Tablice prawdy: formuła z n różnymi zmiennymi ma 2ⁿ wierszy, po jednym dla każdej kombinacji wartości logicznych (1 = prawda, 0 = fałsz). Pracuj od wewnątrz na zewnątrz i każdej podformule daj osobną kolumnę. ¬a odwraca wartość; a ∧ b jest równe 1 tylko wtedy, gdy oba są równe 1; a ∨ b jest równe 0 tylko wtedy, gdy oba są równe 0; a → b jest równe 0 tylko wtedy, gdy a = 1 i b = 0; a ↔ b jest równe 1, gdy obie strony są równe.
Która formuła jest logicznie równoważna (b ∧ c) → a? Kliknij ją.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Pokaż podpowiedzi
Formuły równoważne zgadzają się w każdym wierszu tablicy prawdy. Jeden wiersz, w którym się różnią, wyklucza opcję.
Spróbuj wiersza, w którym (b ∧ c) → a jest równe 0, i sprawdź, które opcje też są tam równe 0.
Prawo eksportacji: (a ∧ b) → c ≡ a → (b → c). Oba są równe 0 tylko wtedy, gdy a = 1, b = 1 i c = 0.
Pokaż odpowiedź i wyjaśnienie
Równoważność logiczna: dwie formuły są równoważne (≡), gdy mają tę samą wartość w każdym wierszu tablicy prawdy. Tautologia jest równa 1 w każdym wierszu, kontradykcja 0 w każdym wierszu, a formuła kontyngentna nie jest ani jednym, ani drugim. Przydatne prawa: prawa de Morgana, ¬(a ∧ b) ≡ ¬a ∨ ¬b oraz ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (kontrapozycja); ¬(a → b) ≡ a ∧ ¬b; oraz prawa rozdzielności, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Prawo
Prawo eksportacji: (a ∧ b) → c ≡ a → (b → c). Oba są równe 0 tylko wtedy, gdy a = 1, b = 1 i c = 0.
(b ∧ c) → a ≡ b → (c → a)
Sprawdź tablicą prawdy
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Odpowiedź
b → (c → a)
Kolumny po kresce to opcje w pokazanej kolejności.
Przykład 3Trudny
Dane są przesłanki (q ∧ p) → r; q; ¬r. Jaki wniosek z nich wynika? Kliknij go.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Pokaż podpowiedzi
Wniosek wynika, gdy jest równy 1 w każdym wierszu, w którym wszystkie przesłanki są równe 1.
Znajdź wiersze, w których wszystkie przesłanki są równe 1, a potem sprawdź każdą opcję w tych wierszach.
To standardowa reguła: modus tollens z koniunkcją.
Pokaż odpowiedź i wyjaśnienie
Kwantyfikatory i wnioskowania: ¬∀x P(x) ≡ ∃x ¬P(x) oraz ¬∃x P(x) ≡ ∀x ¬P(x). Przesuń negację do środka, zamień każdy kwantyfikator, który mija, i zaneguj formułę wewnętrzną prawami rachunku zdań, takimi jak ¬(a → b) ≡ a ∧ ¬b. Wnioskowanie jest poprawne, gdy wniosek jest równy 1 w każdym wierszu, w którym wszystkie przesłanki są równe 1. Pojedynczy wiersz z prawdziwymi przesłankami i fałszywym wnioskiem jest kontrprzykładem i pokazuje, że wnioskowanie jest niepoprawne.
Wiersze z wszystkimi prawdziwymi przesłankami
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Wniosek
¬p (modus tollens z koniunkcją)
Odpowiedź
¬p
Pytania i odpowiedzi
Rachunek zdań i dowody: co to jest?
Spójniki budują większe formuły z mniejszych:
Implikacja zaskakuje wielu studentów: gdy p jest fałszywe, p → q jest prawdziwe niezależnie od q. Obietnica „jeśli będzie padać, wezmę parasol” jest złamana tylko w deszczowy dzień bez parasola.
Rachunek zdań i dowody: jak rozwiązywać zadania krok po kroku?
Policz różne zmienne: tablica prawdy ma 2ⁿ wierszy, a zaczyna się od samych jedynek.
Każdej podformule daj osobną kolumnę i wypełniaj kolumny od wewnątrz na zewnątrz.
Stosuj regułę każdego spójnika: → jest 0 tylko dla 1 → 0, ↔ jest 1, gdy obie strony się zgadzają.
Przy równoważnościach porównaj końcowe kolumny wiersz po wierszu; przy wnioskowaniu patrz tylko na wiersze, w których każda przesłanka jest równa 1.
Aby zaprzeczyć zdaniu z kwantyfikatorem, przesuń ¬ do środka, zamień ∀ i ∃ oraz zaprzecz formule wewnętrznej.
Rachunek zdań i dowody: jakie błędy są najczęstsze?
Uznawanie p → q za fałszywe, gdy p jest fałszywe.
Liczenie powtarzającej się zmiennej dwa razy przy wyznaczaniu liczby wierszy.
Mylenie kontrapozycji ¬q → ¬p z implikacją odwrotną q → p.
Zapisanie zaprzeczenia ∀x P(x) jako ∀x ¬P(x) zamiast ∃x ¬P(x).
Stosowanie praw de Morgana bez zamiany ∧ i ∨.
Rachunek zdań i dowody: co ćwiczysz?
Łatwy: tablice prawdy
Średni: równoważności i metody dowodzenia
Trudny: kwantyfikatory i wnioskowania
Każde zadanie ma nowe wartości, więc uczysz się metody, a nie odpowiedzi. Utknąłeś? Najpierw otwórz małą podpowiedź, a pełne wyjaśnienie dopiero wtedy, gdy go potrzebujesz.
Jak wygląda ćwiczenie
Każde zadanie ma nowe wartości, więc uczysz się metody, a nie odpowiedzi.
Utknąłeś? Najpierw otwórz małą podpowiedź, a pełne wyjaśnienie dopiero wtedy, gdy go potrzebujesz.
Twoje postępy, błędy i zapisane zadania są zachowywane, więc możesz je powtórzyć przed egzaminem.