Tutorial list 4

1

1. We assume $P$ and $P\to Q$ to be true. If $P$, then $\top \to Q$, hence $Q$ must be true. We are trying to prove $Q$ symantically entails from $P,P\to Q$ hence the argument is true.

2. Assume $P\to Q$ is true. $P$ and $Q$ may either be true or false. Consider when $P=0$, $Q=1$. $P\to Q=0\to 1=1$ But $Q\to P=1\to 0=0$ Hence the argument is false.

3. Assume $P\vee \neg Q$ is true. We know neither $P$ is true or false nor $Q$ is true or false hence we cannot deduce that $P$ must be true since we don’t know anything about $Q$. Let $P=0$ and $Q=0$, hence $0\vee 1\to 0=0$. The argument is false.

4. Assume $P\wedge \neg P$ is true. $P\wedge \neg P$ is a contradiction. Since there are no models to contradict $Q$ being true, we assume $Q$ is true. The argument is true.

   I should’ve gone with my original though, this is always false as $P\wedge \neg P$ is a contradiction.

   Anything can follow from a contradiction.

title: Partially correct.

2

• $R\vee W$
• $\neg R\vee L$

When it is raining, they go to the library. When it is not raining, they work in the yard.

Therefore they either go to the library or work in the yard.

title: Correct answer.

3

Let $A$ and $B$ be propositional formulae. Demonstrate that if there exists that $C\models A$ and $\neg C\models B$. Then the formula $A\vee B$ is a tautology.

Lets assume $C$ is $c$. Let $A$ also be $c$ hence $C\models A$ which is equivalent to $c\models c$. Let $B$ be that $\neg c$ hence $\neg C\models B$ which is equivalent to $\neg c\models \neg c$.

Hence the formula $A\vee B=c\vee \neg c$ which we know is a tautology as either $c$ is true or false, which always makes the formula true.

title: Wrong answer.
Should do proof by contradiction.
Suppose that $C \models A$ and $\neg C \models B$ but $A \lor B$ is not a tautology.
Since $A \lor B$ is not a tautology, then there is a valuation $v$ such that $v(A) = 0$ and $v(B) = 0$.
Since $C \models A$ it follows that $v(C) = 0$.
Hence $v(\neg C) = 1$.
 
Therefore, $\neg C \not \models B = 1 \not \models 0$ which contradicts our initial assumption.
 
Hence, if $A$ is a logical consequence of $C$ and $B$ is a logical consequence of $\neg C$ then, for some formula $C$, the formula $A \lor B$ is a tautology.

4

1. “If $n$ is a real number such that $n>1$, then $n^2>1$” “Suppose, $n^2>1$, then $n>1$.” Consider that $n^2=4$, $n$ could be $2$ or $-2$. Hence $n^2>1\to n>1$ does not hold when $n=-2$. As we find $\top \to \perp$ which is false.

   title: Correct answer.
   We can formally define this as:
   - $P(n) = \text{that } n > 1$
   - $Q(n) = \text{that } n^2 > 1$
    
   Consider $n = -2$.
    
   $$
   	\begin{aligned}
    	P \rightarrow Q, Q &\models P \\
    	0 \rightarrow 1, 1 &\models 0 \\
    	1, 1 &\models 0
    \end{aligned}
   $$
    
   Fallacy of affirming the conclusion.

2. “If $n$ is a real number such that $n>3$, then $n^2>9$” “Suppose, $n^2\le 9$, then $n\le 3$.” This argument is correct and uses the inference:

   $$\frac{A\to B}{\neg B\to \neg A}$$

   interpretation	$a$	$b$	$\neg a$	$\neg b$	$a\to b$	$\neg b\to \neg a$
   $v_0$	0	0	1	1	1	1
   $v_1$	0	1	1	0	1	1
   $v_2$	1	0	0	1	0	0
   $v_3$	1	1	0	0	1	1

   title: Correct answer.
   Can once again formally define as:
   - $P(n) = \text{that } n > 3$
   - $Q(n) = \text{that } n^2 > 9$
    
   Suppose $n^2 \le 9$ then $n \le 3$:
   $$
   	\begin{aligned}
    	P \rightarrow Q, \neg Q &\models \neg P \text{ (modus tonens)} \\
    	\\
    	\text{When } P = 1, Q &= 0 \\
    	1 \rightarrow 0, 1 &\models 0 \\
    	0, 1 &\models 0 \\
    	\\
    	\text{When } P = 1, Q &= 1 \\
    	1 \rightarrow 1, 0 &\models 0 \\
    	1, 0 &\models 0
    \end{aligned}
   $$

3. “If $n$ is a real number such that $n>2$, then $n^2>4$” “Suppose, $n\le 2$, then $n^2\le 4$.” Take, $n=-8$, $n^2$ is $64$. Hence this argument does not hold.

   title: Correct answer.
   Formal definition:
   - $P(n) = \text{that } n > 2$
   - $Q(n) = \text{that } n^2 > 4$
    
   $$
   	P \rightarrow Q, \neg P \models \neg Q
   $$
    
   Fallacy of denying the hypothesis.