Logika — zdania, spójniki i kwantyfikatory · Matematyka

Po co ekonomiście logika?

Na pierwszych ćwiczeniach z matematyki tablica szybko zapełnia się dziwnymi znaczkami: $\land$ , $\lor$ , $\Rightarrow$ , $\forall$ , $\exists$ . Prowadzący czyta je płynnie, a my jeszcze zastanawiamy się, który daszek znaczy „i”, a który „lub”. Po dziesięciu minutach łatwo się zgubić — i do końca zajęć już się nie odnaleźć.

Ten moduł robi coś prostego: przedstawia te znaczki po kolei, jeden po drugim. Każdy dostaje nazwę, sposób czytania na głos, przykład z życia i pułapkę, w którą najczęściej się wpada.

Dlaczego warto? Bo logika to nie osobny dział, który zaliczysz i zapomnisz. To język, w którym zapisane są wszystkie kolejne tematy. Zbiór liczb od 1 do 4 zapiszemy jako $\{x \in \mathbb{N} : x \geq 1 \land x \leq 4\}$ — i bez znajomości $\land$ nie przeczytasz nawet definicji.

Co będzie na kolokwium

Z logiki na kolokwium wraca kilka typów poleceń. Każde ma w tym module swój przepis, rozwiązane przykłady i ćwiczenia z natychmiastową odpowiedzią. Jeśli powtarzasz na ostatnią chwilę, zacznij od tej listy.

1
„Oblicz wartość logiczną zdania dla $p = 1$ , $q = 0$ , $r = 0$ ”
Wstawiasz 0 i 1 w miejsce literek i liczysz spójnik po spójniku, od środka nawiasów.
Przepis i przykłady ↓Ćwiczenia ↓
2
„Odczytaj zdanie / zapisz je za pomocą symboli”
Ustalasz kolejność działań, znajdujesz spójnik główny i czytasz od niego.
Przepis i przykłady ↓Ćwiczenia ↓
3
„Sprawdź, czy zdanie jest tautologią”
Budujesz tabelę zero-jedynkową. Same jedynki w ostatniej kolumnie — tautologia.
Przepis i przykłady ↓Ćwiczenia ↓jak w Zad. 1, str. 14–15
4
„Dla jakich wartości $p$ , $q$ , $r$ zdania … są jednocześnie prawdziwe?”
Ta sama tabela, ale szukasz wierszy, w których wszystkie podane zdania mają 1.
Przepis i przykłady ↓Ćwiczenia ↓jak w Zad. 2, str. 15
5
„Zapisz słownie zdanie z kwantyfikatorami i określ jego wartość logiczną”
Czytasz od lewej. Przy $\forall$ szukasz kontrprzykładu, przy $\exists$ — przykładu.
Przepis i przykłady ↓Ćwiczenia ↓jak w Zad. 1, str. 19–20
6
„Zapisz negację (zaprzeczenie) zdania”
$\forall$ zamieniasz na $\exists$ i odwrotnie, a na końcu zaprzeczasz warunek.
Przepis i przykłady ↓Ćwiczenia ↓jak w Zad. 3, str. 20

Słowa w poleceniu mogą być inne („zbadaj”, „ustal”, „wyznacz”). Liczy się to, o co pyta zadanie: o wartość, o tautologię, o wiersze, o zapis słowny czy o zaprzeczenie.

Zdanie logiczne — co nim jest, a co nie

Wszystko zaczyna się od zdania logicznego.

Najczęściej są to zwykłe zdania oznajmujące, na przykład „W Poznaniu jeżdżą tramwaje”. Da się to sprawdzić — i to jest prawda.

Uwaga, bo tu robi się pierwszy błąd: zdanie fałszywe też jest zdaniem logicznym. „2 + 2 = 5” jest fałszem, ale wiemy to na pewno — więc to pełnoprawne zdanie logiczne. Liczy się to, że da się ustalić wartość, a nie to, że wychodzi prawda.

Zdaniami logicznymi nie są:

rozkazy („Zamknij okno!”) — rozkaz można wykonać albo nie, ale nie jest ani prawdziwy, ani fałszywy;
pytania („Która godzina?”) — pytanie niczego nie stwierdza;
prognozy („Jutro będzie padać”) — dziś nie da się tego sprawdzić;
opinie („Matematyka jest nudna”) — zależą od gustu, nie od faktów.

Ćwiczenie

Czy to jest zdanie logiczne? Kliknij odpowiedź przy każdym

„W Poznaniu jeżdżą tramwaje.”
„2 + 2 = 5”
„Zamknij drzwi!”
„Która jest godzina?”
„Jutro w Poznaniu będzie padać.”
„Warszawa jest stolicą Niemiec.”
„ $x + 3 = 7$ ”
„Pizza hawajska jest najlepsza.”

Prawda to 1, fałsz to 0

Pisanie „prawda” i „fałsz” szybko by się znudziło, więc matematycy używają cyfr:

zdanie prawdziwe ma wartość logiczną 1,
zdanie fałszywe ma wartość logiczną 0.

Zdania proste i złożone

Zdanie proste to takie, którego nie da się rozłożyć na mniejsze zdania: „Pada deszcz”.
Zdanie złożone powstaje ze sklejenia zdań prostych: „Pada deszcz i wieje wiatr”.

Zdania proste oznaczamy małymi literami: $p$ , $q$ , $r$ … Litera to tylko skrót, jak ksywka. Zamiast pisać za każdym razem „pada deszcz”, piszemy $p$ .

Spójniki, czyli klej do zdań

Zdania proste sklejamy w złożone za pomocą spójników. Na zajęciach jest ich pięć. Oto cała piątka w jednym miejscu — dalej omówimy każdy osobno.

\neg

Negacja

czytamy: „nieprawda, że…”

Odwraca wartość zdania: z prawdy robi fałsz, z fałszu prawdę.

Jak zapamiętać: kreska z haczykiem, która „przekreśla” zdanie.

\land

Koniunkcja

czytamy: „i”

Prawdziwa tylko wtedy, gdy oba zdania są prawdziwe.

Jak zapamiętać: daszek ∧ jak litera A z angielskiego And.

\lor

Alternatywa

czytamy: „lub”

Prawdziwa, gdy co najmniej jedno zdanie jest prawdziwe.

Jak zapamiętać: ∨ jak „v” z łacińskiego vel (lub). To odwrócony daszek koniunkcji.

\Rightarrow

Implikacja

czytamy: „jeżeli …, to …”

Fałszywa tylko w jednym przypadku: z prawdy wychodzi fałsz.

Jak zapamiętać: strzałka pokazuje kierunek: od warunku do skutku.

\Leftrightarrow

Równoważność

czytamy: „… wtedy i tylko wtedy, gdy …”

Prawdziwa, gdy oba zdania mają tę samą wartość.

Jak zapamiętać: strzałka w obie strony = implikacja w obie strony.

Negacja, koniunkcja, alternatywa

Negacja ¬ — „nieprawda, że”

Negacja to najprostszy spójnik. Bierze jedno zdanie i odwraca jego wartość.

$p$ : „Pada deszcz” — powiedzmy, że to prawda (1).
$\neg p$ : „Nieprawda, że pada deszcz” — fałsz (0).

$p$	$\neg p$
0	1
1	0

Jak czytać tę tabelę:

w lewej kolumnie są wszystkie możliwe wartości $p$ (tylko dwie: 0 i 1). W prawej — wartość $\neg p$ . W każdym wierszu prawa kolumna jest odwrotnością lewej.

Koniunkcja ∧ — „i”

Koniunkcja $p \land q$ jest prawdziwa tylko wtedy, gdy oba zdania są prawdziwe naraz. Wystarczy, że jedno zawiedzie, i cała koniunkcja jest fałszywa.

Przykład z życia: „Do egzaminu jesteś dopuszczony, jeśli masz zaliczone ćwiczenia i oddany projekt”. Samo zaliczenie nie wystarczy. Sam projekt też nie. Potrzebne są oba warunki.

$p$	$q$	$p \land q$
0	0	0
0	1	0
1	0	0
1	1	1

Jak czytać tę tabelę:

dwa zdania mają razem 4 możliwe układy wartości. Jedynka w kolumnie $p \land q$ jest tylko w ostatnim wierszu — tam, gdzie $p = 1$ i $q = 1$ .

p \land q

= 1 — żarówka świeci

Jak czytać ten schemat:

włączniki $p$ i $q$ stoją jeden za drugim (szeregowo). Prąd musi przejść przez oba, więc żarówka świeci tylko wtedy, gdy oba są włączone. Kliknij włącznik, żeby go wyłączyć — i zobacz, że jeden wyłączony gasi wszystko. Dokładnie tak działa $\land$ .

Alternatywa ∨ — „lub”

Alternatywa $p \lor q$ jest prawdziwa, gdy co najmniej jedno ze zdań jest prawdziwe. Fałszywa jest tylko wtedy, gdy oba są fałszywe.

$p$	$q$	$p \lor q$
0	0	0
0	1	1
1	0	1
1	1	1

Jak czytać tę tabelę:

jedyne zero jest w pierwszym wierszu, gdzie oba zdania są fałszywe. Zwróć uwagę na ostatni wiersz: gdy prawdziwe są oba zdania, alternatywa też jest prawdziwa.

p \lor q

= 1 — żarówka świeci

Jak czytać ten schemat:

tu włączniki są w dwóch osobnych gałęziach (równolegle). Prąd może popłynąć górą albo dołem, więc wystarczy, że włączony jest jeden z nich. Żarówka gaśnie dopiero wtedy, gdy wyłączysz oba. Tak działa $\lor$ .

Sprawdź się

Wiemy, że $p$ jest fałszywe (0), a $q$ prawdziwe (1). Ile wynosi $p \land q$ , a ile $p \lor q$ ?

Implikacja — „jeżeli…, to…”

Implikacja $p \Rightarrow q$ to zdanie typu „jeżeli $p$ , to $q$ ”. Jej części mają swoje nazwy:

p \Rightarrow q

Czytamy: jeżeli $p$ , to $q$

$p$: poprzednik (założenie, warunek) — to, co stoi przed strzałką
$\Rightarrow$: strzałka implikacji
$q$: następnik (wniosek, skutek) — to, co stoi za strzałką

Z całej implikacji trzeba zapamiętać jedną regułę:

$p$	$q$	$p \Rightarrow q$
0	0	1
0	1	1
1	0	0
1	1	1

Jak czytać tę tabelę:

trzy wiersze dają 1. Zero jest tylko w trzecim wierszu: $p = 1$ , $q = 0$ — prawda na początku, fałsz na końcu.

jedyny przypadek, gdy implikacja jest fałszywa

Równoważność i tabela wszystkich spójników

Równoważność ⇔ — „wtedy i tylko wtedy”

Równoważność $p \Leftrightarrow q$ jest prawdziwa, gdy oba zdania mają tę samą wartość: oba prawdziwe albo oba fałszywe.

Stąd nazwa: równoważność to implikacja w obie strony — $p \Rightarrow q$ i jednocześnie $q \Rightarrow p$ . W skrócie piszemy „wtw” (wtedy i tylko wtedy).

Wszystkie spójniki naraz

Tę tabelę warto mieć w głowie. Dla dwóch zdań są 4 możliwe układy wartości, a każdy spójnik daje w nich swój wynik:

$p$	$q$	$\neg p$ 1	$p \land q$ 2	$p \lor q$ 3	$p \Rightarrow q$ 4	$p \Leftrightarrow q$ 5
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

Jak czytać tę tabelę:

każdy wiersz to jeden możliwy układ (np. trzeci wiersz: $p$ prawdziwe, $q$ fałszywe). Każda kolumna mówi, jaką wartość ma dany spójnik w tym układzie. Najłatwiej zapamiętać kolumny po ich „wyjątkach”: $\land$ ma jedną jedynkę (oba = 1), $\lor$ ma jedno zero (oba = 0), $\Rightarrow$ ma jedno zero (z 1 wychodzi 0), $\Leftrightarrow$ daje 1, gdy wartości są równe.

Symulator

Przełącz p i q — patrz, co się dzieje

$\neg p$ „nieprawda, że dostałeś 5”?
$p \land q$ „dostałeś 5 i stawiam pizzę”?
$p \lor q$ „dostałeś 5 lub stawiam pizzę”?
$p \Rightarrow q$ „jeśli dostaniesz 5, to stawiam pizzę”?
$p \Leftrightarrow q$ „stawiam pizzę wtedy i tylko wtedy, gdy dostaniesz 5”?

Jak czytać zdanie złożone

W arytmetyce najpierw mnożymy, potem dodajemy: $2 + 3 \cdot 4 = 14$ , a nie $20$ . Ze spójnikami jest tak samo — mają swoją kolejność:

najpierw negacja $\neg$ (wiąże najsilniej),
potem koniunkcja $\land$ i alternatywa $\lor$ ,
na końcu implikacja $\Rightarrow$ i równoważność $\Leftrightarrow$ .

Dzięki temu można pominąć część nawiasów. Te dwa zapisy znaczą dokładnie to samo:

\begin{gathered} [(\neg p) \lor q] \Leftrightarrow (p \land q) \\ \text{to samo co} \\ \neg p \lor q \Leftrightarrow p \land q \end{gathered}

Przepis: jak odczytać zdanie

Negacja dotyczy tylko tego, co stoi tuż za nią: jednej literki ( $\neg p$ ) albo całego nawiasu ( $\neg(p \lor q)$ ).
Nawiasy liczysz najpierw — to, co w nawiasie, traktuj jak jedną całość.
Koniunkcja i alternatywa łączą sąsiednie kawałki.
Implikacja albo równoważność stojąca poza nawiasami zostaje na koniec. Spójnik liczony na samym końcu to spójnik główny — to on mówi, czym jest całe zdanie.
Czytasz od spójnika głównego: przy $\Rightarrow$ — „jeżeli [lewa strona], to [prawa strona]”, przy $\Leftrightarrow$ — „[lewa strona] wtedy i tylko wtedy, gdy [prawa strona]”.

Przykłady

\neg p \lor q \Rightarrow r

Czytamy: jeżeli nieprawda, że $p$ , lub $q$ , to $r$

$\neg p$: negacja dotyczy tylko $p$ — stoi tuż przy nim
$\neg p \lor q$: potem alternatywa łączy $\neg p$ z $q$ — to cała lewa strona
$\Rightarrow$: na końcu implikacja — to spójnik główny. Prawa strona to $r$
$[(\neg p) \lor q] \Rightarrow r$: to samo zdanie ze wszystkimi nawiasami

\neg (p \land q) \Leftrightarrow \neg p \lor \neg q

Czytamy: nieprawda, że ( $p$ i $q$ ) wtedy i tylko wtedy, gdy nieprawda, że $p$ , lub nieprawda, że $q$

$\neg (p \land q)$: negacja stoi przed nawiasem, więc dotyczy całego nawiasu
$\neg p \lor \neg q$: tu każda negacja dotyczy tylko swojej literki, a potem obie łączy $\lor$
$\Leftrightarrow$: spójnik główny — łączy lewą i prawą stronę

(p \land \neg q) \Rightarrow r

Czytamy: zapis zdania „Jeżeli pada deszcz i nieprawda, że mam parasol, to zmoknę”

$p, q, r$: $p$ = „pada deszcz”, $q$ = „mam parasol”, $r$ = „zmoknę”
$\Rightarrow$: „jeżeli …, to …” — to implikacja i zarazem spójnik główny
$p \land \neg q$: warunek „pada deszcz i nieprawda, że mam parasol” — stoi przed strzałką

Sprawdź się

Który spójnik jest główny w zdaniu $p \lor \neg q \Leftrightarrow r$ ?

Obliczanie wartości zdania złożonego

Zadanie · krok po kroku

Oblicz (p ⇒ q) ∨ ¬r dla p = 1, q = 0, r = 0

Plan — co zrobimy i po co

Wstawiamy zera i jedynki w miejsce literek. Od tej chwili liczymy na samych cyfrach.
Liczymy nawias, bo nawias zawsze idzie pierwszy.
Liczymy negację $\neg r$ . Dotyczy tylko jednej literki, więc da się ją policzyć od razu.
Na końcu liczymy spójnik główny $\lor$ . Jego wynik to wartość całego zdania.

Kroki 2 i 3 możesz zamienić miejscami — nawias i negacja nie zależą od siebie. Spójnik główny zawsze zostaje na koniec.

Wstaw wartości w miejsce literek
$(1 \Rightarrow 0) \lor \neg 0$
Policz nawias
$1 \Rightarrow 0 = 0$ .
Dlaczego?
To jedyny przypadek, w którym implikacja jest fałszywa: prawda na początku, fałsz na końcu.
Policz negację
$\neg 0 = 1$ — negacja odwraca wartość.
Policz spójnik główny
Zostało $0 \lor 1 = 1$ . Zdanie jest prawdziwe.
Dlaczego?
Alternatywie wystarczy jedna jedynka. Spójnik główny to $\lor$ , bo nawias i negację policzyliśmy wcześniej.
Inny sposób
Szybciej: spójnik główny to $\lor$ , a alternatywie wystarczy jedna jedynka. Skoro $\neg 0 = 1$ , całe zdanie jest prawdziwe — nawiasu nie trzeba nawet liczyć. Ten skrót działa tylko wtedy, gdy po jednej stronie $\lor$ wyjdzie 1. Przy $\land$ działa odwrotnie: wystarczy jedno 0 po jednej stronie, żeby całość była fałszywa.

Tabela zero-jedynkowa: ile wierszy i jak ją wypełnić

Obliczanie wartości dla jednego układu zer i jedynek już znasz. Tabela zero-jedynkowa robi to samo dla wszystkich możliwych układów naraz — każdy wiersz to jeden układ.

1 literka → 2 wiersze

$p$
0
1

$p$ : 0 i 1 na zmianę

2 literki → 4 wiersze

$p$	$q$
0	0
0	1
1	0
1	1

$p$ : 2 zera, potem 2 jedynki
$q$ : 0 i 1 na zmianę

3 literki → 8 wierszy

$p$	$q$	$r$
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

$p$ : 4 zera, potem 4 jedynki
$q$ : 2 zera, 2 jedynki — i tak na zmianę
$r$ : 0 i 1 na zmianę

Jak czytać:

każda tabela zawiera wszystkie możliwe układy zer i jedynek dla swoich literek. Złota kreska dzieli tabelę na połowy: w górnej pierwsza literka ma 0, w dolnej 1. Zobacz, że w tabeli dla $p$ , $q$ , $r$ obie połowy kolumn $q$ i $r$ wyglądają dokładnie jak tabela dla dwóch literek. Dlatego każda nowa literka podwaja liczbę wierszy.

Liczbę wierszy liczysz ze wzoru:

liczba wierszy = 2^{n}

$n$: liczba różnych literek w zdaniu (np. $p, q, r$ → $n = 3$ ). Jeśli $p$ występuje w zdaniu trzy razy, liczy się raz.
$2^{n}$: każda literka ma 2 możliwe wartości, a każda nowa literka podwaja tabelę: $2 \to 4 \to 8 \to 16$

liczba literek $n$	1	2	3	4
liczba wierszy $2^n$	2	4	8	16

Tautologia: czy zdanie jest zawsze prawdziwe?

Przykład z życia: „Jutro będzie padać lub jutro nie będzie padać”. Nie wiem, jaka będzie pogoda, ale wiem, że to zdanie jest prawdziwe. W symbolach: $p \lor \neg p$ . Jego prawdziwość wynika z samej budowy zdania, nie z faktów.

Zadanie · krok po kroku

Przykład 1 (dwie literki): czy (p ∧ q) ⇒ p jest tautologią?

Plan — co zrobimy i po co

Liczymy literki, bo od nich zależy liczba wierszy. Tabela musi mieć wszystkie układy zer i jedynek.
Szukamy spójnika głównego. Mówi, którą kolumnę liczymy na samym końcu, a kawałki po jego obu stronach to kolumny pomocnicze.
Wypełniamy tabelę kolumna po kolumnie, od kawałków najbardziej w środku.
Patrzymy na ostatnią kolumnę: same 1 — tautologia, choć jedno 0 — nie.

Tak się to robi, gdy polecenie mówi „metodą zero-jedynkową”. Szybszą drogę bez całej tabeli znajdziesz pod następnym przykładem.

Policz literki i wiersze
Literki: $p$ i $q$ , czyli $n = 2$ . Tabela ma $2^2 = 4$ wiersze. Kolumna $p$ : 0, 0, 1, 1. Kolumna $q$ : 0, 1, 0, 1.
Bo tak — umowa
Kolejność wierszy to umowa: w pierwszej kolumnie najpierw zera, potem jedynki, w ostatniej 0 i 1 na zmianę. Dzięki temu każdy układ pojawia się dokładnie raz.
Znajdź spójnik główny i kolumny pomocnicze
Nawias liczymy najpierw, więc spójnikiem głównym jest $\Rightarrow$ . Lewa strona to $p \land q$ (kolumna pomocnicza), prawa to samo $p$ (mamy je już w tabeli).
Wypełnij tabelę kolumna po kolumnie
Policz kolumnę w głowie albo na kartce, a potem ją odkryj.
$p$ $q$ $p \land q$ $(p \land q) \Rightarrow p$
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 1
Jak czytać tę tabelę:
kolumna $p \land q$ ma jedynkę tylko w ostatnim wierszu. Ostatnia kolumna to implikacja: z kolumny $p \land q$ do kolumny $p$ .
Odczytaj wynik
W ostatniej kolumnie są same jedynki — zdanie jest tautologią.
Dlaczego?
Implikacja dałaby 0 tylko przy lewej stronie = 1 i prawej = 0. Lewa strona ( $p \land q$ ) jest równa 1 tylko w ostatnim wierszu, a tam prawa strona ( $p$ ) też jest równa 1. Po ludzku: „jeśli mam kartę i PIN, to mam kartę” — tego nie da się złamać.

$p$	$q$	$p \land q$	$(p \land q) \Rightarrow p$
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	1

Zadanie · krok po kroku

Przykład 2 (trzy literki): czy (p ∨ q) ∧ (p ∧ r) ⇒ p ∧ q ∧ r jest tautologią?

Zad. 1, str. 14–15, przykład r)

Sprawdź metodą zero-jedynkową, czy zdanie

(p \lor q) \land (p \land r) \Rightarrow p \land q \land r

jest tautologią.

Plan — co zrobimy i po co

Liczymy literki: trzy literki to 8 wierszy.
Szukamy spójnika głównego. Dzieli zdanie na lewą i prawą stronę.
Planujemy kolumny pomocnicze od środka na zewnątrz. Każda nowa kolumna korzysta tylko z kolumn, które już są w tabeli.
Wypełniamy tabelę.
Szukamy zera w ostatniej kolumnie. Jedno zero wystarczy, żeby zdanie nie było tautologią.

Polecenie mówi „metodą zero-jedynkową”, więc pełna tabela jest obowiązkowa. Bez tego wymogu można szybciej: od razu szukać wiersza, w którym implikacja daje 0 (ramka pod zadaniem).

Policz literki i wiersze
W zdaniu występują trzy różne literki: $p$ , $q$ , $r$ . Czyli $n = 3$ , a tabela ma $2^3 = 8$ wierszy. Kolumna $p$ : cztery zera, cztery jedynki. Kolumna $q$ : po dwa na zmianę. Kolumna $r$ : 0 i 1 na zmianę.
Znajdź spójnik główny
Według kolejności działań najpóźniej liczymy implikację $\Rightarrow$ . Zdanie ma więc postać „lewa strona $\Rightarrow$ prawa strona”:
- lewa strona (poprzednik): $(p \lor q) \land (p \land r)$ ,
- prawa strona (następnik): $p \land q \land r$ .
Dlaczego?
Nawiasy wokół $p \lor q$ i $p \land r$ są tu potrzebne, bo bez nich mielibyśmy mieszankę $\lor$ i $\land$ na jednym poziomie. Za to wokół całej lewej strony nawiasów już nie ma — $\Rightarrow$ i tak liczy się na końcu.
Zaplanuj kolumny pomocnicze
Liczymy od środka na zewnątrz:
1. $p \lor q$
2. $p \land r$
3. $(p \lor q) \land (p \land r)$ — cała lewa strona
4. $p \land q \land r$ — prawa strona (prawdziwa tylko, gdy wszystkie trzy literki są prawdziwe)
5. całe zdanie: lewa $\Rightarrow$ prawa
Wypełnij tabelę kolumna po kolumnie
Policz kolumnę w głowie albo na kartce, a potem ją odkryj.
1. 1 $p \lor q$
2. 2 $p \land r$
3. 3 $(p \lor q) \land (p \land r)$
4. 4 $p \land q \land r$
5. 5 $\dots \Rightarrow p \land q \land r$
$p$ $q$ $r$ $p \lor q$ 1 $p \land r$ 2 $(p \lor q) \land (p \land r)$ 3 $p \land q \land r$ 4 $\dots \Rightarrow p \land q \land r$ 5
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 1
0 1 0 1 0 0 0 1
0 1 1 1 0 0 0 1
1 0 0 1 0 0 0 1
1 0 1 1 1 1 0 0
1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1
Jak czytać tę tabelę:
pierwsze trzy kolumny to wszystkie 8 układów. Kolumna 3 (lewa strona) i kolumna 4 (prawa strona) to wejścia do implikacji. Ostatnia kolumna to wynik całego zdania.
wiersz, w którym zdanie jest fałszywe
Odczytaj wynik
W ostatniej kolumnie jest jedno zero — w wierszu $p = 1$ , $q = 0$ , $r = 1$ . Zdanie nie jest tautologią.
Dlaczego?
W tym wierszu lewa strona jest prawdziwa: $p \lor q = 1 \lor 0 = 1$ oraz $p \land r = 1 \land 1 = 1$ , więc $1 \land 1 = 1$ . Prawa strona jest fałszywa: $p \land q \land r = 1 \land 0 \land 1 = 0$ . Implikacja $1 \Rightarrow 0$ to jedyny fałszywy przypadek implikacji.

$p$	$q$	$r$	$p \lor q$ 1	$p \land r$ 2	$(p \lor q) \land (p \land r)$ 3	$p \land q \land r$ 4	$\dots \Rightarrow p \land q \land r$ 5
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	1	0	0	0	1
0	1	1	1	0	0	0	1
1	0	0	1	0	0	0	1
1	0	1	1	1	1	0	0
1	1	0	1	0	0	0	1
1	1	1	1	1	1	1	1

Pięć kolejnych zdań do sprawdzenia — z tabelą, którą wypełniasz sam i od razu widzisz błędy — czeka w ćwiczeniach na końcu modułu.

Dla jakich wartości zdania są prawdziwe?

Zadanie · krok po kroku

Dla jakich wartości p, q, r prawdziwe są jednocześnie zdania p ⇒ q ∨ r oraz q ⇒ r?

Zad. 2, str. 15, przykład e)

Plan — co zrobimy i po co

Ustalamy, gdzie stoją niewidoczne nawiasy w $p \Rightarrow q \lor r$ . Od tego zależy, co liczymy.
Budujemy jedną tabelę dla obu zdań. „Jednocześnie” znaczy: w tym samym wierszu, czyli przy tych samych $p$ , $q$ , $r$ .
Wypisujemy wiersze, w których oba zdania mają 1. To jest odpowiedź.
Opisujemy wynik słowami. Nie jest to obowiązkowe, ale pomaga sprawdzić, czy wynik ma sens.

Da się też rozumować bez tabeli (ramka „Dlaczego?” w kroku 4), ale na kolokwium tabela jest pewniejsza.

Ustal, jak czytać pierwsze zdanie
W zapisie $p \Rightarrow q \lor r$ nie ma nawiasów. Z kolejności działań wiemy, że $\lor$ liczymy przed $\Rightarrow$ , więc to zdanie znaczy:
$p \Rightarrow (q \lor r)$
Bo tak — umowa
Kolejność spójników to umowa, tak jak „mnożenie przed dodawaniem” w arytmetyce: najpierw $\neg$ , potem $\land$ i $\lor$ , na końcu $\Rightarrow$ i $\Leftrightarrow$ . Gdy nawiasów brak, liczysz właśnie w tej kolejności.
Zbuduj tabelę dla obu zdań
Trzy literki → 8 wierszy. Kolumna pomocnicza: $q \lor r$ . Potem dwa zdania, które nas interesują. Policz kolumnę, a potem ją odkryj.
1. 1 $q \lor r$
2. 2 $p \Rightarrow q \lor r$
3. 3 $q \Rightarrow r$
$p$ $q$ $r$ $q \lor r$ 1 $p \Rightarrow q \lor r$ 2 $q \Rightarrow r$ 3
0 0 0 0 1 1
0 0 1 1 1 1
0 1 0 1 1 0
0 1 1 1 1 1
1 0 0 0 0 1
1 0 1 1 1 1
1 1 0 1 1 0
1 1 1 1 1 1
Jak czytać tę tabelę:
interesują nas wiersze, w których obie fioletowe kolumny mają 1. Po odkryciu całej tabeli zostaną zaznaczone.
wiersze, w których oba zdania są prawdziwe
Wypisz wiersze, w których oba zdania mają 1
$(p, q, r) = (0, 0, 0)$ , $(0, 0, 1)$ , $(0, 1, 1)$ , $(1, 0, 1)$ , $(1, 1, 1)$ .
Opisz wynik słowami
Oba zdania są prawdziwe, gdy $r$ jest prawdziwe (wtedy $p$ i $q$ mogą być dowolne), albo gdy wszystkie trzy literki są fałszywe.
Dlaczego?
Jeśli $r = 1$ , to $q \lor r = 1$ i $q \Rightarrow r = 1$ — następniki obu implikacji są prawdziwe, więc obie implikacje są prawdziwe niezależnie od reszty. Jeśli $r = 0$ , to $q \Rightarrow 0$ jest prawdziwe tylko przy $q = 0$ . Wtedy $q \lor r = 0$ , a $p \Rightarrow 0$ jest prawdziwe tylko przy $p = 0$ . Zostaje jeden wiersz: 0, 0, 0.

$p$	$q$	$r$	$q \lor r$ 1	$p \Rightarrow q \lor r$ 2	$q \Rightarrow r$ 3
0	0	0	0	1	1
0	0	1	1	1	1
0	1	0	1	1	0
0	1	1	1	1	1
1	0	0	0	0	1
1	0	1	1	1	1
1	1	0	1	1	0
1	1	1	1	1	1

Prawa logiki, które warto znać

Niektóre tautologie przydają się tak często, że mają własne nazwy.

\neg\neg p \Leftrightarrow p

Czytamy: nieprawda, że nieprawda, że $p$ — wtedy i tylko wtedy, gdy $p$ . Nazwa: prawo podwójnego przeczenia.

$\neg\neg p$: podwójne zaprzeczenie. Po ludzku: „Nieprawda, że nie zdałem” = „Zdałem”.

p \Leftrightarrow p

$p \Leftrightarrow p$: każde zdanie jest równoważne samemu sobie. Na zajęciach nazywane prawem równoważności. Oczywiste — ale formalnie to też tautologia.

Prawa de Morgana

To najważniejsze prawa tego modułu. Mówią, jak zaprzeczyć zdaniu z „i” albo z „lub”.

\neg (p \lor q) \Leftrightarrow (\neg p \land \neg q)

Czytamy: nieprawda, że ( $p$ lub $q$ ) wtedy i tylko wtedy, gdy nieprawda, że $p$ , i nieprawda, że $q$

$\neg (p \lor q)$: „Nieprawda, że (pada deszcz lub wieje wiatr)”
$\neg p \land \neg q$: „Nieprawda, że pada deszcz, i nieprawda, że wieje wiatr” — po ludzku: nie pada i nie wieje

\neg (p \land q) \Leftrightarrow (\neg p \lor \neg q)

Czytamy: nieprawda, że ( $p$ i $q$ ) wtedy i tylko wtedy, gdy nieprawda, że $p$ , lub nieprawda, że $q$

$\neg (p \land q)$: „Nieprawda, że (mam kartę i znam PIN)”
$\neg p \lor \neg q$: „Nieprawda, że mam kartę, lub nieprawda, że znam PIN” (a może jedno i drugie)

Skąd to się bierze?

Dlaczego przy zaprzeczaniu „lub” zamienia się w „i”? Alternatywa jest fałszywa tylko wtedy, gdy oba zdania są fałszywe. Powiedzieć „nieprawda, że ( $p$ lub $q$ )” to więc powiedzieć „oba są fałszywe”, czyli „nieprawda, że $p$ , i nieprawda, że $q$ ”.

Koniunkcja jest fałszywa, gdy choć jedno zdanie zawiedzie — dlatego „nieprawda, że ( $p$ i $q$ )” to „nieprawda, że $p$ , lub nieprawda, że $q$ ”.

Każde prawo da się sprawdzić tabelą. Policz kolumnę, a potem ją odkryj:

$p$	$q$	$p \lor q$ 1	$\neg (p \lor q)$ 2	$\neg p$ 3	$\neg q$ 4	$\neg p \land \neg q$ 5	$\neg (p \lor q) \Leftrightarrow (\neg p \land \neg q)$ 6
0	0	0	1	1	1	1	1
0	1	1	0	1	0	0	1
1	0	1	0	0	1	0	1
1	1	1	0	0	0	0	1

Jak czytać tę tabelę:

kolumna 2 i kolumna 5 są identyczne w każdym wierszu. Dlatego ich równoważność (ostatnia kolumna) to same jedynki — tautologia.

Trzy prawa spoza slajdów, które oszczędzają czas

Te prawa możesz sprawdzić tabelą tak samo jak de Morgana.

$(p \Rightarrow q) \Leftrightarrow (\neg p \lor q)$ — implikację zawsze da się zapisać jako alternatywę. Z tego korzysta formuła z Excela =LUB(NIE(A1);B1).
$(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$ — prawo kontrapozycji. Czytamy: „jeżeli nieprawda, że $q$ , to nieprawda, że $p$ ”. „Jeśli pada, to ulica jest mokra” znaczy to samo, co „jeśli ulica nie jest mokra, to nie pada”.
$\neg(p \Rightarrow q) \Leftrightarrow (p \land \neg q)$ — zaprzeczenie implikacji. Implikacja jest fałszywa tylko przy $1 \Rightarrow 0$ , czyli gdy $p$ zachodzi, a $q$ nie. „Nieprawda, że jeśli dostaniesz 5, to stawiam pizzę” znaczy: „dostałeś 5 i nieprawda, że stawiam pizzę”. Przyda się przy zaprzeczaniu zdań z kwantyfikatorami.

Funkcja zdaniowa — zdanie z dziurą

Wyrażenie $5x^2 = 125$ nie jest zdaniem logicznym. Dopóki nie wiemy, ile wynosi $x$ , nie da się powiedzieć, czy to prawda, czy fałsz:

dla $x = 5$ : $5 \cdot 25 = 125$ — prawda,
dla $x = -41$ : $5 \cdot 1681 = 8405$ — fałsz,
dla $x = -5$ : $5 \cdot 25 = 125$ — też prawda (minus podniesiony do kwadratu znika).

Takie wyrażenie to funkcja zdaniowa. Zapisujemy ją jako $P(x)$ — „ $P$ od $x$ ”.

P (x)

Czytamy: $P$ od $x$

$P$: nazwa funkcji zdaniowej (dowolna litera, zwykle wielka)
$x$: zmienna — „dziura”, w którą wstawiamy liczbę lub obiekt
$P (5)$: funkcja z wstawioną liczbą 5 — to już zwykłe zdanie logiczne (tu: prawdziwe)

Funkcję zdaniową można zamienić w zdanie logiczne na dwa sposoby:

wstawić konkretną wartość zmiennej (jak wyżej: $x = 5$ ),
powiedzieć, dla ilu wartości ma zachodzić — „dla każdego $x$ ” albo „istnieje $x$ ”. Do tego służą kwantyfikatory.

Kwantyfikatory ∀ i ∃ — jak je czytać

\forall

Kwantyfikator ogólny

czytamy: „dla każdego…”

Warunek ma być spełniony przez wszystkie elementy, bez wyjątku.

Jak zapamiętać: odwrócone A — od angielskiego All (wszystkie).

\exists

Kwantyfikator szczegółowy

czytamy: „istnieje…”

Wystarczy, że warunek spełnia co najmniej jeden element.

Jak zapamiętać: odwrócone E — od angielskiego Exists (istnieje).

\exists!

Kwantyfikator „dokładnie jeden”

czytamy: „istnieje dokładnie jeden…”

Warunek spełnia jeden element — nie zero i nie dwa. Używany rzadko, w zadaniach z zajęć praktycznie się nie pojawia.

Zdanie „dla każdej liczby rzeczywistej $x$ zachodzi $x^2 \geq 0$ ” spotkasz w jednym z dwóch zapisów. Oba znaczą to samo:

\forall_{x \in \mathbb{R}}\ \ x^2 \geq 0 \qquad\qquad \forall x \in \mathbb{R}:\ x^2 \geq 0

\forall_{x \in R} x^{2} \geq 0

Czytamy: dla każdej liczby rzeczywistej $x$ : $x$ do kwadratu jest większe lub równe zero

$\forall$: „dla każdego”
$x \in R$: „ $x$ należące do $R$ ” — skąd bierzemy $x$ . Znak $\in$ czytamy „należy do”.
$x^{2} \geq 0$: warunek, czyli funkcja zdaniowa, która ma być spełniona

\forall_{x \in R} \exists_{y \in R} y > x

Czytamy: dla każdej liczby rzeczywistej $x$ istnieje liczba rzeczywista $y$ taka, że $y > x$

$\forall_{x \in R}$: „dla każdej liczby rzeczywistej $x$ ”
$\exists_{y \in R}$: „istnieje liczba rzeczywista $y$ taka, że”
$y > x$: warunek: „ $y$ jest większe od $x$ ”

\exists_{m, n \in N} \forall_{x \in R} mn = m x

Czytamy: istnieją liczby naturalne $m$ i $n$ takie, że dla każdej liczby rzeczywistej $x$ iloczyn $mn$ jest równy iloczynowi $m x$

$\exists_{m, n \in N}$: „istnieją liczby naturalne $m$ i $n$ takie, że” — dwa kwantyfikatory $\exists$ zapisane razem
$\forall_{x \in R}$: „dla każdej liczby rzeczywistej $x$ ”
$mn = m x$: warunek: równanie, w którym lewa strona to $m \cdot n$ , a prawa to $m \cdot x$

Czy zdanie z kwantyfikatorami jest prawdziwe?

Jeden kwantyfikator

$\forall_{x \in \mathbb{R}}\ x^2 \geq 0$ — prawda. Kwadrat liczby nigdy nie jest ujemny.
$\forall_{x \in \mathbb{R}}\ x^2 > 0$ — fałsz. Kontrprzykład: $x = 0$ , bo $0^2 = 0$ , a nie $> 0$ .
$\exists_{x \in \mathbb{R}}\ x^2 = 4$ — prawda. Przykład: $x = 2$ .
$\exists_{x \in \mathbb{R}}\ x^2 = -1$ — fałsz. Żaden kwadrat liczby rzeczywistej nie jest ujemny.

Dwa kwantyfikatory: liczy się kolejność

Kwantyfikatory tego samego rodzaju można zamieniać miejscami: „dla każdego $x$ i dla każdego $y$ ” znaczy to samo, co „dla każdego $y$ i dla każdego $x$ ”. Kwantyfikatorów różnego rodzaju zamieniać nie wolno — zmienia się sens zdania.

Jak to sprawdzać w zadaniu? Zależy od tego, co stoi pierwsze:

Najpierw $\forall$ , potem $\exists$

\forall_{x}\ \exists_{y}\ \ldots

„Do każdego $x$ da się dobrać jakieś $y$ .”

Weź dowolne $x$ .
Poszukaj $y$ , które do niego pasuje. Wolno, żeby $y$ zależało od $x$ — np. $y = x + 1$ .
Umiesz podać taki przepis na $y$ — zdanie jest prawdziwe. Istnieje $x$ , do którego nie pasuje żadne $y$ — fałszywe (podaj to $x$ ).

Najpierw $\exists$ , potem $\forall$

\exists_{y}\ \forall_{x}\ \ldots

„Istnieje jedno $y$ , które działa dla wszystkich $x$ naraz.”

Wybierz jedną konkretną liczbę $y$ — bez $x$ w środku. Najczęściej warto sprawdzić 0 albo 1.
Sprawdź, czy z tym $y$ warunek zachodzi dla każdego $x$ .
Tak — zdanie jest prawdziwe. Każde $y$ da się „zepsuć” jakimś $x$ — fałszywe.

Zadanie · krok po kroku

Przykład 1: czy ∀x∈ℝ ∃y∈ℝ y > x jest prawdziwe?

Plan — co zrobimy i po co

Czytamy zdanie na głos. Dopiero słowami widać, o co pyta.
Rozpoznajemy typ: najpierw $\forall$ , potem $\exists$ . Od typu zależy przepis.
Szukamy przepisu na $y$ , który zależy od $x$ . Przy $\forall \exists$ wolno dobrać $y$ osobno do każdego $x$ .
Sprawdzamy przepis na literze $x$ , a nie na kilku liczbach. $\forall$ wymaga, żeby działał dla każdego $x$ .
Zapisujemy wniosek.

Tak się to robi przy każdym zdaniu, które zaczyna się od $\forall \exists$ .

Przeczytaj zdanie
„Dla każdej liczby rzeczywistej $x$ istnieje liczba rzeczywista $y$ taka, że $y > x$ .” Czyli: do każdej liczby da się znaleźć większą.
Rozpoznaj typ
Najpierw $\forall$ , potem $\exists$ . Do każdego $x$ szukamy pasującego $y$ — i $y$ może zależeć od $x$ .
Znajdź przepis na y
Weźmy $y = x + 1$ . Na przykład: $x = 5 \to y = 6$ , $x = -3 \to y = -2$ .
Inny sposób
Przepis nie musi być jeden. $y = x + 2$ albo $y = x + 0{,}5$ też działają. Uważaj tylko na przepisy, które działają nie zawsze: $y = 2x$ dla $x = -1$ daje $y = -2$ , a $-2 > -1$ jest fałszem.
Sprawdź przepis dla każdego x
Wstawiamy $y = x + 1$ do warunku $y > x$ i dostajemy $x + 1 > x$ . Dodanie 1 zawsze daje liczbę większą, więc nierówność zachodzi dla każdego $x$ .
Dlaczego?
Sprawdzamy przepis ogólnie, a nie tylko dla kilku liczb, bo $\forall$ wymaga, żeby działało dla każdego $x$ .
Wniosek
Zdanie jest prawdziwe.

Zadanie · krok po kroku

Przykład 2: czy ∃y∈ℝ ∀x∈ℝ y > x jest prawdziwe?

Plan — co zrobimy i po co

Czytamy zdanie na głos.
Rozpoznajemy typ: najpierw $\exists$ , potem $\forall$ . Potrzebne jest jedno $y$ , które działa dla wszystkich $x$ naraz.
Próbujemy kilku kandydatów na $y$ . To rozgrzewka: widać, jak każdy kandydat się psuje.
Pokazujemy, że da się zepsuć każde $y$ . Kilka nieudanych prób to za mało — trzeba pokazać, że nie zadziała żadne $y$ .
Zapisujemy wniosek.

Kroku 3 nie musisz pisać na kolokwium. Dowodem jest krok 4.

Przeczytaj zdanie
„Istnieje liczba rzeczywista $y$ taka, że dla każdej liczby rzeczywistej $x$ : $y > x$ .” Czyli: istnieje liczba większa od wszystkich liczb.
Rozpoznaj typ
Najpierw $\exists$ , potem $\forall$ . Musimy wskazać jedno konkretne $y$ , a potem ono musi być większe od każdego $x$ .
Spróbuj kilku kandydatów
$y = 1000$ ? Nie działa, bo $x = 1001$ jest większe. $y = 1\,000\,000$ ? Psuje je $x = 1\,000\,001$ .
Pokaż, że każde y da się zepsuć
Jakie $y$ nie wybierzesz, weź $x = y + 1$ . Wtedy $y > y + 1$ jest fałszem. Żadne $y$ nie działa dla wszystkich $x$ .
Inny sposób
Wystarczy nawet $x = y$ . Wtedy warunek brzmi $y > y$ , a żadna liczba nie jest większa od samej siebie.
Wniosek
Zdanie jest fałszywe.
Dlaczego?
W przykładzie 1 dobieraliśmy $y$ do każdego $x$ osobno. Tutaj $y$ musi być ustalone z góry — i to robi różnicę.

Podobny przykład· jeszcze trzy zdania

$\forall_{x \in \mathbb{R}}\ \exists_{y \in \mathbb{R}}\ x + y = 0$ — prawda: do każdego $x$ bierzemy $y = -x$ , bo $x + (-x) = 0$ .
$\exists_{y \in \mathbb{R}}\ \forall_{x \in \mathbb{R}}\ x + y = 0$ — fałsz: jedno $y$ musiałoby pasować do wszystkich $x$ . Weź np. $y = 0$ : dla $x = 1$ wychodzi $1 \neq 0$ . Jakie $y$ nie weźmiesz, $x = 1 - y$ da $x + y = 1$ .
$\forall_{x \in \mathbb{R}}\ \exists_{y \in \mathbb{R}}\ x \cdot y = 1$ — fałsz, choć zaczyna się od $\forall \exists$ : dla $x = 0$ każde $y$ daje $0 \cdot y = 0$ , a nie 1. Jeden taki $x$ wystarczy.

Zadanie · krok po kroku

Czy zdanie ∃m,n∈ℕ ∀x∈ℝ mn = mx jest prawdziwe?

Zad. 1, str. 19–20, przykład h)

Zapisz słownie i określ wartość logiczną zdania

\exists_{m, n \in \mathbb{N}}\ \forall_{x \in \mathbb{R}}\ \ mn = mx

Plan — co zrobimy i po co

Czytamy zdanie i dzielimy warunek na lewą i prawą stronę równania.
Rozpoznajemy typ: $\exists$ przed $\forall$ . Szukamy konkretnych $m$ i $n$ , które działają dla każdego $x$ .
Sprawdzamy, która strona zmienia się razem z $x$ . Tę stronę trzeba „unieruchomić”.
Dobieramy $m$ tak, żeby $x$ przestał mieć znaczenie.
Sprawdzamy równanie dla dowolnego $x$ : lewa strona, prawa strona, porównanie.
Zapisujemy wniosek.

To ten sam przepis co w przykładzie 2 wyżej. Tam żadne $y$ nie działało, a tu udaje się znaleźć $m$ i $n$ .

Przeczytaj zdanie i nazwij jego części
„Istnieją liczby naturalne $m$ i $n$ takie, że dla każdej liczby rzeczywistej $x$ iloczyn $mn$ jest równy iloczynowi $mx$ .”
Warunek to równanie. Lewa strona: $m \cdot n$ . Prawa strona: $m \cdot x$ .
Rozpoznaj typ
Najpierw $\exists$ , potem $\forall$ . Szukamy więc konkretnych liczb $m$ i $n$ (bez $x$ ), przy których równanie jest prawdziwe dla każdego $x$ .
Zobacz, która strona zależy od x
Lewa strona $m \cdot n$ nie ma w sobie $x$ . Gdy wybierzemy $m$ i $n$ , jest jedną stałą liczbą. Prawa strona $m \cdot x$ zmienia się razem z $x$ — np. dla $m = 2$ : przy $x = 1$ daje 2, przy $x = 5$ daje 10.
Dlaczego?
Stała liczba nie może być równa czemuś, co ciągle się zmienia. Musimy więc tak dobrać $m$ , żeby prawa strona przestała zależeć od $x$ .
Wybierz m, przy którym x przestaje mieć znaczenie
W prawej stronie $x$ jest mnożone przez $m$ . Przy mnożeniu zmienna przestaje mieć znaczenie, gdy mnożymy przez 0 (ramka „Kiedy tego użyć” wyżej). Bierzemy $m = 0$ . Liczbę $n$ wybieramy dowolnie, np. $n = 0$ .
Dlaczego?
$n$ występuje tylko po lewej stronie, a ta przy $m = 0$ i tak wyjdzie 0. Dlatego wartość $n$ nie ma tu znaczenia.
Bo tak — umowa
Wolno wziąć $m = 0$ , bo w tym kursie — tak jak w rozwiązaniach z zajęć — $\mathbb{N} = \{0, 1, 2, \ldots\}$ . To umowa. Co by było bez niej, pokazuje ramka pod zadaniem.
Sprawdź równanie: policz każdą stronę osobno
Lewa strona: $m \cdot n = 0 \cdot 0 = 0$ .
Prawa strona: $m \cdot x = 0 \cdot x = 0$ — dla każdego $x$ , bo zero razy dowolna liczba daje zero.
Obie strony są równe: $0 = 0$ .
Dlaczego?
Równanie jest prawdziwe wtedy, gdy lewa i prawa strona mają tę samą wartość. Dlatego zawsze sprawdzamy je tak samo: liczymy lewą stronę, liczymy prawą stronę i porównujemy wyniki.
Wniosek
Znaleźliśmy $m = 0$ i $n = 0$ , przy których równanie zachodzi dla wszystkich $x$ . Zdanie jest prawdziwe.

Zaprzeczanie zdań z kwantyfikatorami

Jak zaprzeczyć zdaniu „Wszyscy zdali”? Bardzo częsta odpowiedź brzmi „Nikt nie zdał” — i jest błędna. Żeby „wszyscy zdali” było nieprawdą, wystarczy, że ktoś nie zdał.

To jest treść praw de Morgana dla kwantyfikatorów:

\begin{gathered} \neg\left(\forall_{x}\ P(x)\right) \Leftrightarrow \exists_{x}\ \neg P(x) \\ \neg\left(\exists_{x}\ P(x)\right) \Leftrightarrow \forall_{x}\ \neg P(x) \end{gathered}

\neg (\forall_{x} P (x)) \Leftrightarrow \exists_{x} \neg P (x)

Czytamy: nieprawda, że dla każdego $x$ zachodzi $P (x)$ — wtedy i tylko wtedy, gdy istnieje $x$ taki, że nieprawda, że $P (x)$

$\neg (\forall_{x} P (x))$: „nieprawda, że każdy zdał”
$\exists_{x} \neg P (x)$: „istnieje ktoś, kto nie zdał”

Symulator

Grupa ćwiczeniowa: kliknij osobę, żeby zmienić jej wynik

$Z (x)$ = „osoba $x$ zdała kolokwium”

$\forall_{x} Z (x)$ „każdy zdał”?
$\exists_{x} Z (x)$ „ktoś zdał (co najmniej jedna osoba)”?
$\neg \forall_{x} Z (x)$ „nieprawda, że każdy zdał”?
$\exists_{x} \neg Z (x)$ „ktoś nie zdał”?
$\neg \exists_{x} Z (x)$ „nieprawda, że ktoś zdał”?
$\forall_{x} \neg Z (x)$ „każdy nie zdał (nikt nie zdał)”?

Zauważ: wiersze 3 i 4 mają zawsze tę samą wartość. Tak samo wiersze 5 i 6. Klikaj, ile chcesz — nie da się ich rozdzielić. To właśnie prawa de Morgana dla kwantyfikatorów.

Jak zaprzeczać warunki

warunek	zaprzeczenie	po ludzku
$a = b$	$a \neq b$	„nie jest równe”
$a < b$	$a \geq b$	jeśli nie mniejsze, to większe albo równe
$a > b$	$a \leq b$	jeśli nie większe, to mniejsze albo równe
$a \leq b$	$a > b$
$a \geq b$	$a < b$

Przykłady krok po kroku

\forall_{x \in R} x^{2} \geq 0

Czytamy: zaprzeczenie: $\exists_{x \in R} x^{2} < 0$

$\forall \to \exists$: zamieniamy kwantyfikator
$\geq \to <$: zaprzeczamy warunek
$\exists_{x \in R} x^{2} < 0$: wynik: „istnieje liczba rzeczywista, której kwadrat jest ujemny”. Zdanie wyjściowe było prawdziwe, więc zaprzeczenie jest fałszywe.

\forall_{x \in R} \exists_{y \in R} y > x

Czytamy: zaprzeczenie: $\exists_{x \in R} \forall_{y \in R} y \leq x$

$\forall_{x} \exists_{y} \to \exists_{x} \forall_{y}$: oba kwantyfikatory zmieniają rodzaj, ale kolejność zostaje: najpierw $x$ , potem $y$
$> \to \leq$: zaprzeczamy warunek

\exists_{x \in R} (x > 2 \land x < 5)

Czytamy: zaprzeczenie: $\forall_{x \in R} (x \leq 2 \lor x \geq 5)$

$\exists \to \forall$: zamieniamy kwantyfikator
$\land \to \lor$: warunek to koniunkcja, więc prawo de Morgana zamienia ją w alternatywę
$> 2 \to \leq 2, < 5 \to \geq 5$: każdą nierówność zaprzeczamy osobno

Zadanie · krok po kroku

Zaneguj zdanie ∃m,n∈ℕ ∀x∈ℝ mn = mx

Zad. 3, str. 20, przykład h)

Napisz zaprzeczenie zdania

\exists_{m, n \in \mathbb{N}}\ \forall_{x \in \mathbb{R}}\ \ mn = mx

Plan — co zrobimy i po co

Czytamy zdanie na głos. Wtedy łatwiej zauważyć, ile jest kwantyfikatorów: $\exists_{m, n}$ to dwa.
Zamieniamy każdy kwantyfikator na przeciwny. Kolejność i zbiory zostają.
Zaprzeczamy warunek: $=$ zamienia się w $\neq$ .
Jeśli polecenie pyta też o wartość, podajemy ją: zaprzeczenie ma wartość przeciwną do zdania wyjściowego.

Dopisanie $\neg$ przed całym zdaniem to jeszcze nie odpowiedź. Chodzi o postać, w której $\neg$ przeniesiono do środka — tu zostało tylko w znaku $\neq$ .

Przeczytaj zdanie na głos
„Istnieją liczby naturalne $m$ i $n$ takie, że dla każdej liczby rzeczywistej $x$ : $m \cdot n = m \cdot x$ .”
Dlaczego?
Zapis $\exists_{m, n \in \mathbb{N}}$ to skrót od dwóch kwantyfikatorów tego samego typu: „istnieje $m$ ” i „istnieje $n$ ”. Oba zmienią się w $\forall$ .
Zamień kwantyfikatory
$\exists_{m, n \in \mathbb{N}}$ zamienia się w $\forall_{m, n \in \mathbb{N}}$ , a $\forall_{x \in \mathbb{R}}$ w $\exists_{x \in \mathbb{R}}$ . Kolejność i zbiory zostają bez zmian.
Zaprzecz warunek
Zaprzeczeniem $mn = mx$ jest $mn \neq mx$ . Cały wynik:
$\begin{aligned} &\neg\left(\exists_{m, n \in \mathbb{N}}\ \forall_{x \in \mathbb{R}}\ mn = mx\right) \\ &\Leftrightarrow\; \forall_{m, n \in \mathbb{N}}\ \exists_{x \in \mathbb{R}}\ \ mn \neq mx \end{aligned}$
Czytamy: „dla każdych liczb naturalnych $m$ , $n$ istnieje liczba rzeczywista $x$ , dla której $mn \neq mx$ ”.
Inny sposób
Można też przesuwać $\neg$ do środka po jednym kroku. Każde przejście przez kwantyfikator zmienia jego rodzaj (prawa de Morgana):
$\begin{aligned} &\neg \exists_{m, n \in \mathbb{N}}\ \forall_{x \in \mathbb{R}}\ mn = mx \\ &\Leftrightarrow \forall_{m, n \in \mathbb{N}}\ \neg \forall_{x \in \mathbb{R}}\ mn = mx \\ &\Leftrightarrow \forall_{m, n \in \mathbb{N}}\ \exists_{x \in \mathbb{R}}\ \neg(mn = mx) \\ &\Leftrightarrow \forall_{m, n \in \mathbb{N}}\ \exists_{x \in \mathbb{R}}\ mn \neq mx \end{aligned}$
Wynik jest ten sam. Ten zapis pokazuje, skąd się bierze przepis „zamień kwantyfikatory i zaprzecz warunek”.
Jeśli trzeba: wartość zaprzeczenia
Zdanie wyjściowe jest prawdziwe ( $m = 0$ , zobacz zadanie wyżej). Zaprzeczenie prawdziwego zdania jest zawsze fałszywe — tu: dla $m = 0$ nie znajdziemy $x$ , przy którym $0 \neq 0$ .

Ściąga przed kolokwium

Zdanie logiczneDa się powiedzieć „prawda” (1) albo „fałsz” (0). Nie są nimi: rozkazy, pytania, prognozy, opinie, wyrażenia ze zmienną.

¬ negacjaCzytamy „nieprawda, że”. Odwraca wartość.

\neg\neg p \Leftrightarrow p

∧ koniunkcja „i”1 tylko gdy oba = 1. Działa jak mnożenie.

∨ alternatywa „lub”0 tylko gdy oba = 0. „Lub” nie wyklucza obu naraz.

⇒ implikacja0 tylko dla

1 \Rightarrow 0

: z prawdy nie wynika fałsz. Nie wolno jej odwracać.

⇔ równoważność1 gdy wartości są równe. To implikacja w obie strony.

Kolejność¬, potem ∧ i ∨, na końcu ⇒ i ⇔. Mieszasz ∧ z ∨? Daj nawiasy.

Wypełnianie tabeli

2^n

wierszy. Pierwsza kolumna: połowa zer, połowa jedynek. Każda następna: bloki o połowę krótsze. Ostatnia: 0, 1 na zmianę.

TautologiaSame jedynki w ostatniej kolumnie. Jedno 0 — nie jest tautologią.

De Morgan

\neg(p \lor q) \Leftrightarrow \neg p \land \neg q

;

\neg(p \land q) \Leftrightarrow \neg p \lor \neg q

∀ i ∃∀ — obalasz jednym kontrprzykładem. ∃ — wystarczy jeden przykład.

\forall_x \exists_y

y

może zależeć od

x

\exists_y \forall_x

: jedno

y

dla wszystkich (szukaj 0 albo 1).

Negacja z kwantyfikatorami∀ ↔ ∃, kolejność bez zmian, na końcu zaprzecz warunek (

<

↔

\geq

\land

↔

\lor

Ćwiczenia przed kolokwium

Krótkie zadania z natychmiastową odpowiedzią, ułożone według poleceń z kolokwium. Przy każdej odpowiedzi — dobrej i złej — zobaczysz, dlaczego tak jest. Wszystko da się zrobić na telefonie.

Oblicz wartość zdania

Ćwiczenia · 6 zadań

Oblicz $(p \Rightarrow q) \lor \neg p$ dla $p = 1$ , $q = 0$ .
Oblicz $\neg p \land (q \Rightarrow r)$ dla $p = 0$ , $q = 1$ , $r = 0$ .
Oblicz $p \land q \Rightarrow r$ dla $p = 0$ , $q = 1$ , $r = 0$ .
Oblicz $\neg (p \lor q) \Leftrightarrow r$ dla $p = 0$ , $q = 0$ , $r = 1$ .
Oblicz $p \lor q \Rightarrow \neg r$ dla $p = 1$ , $q = 0$ , $r = 1$ .
Oblicz $(p \Leftrightarrow q) \land (q \lor r)$ dla $p = 1$ , $q = 1$ , $r = 0$ .

Odczytaj zdanie i zapisz je symbolami

Ćwiczenia · 9 zadań

Który spójnik jest główny w zdaniu $\neg p \lor q \Rightarrow r$ ?
Jak wstawić nawiasy w zdaniu $p \land q \Rightarrow \neg r$ ?
Jak przeczytać $\neg p \land q$ ?
Jak zapisać symbolami „nieprawda, że ( $p$ lub $q$ )”?
$p$ = „uczę się”, $q$ = „zdam”. Jak zapisać „Jeżeli się uczę, to zdam”?
$p$ = „pada deszcz”, $q$ = „wieje wiatr”, $r$ = „zostaję w domu”. Jak zapisać „Jeżeli pada deszcz lub wieje wiatr, to zostaję w domu”?
Jak przeczytać $p \Rightarrow q \land r$ ?
Spójnikiem głównym w zdaniu $(p \Rightarrow q) \land \neg (q \lor r)$ jest:
Jak przeczytać $\neg p \Rightarrow \neg q$ ?

Czy to tautologia?

Każdą tabelę wypełniasz sam. Kolumny z literkami są już gotowe — w kolejnych wpisujesz 0 albo 1. Po „Sprawdź” zobaczysz, które pola są złe i jak je policzyć.

Wypełnij tabelę

Zadanie 1 · jedna literka

Sprawdź, czy zdanie $p \lor \neg p$ jest tautologią. Jedna literka, więc tabela ma $2^1 = 2$ wiersze.

$p$	$\neg p$	$p \lor \neg p$
0
1

Wniosek

Czy zdanie $p \lor \neg p$ jest tautologią?

Wypełnij tabelę

Zadanie 2 · odwrócona implikacja

Sprawdź, czy zdanie $(p \Rightarrow q) \Rightarrow (q \Rightarrow p)$ jest tautologią.

$p$	$q$	$p \Rightarrow q$ 1	$q \Rightarrow p$ 2	$(p \Rightarrow q) \Rightarrow (q \Rightarrow p)$ 3
0	0
0	1
1	0
1	1

Wniosek

Czy zdanie $(p \Rightarrow q) \Rightarrow (q \Rightarrow p)$ jest tautologią?

Wypełnij tabelę

Zadanie 3 · dwie literki

Sprawdź, czy zdanie $[(p \Rightarrow q) \land p] \Rightarrow q$ jest tautologią.

$p$	$q$	$p \Rightarrow q$ 1	$(p \Rightarrow q) \land p$ 2	$[(p \Rightarrow q) \land p] \Rightarrow q$ 3
0	0
0	1
1	0
1	1

Wniosek

Czy zdanie $[(p \Rightarrow q) \land p] \Rightarrow q$ jest tautologią?

Wypełnij tabelę

Zadanie 4 · trzy literki

Sprawdź, czy zdanie $(p \lor q) \land r \Rightarrow p$ jest tautologią.

$p$	$q$	$r$
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Wiersz $p = 0, q = 0, r = 0$ : $p$ ma wartość 0, a $q$ ma wartość 0, więc $0 \lor 0 = 0$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 0, q = 0, r = 0$ : $p \lor q$ ma wartość 0, a $r$ ma wartość 0, więc $0 \land 0 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 0, q = 0, r = 0$ : $(p \lor q) \land r$ ma wartość 0, a $p$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 1$ : $p$ ma wartość 0, a $q$ ma wartość 0, więc $0 \lor 0 = 0$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 0, q = 0, r = 1$ : $p \lor q$ ma wartość 0, a $r$ ma wartość 1, więc $0 \land 1 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 0, q = 0, r = 1$ : $(p \lor q) \land r$ ma wartość 0, a $p$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 0$ : $p$ ma wartość 0, a $q$ ma wartość 1, więc $0 \lor 1 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 0, q = 1, r = 0$ : $p \lor q$ ma wartość 1, a $r$ ma wartość 0, więc $1 \land 0 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 0, q = 1, r = 0$ : $(p \lor q) \land r$ ma wartość 0, a $p$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 1$ : $p$ ma wartość 0, a $q$ ma wartość 1, więc $0 \lor 1 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 0, q = 1, r = 1$ : $p \lor q$ ma wartość 1, a $r$ ma wartość 1, więc $1 \land 1 = 1$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 0, q = 1, r = 1$ : $(p \lor q) \land r$ ma wartość 1, a $p$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 0$ : $p$ ma wartość 1, a $q$ ma wartość 0, więc $1 \lor 0 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 1, q = 0, r = 0$ : $p \lor q$ ma wartość 1, a $r$ ma wartość 0, więc $1 \land 0 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 1, q = 0, r = 0$ : $(p \lor q) \land r$ ma wartość 0, a $p$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 1$ : $p$ ma wartość 1, a $q$ ma wartość 0, więc $1 \lor 0 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 1, q = 0, r = 1$ : $p \lor q$ ma wartość 1, a $r$ ma wartość 1, więc $1 \land 1 = 1$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 1, q = 0, r = 1$ : $(p \lor q) \land r$ ma wartość 1, a $p$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 0$ : $p$ ma wartość 1, a $q$ ma wartość 1, więc $1 \lor 1 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 1, q = 1, r = 0$ : $p \lor q$ ma wartość 1, a $r$ ma wartość 0, więc $1 \land 0 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 1, q = 1, r = 0$ : $(p \lor q) \land r$ ma wartość 0, a $p$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 1$ : $p$ ma wartość 1, a $q$ ma wartość 1, więc $1 \lor 1 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 1, q = 1, r = 1$ : $p \lor q$ ma wartość 1, a $r$ ma wartość 1, więc $1 \land 1 = 1$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 1, q = 1, r = 1$ : $(p \lor q) \land r$ ma wartość 1, a $p$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .

Wniosek

Czy zdanie $(p \lor q) \land r \Rightarrow p$ jest tautologią?

Wypełnij tabelę

Zadanie 5 · trzy literki, łańcuch implikacji

Sprawdź, czy zdanie $(p \Rightarrow q) \land (q \Rightarrow r) \Rightarrow (p \Rightarrow r)$ jest tautologią.

$p$	$q$	$r$
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Wiersz $p = 0, q = 0, r = 0$ : $p$ ma wartość 0, a $q$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 0$ : $q$ ma wartość 0, a $r$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 0$ : $p \Rightarrow q$ ma wartość 1, a $q \Rightarrow r$ ma wartość 1, więc $1 \land 1 = 1$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 0, q = 0, r = 0$ : $p$ ma wartość 0, a $r$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 0$ : $(p \Rightarrow q) \land (q \Rightarrow r)$ ma wartość 1, a $p \Rightarrow r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 1$ : $p$ ma wartość 0, a $q$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 1$ : $q$ ma wartość 0, a $r$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 1$ : $p \Rightarrow q$ ma wartość 1, a $q \Rightarrow r$ ma wartość 1, więc $1 \land 1 = 1$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 0, q = 0, r = 1$ : $p$ ma wartość 0, a $r$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 1$ : $(p \Rightarrow q) \land (q \Rightarrow r)$ ma wartość 1, a $p \Rightarrow r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 0$ : $p$ ma wartość 0, a $q$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 0$ : $q$ ma wartość 1, a $r$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 0$ : $p \Rightarrow q$ ma wartość 1, a $q \Rightarrow r$ ma wartość 0, więc $1 \land 0 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 0, q = 1, r = 0$ : $p$ ma wartość 0, a $r$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 0$ : $(p \Rightarrow q) \land (q \Rightarrow r)$ ma wartość 0, a $p \Rightarrow r$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 1$ : $p$ ma wartość 0, a $q$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 1$ : $q$ ma wartość 1, a $r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 1$ : $p \Rightarrow q$ ma wartość 1, a $q \Rightarrow r$ ma wartość 1, więc $1 \land 1 = 1$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 0, q = 1, r = 1$ : $p$ ma wartość 0, a $r$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 1$ : $(p \Rightarrow q) \land (q \Rightarrow r)$ ma wartość 1, a $p \Rightarrow r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 0$ : $p$ ma wartość 1, a $q$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 0$ : $q$ ma wartość 0, a $r$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 0$ : $p \Rightarrow q$ ma wartość 0, a $q \Rightarrow r$ ma wartość 1, więc $0 \land 1 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 1, q = 0, r = 0$ : $p$ ma wartość 1, a $r$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 0$ : $(p \Rightarrow q) \land (q \Rightarrow r)$ ma wartość 0, a $p \Rightarrow r$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 1$ : $p$ ma wartość 1, a $q$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 1$ : $q$ ma wartość 0, a $r$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 1$ : $p \Rightarrow q$ ma wartość 0, a $q \Rightarrow r$ ma wartość 1, więc $0 \land 1 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 1, q = 0, r = 1$ : $p$ ma wartość 1, a $r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 1$ : $(p \Rightarrow q) \land (q \Rightarrow r)$ ma wartość 0, a $p \Rightarrow r$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 0$ : $p$ ma wartość 1, a $q$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 0$ : $q$ ma wartość 1, a $r$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 0$ : $p \Rightarrow q$ ma wartość 1, a $q \Rightarrow r$ ma wartość 0, więc $1 \land 0 = 0$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 1, q = 1, r = 0$ : $p$ ma wartość 1, a $r$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 0$ : $(p \Rightarrow q) \land (q \Rightarrow r)$ ma wartość 0, a $p \Rightarrow r$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 1$ : $p$ ma wartość 1, a $q$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 1$ : $q$ ma wartość 1, a $r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 1$ : $p \Rightarrow q$ ma wartość 1, a $q \Rightarrow r$ ma wartość 1, więc $1 \land 1 = 1$ . $\land$ daje 1 tylko wtedy, gdy obie strony są równe 1.
Wiersz $p = 1, q = 1, r = 1$ : $p$ ma wartość 1, a $r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 1$ : $(p \Rightarrow q) \land (q \Rightarrow r)$ ma wartość 1, a $p \Rightarrow r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .

Wniosek

Czy zdanie $(p \Rightarrow q) \land (q \Rightarrow r) \Rightarrow (p \Rightarrow r)$ jest tautologią?

Dla jakich wartości zdania są prawdziwe?

Wypełnij tabelę

Dwa zdania naraz

Dla jakich wartości $p$ , $q$ , $r$ prawdziwe są jednocześnie zdania $p \lor q$ oraz $\neg p \Rightarrow r$ ? Wypełnij tabelę, a potem odpowiedz na pytanie pod nią.

$p$	$q$	$r$
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Wiersz $p = 0, q = 0, r = 0$ : $p$ ma wartość 0, więc $\neg0 = 1$ . Negacja odwraca wartość: z 1 robi 0, a z 0 robi 1.
Wiersz $p = 0, q = 0, r = 0$ : $p$ ma wartość 0, a $q$ ma wartość 0, więc $0 \lor 0 = 0$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 0, q = 0, r = 0$ : $\neg p$ ma wartość 1, a $r$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 0, r = 1$ : $p$ ma wartość 0, więc $\neg0 = 1$ . Negacja odwraca wartość: z 1 robi 0, a z 0 robi 1.
Wiersz $p = 0, q = 0, r = 1$ : $p$ ma wartość 0, a $q$ ma wartość 0, więc $0 \lor 0 = 0$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 0, q = 0, r = 1$ : $\neg p$ ma wartość 1, a $r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 0$ : $p$ ma wartość 0, więc $\neg0 = 1$ . Negacja odwraca wartość: z 1 robi 0, a z 0 robi 1.
Wiersz $p = 0, q = 1, r = 0$ : $p$ ma wartość 0, a $q$ ma wartość 1, więc $0 \lor 1 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 0, q = 1, r = 0$ : $\neg p$ ma wartość 1, a $r$ ma wartość 0, więc $1 \Rightarrow 0 = 0$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 0, q = 1, r = 1$ : $p$ ma wartość 0, więc $\neg0 = 1$ . Negacja odwraca wartość: z 1 robi 0, a z 0 robi 1.
Wiersz $p = 0, q = 1, r = 1$ : $p$ ma wartość 0, a $q$ ma wartość 1, więc $0 \lor 1 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 0, q = 1, r = 1$ : $\neg p$ ma wartość 1, a $r$ ma wartość 1, więc $1 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 0$ : $p$ ma wartość 1, więc $\neg1 = 0$ . Negacja odwraca wartość: z 1 robi 0, a z 0 robi 1.
Wiersz $p = 1, q = 0, r = 0$ : $p$ ma wartość 1, a $q$ ma wartość 0, więc $1 \lor 0 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 1, q = 0, r = 0$ : $\neg p$ ma wartość 0, a $r$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 0, r = 1$ : $p$ ma wartość 1, więc $\neg1 = 0$ . Negacja odwraca wartość: z 1 robi 0, a z 0 robi 1.
Wiersz $p = 1, q = 0, r = 1$ : $p$ ma wartość 1, a $q$ ma wartość 0, więc $1 \lor 0 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 1, q = 0, r = 1$ : $\neg p$ ma wartość 0, a $r$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 0$ : $p$ ma wartość 1, więc $\neg1 = 0$ . Negacja odwraca wartość: z 1 robi 0, a z 0 robi 1.
Wiersz $p = 1, q = 1, r = 0$ : $p$ ma wartość 1, a $q$ ma wartość 1, więc $1 \lor 1 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 1, q = 1, r = 0$ : $\neg p$ ma wartość 0, a $r$ ma wartość 0, więc $0 \Rightarrow 0 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .
Wiersz $p = 1, q = 1, r = 1$ : $p$ ma wartość 1, więc $\neg1 = 0$ . Negacja odwraca wartość: z 1 robi 0, a z 0 robi 1.
Wiersz $p = 1, q = 1, r = 1$ : $p$ ma wartość 1, a $q$ ma wartość 1, więc $1 \lor 1 = 1$ . $\lor$ daje 0 tylko wtedy, gdy obie strony są równe 0.
Wiersz $p = 1, q = 1, r = 1$ : $\neg p$ ma wartość 0, a $r$ ma wartość 1, więc $0 \Rightarrow 1 = 1$ . $\Rightarrow$ daje 0 tylko w jednym przypadku: $1 \Rightarrow 0$ .

Odpowiedź

W których wierszach oba zdania ( $p \lor q$ oraz $\neg p \Rightarrow r$ ) mają wartość 1?

Kwantyfikatory: przeczytaj i oceń

Ćwiczenia · 9 zadań

Jak przeczytać $\exists_{x \in N} \forall_{y \in N} x \leq y$ ?
Czy zdanie $\exists_{x \in N} \forall_{y \in N} x \leq y$ jest prawdziwe?
Czy zdanie $\forall_{x \in R} x^{2} > 0$ jest prawdziwe?
Czy zdanie $\exists_{x \in R} x^{2} = 9$ jest prawdziwe?
Czy zdanie $\forall_{x \in R} \exists_{y \in R} x + y = 5$ jest prawdziwe?
Czy zdanie $\exists_{y \in R} \forall_{x \in R} x + y = 5$ jest prawdziwe?
Czy zdanie $\exists_{a \in R} \forall_{x \in R} a \cdot x = 0$ jest prawdziwe?
Czy zdanie $\forall_{x \in R} \exists_{y \in R} x \cdot y = 1$ jest prawdziwe?
Czy zdanie $\exists_{a \in R} \forall_{x \in R} a \cdot x = x$ jest prawdziwe?

Zaneguj zdanie

Ćwiczenia · 9 zadań

Zaprzeczenie zdania $\forall_{x \in R} x^{2} \geq 0$ to:
Zaprzeczenie zdania $\exists_{x \in N} x + 3 = 7$ to:
Zaprzeczenie zdania $\forall_{x \in R} \exists_{y \in R} y > x$ to:
Zaprzeczenie zdania $\exists_{x \in R} \forall_{y \in R} x \cdot y = 0$ to:
Zaprzeczenie zdania $\exists_{x \in R} (x > 2 \land x < 5)$ to:
Zaprzeczenie zdania $\forall_{x \in R} (x < 0 \lor x \geq 1)$ to:
Zaprzeczeniem zdania „Istnieje student, który zdał wszystkie kolokwia” jest:
Zaprzeczenie zdania $\exists_{m \in N} \forall_{x \in R} m \cdot x = 0$ to:
Zaprzeczenie zdania $\forall_{x \in R} (x > 3 \Rightarrow x^{2} > 9)$ to:

Quiz z teorii

Quiz · 10 pytań

Logika — 10 pytań

Które z tych wyrażeń jest zdaniem logicznym?
Jak przeczytać $p \land q$ ?
$p = 1$ , $q = 1$ . Ile wynosi $p \lor q$ ?
Kiedy implikacja $p \Rightarrow q$ jest fałszywa?
Ile wierszy ma tabela zero-jedynkowa dla zdania $(p \Rightarrow q) \land (q \lor \neg p) \Rightarrow r$ ?
Jak wypełnia się kolumnę $p$ w tabeli dla trzech literek $p$ , $q$ , $r$ ?
Co jest zaprzeczeniem zdania $p \land q$ ?
Zdanie jest tautologią, gdy…
Zaprzeczeniem zdania „Każdy student zdał” jest:
Czym różni się $\forall_{x} \exists_{y}$ od $\exists_{y} \forall_{x}$ ?

$p$	$q$	$r$	$p \lor q$ 1	$p \land r$ 2	$(p \lor q) \land (p \land r)$ 3	$p \land q \land r$ 4	$\dots \Rightarrow p \land q \land r$ 5
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	1	0	0	0	1
0	1	1	1	0	0	0	1
1	0	0	1	0	0	0	1
1	0	1	1	1	1	0	0
1	1	0	1	0	0	0	1
1	1	1	1	1	1	1	1

$p$	$q$	$r$	$p \lor q$ 1	$p \land r$ 2	$(p \lor q) \land (p \land r)$ 3	$p \land q \land r$ 4	$\dots \Rightarrow p \land q \land r$ 5
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	1	0	0	0	1
0	1	1	1	0	0	0	1
1	0	0	1	0	0	0	1
1	0	1	1	1	1	0	0
1	1	0	1	0	0	0	1
1	1	1	1	1	1	1	1

$p$	$q$	$r$	$p \lor q$ 1	$p \land r$ 2	$(p \lor q) \land (p \land r)$ 3	$p \land q \land r$ 4	$\dots \Rightarrow p \land q \land r$ 5
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	1	0	0	0	1
0	1	1	1	0	0	0	1
1	0	0	1	0	0	0	1
1	0	1	1	1	1	0	0
1	1	0	1	0	0	0	1
1	1	1	1	1	1	1	1