4. Logika, zbiory i relacje#
4.1. Zadania na zajęcia#
Ćwiczenie 4.6
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.
Ćwiczenie 4.7
Sprawdzić, które z podanych formuł są tautologiami.
\((p\vee \sim q )\wedge (\sim p \vee q)\wedge (p\vee q)\wedge (\sim p\vee \sim q)\)
\([(p\Rightarrow q)\Rightarrow r]\Rightarrow [(p\Rightarrow r)\Rightarrow (q\Rightarrow r)]\)
Ćwiczenie 4.8
Obliczyć \(\{\mathbb{N},0\}\cap\mathbb{N} .\)
Ćwiczenie 4.9
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 .\)
4.2. Zadania dodatkowe#
Ćwiczenie 4.10
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ą.
Ćwiczenie 4.11
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 .\)
Ćwiczenie 4.12
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.
Ćwiczenie 4.13
Podać przykład zbioru dwuelementowego takiego, że każdy jego element jest również jego podzbiorem.
Ćwiczenie 4.14
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\)
Ćwiczenie 4.15
Pokazać, że podane relacje są relacjami równoważności.
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} .\)
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.
Ćwiczenie 4.16
Narysować diagram Hassego poniższych zbiorów częściowo-uporządkowanych. Wskazać, o ile istnieją, elementy minimalne, maksymalne, najmniejsze, największe.
\((\{p\in \mathbb{N}^+: p|96 \},\preceq) \), gdzie \(a\preceq b\;\Leftrightarrow \; \exists c\in \mathbb{N}^+\quad b=ac\),
\((\{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 .\)
Ćwiczenie 4.17
W częściowo uporządkowanym zbiorze \((\mathbb{N},\mid)\) znaleźć dla zbioru \(X=\{6,8,12\}\subseteq\mathbb{N}\): \(X^*\) oraz \(X_* .\)
Ćwiczenie 4.18
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)\):
Informacja
Materiały na tej stronie przygotowała Agata Pilitowska.
Projekt „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.
Zadanie 7 pn. „Pilotażowa realizacja innowacyjnej ścieżki kształcenia obejmującej znaczny komponent zespołowych zajęć projektowych we wczesnej fazie studiów” realizowane w ramach projektu „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.
