Mathematical Logic and Set Theory: Problems with Solutions

Solution:
The implication [tex]p\Rightarrow q[/tex] is false only when [tex]p[/tex] is true and [tex]q[/tex] is false.
The contrapositive [tex]\neg q\Rightarrow\neg p[/tex] (“the streets are not wet, therefore it is not raining”) is false only when [tex]\neg q[/tex] is true and [tex]\neg p[/tex] is false, i.e. again only when [tex]p[/tex] is true and [tex]q[/tex] is false. Hence it is equivalent to the given implication and is certainly true:
[tex](\neg q\Rightarrow\neg p)\Leftrightarrow(p\Rightarrow q)[/tex]
The converse [tex]q\Rightarrow p[/tex] and the inverse [tex]\neg p\Rightarrow\neg q[/tex] do not follow: if [tex]p[/tex] is false and [tex]q[/tex] is true (the streets are wet for another reason, e.g. they were washed), then [tex]p\Rightarrow q[/tex] is true, but both [tex]q\Rightarrow p[/tex] and [tex]\neg p\Rightarrow\neg q[/tex] are false.
The statement [tex]\neg q\land p[/tex] is exactly the negation of [tex]p\Rightarrow q[/tex], so it is false:
[tex]\neg(p\Rightarrow q)\Leftrightarrow p\land\neg q[/tex]
The answer is [tex]\neg q\Rightarrow\neg p[/tex].

Solution:
Let [tex]p[/tex] be the statement “Petar is at school” and [tex]k[/tex] the statement “Kiril is at school”. By the teacher's answers [tex]p[/tex] is true and [tex]k[/tex] is false; we write [tex]p=1[/tex], [tex]k=0[/tex] ([tex]1[/tex] for true, [tex]0[/tex] for false). We translate every comment into a formula and evaluate it:
[tex](1)\quad p\land k=1\land 0=0[/tex]
[tex](2)\quad p\lor k=1\lor 0=1[/tex]
[tex](3)\quad p\Rightarrow k=1\Rightarrow 0=0[/tex]
[tex](4)\quad p\Leftrightarrow k=1\Leftrightarrow 0=0[/tex]
[tex](5)\quad \neg(\neg p)=p=1[/tex]
[tex](6)\quad \neg p\Rightarrow\neg k=0\Rightarrow 1=1[/tex]
[tex](7)\quad \neg p\Leftrightarrow\neg k=0\Leftrightarrow 1=0[/tex]
By De Morgan's laws [tex]\neg(\neg p\land\neg k)=p\lor k[/tex] and [tex]\neg(\neg p\lor\neg k)=p\land k[/tex], hence
[tex](8)\quad \neg(\neg p\land\neg k)=p\lor k=1[/tex]
[tex](9)\quad \neg(\neg p\lor\neg k)=p\land k=0[/tex]
Since [tex]\neg k=1[/tex]:
[tex](10)\quad \neg(p\Rightarrow\neg k)=\neg(1\Rightarrow 1)=\neg 1=0[/tex]
[tex](11)\quad \neg(p\Leftrightarrow\neg k)=\neg(1\Leftrightarrow 1)=\neg 1=0[/tex]
The true comments are [tex](2)[/tex], [tex](5)[/tex], [tex](6)[/tex] and [tex](8)[/tex], so exactly [tex]4[/tex] of the statements are true.

Solution:
A real number [tex]x[/tex] belongs to [tex]\bigcap\mathcal{A}[/tex] if and only if [tex]x\in\left(-a , a\right)[/tex] for every [tex]a\gt 0[/tex], i.e.
[tex]x\in\bigcap\mathcal{A}\iff \forall a\gt 0:\ |x|\lt a[/tex]
For [tex]x=0[/tex] we have [tex]|0|=0\lt a[/tex] for every [tex]a\gt 0[/tex], so [tex]0[/tex] belongs to every interval of the family.
If [tex]x\ne 0[/tex], take [tex]a=|x|\gt 0[/tex]; then [tex]|x|\lt a[/tex] fails, i.e. [tex]x\notin\left(-|x| , |x|\right)[/tex], hence [tex]x\notin\bigcap\mathcal{A}[/tex]. Therefore
[tex]\bigcap\mathcal{A}=\{0\}[/tex]
Note that the intersection is not empty, although the intervals become arbitrarily short (for comparison, the union of the family is [tex]\mathbb{R}[/tex]).

Solution:
In the first set, for integers [tex]x^2+y^2\le 1[/tex] forces [tex]|x|\le 1[/tex] and [tex]|y|\le 1[/tex], and [tex]x[/tex], [tex]y[/tex] cannot both be non-zero (then [tex]x^2+y^2=2\gt 1[/tex]). Hence
[tex]\{(x, y)\in\mathbb{Z}^2 : x^2+y^2\le 1\}=\{(0, 0),\ (1, 0),\ (-1, 0),\ (0, 1),\ (0, -1)\}[/tex]
In the second set [tex]x^2-y^2=(x-y)(x+y)=1[/tex]. Both factors are integers, so they are both equal to [tex]1[/tex] or both equal to [tex]-1[/tex]:
[tex]x-y=x+y=\pm 1\ \Rightarrow\ y=0,\ x=\pm 1[/tex]
These are the points [tex](1, 0)[/tex] and [tex](-1, 0)[/tex], which already belong to the first set. Therefore [tex]B[/tex] consists of the [tex]5[/tex] points listed above:
[tex]|B|=5[/tex]

Solution:
Factor the elements of [tex]A[/tex]:
[tex]9=3^2, \ 10=2\times 5, \ 11, \ 12=2^2\times 3, \ 13, \ 14=2\times 7, \ 15=3\times 5, \ 16=2^4[/tex]
Hence
[tex]f(9)=3, \ f(10)=10, \ f(11)=11, \ f(12)=6, \ f(13)=13, \ f(14)=14, \ f(15)=15, \ f(16)=2[/tex]
These [tex]8[/tex] values are pairwise different, so different arguments have different images and [tex]f[/tex] is injective.
The image [tex]f(A)=\{2, 3, 6, 10, 11, 13, 14, 15\}[/tex] is finite, while [tex]\mathbb{N}[/tex] is infinite; for example, [tex]1[/tex] and [tex]4[/tex] have no preimage. So [tex]f[/tex] is not surjective (and therefore not bijective).
The function is injective, but not surjective.

Solution:
By distributivity, the complement law [tex]\neg B\land B=0[/tex] and the identity law [tex]X\lor 0=X[/tex]:
[tex]\neg B\land(\neg C\lor B)=(\neg B\land\neg C)\lor(\neg B\land B)=(\neg B\land\neg C)\lor 0=\neg B\land\neg C[/tex]
Next, by commutativity, associativity and the absorption law [tex]\neg C\land(\neg C\lor A)=\neg C[/tex]:
[tex]\neg B\land(\neg C\lor A)\land(\neg C\lor B)=(\neg B\land\neg C)\land(\neg C\lor A)=\neg B\land\bigl(\neg C\land(\neg C\lor A)\bigr)=\neg B\land\neg C[/tex]
Therefore [tex]Y=(\neg B\land\neg C)\lor C[/tex]. By the distributivity of [tex]\lor[/tex] over [tex]\land[/tex], the complement law [tex]\neg C\lor C=1[/tex] and the identity law [tex]X\land 1=X[/tex]:
[tex]Y=(\neg B\lor C)\land(\neg C\lor C)=(\neg B\lor C)\land 1=\neg B\lor C[/tex]
Check with the truth table: [tex]Y=0[/tex] exactly when [tex]B=1[/tex] and [tex]C=0[/tex] (for any [tex]A[/tex]), which is exactly when [tex]\neg B\lor C=0[/tex].