how to prove it - ch3, sec3.1(Proof Strategies) ex

In this section, we learn how to prove statements of the type $P\to Q$.

Strategy#1 Suppose P is true and from it derive that Q is also true.

Strategy#2 Prove the contrapositive. We know that $P\to Q$ $\equiv$ $\neg Q\to \neg P$

In the course of figuring out a proof, we have "givens" which are the statements that are facts or hypothesis or assumptions and "goal" that needs to be proven. We start with some givens and goal, apply a proof strategy and get different givens and goal. In other words, application of a proof strategy transforms a problem into another problem which is(hopefully) easier to solve.

We usually do "hit and trial" to figure out which strategy actually works and with practice it might start coming from gut feeling also.

For example the proof of $P\to Q$ with strategy#2 can be thought as follows...

Scratch work:

Before using any strategy -

givens: -
goal: $P\to Q$

After applying strategy#2

givens: -
goal: $\neg Q\to \neg P$

After applying strategy#1

givens: $\neg Q$
goal: $\neg P$

and the formal proof(after we've thought through the strategy will look like following)..

We're proving the contrapositive.
Suppose Q is false.
[Proof of $\neg P$ goes here]
Therefore $P\to Q$

Notice that, it is usual to use a lot of logical notations in the scratch work to figure out the proof, but the final write up of the proof should be in plain english and simple to understand as much possible.

=======================================================================================

Ex-1
(a)
Hypotheses:
n is an integer larger than 1
n is not prime

Conclusion: $2^n-1$ is not prime

For n = 6, hypotheses are true as 6 is larger than 1 and also not a prime. Theorem tells us that $2^6-1$ should not be a prime, which is true as $2^6-1$ = 63 is not a prime.

(b) 15 is not prime, so hypotheses are true.
$2^{15}-1$ = 32767( = 7 * 4681) is not a prime so conclusion is also correct.

(c) 11 is prime, so hypotheses are false. So, theorem does not tell anything.


Ex-2
(a)
Hypotheses: $b^2>4ac$
Conclusion: $a{x}^2+bx+c=0$ has exactly two real solutions

(b) Because a,b and c are free variables while x is not. Fixing the values of a,b and c fixes the True/False value of the statement.

(c)
$(-5{)}^2-4(2\left)\right(3)$ = 26 > 0, so hypothesis is true and as per the theorem $2x^2-5x+3=0$ should have two real solutions, which is true. 1 and 3/2 are two solutions.

(d)
$4^2-4\left(2\right)\left(3\right)$ = -8, -8 < 0 so hypothesis is false. So theorem does not tell anything.


Ex-3
Hypotheses:
n is a natural number
n > 2
n is not prime

Conclusion:
2n+13 is not prime

The instance for n = 8 is a counterexample. As 8 is a natural number, greater than 2 and not prime; so hypotheses are true. But 2(8)+13 = 29 is a prime, so conclusion is false.


Ex-4
Suppose 0 < a < b. Then b-a > 0.
b+a > 0 because both b and a are greater than 0
so (b-a)(b+a) > 0
=> $b^2-a^2$ > 0
Since $b^2-a^2$ > 0, it follows . Therefore if 0 < a < b then .


Ex-5
Suppose a < b < 0, Then a-b < 0
a+b < 0 because both b and a are less than 0
so (a-b)(a+b) > 0 (multiplication of two negative real numbers is a positive real number)
=> $a^2-b^2$ > 0
Since $a^2-b^2$ > 0, it follows $a^2>b^2$. Therefore if a < b < 0 then $a^2>b^2$.


Ex-6
Suppose 0 < a < b, Then a < b
On dividing both sides by ab we get

It follows,
Therefore if 0 < a < b, then

Ex-7 Suppose a is a real number and $a^3>a$
So $a^3-a$ > 0 ....... (i)
$a^2$ > 0 as a is real,
so $a^2+1$ > 0 ........(ii)

on multiplying eq (i) and (ii) we get
$(a^3-a)(a^2+1)$ > 0
=> $a^5-a$ > 0

It follows that $a^5>a$, So if a is a real number and $a^3>a$, then $a^5>a$.


Ex-8 We will prove the contrapositive, If $x\notin B$ then $x\in D$.
Given that, $A\backslash B\subseteq C\cap D$
it means $\forall y[y\in (A\backslash B)\to y\in (C\cap D\left)\right]$
So, $\forall y\left[\right(y\in A\wedge y\notin B)\to (y\in C\wedge y\in D\left)\right]$

Now it must be true for y = x also, so
$(x\in A\wedge x\notin B)\to (x\in C\wedge x\in D)$ is true.

It is given that $x\in A$ and suppose $x\notin B$
=> $x\in C\wedge x\in D$
It follows that $x\in D$

So If $x\notin B$ then $x\in D$. And hence, If $x\notin D$ then $x\in B$


Ex-9 We will prove the contrapositive, If $\frac{a+b}{2}>b$ then $a>b$

Suppose $\frac{a+b}{2}>b$

on multiplying both sides by 2, we get
$a+b>2b$

on subtracting b from both sides we get
$a>b$

So, If $\frac{a+b}{2}>b$ then $a>b$

And hence, If then


Ex-10 We will prove the contrapositive, If x = 8 then $\frac{x^{1/3}+5}{x^2+6}\ne \frac{1}{x}$

Suppose x = 8, Then $\frac{x^{1/3}+5}{x^2+6}$
= $\frac{8^{1/3}+5}{8^2+6}$
= $\frac{2+5}{64+6}$
= $\frac{7}{70}$
= $\frac{1}{10}$ $\ne$ $\frac{1}{8}$

And hence, If $\frac{x^{1/3}+5}{x^2+6}$ = $\frac{1}{x}$ then $x\ne 8$


Ex-11 We'll prove the contrapositive. If $c\le d$ then .

Suppose $c\le d$

on multiplying it with $a$ (given that $a>o$)
$ac\le ad$ ............. (i)

also given that

on multiplying it with $d$ (given that $d>0$)
........... (ii)

From eq (i) and (ii)


It follows,

And hence, If $ac\ge bd$ then $c>d$


Ex-12
It is given that $3x+2y\le 5$
=> $x\le \frac{5-2y}{3}$

Suppose $x>1$, then

=>
=>
=>
=>

Thus, If $x>1$ then


Ex-13
Suppose $x^2+y=-3$ ....... (i)
$2x-y=2$ .......(ii)

From eq (i)
$y=-3-x^2$

substituting the value of y in eq (ii)
$2x-(-3-x^2)=2$
=> $2x+3+x^2=2$
=> $x^2+2x+1=0$
=> $(x+1{)}^2=0$
=> $x+1=0$
=> $x=-1$

So, If $x^2+y=-3$ and $2x-y=2$ then $x=-1$


Ex-14 Prove that, If x > 3 and y < 2 then $x^2-2y>5$.

Suppose x < 3 and y < 2

Since 0 < 3 < x, so from the theorem proven in Ex-4, it follows that

=> $x^2>9$ ...... (i)

On multiplying -2 with both sides of y < 2
-2y > -4 ..... (ii)(sign changes because we're multiplying by a negative number)

Adding eq (i) and (ii)
$x^2-2y>9-4$
=> $x^2-2y>5$

Thus, If x > 3 and y < 2 then $x^2-2y>5$


Ex-15
(a) We've proven that
$(x=7)\to \frac{2x-5}{x-4}=3$
and NOT
$\frac{2x-5}{x-4}=3\to (x=7)$

and $(A\to B)$ is not logically equivalent to $(B\to A)$

(b) Suppose $\frac{2x-5}{x-4}=3$
on multiplying both sides with (x - 4), which is $\ne 0$, we get
2x - 5 = 3(x - 4)
=> 2x - 5 = 3x - 12
=> 2x - 3x = -12 + 5
=> -x = -7
=> x = 7

Thus, If $\frac{2x-5}{x-4}=3$ then x = 7


Ex-16
(a) The flaw is in, Since $x\ne 3$ so $x^2\ne 9$. This is not true, as $x^2=9$ for x = -3

(b) One counterexample is, x = -3 and y = 1 as $(-3{)}^2(1)=9(1)$

how to prove it - ch2, sec2.3(More On Sets) ex

So far we've learnt 3 ways to represent sets.
- By listing all elements e.g. {1,2,3,4} represents a set that contains 1,2,3 and 4
- By using ellipsis, e.g. {1,2,3,4,...} represents set of all positive integers
- By using elementhood test as in {x | P(x)}, e.g. {x | $x^2=9$} represents set {-3,3}. And if we want to be more precise and S is the universe of discourse then we say {$x\in S\mid P\left(x\right)$}

This section introduces another way called "index set" or "index family" which is to write
{$x_i\mid i\in I$} where $x_i$ is some function of i.
For example {$n^2\mid n\in N$} represents set of square of all natural numbers.
Note that set of square of all natural numbers can also be represented by

{$x\mid \exists i\in N(i^2=x)$}

This means ($x\in \{n^2\mid n\in N\}$) $\equiv$ ($\exists n\in N(x=n^2)$)

In general, ($x\in \{x_i\mid i\in I\}$) $\equiv$ ($\exists i\in I(x=x_i)$)

Family Of Set A set, all of whose elements are sets.
For example, Power Set of a set S is the set of all the subsets of S, i.e. {A | A $\subseteq$ S}.
So an element x belonging to power set of S means $x\subseteq S$

Intersection of all the sets in a family of set F is denoted by $\cap F$ = {$x\mid \forall A\in F(x\in A)$}

Union of all the sets in a family of set F is denoted by $\cup F$ = {$x\mid \exists A\in F(x\in A)$}

Alternatively
A family F of sets $A_i$ can be convenienty defined as {$A_i\mid i\in I$}.

There exists, additional notations for intersection/union of family based on above definition.

$\cap F$ = ${\cap }_{i\in I}{A}_i$ = {$x\mid \forall i\in I(x\in A_i)$}

and

$\cup F$ = ${\cup }_{i\in I}{A}_i$ = {$x\mid \exists i\in I(x\in A_i)$}




======================================================================================
$P\left(A\right)$ in all of these exercises represents Power Set of A and $F$ represents famility of set.

Ex-1(a) $F\subseteq P\left(A\right)$
= $\forall x(x\in F\to x\in P(A\left)\right)$
= $\forall x(x\in F\to x\subseteq A)$
= $\forall x[x\in F\to (\forall y(y\in x\to y\in A)\left)\right]$

Ex-1(b) $A\subseteq \{2n+1\mid n\in N\}$
= $\forall x[x\in A\to x\in \{2n+1\mid n\in N\left\}\right]$
= $\forall x[x\in A\to \exists n\in N(2n+1=x\left)\right]$

Ex-1(c) $\{n^2+n+1\mid n\in N\}\subseteq \{2n+1\mid n\in N\}$
= $\forall x[x\in \{n^2+n+1\mid n\in N\}\to x\in \{2n+1\mid n\in N\}$
= $\forall x[\exists n\in N(n^2+n+1=x)\to \exists n\in N(2n+1=x\left)\right]$

Ex-1(d) $\neg \left[P\right({\cup }_{i\in I}{A}_i)\subseteq {\cup }_{i\in I}P(A_i\left)\right]$
= $\neg [\forall x(x\in P\left({\cup }_{i\in I}{A}_i\right)\to x\in {\cup }_{i\in I}P\left(A_i\right)]$
= $\exists x\neg \left[\right(x\in P\left({\cup }_{i\in I}{A}_i\right)\to x\in {\cup }_{i\in I}P\left(A_i\right)]$
= $\exists x\neg [x\notin P({\cup }_{i\in I}{A}_i)\vee x\in {\cup }_{i\in I}P(A_i\left)\right]$
= $\exists x[x\in P({\cup }_{i\in I}{A}_i)\wedge x\notin {\cup }_{i\in I}P(A_i\left)\right]$
= $\exists x[x\subseteq ({\cup }_{i\in I}{A}_i)\wedge \neg (\exists i\in I(x\in P(A_i\left)\right)\left)\right]$
= $\exists x[\forall y(y\in x\to y\in \left({\cup }_{i\in I}{A}_i\right))\wedge \neg (\exists i\in I(x\subseteq A_i)\left)\right]$
= $\exists x[\forall y(y\in x\to \exists i\in I(y\in A_i))\wedge \forall i\in I\neg (x\subseteq A_i\left)\right]$
= $\exists x[\forall y(y\in x\to \exists i\in I(y\in A_i))\wedge \forall i\in I\exists y(y\in x\wedge y\notin A_i\left)\right]$


Ex-2(a) $x\in \cup F\backslash \cup G$
= $x\in \cup F\wedge x\notin \cup G$
= $\exists A\in F(x\in A)\wedge \neg \exists A\in G(x\in A)$
= $\exists A\in F(x\in A)\wedge \forall A\in G(x\notin A)$

Ex-2(b) $\{x\in B\mid x\notin C\}\in P\left(A\right)$
= $\{x\in B\mid x\notin C\}\subseteq A$
= $\forall y[y\in \{x\in B\mid x\notin C\}\to y\in A]$
= $\forall y[y\in B\wedge y\notin C\to y\in A]$

Ex-2(c) $x\in {\cap }_{i\in I}(A_i\cup B_i)$
= $\forall i\in I[x\in (A_i\cup B_i\left)\right]$
= $\forall i\in I[x\in A_i\vee x\in B_i]$

Ex-2(d) $x\in \left({\cap }_{i\in I}{A}_i\right)\cup \left({\cap }_{i\in I}{B}_i\right)$
= $x\in \left({\cap }_{i\in I}{A}_i\right)\vee x\in \left({\cap }_{i\in I}{B}_i\right)$
= $\forall i\in I(x\in A_i)\vee \forall i\in I(x\in B_i)$


Ex-3 $P\left(\right\{\varnothing \left\}\right)=\{\varnothing ,\{\varnothing \left\}\right\}$


Ex-4
$\cap F$ = {red, blue}
$\cup F$ = {red, green, blue, orange, purple}


Ex-5
$\cap F$ = $\varnothing$ , Mathematicians would say that $\cap F$ is undefined for this case
$\cup F$ = {3, 7, 12, 5, 16, 23}


Ex-6 I = {2, 3, 4, 5} and for each $i\in I$ $A_i$ = {i, i+1, i-1, 2i}
(a) Find all $A_i$
$A_2$ = {2, 3, 1, 4}
$A_3$ = {3, 4, 2, 6}
$A_4$ = {4, 5, 3, 8}
$A_5$ = {5, 6, 4, 10}

(b)
${\cap }_{i\in I}{A}_i$ = {4}
${\cup }_{i\in I}{A}_i$ = {1, 2, 3, 4, 5, 6, 8, 10}


Ex-7 trivial, passed


Ex-8 I = {2, 3} ; for all $i\in I$ $A_i$ = {i, 2i} and $B_i$ = {i, i+1}
(a)
$A_2$ = {2, 4}
$A_3$ = {3, 6}

$B_2$ = {2, 3}
$B_3$ = {3, 4}

(b)
Find ${\cap }_{i\in I}(A_i\cup B_i)$

$(A_2\cup B_2)$ = {2, 3, 4}
$(A_3\cup B_3)$ = {3, 4, 6}

${\cap }_{i\in I}(A_i\cup B_i)$ = {3, 4}


Find, $\left({\cap }_{i\in I}{A}_i\right)\cup \left({\cap }_{i\in I}{B}_i\right)$
= {} $\cup$ {3}
= {3}

(c) They are not equivalent.


Ex-9 I = {1,2}; $A_i$ = {i, 2i}; $B_i$ = {3i, 4i}

$A_1$ = {1,2}
$A_2$ = {2,4}

$B_1$ = {3,4}
$B_2$ = {6,8}

$A_1\cap B_1$ = { }
$A_2\cap B_2$ = { }
So, ${\cup }_{i\in I}(A_i\cap B_i)$ = { } .............result-a

${\cup }_{i\in I}{A}_i$ = {1,2,4}
${\cup }_{i\in I}{B}_i$ = {3,4,6,8}
So,
$\left({\cup }_{i\in I}{A}_i\right)\cap \left({\cup }_{i\in I}{B}_i\right)$ = {4} ............result-b

clearly result-a and result-b are not same.


Ex-10 $x\in P(A\cap B)$
= $x\subseteq (A\cap B)$
= $\forall y[y\in x\to y\in (A\cap B\left)\right]$
= $\forall y[y\in x\to (y\in A\wedge y\in B\left)\right]$
= $\forall y[y\notin x\vee (y\in A\wedge y\in B\left)\right]$
= $\forall y\left[\right(y\notin x\vee y\in A)\wedge (y\notin x\vee y\in B\left)\right]$
= $\forall y\left[\right(y\in x\to y\in A)\wedge (y\in x\to y\in B\left)\right]$
= $[\forall y(y\in x\to y\in A\left)\right]\wedge [\forall y(y\in x\to y\in A\left)\right]$
= $(x\subseteq A)\wedge (x\subseteq B)$
= $x\in P\left(A\right)\wedge x\in P\left(B\right)$


Ex-11 A = {1} and B = {2}
$P(A\cup B)$
= $P\left(\right\{1,2\left\}\right)$
= {$\varnothing$, {1}, {2}, {1,2}}

$P\left(A\right)\cup P\left(B\right)$
= $P\left(\right\{1\left\}\right)\cup P\left(\right\{2\left\}\right)$
= {$\varnothing$, {1}} $\cup$ {$\varnothing$, {2}}
= {$\varnothing$, {1}, {2}}

clearly the two are not equal.


Ex-12(a) LHS
= $x\in {\cup }_{i\in I}(A_i\cup B_i)$
= $\exists i\in I[x\in (A_i\cup B_i\left)\right]$
= $\exists i\in I[x\in A_i\vee x\in B_i]$
= $\exists i\in I(x\in A_i)\vee \exists i\in I(x\in B_i)$
= $(x\in {\cup }_{i\in I}{A}_i)\vee (x\in {\cup }_{i\in I}{B}_i)$
= $x\in \left[\right({\cup }_{i\in I}{A}_i)\cup ({\cup }_{i\in I}{B}_i\left)\right]$
= RHS

Ex-12(b) LHS
$x\in (\cap F)\cap (\cap G)$
= $x\in (\cap F)\wedge x\in (\cap G)$
= $[\forall A\in F(x\in A\left)\right]\wedge [\forall A\in G(x\in A\left)\right]$

RHS
$x\in \cap (F\cup G)$
= $\forall A\in (F\cup G)(x\in A)$
= $\forall A[A\in (F\cup G)\to (x\in A\left)\right]$
= $\forall A\left[\right(A\in F)\vee (A\in G)\to (x\in A\left)\right]$
= $\forall A[\neg ((A\in F)\vee (A\in G))\vee (x\in A\left)\right]$
= $\forall A\left[\right((A\notin F)\wedge (A\notin G))\vee (x\in A\left)\right]$
= $\forall A\left[\right((A\notin F)\vee (x\in A))\wedge ((A\notin G)\vee (x\in A)\left)\right]$
= $\forall A\left[\right(A\in F\to x\in A)\wedge (A\in G\to x\in A\left)\right]$
= $[\forall A\in F(x\in A\left)\right]\wedge [\forall A\in G(x\in A\left)\right]$

clearly both sides are equal

Ex-12(c) LHS
= $x\in {\cap }_{i\in I}(A_i\backslash B_i)$
= $\forall i\in I(x\in A_i\backslash B_i)$
= $\forall i\in I(x\in A_i\wedge x\notin B_i)$
= $[\forall i\in I(x\in A_i\left)\right)]\wedge [\forall i\in I(x\notin B_i)\left)\right]$
= $(x\in {\cap }_{i\in I}{A}_i)\wedge [\forall i\in I\neg (x\in B_i\left)\right]$
= $(x\in {\cap }_{i\in I}{A}_i)\wedge \neg [\exists i\in I(x\in B_i\left)\right]$
= $(x\in {\cap }_{i\in I}{A}_i)\wedge \neg (x\in {\cap }_{i\in I}{B}_i)$
= $x\in \left({\cap }_{i\in I}{A}_i\right)\backslash \left({\cap }_{i\in I}{B}_i\right)$
= RHS


Ex-13

(a)
$B_3=A_{1,3}\cup A_{2,3}$
$B_3=\{1,3,4\}\cup \{2,3,5\}$
$B_3=\{1,2,3,4,5\}$

$B_4=A_{1,4}\cup A_{2,4}$
$B_4=\{1,4,5\}\cup \{2,4,6\}$
$B_4=\{1,2,4,5,6\}$

(b) ${\cap }_{j\in J}{B}_j$
= $B_3\cap B_4$
= $\{1,2,3,4,5\}\cap \{1,2,4,5,6\}$
= $\{1,2,4,5\}$

(c) Let $C_i$ = ${\cap }_{j\in J}{A}_{i,j}$ = $A_{i,3}\cap A_{i,4}$

$C_1=$A_{1,3} \cap A_{1,4}$$
= $\{1,3,4\}\cap \{1,4,5\}$
= $\{1,4\}$

$C_2=$A_{2,3} \cap A_{2,4}$$
= $\{2,3,5\}\cap \{2,4,6\}$
= $\left\{2\right\}$

${\cup }_{i\in I}\left({\cap }_{j\in J}{A}_{i,j}\right)$
= ${\cup }_{i\in I}{C}_i$
= $C_1\cup C_2$
= $\{1,4\}\cup \left\{2\right\}$
= $\{1,2,4\}$

clearly ${\cap }_{j\in J}\left({\cup }_{i\in I}{A}_{i,j}\right)$ and ${\cup }_{i\in I}\left({\cap }_{j\in J}{A}_{i,j}\right)$ are not equal.

(d)
$x\in {\cap }_{j\in J}\left({\cup }_{i\in I}{A}_{i,j}\right)$
= $\forall j\in J(x\in {\cup }_{i\in I}{A}_{i,j})$
= $\forall j\in J\exists i\in I(x\in A_{i,j})$

$x\in {\cup }_{i\in I}\left({\cap }_{j\in J}{A}_{i,j}\right)$
= $\exists i\in I(x\in {\cap }_{j\in J}{A}_{i,j})$
= $\exists i\in I\forall j\in J(x\in A_{i,j})$

clearly, they are not equivalent.

Ex-14
(a) $x\in \cup F$ means
$\exists A(A\in F\wedge x\in A)$
For $F=\varnothing$, above is not possible because there is no A
and hence, for any x $x\notin \cup F$ if $F=\varnothing$
$\therefore \cup \varnothing =\varnothing$

(b)
$x\in \cap F$ means
$\forall A(A\in F\to x\in A)$
For $F=\varnothing$, above is definitely true because there is no A to check for
and hence, for any x $x\in \cap \varnothing$ is always true
$\therefore \cap \varnothing =U$, where $U$ is the universe of discourse

However, for the reasons specified in the book it is too confusing(because $U$ will be context dependant) and mathematicians consider $\cap \varnothing$ undefined.


Ex-15

(a) Let us take a look at the two possiblities..

1. R belongs to the class of sets where set is an element of itself Then R is an element of itself, BUT elements of R are the sets which are not element of themselves. So, we have a contradiction here and its not possible.

2. R belongs to the class of sets where set is not element of itself Then R is not an element of itself, BUT R is the set of ALL such sets which are not element of themselves. So, we have a contracition here and its not possible.

Hence, R can not exist.

(b) This means a set can never be an element of itself. And hence, a universe of discourse of ALL the sets is meaningless.

how to prove it - ch2, sec2.2(Equivalence Involving Quantifiers) ex

To understand various equivalences involving quantifiers, it is important to realize that

$\forall xP\left(x\right)$ = $P\left(x_1\right)\wedge P\left(x_2\right)\wedge P\left(x_3\right)....$
$\exists xP\left(x\right)$ = $P\left(x_1\right)\vee P\left(x_2\right)\vee P\left(x_3\right)....$

With above, we can easily check the Quantifier Negation Laws:

$\neg \exists xP\left(x\right)$ = $\forall x\neg P\left(x\right)$
$\neg \forall xP\left(x\right)$ = $\exists x\neg P\left(x\right)$

Ordering of quantifiers does not matter when both are of the same kind(either existential or universal) so $\exists x\exists y\left(T\right(x,y)\wedge P(x,y\left)\right)$ = $\exists y\exists x\left(T\right(x,y)\wedge P(x,y\left)\right)$
This suggests that a good way of reading the pair of quantifiers $\exists x\exists y..$ would be "there are objects x and y such that..."
and a good way of reading the pair of quantifiers $\forall x\forall y..$ would be "for all objects x and y..$$

One more important thing to realize is that when we talk about objects x and y, we are not ruling out the possibility that x and y are the same object.


Bounded Quantifiers: If set A is the universe of discourse then we can write statements like
$\forall x\in A,P\left(x\right)$, which actually means $\forall x(x\in A\to P(x\left)\right)$ and
$\exists x\in A,P\left(x\right)$, which actually means $\exists x(x\in A\wedge P(x\left)\right)$

and it should be easy to prove that $\neg \forall x\in A,P\left(x\right)$ = $\exists x\in A,\neg P\left(x\right)$ and $\neg \exists x\in A,P\left(x\right)$ = $\forall x\in A,\neg P\left(x\right)$


It is also obvious that for $A=\phi$, $\exists x\in A,P\left(x\right)$ is always False and $\forall x\in A,P\left(x\right)$ is always True. These statements are called "vacuously" true.

More equivalences:
Universal quantifier distributes over conjunction that is $\forall x\left(E\right(x)\wedge T(x\left)\right)$ = $\forall xE\left(x\right)\wedge \forall xT\left(x\right)$
Existential quantifier distributes over disjunction that is $\exists x\left(E\right(x)\vee T(x\left)\right)$ = $\exists xE\left(x\right)\vee \exists xT\left(x\right)$

Another special quantifier notation is introduced here, $\exists !xP\left(x\right)$ means There exists exactly one x such that P(x) is true.

=============================================================================
Ex-1(a) Let us first write the given statement in logical form..
$\forall x\left[M\right(x)\to \exists yF(x,y)\wedge H(y\left)\right]$

M(x) means, x is majoring in Maths
F(x,y) means, x and y are friends
H(y) means, y needs help with homework

Now Let us negate the statement.
$\neg \forall x\left[M\right(x)\to \exists yF(x,y)\wedge H(y\left)\right]$
=$\neg \forall x[\neg M(x)\vee \exists y(F(x,y)\wedge H\left(y\right)\left)\right]$
=$\exists x\neg [\neg M(x)\vee \exists y(F(x,y)\wedge H\left(y\right)\left)\right]$
=$\exists x\left[M\right(x)\wedge \neg \exists y(F(x,y)\wedge H\left(y\right)\left)\right]$
=$\exists x\left[M\right(x)\wedge \forall y\neg (F(x,y)\wedge H\left(y\right)\left)\right]$
=$\exists x\left[M\right(x)\wedge \forall y(\neg F(x,y)\vee \neg H\left(y\right)\left)\right]$
=$\exists x\left[M\right(x)\wedge \forall y(F(x,y)\to \neg H\left(y\right)\left)\right]$

The negated statement in English is, There exists someone who is majoring in Maths and all of his friends don't need help with homework.

Ex-1(b) Logical form of original statement is...
$\forall x\exists y\left[R\right(x,y)\wedge \forall z\neg L(y,z\left)\right]$

R(x,y) means, x and y are roommates
L(y,z) means, y likes z

Its negation is...

$\neg \forall x\exists y\left[R\right(x,y)\wedge \forall z\neg L(y,z\left)\right]$
=$\exists x\neg \exists y\left[R\right(x,y)\wedge \forall z\neg L(y,z\left)\right]$
=$\exists x\forall y\neg \left[R\right(x,y)\wedge \forall z\neg L(y,z\left)\right]$
=$\exists x\forall y[\neg R(x,y)\vee \neg \forall z\neg L(y,z\left)\right]$
=$\exists x\forall y[\neg R(x,y)\vee \exists zL(y,z\left)\right]$
=$\exists x\forall y\left[R\right(x,y)\to \exists zL(y,z\left)\right]$

In English, There is someone such that all of his room-mates have someone they like.

Ex-1(c) $\forall x(x\in A\cup B\to x\in C\backslash D)$
=$\forall x\left[\right(x\notin A\cup B)\vee (x\in C\backslash D\left)\right]$

Its negation is...

$\neg \forall x\left[\right(x\notin A\cup B)\vee (x\in C\backslash D\left)\right]$
=$\exists x\neg \left[\right(x\notin A\cup B)\vee (x\in C\backslash D\left)\right]$
=$\exists x\left[\right(x\in A\cup B)\wedge (x\notin C\backslash D\left)\right]$

Ex-1(d) $\neg \exists x\forall y[y>x\to \exists z(z^2+5z=y\left)\right]$
=$\forall x\neg \forall y[y>x\to \exists z(z^2+5z=y\left)\right]$
=$\forall x\exists y\neg [y>x\to \exists z(z^2+5z=y\left)\right]$
=$\forall x\exists y\neg [\neg (y>x)\vee \exists z(z^2+5z=y\left)\right]$
=$\forall x\exists y[y>x\wedge \neg \exists z(z^2+5z=y\left)\right]$
=$\forall x\exists y[y>x\wedge \forall z\neg (z^2+5z=y\left)\right]$
=$\forall x\exists y[y>x\wedge \forall z(z^2+5z\ne y\left)\right]$



Ex-2(a) Original statement is
$\exists x\left[F\right(x)\wedge \neg \exists yR(x,y\left)\right]$

F(x) means, x is in Freshman class
R(x,y) means, x and y are roommates

Its negation is

$\neg \exists x\left[F\right(x)\wedge \neg \exists yR(x,y\left)\right]$
=$\forall x\neg \left[F\right(x)\wedge \neg \exists yR(x,y\left)\right]$
=$\forall x[\neg F(x)\vee \exists yR(x,y\left)\right]$
=$\forall x\left[F\right(x)\to \exists yR(x,y\left)\right]$

In English, Everyone in freshman class has atleast one roommate.

Ex-2(b) Original statement is...
$(\forall x\exists yL(x,y\left)\right)\wedge (\neg \exists z\forall wL(z,w\left)\right)$

L(x,y) means, x likes y

Its negation is...
$\neg \left[\right(\forall x\exists yL(x,y))\wedge (\neg \exists z\forall wL(z,w)\left)\right]$
=$\neg (\forall x\exists yL(x,y\left)\right)\vee \neg (\neg \exists z\forall wL(z,w\left)\right)$
=$(\exists x\neg \exists yL(x,y\left)\right)\vee (\exists z\forall wL(z,w\left)\right)$
=$(\exists x\forall y\neg L(x,y\left)\right)\vee (\exists z\forall wL(z,w\left)\right)$

In English, Either there exists someone whom everyone dislikes or there exists someone whom everyone likes.

Ex-2(c) $\neg \forall a\in A\exists b\in B(a\in C\leftrightarrow b\in C)$
=$\exists a\in A\neg \exists b\in B(a\in C\leftrightarrow b\in C)$
=$\exists a\in A\forall b\in B\neg (a\in C\leftrightarrow b\in C)$

Ex-2(d) $\neg \forall y>0\exists x(a{x}^2+bx+c=y)$
=$\exists y>0\neg \exists x(a{x}^2+bx+c=y)$
=$\exists y>0\forall x(a{x}^2+bx+c\ne y)$


Ex-3(a) Let us try it for some x < 7 values, if we could find even a single x for which a,b,c can't exist then this statement is false.

for x = 0; a = b = c = 0
for x = 1; a = 1, b = c = 0
for x = 2; a = 1, b = 1, c = 0
for x = 3; a = 1, b = 1, c = 1
for x = 4; a = 2, b = c = 0

clearly, the statement is True.

Ex-3(b) clearly x = 1 and x = 7, both fulfill the condition, so its False.

Ex-3(c) clearly *only* x = 9 (-1 is not a natural number) fulfills the condition, so its True.

Ex-3(d) x = y = 9 fulfill the condition, so its True.


Ex-4 Given: $\neg \exists xP\left(x\right)$ = $\forall x\neg P\left(x\right)$

To Prove: $\neg \forall xP\left(x\right)$ = $\exists x\neg P\left(x\right)$

RHS = $\exists x\neg P\left(x\right)$
= $\neg \neg (\exists x\neg P(x\left)\right)$
= $\neg (\neg \exists x\neg P(x\left)\right)$
= $\neg (\forall x\neg (\neg P\left(x\right)\left)\right)$
= $\neg \forall xP\left(x\right)$
= LHS


Ex-5 $\neg \exists x\in AP\left(x\right)$
=$\neg \exists x(x\in A\wedge P(x\left)\right)$
=$\forall x\neg (x\in A\wedge P(x\left)\right)$
=$\forall x(x\notin A\vee \neg P(x\left)\right)$
=$\forall x(x\in A\to \neg P(x\left)\right)$
=$\forall x\in A\neg P\left(x\right)$



Ex-6 From Quantifier negation law
$\neg \exists x\left(P\right(x)\vee Q(x\left)\right)$
= $\forall x(\neg P(x)\wedge \neg Q(x\left)\right)$
= $(\forall x\neg P(x\left)\right)\wedge (\forall x\neg Q(x\left)\right)$
= $(\neg \exists xP(x\left)\right)\wedge (\neg \exists xQ(x\left)\right)$
= $\neg (\exists xP(x\left)\right)\wedge \neg (\exists xQ(x\left)\right)$
= $\neg [\exists xP(x)\vee \exists xQ(x\left)\right]$

so we proved
$\neg \exists x\left(P\right(x)\vee Q(x\left)\right)$ = $\neg [\exists xP(x)\vee \exists xQ(x\left)\right]$

now, taking negation of both sides we get
$\exists x\left(P\right(x)\vee Q(x\left)\right)$ = $\exists xP\left(x\right)\vee \exists xQ\left(x\right)$


Ex-7 $\exists x\left(P\right(x)\to Q(x\left)\right)$
= $\exists x(\neg P(x)\vee Q(x\left)\right)$ ...Existential quantifier distributes over $\vee$
= $(\exists x\neg P(x\left)\right)\vee (\exists xQ(x\left)\right)$
= $(\neg \forall xP(x\left)\right)\vee (\exists xQ(x\left)\right)$
= $\forall xP\left(x\right)\to \exists xQ\left(x\right)$


Ex-8 $(\forall x\in AP(x\left)\right)\wedge (\forall x\in BP(x\left)\right)$
= $(\forall x(x\in A\to P\left(x\right)\left)\right)\wedge (\forall x(x\in B\to P\left(x\right)\left)\right)$
= $\forall x(x\in A\to P(x\left)\right)\wedge (x\in B\to P(x\left)\right)$
= $\forall x(x\notin A\vee P(x\left)\right)\wedge (x\notin B\vee P(x\left)\right)$
= $\forall x\left[\right((x\notin A\vee P(x\left)\right)\wedge x\notin B)\vee ((x\notin A\vee P(x\left)\right)\wedge P\left(x\right)\left)\right]$
= $\forall x\left[\right((x\notin A\wedge x\notin B)\vee \left(P\right(x)\wedge x\notin B))\vee P(x\left)\right]$
= $\forall x\left[\right(x\notin A\wedge x\notin B)\vee (P\left(x\right)\wedge x\notin B)\vee P(x\left)\right]$
= $\forall x\left[\right(x\notin A\wedge x\notin B)\vee (\left(P\right(x)\wedge x\notin B)\vee P\left(x\right)\left)\right]$
= $\forall x\left[\right(x\notin A\wedge x\notin B)\vee P(x)$
= $\forall x[\neg (x\in A\vee x\in B)\vee P(x\left)\right]$
= $\forall x[\neg (x\in A\cup B)\vee P(x\left)\right]$
= $\forall x[x\in A\cup B\to P(x\left)\right]$
= $\forall x\in A\cup B$ $P\left(x\right)$


Ex-9 No.
Let say P(x) means, x has red hair and Q(x) means, x has brown eyes

Then, $\forall x\left(P\right(x)\vee Q(x\left)\right)$ means, Everyone has red hair or brown eyes or both.

And, $\forall xP\left(x\right)\vee \forall xQ\left(x\right)$ means, Either everyone has red hair or everyone has brown eyes.

Clearly, both mean different things.


Ex-10(a) In ex-8 we proved that
$(\forall x\in AP(x\left)\right)\wedge (\forall x\in BP(x\left)\right)$ = $\forall x\in A\cup B$ $P\left(x\right)$

So,
$(\forall x\in A\neg P(x\left)\right)\wedge (\forall x\in B\neg P(x\left)\right)$ = $\forall x\in A\cup B$ $\neg P\left(x\right)$

negating both sides, we get
$(\exists x\in AP(x\left)\right)\vee (\exists x\in BP(x\left)\right)$ = $\exists x\in A\cup B$ $P\left(x\right)$

Ex-10(b) No.
$\exists x\in (A\cap B)P\left(x\right)$
= $\exists x(x\in (A\cap B)\wedge P(x\left)\right)$
= $\exists x(x\in A\wedge x\in B\wedge P(x\left)\right)$

Since, existential quantifier does not distribute over $\wedge$ so it can not be equivalent to what is asked in the exercise.


Ex-11 $A\subseteq B$ in logical form is $\forall x(x\in A\to x\in B)$

$A\backslash B=\varnothing$ in logical form is...
$\neg \exists x(x\in A\backslash B)$

which is...
= $\forall x\neg (x\in A\backslash B)$
= $\forall x\neg (x\in A\wedge x\notin B)$
= $\forall x(x\notin A\vee x\in B)$
= $\forall x(x\in A\to x\in B)$

clearly, both the statements are same.


Ex-12

(a) x has exactly one student.

(b) There is atleast one person having exactly one student.

(c) There is exactly one teacher who has one or more students.

(d) There is atleast one person who has exactly one teacher.

(e) There is only one teacher-student pair.

(f) There is only one teacher-student pair. (e) and (f) are same.

how to prove it - ch2, sec2.1(quantifiers) ex

This section introduces the two well known quantifiers, universal($\forall$) meaning "for all" and existential($\exists$) meaning "there exists".

It also says that quantifier "binds" a variable, that is, a variable that is bound by a quantifier can always be replaced with a new variable without changing the meaning of the statement. For example $\forall xP\left(x\right)$ = $\forall yP\left(y\right)$

One statement can also contain more than one quantifier, for example, $\forall x\exists y(x+y=5)$ is a valid statement that means, for all values of x there exists at lease one y such that (x + y = 5).
It may be best in these cases to think about the quantifiers one at a time , in order.

Quantifiers have higher precedence than conditional/biconditional which means $\forall xP\left(x\right)\to Q\left(x\right)$ means $[\forall xP(x\left)\right]\to Q\left(x\right)$ and not $\forall x\left[P\right(x)\to Q(x\left)\right]$

================================================================================================

Ex-1(a) $\forall x[\exists yF(x,y)\to S(x\left)\right]$
where F(x,y) means x has forgiven y
S(x) means x is a saint

Ex-1(b) $\neg \exists xC\left(x\right)\wedge [\forall yD(y)\wedge S(x,y\left)\right]$
C(x) means, x is in Calculus class
D(y) means, y is in discrete math class
S(x,y) means, x is smarter than y

Ex-1(c) $\forall xL(x,Mary)\wedge \neg (x=Mary)$
L(x,Mary) means, x likes Mary
x = Mary means, x is Mary

Ex-1(d) $[\exists xP(x)\wedge S(Jane,x\left)\right]\wedge [\exists yP(y)\wedge S(Roger,y\left)\right]$
P(x) means, x is a police officer
S(x,y) means, x saw y

Ex-1(e) $\exists xP\left(x\right)\wedge S(Jane,x)\wedge S(Roger,x)$


Ex-2(a) $\forall x\left[B\right(x,Cash)\to \exists yR(y)\wedge U(y,x\left)\right]$
B(x,y) means, x bought a Rolls Royce with y
R(y) means, y is Rich
U(y,x) means, y is Uncle of x

Ex-2(b) This statement says, "If anyone in the dorm has the measles, then everyone who has a friend in the dorm will have to be quarantined."

$\exists x\left(D\right(x)\wedge M(x\left)\right)\to \forall z[\exists y(F(z,y)\wedge D\left(y\right))\to Q(z\left)\right]$

D(x) means, x lives in the form
F(x,y) means, x and y are friends
M(x) means, x has measles
Q(x) means, x has to be quarantined

Ex-2(c) This statement says, "If there does not exists anyone who failed the test, then everybody with grade A will tutor someone with grade D"

$\neg \exists xF\left(x\right)\to \forall y\left(A\right(y)\to \exists zD(z)\wedge T(y,z\left)\right)$

F(x) means, x has failed the test
A(y) means, y got grade A
D(z) means, z got grade D
T(y,z) means, y will tutor z

Ex-2(d) $\exists xD\left(x\right)\to D\left(Jones\right)$
D(x) means, x can do it

Ex-2(e) $D\left(Jones\right)\to \forall xD\left(x\right)$


Ex-3(a) $\forall z\left[\right(z>x)\to (z>y\left)\right]$

this statements is about x and y, that is values of x,y fix the True/False value of the statement.. x,y are the free variables

Ex-3(b) $\forall a\exists x\left[\right(a{x}^2+4x-2=0)\leftrightarrow (a\ge -2\left)\right]$

clearly, there is no free variable.

Ex-3(c)
no free variables

Ex-3(d)
w is the free variable


Ex-4(a) Every unmarried man is unhappy.

Ex-4(b) y is a sibling(sister) of one of x's parent.


Ex-5(a) Every prime number except 2 is odd.

Ex-5(b) There exists a perfect number such that all the other perfect numbers are either less or equal to it.


Ex-6(a) It means, there exists atleast one person who is parent of everyone. clearly its False.

Ex-6(b) It means, Everyone is a parent. clearly its False.

Ex-6(c) It means, There does not exist anyone who is parent of someone. clearly its False.

Ex-6(d) It means, There exists someone who is parent of none. its True.

Ex-6(e) It means, There exists someone who is not parent of someone. its True.


Ex-7(a) using $y=2x$ we can find a y for any x, clearly its True.

Ex-7(b) It means, there exists a y such that for all x, $2x-y=0$. clearly its False.

Ex-7(c) Using y = x/2, for odd x there would not be any y which is a natural number. so its False. This would be true if universe of discourse was real numbers.

Ex-7(d) True

Ex-7(e) holds true for y = z = 50; y = 40 , z = 60 ..etc. Clearly its True.

Ex-7(f) This statement will fail for x = 100, there is no y which is greater than 100 for which there exists some (natural number)z such that $y+z=100$. Clearly its False.


Ex-8(a) True

Ex-8(b) False

Ex-8(c) True

Ex-8(d) False

Ex-8(e) True

Ex-8(f) True


Ex-9(a) True

Ex-9(b) False

Ex-9(c) False

Ex-9(d) True

Ex-9(e) True

Ex-9(f) True

globalizing a web app

I'm involved in globalizing a web-app, which was not designed keeping g11n in mind. This material might be trivial but I'm noting down here things that are coming up(so that its quicker/easier the next time).

We realise, we need to store 4 user preferences(at least) to make decisions on what to do/show

Country
Locale
Currency
Time-Zone

We're putting following things in, stuff is chosen based on logged in user's preferences.

For Client Side:
Resource Bundles per country-locale
CSS per country-locale
Display Images per country-locale
Client Side validations per country-locale

For Server Side:
App properties per country-locale
A Validation framework where we can write different validation rules for different country-locale pair
Each date is stored as long + timezone string
Oracle DB instance needs to support UTF-8 encoding and VARCHAR2 with char semantics

how to prove it - ch1, sec1.5(the conditional and biconditional connectives) ex

This section introduces the Conditional($\to$) and the Biconditional($\leftrightarrow$) logical connectives and a form of valid reasoning, which is

$\frac{P\to Q,P}{\therefore Q}$

Another important thing to learn is, what these connectives usually translate in English to, Conditional can translate to

If P then Q
Q, if P
Q, when P
Q unless $\neg$P
P only if Q
P is a sufficient condition for Q
Q is a necessary condition for P

and Biconditional can translate to

P if and only if Q
P iff Q
P is the necessary and sufficient condition for Q

Some important equivalences...

$P\to Q$ = $\neg P\vee Q$ = $\neg Q\to \neg P$ (this last one is known as contrapositive law)

$P\leftrightarrow Q$ = $P\to Q\wedge Q\to P$

=========================================================================================

Ex-1(a)
$S\vee \neg E\to \neg H$ where
S = Unpleasant smell
E = Explosive
H = Hydrogen

Ex-1(b) $F\wedge H\to D$

Ex-1(c) $F\vee H\to D$
= $\neg (F\vee H)\vee D$
= $(\neg F\wedge \neg H)\vee D$
= $(\neg F\vee D)\wedge (\neg H\vee D)$
= $(F\to D)\wedge (H\to D)$

Ex-1(d) $A\to (O\to P)$ or $(A\wedge O)\to P$
A means $x\ne 2$
O means x is odd
P means x is prime


Ex-2(a) $S\to P\wedge A$
S means, Marry will sell her house
P means, she can get a good price
A means, she finds a nice apartment

Ex-2(b) $M\to C\wedge D$
C means, having a good credit history
D means, an adequate down payment
M means, getting the mortgate

Ex-2(c) Given sentence is equivalent to, If someone does not stop John then he'll kill himself. Its logical form is.. $\neg S\to K$

where S means, someone stops john and
K means, john kills himself

Ex-2(d) $D(x,4)\vee D(x,6)\to \neg P\left(x\right)$
where D(x,y) means, x is divisible by y and
P(x) means x is prime

Ex-3
(a) $R\to W\wedge \neg S$
R means, its raining
W means, its windy
S means, sun is shining

(b) $W\wedge \neg S\to R$ , clearly its the converse of (a)

(c) $R\to W\wedge \neg S$, its same as (a)

(d) $W\wedge \neg S\to R$ , clearly its the converse of (a)

(e) $S\vee \neg W\to \neg R$
= $\neg (\neg S\wedge W)\to \neg R$
= $R\to \neg S\wedge W$
= $R\to W\wedge \neg S$ , same as (a)

(f) $(R\to W)\wedge (R\to \neg S)$
= $(\neg R\vee W)\wedge (\neg R\vee \neg S)$
= $\left(\right(\neg R\vee W)\wedge \neg R)\vee \left(\right(\neg R\vee W)\wedge \neg S))$
= $\neg R\vee \left(\right(\neg R\vee W)\wedge \neg S))$
= $\neg R\vee \left(\right(\neg R\wedge \neg S)\vee (W\wedge \neg S\left)\right)$
= $(\neg R\vee (\neg R\wedge \neg S\left)\right)\vee (W\wedge \neg S)$
= $\neg R\vee (W\wedge \neg S)$
= $R\to W\wedge \neg S$, same as (a)

(g) $(W\to R)\vee (\neg S\to R)$
= $(\neg W\vee R)\vee (S\vee R)$
= $(\neg W\vee S)\vee (R\vee R)$
= $\neg (W\wedge \neg S)\vee R$
= $W\wedge \neg S\to R$, converse of (a)

Ex-4(a)
S means, Sales will go up
E means, Expenses will go up
H means, Boss will be Happy

Logical form of given statement is $(S\vee E)\wedge (S\to H)\wedge (E\to \neg H)$ and $\therefore$ $\neg (S\wedge E)$

S	E	H	$S\vee E$	$S\to H$	$E\to \neg H$	$(S\vee E)\wedge (S\to H)\wedge (E\to \neg H)$	$\neg (S\wedge E)$
F	F	F	F	T	T	F	T
T	F	F	T	F	T	F	T
F	T	F	T	T	T	T	T
T	T	F	T	F	T	F	F
F	F	T	F	T	T	F	T
T	F	T	T	T	T	T	T
F	T	T	T	T	F	F	T
T	T	T	T	T	F	F	F

Clearly all the places where $(S\vee E)\wedge (S\to H)\wedge (E\to \neg H)$ is T, $\neg (S\wedge E)$ is also T . So, $\neg (S\wedge E)$ can be inferred from $(S\vee E)\wedge (S\to H)\wedge (E\to \neg H)$ and the argument is valid.

Ex-4(b)
X means, Tax rate goes up
U means, Unemployment rate goes up
R means, there will be a recession
G means, GNP goes up

logical form of the given statement is $(X\wedge U\to R)\wedge (G\to \neg R)\wedge (G\wedge X)$, $\therefore$ $\neg U$

X	U	R	G	$X\wedge U\to R$	$G\to \neg R$	$G\wedge X$	$(X\wedge U\to R)\wedge (G\to \neg R)\wedge (G\wedge X)$	$\neg U$
F	F	F	F	T	T	F	F	T
T	F	F	F	T	T	F	F	T
F	T	F	F	T	T	F	F	F
T	T	F	F	F	T	F	F	F
F	F	T	F	T	T	F	F	T
T	F	T	F	T	T	F	F	T
F	T	T	F	T	T	F	F	F
T	T	T	F	T	T	F	F	F
F	F	F	T	T	T	F	F	T
T	F	F	T	T	T	T	T	T
F	T	F	T	T	T	F	F	F
T	T	F	T	F	T	T	F	F
F	F	T	T	T	F	F	F	T
T	F	T	T	T	F	T	F	T
F	T	T	T	T	F	F	F	F
T	T	T	T	T	F	T	F	F

using the same argument as earlier, its a valid argument.

Ex-4(c)
W means, Warning light will come on
P means, Pressure is too high
R means, Relief valve is clogged

logical form is $(W\leftrightarrow P\wedge R)\wedge \neg R$ , $\therefore$ $W\leftrightarrow P$

W	P	R	$P\wedge R$	$W\leftrightarrow P\wedge R$	$W\leftrightarrow P$
F	F	F	F	T	T
T	F	F	F	F	F
F	T	F	F	T	F
T	T	F	F	F	T
F	F	T	F	T	T
T	F	T	F	F	F
F	T	T	T	F	F
T	T	T	T	T	T

we can see an inconsistency at line 3, so its not a valid argument.


Ex-5(a) $P\leftrightarrow Q$
= $(P\to Q)\wedge (Q\to P)$
= $(\neg P\vee Q)\wedge (\neg Q\vee P)$
= $\left(\right(\neg P\vee Q)\wedge \neg Q)\vee \left(\right(\neg P\vee Q)\wedge P)$
= $\left(\right(\neg P\wedge \neg Q)\vee (Q\wedge \neg Q\left)\right)\vee \left(\right(\neg P\wedge P)\vee (Q\wedge P\left)\right)$
= $(\neg P\wedge \neg Q)\vee (Q\wedge P)$
= $(P\wedge Q)\vee (\neg P\wedge \neg Q)$

Ex-5(b) $(P\to Q)\vee (P\to R)$
= $(\neg P\vee Q)\vee (\neg P\vee R)$
= $(\neg P\vee \neg P)\vee (Q\vee R)$
= $\neg P\vee (Q\vee R)$
= $P\to (Q\vee R)$


Ex-6(a) $(P\to R)\wedge (Q\to R)$
= $(\neg P\vee R)\wedge (\neg Q\vee R)$
= $\left(\right(\neg P\vee R)\wedge \neg Q)\vee \left(\right(\neg P\vee R)\wedge R)$
= $\left(\right(\neg P\vee R)\wedge \neg Q)\vee R$
= $\left(\right(\neg P\wedge \neg Q)\vee (R\wedge \neg Q\left)\right)\vee R$
= $(\neg (P\vee Q\left)\right)\vee \left(\right(R\wedge \neg Q)\vee R)$
= $(\neg (P\vee Q\left)\right)\vee R$
= $P\vee Q\to R$

Ex-6(b) $(P\to R)\vee (Q\to R)$ = $P\wedge Q\to R$
Here is the proof...
$(P\to R)\vee (Q\to R)$
= $(\neg P\vee R)\vee (\neg Q\vee R)$
= $(\neg P\vee \neg Q)\vee (R\vee R)$
= $\neg (P\wedge Q)\vee R$
= $P\wedge Q\to R$


Ex-7(a)

P

Q

R

$P\to Q$

$Q\to P$

$Q\to R$

$R\to Q$

$(P\to Q)\wedge (Q\to R)$

$P\leftrightarrow Q$

$R\leftrightarrow Q$

$(P\leftrightarrow Q)\vee (R\leftrightarrow Q)$

$P\to R$

$(P\to R)\wedge \left(\right(P\leftrightarrow Q)\vee (R\leftrightarrow Q\left)\right)$

F

F

F

T

T

T

T

T

T

T

T

T

T

T

F

F

F

T

T

T

F

F

T

T

F

F

F

T

F

T

F

F

T

F

F

F

F

T

F

T

T

F

T

T

F

T

F

T

F

T

F

F

F

F

T

T

T

T

F

T

T

F

T

T

T

T

F

T

F

T

T

F

F

F

F

F

T

F

F

T

T

T

F

T

T

T

F

T

T

T

T

T

T

T

T

T

T

T

T

T

T

T

T

T

Match column 8 and 13, clearly both are same.

Ex-7(b)
$(P\to Q)\vee (Q\to R)$
= $(\neg P\vee Q)\vee (\neg Q\vee R)$
= $\neg P\vee (Q\vee \neg Q)\vee R$
= $\neg P\vee \left(TRUE\right)\vee R$
= TRUE

Ex-8 $P\wedge Q$
= $\neg (\neg P\vee \neg Q)$
= $\neg (P\to \neg Q)$

Ex-9 $P\leftrightarrow Q$
= $(P\to Q)\wedge (Q\to P)$ , now using Ex-8
= $\neg \left(\right(P\to Q)\to \neg (Q\to P\left)\right)$


Ex-10

(a) $P\to (Q\to R)$
= $\neg P\vee (\neg Q\vee R)$
= $\neg P\vee \neg Q\vee R$

(b) $Q\to (P\to R)$
= $\neg Q\vee (\neg P\vee R)$
= $\neg Q\vee \neg P\vee R$
= $\neg P\vee \neg Q\vee R$ , clearly its same as (a)

(c) $(P\to Q)\wedge (P\to R)$
= $(\neg P\vee Q)\wedge (\neg P\vee R)$
= $\left(\right(\neg P\vee Q)\wedge \neg P)\vee \left(\right(\neg P\vee Q)\wedge R)$
= $(\neg P)\vee \left(\right(\neg P\wedge R)\vee (Q\wedge R\left)\right)$
= $\neg P\vee (\neg P\wedge R)\vee (Q\wedge R)$
= $(\neg P\vee (\neg P\wedge R\left)\right)\vee (Q\wedge R)$
= $\neg P\vee (Q\wedge R)$

we've reduced original form to disjunctive normal form(disjunction of conjunctions) here

(d) $(P\wedge Q)\to R$
= $\neg (P\wedge Q)\vee R$
= $\neg P\vee \neg Q\vee R$
clearly its same as (a) and (b)

(e) $P\to (Q\wedge R)$
= $\neg P\vee (Q\wedge R)$
clearly its same as (c)

how to prove it - ch1, sec1.4(operations on sets) ex

This section introduces set operations: Intersection, Union and Difference ($\cap ,\cup$ and \)

Most important take away of this section is that, there are two main ways to prove equivalence of two sets
1. By drawing venn diagrams
2. By converting set operations into logic statements(with logic connectives) and then using logical equivalences. Following are the conversion of 3 basic set operations...
x $\in$ $A\cup B$ = $(x\in A)\vee (x\in B)$
x $\in$ $A\cap B$ = $(x\in A)\wedge (x\in B)$
x $\in$ $A\backslash B$ = $(x\in A)\wedge \neg (x\in B)$


Ex-1(a) {3, 12}
Ex-1(b) {1,3,7,12,20,35} \ {x | x is a prime} = {1,12,20,35}
Ex-1(c) {1,3,12,35} $\cup$ ({3,7,12,20} \ {x | x is a prime}) = {1,3,12,35} $\cup$ {12,20} = {1,3,12,20,35}


Ex-2(a) {United States, Germany, China, Australia, France, India, Brazil}
Ex-2(b) {Germany} \ {x | x is a country in Europe} = {}
Ex-2(c) {Germany, France} \ A = {France}

Ex-4 look in the attached pic


Ex-5(a)
x $\in$ $A\backslash (A\cap B)$
= $(x\in A)\wedge x\notin (A\cap B)$
= $(x\in A)\wedge \neg \left(\right(x\in A)\wedge (x\in B\left)\right)$
= $(x\in A)\wedge (\neg (x\in A)\vee \neg (x\in B\left)\right)$
= $\left(\right(x\in A)\wedge \neg (x\in A\left)\right)\vee \left(\right(x\in A)\wedge \neg (x\in B\left)\right)$
= $(x\in A)\wedge \neg (x\in B)$
= $x\in A\backslash B$

Ex-5(b)
x $\in$ $A\cup (B\cap C)$
= $(x\in A)\vee (x\in (B\cap C\left)\right)$
= $(x\in A)\vee \left(\right(x\in B)\wedge (x\in C\left)\right)$
= $\left(\right(x\in A)\vee (x\in B\left)\right)\wedge \left(\right(x\in A)\vee (x\in C\left)\right)$
= $(x\in A\cup B)\wedge (x\in A\cup C)$
= $x\in (A\cup B)\cap (A\cup C)$


Ex-6 look in the attached pic


Ex-7(a)
x $\in$ $(A\cup B)\backslash C$
= $(x\in (A\cup B\left)\right)\wedge (x\notin C)$
= $\left(\right(x\in A)\vee (x\in B\left)\right)\wedge (x\notin C)$
= $\left(\right(x\in A)\wedge (x\notin C\left)\right)\vee \left(\right(x\in B)\wedge (x\notin C\left)\right)$
= $(x\in A\backslash C)\vee (x\in B\backslash C)$
= $x\in (A\backslash C)\cup (B\backslash C)$

Ex-7(b)
x $\in$ $A\cup (B\backslash C)$
= $(x\in A)\vee x\in (B\backslash C)$
= $(x\in A)\vee \left(\right(x\in B)\wedge \neg (x\in C\left)\right)$
= $\left(\right(x\in A)\vee (x\in B\left)\right)\wedge \left(\right(x\in A)\vee \neg (x\in C\left)\right)$
= $(x\in (A\cup B\left)\right)\wedge \neg \left(\right(x\in C)\wedge \neg (x\in A\left)\right)$
= $(x\in (A\cup B\left)\right)\wedge \neg (x\in (C\backslash A\left)\right)$
= $x\in (A\cup B)\backslash (C\backslash A)$


Ex-8

(a) x $\in$ $(A\backslash B)\backslash C$
= $(x\in (A\backslash B\left)\right)\wedge (x\notin C)$
= $\left(\right(x\in A)\wedge (x\notin B\left)\right)\wedge (x\notin C)$
= $(x\in A)\wedge (x\notin B)\wedge (x\notin C)$
= $(x\in A)\wedge \neg \left(\right(x\in B)\vee (x\in C\left)\right)$
= $(x\in A)\wedge \neg (x\in (B\cup C\left)\right)$
= $x\in A\backslash (B\cup C)$

(b) x $\in$ $A\backslash (B\backslash C)$
= $(x\in A)\wedge \neg (x\in (B\backslash C\left)\right)$
= $(x\in A)\wedge \neg \left(\right(x\in B)\wedge \neg (x\in C\left)\right)$
= $(x\in A)\wedge \left(\right(x\notin B)\vee (x\in C\left)\right)$
= $\left(\right(x\in A)\wedge (x\notin B\left)\right)\vee \left(\right(x\in A)\wedge (x\in C\left)\right)$
= $(x\in (A\backslash B\left)\right)\vee (x\in (A\cap C\left)\right)$
= $x\in (A\backslash B)\cup (A\cap C)$

(c) from analysis of b, clearly b and c are same

(d) x $\in$ $(A\backslash B)\cap (A\backslash C)$
= $(x\in (A\backslash B\left)\right)\wedge (x\in (A\backslash C\left)\right)$
= $\left(\right(x\in A)\wedge (x\notin B\left)\right)\wedge \left(\right(x\in A)\wedge (x\notin C\left)\right)$
= $\left(\right(x\in A)\wedge (x\in A\left)\right)\wedge \left(\right(x\notin B)\wedge (x\notin C\left)\right)$
= $(x\in A)\wedge \neg \left(\right(x\in B)\vee (x\in C\left)\right)$
= $(x\in A)\wedge \neg (x\in (B\cup C\left)\right)$
= $x\in A\backslash (B\cup C)$


(e) from analysis of a and d, clearly a,d and e are same


Ex-9
A = {1,2,3)
B = {2,4}

$(A\cup B)$ = {1,2,3,4}
$(A\cup B)\backslash B$ = {1,3} , which is not A

Ex-11(a) Look in the attached pic, its clear that $(A\cup B)\backslash C\backslash hspace2\subseteq \backslash hspace2A\cup (B\backslash C)$

Ex-11(b) Clearly, for two can be made non-equal by making $A\cap C$ non-empty
A = {1,2,3,4}
B = {3,4,5,6}
C = {0,2,3,4,7}

$(A\cup B)\backslash C$ = {1,5,6}
$A\cup (B\backslash C)$ = {1,2,3,4,5,6}

Rest of the exercises are pretty similar to the ones done, so I'm passing them :)

how to prove it, ch-1, sec 1.3(Variables and Sets) ex

With variables we can have general statements containing free variables, True/False of which is fixed only when variable is fixed to a value unlike propositional statement whose value is fixed.

Writing a set definition using elementhood test means writing it like {x | P(x)} where P(x) is the desired test/predicate.

In general $y\in \{x\in A\mid P(x\left)\right\}$ means the same thing as $(y\in A)\wedge P\left(y\right)$
=========================================================================================

Ex-1(a) $D\left(6\right)\wedge D\left(9\right)\wedge D\left(15\right)$ where D(x) means "x is divisible by 3"

Ex-1(b) $D(x,2)\wedge D(x,3)\wedge \neg D(x,4)$ where D(x,y) means "x is divisible by y"

Ex-1(c) $N\left(x\right)\wedge N\left(y\right)\wedge \left(P\right(x)\vee P(y\left)\right)\wedge \neg \left(P\right(x)\wedge P(y\left)\right)$ where N(x) means "x is a natutal number" and P(x) means "x is a prime number"


Ex-2(a) $M\left(x\right)\wedge M\left(y\right)\wedge \left(Taller\right(x,y)\vee Taller(y,x\left)\right)$ where M(x) means "x is a Man" and Taller(x,y) means "x is taller than y"

Ex-2(b) $\left(B\right(x)\vee B(y\left)\right)\wedge \left(R\right(x)\vee R(y\left)\right)$ where B(x) means "x has brown eyes" and R(x) means "x has red hair"

Ex-2(c) $\left(B\right(x)\wedge R(x\left)\right)\vee \left(B\right(y)\wedge R(y\left)\right)$ where B(x) means "x has brown eyes" and R(x) means "x has red hair"


Ex-3(a) {x | x is a planet}

Ex-3(b) {x | x is an university}

Ex-3(c) {x | x is a state of USA}

Ex-3(d) {x | x is province or territory in canada}

Ex-4(a) {$x^2$ | $x\in Z+$}

Ex-4(b) {$2^x$ | $x\in N$}

Ex-4(c) {$x\in Z\mid (x\ge 10)\wedge (x\le 19)$}


Ex-5(a) $(-3\in R)\wedge (13-2*-3>1)$ = $(-3\in R)\wedge (19>1)$
bound variable is 'x', no free variables and statement is True.

Ex-5(b) $(4\in R-)\wedge (5>1)$
bound variable is 'x', no free variables, but statement is False as $4\in R-$ is False.

Ex-5(c) $\neg \left(\right(5\in R)\wedge (3>c\left)\right)$
bound variable is 'x', one free variable 'c'


Ex-6(a) $(w\in R)\wedge (13-2w>c)$
bound variable is 'x'; free variables are 'w' and 'c'

Ex-6(b) P(y) means "y is a prime number"
$(4\in R)\wedge P\left(5\right)$
bound variables are 'x' and 'y'; no free variables; statement is True.

Ex-6(c) P(y) means "y is a prime number"
$P\left(4\right)\wedge (5>1)$
bound variables are 'x' and 'y'; no free variables; statement is False


Ex-7(a) {x | x is or was husband of Elizabeth Taylor }

Ex-7(b) $\{\wedge ,\vee ,\neg \}$

Ex-7(c) {"Daniel J. Velleman"}


Ex-8(a) $\{x\in R\mid x^2-4x+3=0\}$ = {1,3}

Ex-8(b) $\{x\in R\mid x^2-2x+3=0\}$ = $\phi$

Ex-8(c)
= {}
= {}
= {1,2,3,...}

how to prove it - ch1, sec1.2 ex

Validity:To prove validity of an argument of the form $premises\Rightarrow conclusion$ we need to create the truth table and see that all the cases where premises are true, conclusion must be true.

Tautology: A statement that is always true.

Contradiction: A statement that is always false.

This section also introduces various equivalences such as DeMorgan's laws, Commutative laws, Associative laws, Idempotent laws, Distributive laws, Double Negation law and Absorption laws($P\vee (P\wedge Q)\equiv P$ and $P\wedge (P\vee Q)\equiv P$)

There are two ways to prove the equivalence of two complex logical statements.

1. Draw truth tables for both and see if they are exactly the same.
2. Use equivalence relations described above to see if one can be transformed into other

===========================================================================================

Ex-1(a)

P	Q	$\neg P$	$\neg P\vee Q$
F	F	T	T
T	F	F	F
F	T	T	T
T	T	F	T

Ex-1(b)

S	G	$\neg S$	$\neg G$	$S\vee G$	$\neg S\vee \neg G$	$(S\vee G)\wedge (\neg S\vee \neg G)$
F	F	T	T	F	T	F
T	F	F	T	T	T	T
F	T	T	F	T	T	T
T	T	F	F	T	F	F

Ex-2(a)

P	Q	$\neg P$	$(Q\vee \neg P)$	$P\wedge (Q\vee \neg P)$	$\neg (P\wedge (Q\vee \neg P\left)\right)$
F	F	T	T	F	T
T	F	F	F	F	T
F	T	T	T	F	T
T	T	F	T	T	F

Ex-2(b)

P	Q	R	$\neg P$	$P\vee Q$	$\neg P\vee R$	$(P\vee Q)\wedge (\neg P\vee R)$
F	F	F	T	F	T	F
T	F	F	F	T	F	F
F	T	F	T	T	T	T
T	T	F	F	T	F	F
F	F	T	T	F	T	F
T	F	T	F	T	T	T
F	T	T	T	T	T	T
T	T	T	F	T	T	T

Ex-3(a) '+' denotes exclusive or

P	Q	P+Q
F	F	F
T	F	T
F	T	T
T	T	F

Ex-3(b)
In general, to find the formula from truth table, take the rows where the output of unknown formula is T, for each such row take negation/conjunction of input propositions in such a way that they produce T and then take disjunction of them all.

For above truth table, P+Q is T for 2 cases
1. P = T, Q = F : this suggests $P\wedge \neg Q$
2. P = F, Q = T : this suggests $\neg P\wedge Q$

taking disjunction of above 2, we get
$(P\wedge \neg Q)\vee (\neg P\wedge Q)$

Let us see the truth table for this:

P	Q	$\neg P$	$\neg Q$	$P\wedge \neg Q$	$\neg P\wedge Q$	$(P\wedge \neg Q)\vee (\neg P\wedge Q)$
F	F	T	T	F	F	F
T	F	F	T	T	F	T
F	T	T	F	F	T	T
T	T	F	F	F	F	F

Ex-4
Using DeMorgan's law we can easily see that $P\vee Q\equiv \neg (\neg P\wedge \neg Q)$ . Let us justify it with the truth table.

P	Q	$\neg P$	$\neg Q$	$\neg P\wedge \neg Q$	$\neg (\neg P\wedge \neg Q)$	$P\vee Q$
F	F	T	T	T	F	F
T	F	F	T	F	T	T
F	T	T	F	F	T	T
T	T	F	F	F	T	T

Ex-5(a)
$\downarrow$ means nor(not or)

P	Q	$P\downarrow Q$
F	F	T
T	F	F
F	T	F
T	T	F

Ex-5(b)
Its easily seen that it is NOT OR that is $\neg (P\vee Q)$

Ex-5(c)
$\neg P\equiv (P\downarrow P)$
$P\vee Q\equiv \neg (P\downarrow Q)\equiv (P\downarrow Q)\downarrow (P\downarrow Q)$
$P\wedge Q\equiv \neg (\neg P\vee \neg Q)\equiv \neg P\downarrow \neg Q\equiv (P\downarrow P)\downarrow (Q\downarrow Q)$

Ex-6(a)
| means nand (Not And)

P	Q	P|Q
F	F	T
T	F	T
F	T	T
T	T	F

Ex-6(b) $\neg (P\wedge Q)$

Ex-6(c)
$\neg P\equiv P\mid P$
$P\vee Q\equiv \neg (\neg P\wedge \neg Q)\equiv \neg P\mid \neg Q\equiv (P\mid P)\mid (Q\mid Q)$
$P\wedge Q\equiv \neg (\neg (P\wedge Q\left)\right)\equiv \neg (P\mid Q)\equiv (P\mid Q)\mid (P\mid Q)$

Ex-7(a)

Jm	Pm	Pc	$Jm\wedge Pm$	$\neg (Jm\wedge Pm)$	$Pm\vee Pc$
F	F	F	F	T	F
T	F	F	F	T	F
F	T	F	F	T	T
T	T	F	T	F	T
F	F	T	F	T	T
T	F	T	F	T	T
F	T	T	F	T	T
T	T	T	T	F	T

clearly the argument is valid.

Ex-7(b)

B	F	P	C	$B\vee F$	$P\vee C$	$F\wedge C$	$\neg (F\wedge C)$	$B\wedge P$	$\neg (B\wedge P)$
F	F	F	F	F	F	F	T	F	T
T	F	F	F	T	F	F	T	F	T
F	T	F	F	T	F	F	T	F	T
T	T	F	F	T	F	F	T	F	T
F	F	T	F	F	T	F	T	F	T
T	F	T	F	T	T	F	T	T	F
F	T	T	F	T	T	F	T	F	T
T	T	T	F	T	T	F	T	T	F
F	F	F	T	F	T	F	T	F	T
T	F	F	T	T	T	F	T	F	T
F	T	F	T	T	T	T	F	F	T
T	T	F	T	T	T	T	F	F	T
F	F	T	T	F	T	F	T	F	T
T	F	T	T	T	T	F	T	T	F
F	T	T	T	T	T	T	F	F	T
T	T	T	T	T	T	T	F	T	F

clearly argument is not valid at row # 6

Ex-7(c)

J	B	S	$\neg B$	$\neg S$	$J\vee B$	$\neg S\vee \neg B$	$J\vee \neg S$
F	F	F	T	T	F	T	T
T	F	F	T	T	T	T	T
F	T	F	F	T	T	T	T
T	T	F	F	T	T	T	T
F	F	T	T	F	F	T	F
T	F	T	T	F	T	T	T
F	T	T	F	F	T	F	F
T	T	T	F	F	T	F	T

clearly argument is valid.

Ex-7(d)

S	B	E	$\neg B$	$S\wedge B$	$E\wedge \neg B$	$(S\wedge B)\vee (E\wedge \neg B)$	$S\wedge E$	$\neg (S\wedge E)$
F	F	F	T	F	F	F	F	T
T	F	F	T	F	F	F	F	T
F	T	F	F	F	F	F	F	T
T	T	F	F	T	F	T	F	T
F	F	T	T	F	T	T	F	T
T	F	T	T	F	T	T	T	F
F	T	T	F	F	F	F	F	T
T	T	T	F	T	F	T	T	F

clearly argument is not valid at row # 6 and 8.

Ex-8

P

Q

$\neg P$

$\neg Q$

$P\wedge Q$

$\neg P\wedge \neg Q$

a = $(P\wedge Q)\vee (\neg P\wedge \neg Q)$

b = $\neg P\vee Q$

$P\vee \neg Q$

$Q\vee \neg P$

c = $(P\vee \neg Q)\wedge (Q\vee \neg P)$

d = $\neg (P\vee Q)$

$Q\wedge P$

e = $(Q\wedge P)\vee \neg P$

F

F

T

T

F

T

T

T

T

T

T

T

F

T

T

F

F

T

F

F

F

F

T

F

F

F

F

F

F

T

T

F

F

F

F

T

F

T

F

F

F

T

T

T

F

F

T

F

T

T

T

T

T

F

T

T

clearly a $\equiv$ c and b $\equiv e$ and d is equivalent to none

Ex-9

P	Q	$\neg P$	$\neg Q$	$P\vee Q$	$\neg P\vee \neg Q$	a = $(P\vee Q)\wedge (\neg P\vee \neg Q)$	$\neg P\wedge \neg Q$	b = $(P\vee Q)\wedge (\neg P\wedge \neg Q)$	c = $(P\vee Q)\vee (\neg P\vee \neg Q)$
F	F	T	T	F	T	F	T	F	T
T	F	F	T	T	T	T	F	F	T
F	T	T	F	T	T	T	F	F	T
T	T	F	F	T	F	F	F	F	T

clearly a is none, b is contradiction and c is tautology

P	Q	R	$\neg P$	$\neg R$	$Q\vee \neg R$	$P\wedge (Q\vee \neg R)$	$\neg P\vee R$	d = $(P\wedge (Q\vee \neg R\left)\right)\vee (\neg P\vee R)$
F	F	F	T	T	T	F	T	T
T	F	F	F	T	T	T	F	T
F	T	F	T	T	T	F	T	T
T	T	F	F	T	T	T	F	T
F	F	T	T	F	F	F	T	T
T	F	T	F	F	F	F	T	T
F	T	T	T	F	T	F	T	T
T	T	T	F	F	T	T	T	T

clearly d is tautology.

Ex-10 Its trivial, pass.

Ex-11(a)
$\neg (\neg P\wedge \neg Q)$
= $\neg \neg P\vee \neg \neg Q$ ...DeMorgan's Law
= $P\vee Q$ ...Double Negation Law

Ex-11(b)
$(P\wedge Q)\vee (P\wedge \neg Q)$
= $\left(\right(P\wedge Q)\vee P)\wedge \left(\right(P\wedge Q)\vee \neg Q))$ ...Distribution Law
= $P\wedge \left(\right(P\wedge Q)\vee \neg Q))$ ...Absorption Law
= $P\wedge \left(\right(P\vee \neg Q)\wedge (Q\vee \neg Q\left)\right)$ ...Distribution Law
= $P\wedge (P\vee \neg Q)$
= $P$ ...Absorption law

Ex-11(c)
$\neg (P\wedge \neg Q)\vee (\neg P\wedge Q)$
= $(\neg P\vee Q)\vee (\neg P\wedge Q)$ ...DeMorgan's and then Double Negation law
= $\left(\right(\neg P\vee Q)\vee \neg P)\wedge (\neg P\vee Q)\vee Q\left)\right)$ ...Distribution law
= $\left(\right(\neg P\vee \neg P)\vee Q)\wedge (\neg P\vee (Q\vee Q\left)\right)$ ...Commutative and Associative laws
= $(\neg P\vee Q)\wedge (\neg P\vee Q)$ ...Idempotent law
= $\neg P\vee Q$ ...Idempotent law

Ex-12(a)
$\neg (\neg P\vee Q)\vee (P\wedge \neg R)$
= $(P\wedge \neg Q)\vee (P\wedge \neg R)$ ...DeMorgan's, Double Negation law
= $\left(\right(P\wedge \neg Q)\vee P)\wedge \left(\right(P\wedge \neg Q)\vee \neg R)$ ...Distribution law
= $P\wedge \left(\right(P\wedge \neg Q)\vee \neg R)$ ...Absorption law
= $(P\wedge (P\wedge \neg Q\left)\right)\vee (P\wedge \neg R)$ ...Distribution law
= $(P\wedge \neg Q)\vee (P\wedge \neg R)$ ...Associative, Idempotent law


Ex-12(b)
$\neg (\neg P\wedge Q)\vee (P\wedge \neg R)$
= $(P\vee \neg Q)\vee (P\wedge \neg R)$ ...DeMorgan's, Double Negation law
= $\left(\right(P\vee \neg Q)\vee P)\wedge \left(\right(P\vee \neg Q)\vee \neg R)$ ...Distribution law
= $(P\vee \neg Q)\wedge \left(\right(P\vee \neg Q)\vee \neg R)$ ...Commutative,Associative law
= $P\vee \neg Q$ ...Absorption law

Ex-12(c)
$(P\wedge R)\vee (\neg R\wedge (P\vee Q\left)\right)$
$(P\wedge R)\vee \left(\right(\neg R\wedge P)\vee (\neg R\wedge Q\left)\right)$ ...Distribution law
$(P\wedge R)\vee (\neg R\wedge P)\vee (\neg R\wedge Q)$
$\left(\right(P\wedge R)\vee (\neg R\wedge P\left)\right)\vee (\neg R\wedge Q)$
$(P\wedge (R\vee \neg R\left)\right)\vee (\neg R\wedge Q)$ ...Distribution law
$(P\wedge TRUE)\vee (\neg R\wedge Q)$ ...Tautology
$P\vee (\neg R\wedge Q)$


Ex-13
LHS
= $\neg (P\vee Q)$
= $\neg (\neg \neg P\vee \neg \neg Q)$ ...Double Negation law
= $\neg (\neg (\neg P\wedge \neg Q\left)\right)$ ...First DeMorgan's law
= $\neg P\wedge \neg Q$ ...Double Negation law
= RHS

Ex-14
$(P\wedge (Q\wedge R\left)\right)\wedge S$
= $\left(\right(P\wedge Q)\wedge R)\wedge S$
= $\left(\right(P\wedge Q)\wedge (R\wedge S\left)\right)$
= $(P\wedge Q)\wedge (R\wedge S)$

Ex-15 $2^n$

Ex-16
Using the same strategy as described in Ex-3(b)..

output holds true for
P = F, Q = F ; suggests $\neg P\wedge \neg Q$
P = T, Q = F ; suggests $P\wedge \neg Q$
P = T, Q = T ; suggests $P\wedge Q$

taking disjunction of all
$(\neg P\wedge \neg Q)\vee (P\wedge \neg Q)\vee (P\wedge Q)$
= $(\neg P\wedge \neg Q)\vee \left(\right(P\wedge \neg Q)\vee (P\wedge Q\left)\right)$ ...Commutative law
= $(\neg P\wedge \neg Q)\vee \left(\right((P\wedge \neg Q)\vee P)\wedge ((P\wedge \neg Q)\vee Q\left)\right)$ ...Distribution law
= $(\neg P\wedge \neg Q)\vee (P\wedge ((P\wedge \neg Q)\vee Q\left)\right)$ ...Absorption law
= $(\neg P\wedge \neg Q)\vee (P\wedge ((P\vee Q)\wedge (\neg Q\vee Q)\left)\right)$ ...Distribution law
= $(\neg P\wedge \neg Q)\vee (P\wedge (P\vee Q\left)\right)$ ...Tautology
= $(\neg P\wedge \neg Q)\vee P$ ...Absorption law
= $(\neg P\vee P)\wedge (\neg Q\vee P)$ ...Distribution law
= $\neg Q\vee P$ ...Tautology

Ex-17
Again using the same strategy as described in Ex-3(b)..we get

$(P\wedge \neg Q)\vee (\neg P\wedge Q)$

Ex-18
Suppose the conclusion of an argument is a tautology. What can you say about the validity of the argument?
We can say, its always valid because for all the cases where premises are true conclusion will also be true(as its a tautology).

What if conclusion is contradiction?
We can't say anything.

What if one of the premises is a tautology?
We can't say anything.

What if one of the premises is a contradiction?
We can say, the argument is always valid as all premises will never be true.

how to prove it - ch1, sec1.1 ex

Ex-1(a)
P $\equiv$ We have a reading assignment.
Q $\equiv$ We have homework.
R $\equiv$ We have a test.

$(P\vee Q)\wedge \neg (Q\wedge R)$

Ex-1(b)
P $\equiv$ You will go skiing.
Q $\equiv$ There will be snow.

$\neg P\vee (P\wedge \neg Q)$

Ex-1(c)
P
Q $\equiv \sqrt{7}=2$

$\neg (P\vee Q)$

Ex-2(a)
J $\equiv$ John is telling the truth.
B $\equiv$ Bill is telling the truth.

$(J\wedge B)\vee (\neg J\wedge \neg B)$

Ex-2(b)
F $\equiv$ I'll have fish.
C $\equiv$ I'll have chicken.
P $\equiv$ I'll have mashed potatoes.

$(F\vee C)\wedge \neg (F\wedge P)$

Ex-2(c)
P $\equiv$ 3 is a common divisor of 6.
Q $\equiv$ 3 is a common divisor of 9.
R $\equiv$ 3 is a common divisor of 15.

$P\wedge Q\wedge R$

Ex-3(a) $(A\vee B)\wedge \neg (A\wedge B)$
Ex-3(b) $\neg A\wedge \neg B$
Ex-3(c) $\neg A\vee \neg B$
Ex-3(d) $\neg A\wedge \neg B$

Ex-4 a and c only

Ex-5(a)
$\neg (P\wedge \neg S)=\neg P\vee S$ means: Either I will not buy the pants or I'll buy the shirt
Ex-5(b) I will neither buy pants nor shirt.
Ex-5(c) Either I'll not buy pants or I'll not buy the shirt... Or we could say... I'll not buy both pants and shirt.

Ex-7(a)
Premises:
Jane and Pete won't both win the math prize. $\equiv \neg (Jm\wedge Pm)$
Pete will either win the math prize or the chemistry prize. $\equiv (Pm\vee Pc)$
Jane will win the math prize. $\equiv Jm$

Conclusion:
Pete will win the chemistry prize. $\equiv Pc$

Reasoning is valid.

Ex-7(b)
Premises:
The main course will be either beef or fish. $\equiv B\vee F$
The vegetable will be either peas or corn. $\equiv P\vee C$
We will not have both fish as a main course and corn as a vegetable. $\equiv \neg (F\wedge C)$

Conclusion:
We will not have both beef as a main course and peas as a vegetable. $\equiv \neg (B\wedge P)$

Reasoning is not valid because when B = true, P = true, F = false, C = false; all the premises are true but the conclusion is false.

Ex-7(c)
Premises:
Either John or Bill is telling the truth. $\equiv J\vee B$
Either Sam or Bill is lying. $\equiv \neg S\vee \neg B$

Conclusion:
Either John is telling the truth or Sam is lying. $\equiv J\vee \neg S$

Reasoning is valid.

Ex-7(d)
Premises:
Either sales will go up and the boss will be happy, or expenses will go up and the boss won't be happy. $\equiv (S\wedge B)\vee (E\wedge \neg B)$

Conclusion:
Sales and expenses will not both go up. $\equiv \neg (S\wedge E)$

Reasoning is not valid because when S = true, B = true, E = true; the premise is true but conclusion is false.

how to prove it - intro exercises

Ex-1 (a)
Using the formula
$2^{15}-1$ = $2^{3*5}-1$
a = 5, b = 3
$2^b-1$ = $2^3-1$ = 7

and

$1+2^b+2^{2b}+...+2^{(a-1)b}$ = $1+2^3+2^{2*3}+2^{3*3}+2^{4*3}$ = 4681

Ex-1 (b)
$2^{32767}-1$ = $2^{7*4681}-1$
b = 7, so
x = $2^7-1$ = 127

Ex-2

n	$3^n-1$	$3^n-2^n$
1	2	1
2	8	5
3	26	19
4	80	65
5	242	211
6	728	665
7	2186	2059
8	6560	6305
9	19682	19171
10	59048	58025

2 conjectures are:
$3^n-2^n$ is prime for prime n
$3^n-1$ is never prime except for n = 1

Ex-3(a)
2*3*5*7 + 1 = 211

Ex-3(b)
2*3*5*7*11 + 1 = 2311

Ex-4
x = (n+1)! + 2 = (5+1)! + 2 = 722
5 consecutive non-prime numbers are x, x + 1, x + 2, x + 3, x + 4 = 722,723,724,725,726

Ex-5
Use: If $2^n-1$ is prime $\Rightarrow$ $2^{(n-1)}(2^n-1)$ is perfect number
$2^5-1=31$ is prime $\Rightarrow$ $2^{(5-1)}(2^5-1)$ = 496 is perfect number
$2^7-1=127$ is prime $\Rightarrow$ $2^{(7-1)}(2^7-1)$ = 8128 is perfect number

Ex-6 There are no more triplet primes other than 3,5,7 where adjacent numbers in the list differ by 2.

Proof: I'll prove it by contradiction. Let say p, p+2, p+4 (p > 3)be such a triplet prime list.

Since one of the 3 consecutive numbers has to be divisible by 3, so
one out of p, p+1 or p+2 is divisible by 3. Since p and p+2 are primes by assumption so p+1 is divisible by 3. But then p+4 = (p+1)+3 and hence p+4 should be divisible by 3 and this is a contradiction.

Generic Matrix[T] impl in Scala v2.8+

This is my attempt to learn how to implement generic math libraries(generic in the sense that they can work with any "Numeric" type such as Int,Long,Double,...etc) in Scala. Similar efforts have been tried at following places..

http://stackoverflow.com/questions/485896/how-does-one-write-the-pythagoras-theorem-in-scala
http://dcsobral.blogspot.com/search/label/matrix

I got enough guidance from scala community here, and from this write-up[warn: PDF] on new array impl in scala v2.8 .

Here is the result...

//Generic Rep for m X n immutable matrix
class Matrix[T: ClassManifest] private (private val elems: Array[Array[T]])(n: Numeric[T]) {

  import n.mkNumericOps

  val rows = elems.size        //Returns # of rows
  val cols = elems(0).size     //Returns # of cols

  //Returns jth elem in ith row
  // 0 <= i < rows And 0 <= j < cols
  def apply(i: Int, j: Int): T = elems(i)(j)

  //Returns ith row, 0 <= i < rows
  def row(i: Int): Array[T] = elems(i).clone

  //Returns ith col, 0 <= i < cols
  def col(i: Int): Array[T] = elems.map(_(i))

  def *(that: Matrix[T]): Matrix[T] = {
    if(this.cols != that.rows)
      throw new IllegalArgumentException("Can't be multiplied")
    else {
      val newArr = Array.ofDim[T](this.rows, that.cols)

      for(i <- 0 to this.rows-1) {
        for(j <- 0 to that.cols-1) {
          newArr(i)(j) = this.row(i).zip(that.col(j)).map(a => a._1 * a._2).sum(n)
        }
      }
      new Matrix(newArr)(n)
    }
  }

  /* ------------ More Matrix Operations ----------- */
}

object Matrix {

  def apply[T](elems: Array[Array[T]])(implicit n: Numeric[T],m: ClassManifest[T]): Matrix[T] =
    new Matrix[T](clone(elems))(n)

  private def clone[T: ClassManifest](arr: Array[Array[T]]): Array[Array[T]] = arr.map(_.clone)
}