---
title: "Logika, zbiory i relacje"
lecture_number: 3
has_solutions: false
has_exercises: true
---

```{include} ../_includes/sagecell-loader.md
```

# Logika, zbiory i relacje

## Zadania na zajęcia

::::{exercise}
:class: [exercise]

Dla jakich wartości logicznych zdań $p, q$ i $r$ formuła
$\left[(p\Rightarrow q)\Rightarrow(r\Rightarrow \sim p)\right]\Rightarrow(\sim q\Rightarrow \sim r)$
jest prawdziwa? Zapisać podaną formułę w postaci alternatywno-koniunkcyjnej.

::::

::::{exercise}
:class: [exercise]

Sprawdzić, które z podanych formuł są tautologiami.

1. $(p\vee \sim q )\wedge (\sim p \vee q)\wedge (p\vee q)\wedge (\sim p\vee \sim q)$
2. $[(p\Rightarrow q)\Rightarrow r]\Rightarrow [(p\Rightarrow r)\Rightarrow (q\Rightarrow r)]$

::::

::::{exercise}
:class: [exercise]

Obliczyć $\{\mathbb{N},0\}\cap\mathbb{N} .$

::::

::::{exercise}
:class: [exercise]

Niech
$A=\{\{X\},\emptyset\}$ i $B=\{\emptyset,\{\{\emptyset\},\{\{\emptyset\}\}\},\{\emptyset,\{\{\emptyset\}\}\},\{\emptyset\}\} .$
Dobierz zbiór $X$, tak by $A\in B .$
Analogicznie, -- by $A\subseteq B .$

::::

## Zadania dodatkowe

::::{exercise}
:class: [exercise]

Pokazać, że jeśli formuła $\alpha \Rightarrow \sim\beta$
jest tautologią, to dla każdej $\gamma$, formuła
$(\alpha\wedge\beta)\Rightarrow\gamma$ też jest tautologią.

::::

::::{exercise}
:class: [exercise]

Pokazać, że jeśli prawdziwe są: wynikania $p_1\Rightarrow
q_1, \dots,p_n\Rightarrow q_n$ oraz zdania $(p_1\vee\dots \vee
p_n)$ i $\sim(q_i\wedge q_j)$ dla $i\neq j$, to prawdziwe są również
wynikania $q_1\Rightarrow p_1,\dots,q_n\Rightarrow p_n .$

::::

::::{exercise}
:class: [exercise]

Pan A w jednym przemówieniu stwierdził, że jeśli podniesie podatki, stopa inflacji spadnie wtedy i tylko wtedy, gdy nie spadnie wartość euro. Z kolei w programie TV oznajmił, że jeśli zmniejszy się stopa inflacji lub wartość euro spadnie, to podatki nie zostaną podniesione. W innym natomiast wystąpieniu przekonywał, że albo należy podnieść podatki, albo euro spadnie i stopa inflacji się zmniejszy. Wywnioskował z tego, że podatki wzrosną, ale stopa inflacji zmniejszy się, a wartość euro nie spadnie. Ustalić, czy rozumowanie pana A jest niesprzeczne.

::::

::::{exercise}
:class: [exercise]

Podać przykład zbioru dwuelementowego takiego, że każdy jego
element jest również jego podzbiorem.

::::

::::{exercise}
:class: [exercise]

Sprawdzić czy podane równości są prawdziwe. Prawdziwe uzasadnić, dla
fałszywych podać kontrprzykład.

- $A\setminus [(B\setminus C)\cup(C\setminus B)]=A\cap (B\cup -C)\cap (C\cup -B)$
- $(A\setminus C)\cup (B\cap C)=(A\cup C)\cap (B\cup A)$
- $A\times (B\cup C)=(A\times B)\cup (A\times C)$
- $2^{X\cap Y}=2^X\cap 2^Y$
- $2^{X\cup Y}=2^X\cup 2^Y$

::::

::::{exercise}
:class: [exercise]

Pokazać, że podane relacje są relacjami równoważności.

1. Dla $x,y\in {\mathbb{R}}$, $x\sim y \Leftrightarrow (\exists a,b\in \mathbb{Q})\; x-y=a+b\sqrt{2} .$ Podać klasę równoważności $[0]_{\sim} .$
2. Dla $f,g\in  \mathbb{R} [x]=\{a_0+a_1x+\ldots+a_nx^n\mid a_i\in\mathbb{R}, n\in\mathbb{N}\}$,
   $f\sim g\Leftrightarrow  \;x|(f(x)-g(x)) .$ Podać klasy abstrakcji tej relacji.

::::

::::{exercise}
:class: [exercise]

Narysować diagram Hassego poniższych zbiorów częściowo-uporządkowanych.
Wskazać, o ile istnieją, elementy minimalne, maksymalne,
najmniejsze, największe.

1. $(\{p\in \mathbb{N}^+: p|96 \},\preceq) $, gdzie $a\preceq b\;\Leftrightarrow \; \exists c\in \mathbb{N}^+\quad b=ac$,
2. $(\{a,b,c\}\times \{x,y,z\}, \preceq)$, gdzie $(s,t)\preceq(u,w)\Leftrightarrow s\leq_Pu \wedge t\leq _Qw$,
   przy założeniu, że $a\leq_P b\geq_Pc$ oraz $x\geq_Qy\leq_Qz .$

::::

::::{exercise}
:class: [exercise]

W częściowo uporządkowanym zbiorze $(\mathbb{N},\mid)$ znaleźć dla zbioru $X=\{6,8,12\}\subseteq\mathbb{N}$:
$X^*$ oraz $X_* .$

::::

::::{exercise}
:class: [exercise]

Nich $(P,\preceq)$ będzie zbiorem częściowo uporządkowanym. Element $a\in P$ jest *kresem górnym* zbioru $X$, jeśli jest elementem najmniejszym w zbiorze $(X^*,\preceq)$ górnych ograniczeń $X .$ Kres górny zbioru $X$ oznaczamy $supX .$
Element $a\in P$ nazywamy *kresem dolnym* zbioru $X$, jeśli jest elementem największym w zbiorze $(X_*,\preceq)$ dolnych ograniczeń $X .$ Kres dolny zbioru $X$ oznaczamy $infX .$
Znaleźć  $\sup (x,y)$ i $\inf (x,y)$ (o ile istnieją) dla każdej pary $x,y\in P$ w zbiorze częściowo-uporządkowanym $(P,\preceq)$:

::::

```{include} ../_includes/titlepage-info.md
```