1

I am having issues solving this problem and I believe I would benefit if someone could help me break it down into simpler terms to perhaps give me a starting point. I tried applying DeMorgan's Law to the first line but I don't know what to do next or if that's even right.

$\exists x(A(x) \wedge \neg B(x))$

$\forall x(A(x) \rightarrow C(x))$

$\therefore \exists x(C(x) \wedge \neg B(x))$

adamaero
  • 127
M.M.
  • 19
  • Certainly. This is my first time using this platform so I'm still getting use to it. I tried solving the first part of the problem using DeMorgan's law and thought Modus Ponens might have worked for the 2nd step but I'm unsure if this is correct. – M.M. May 27 '20 at 16:54
  • Which inference rules are you allowed to use? Do you understand the inference rules in @F.Zer's answer? – Taroccoesbrocco May 27 '20 at 19:08

2 Answers2

1

$ \def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} \def\Ae#1{\qquad\mathbf{\forall E} \: #1 \\} \def\Ai#1{\qquad\mathbf{\forall I} \: #1 \\} \def\Ee#1{\qquad\mathbf{\exists E} \: #1 \\} \def\Ei#1{\qquad\mathbf{\exists I} \: #1 \\} \def\R#1{\qquad\mathbf{R} \: #1 \\} \def\ci#1{\qquad\mathbf{\land I} \: #1 \\} \def\ce#1{\qquad\mathbf{\land E} \: #1 \\} \def\oi#1{\qquad\mathbf{\lor I} \: #1 \\} \def\oe#1{\qquad\mathbf{\lor E} \: #1 \\} \def\ii#1{\qquad\mathbf{\to I} \: #1 \\} \def\ie#1{\qquad\mathbf{\to E} \: #1 \\} \def\be#1{\qquad\mathbf{\leftrightarrow E} \: #1 \\} \def\bi#1{\qquad\mathbf{\leftrightarrow I} \: #1 \\} \def\qi#1{\qquad\mathbf{=I}\\} \def\qe#1{\qquad\mathbf{=E} \: #1 \\} \def\ne#1{\qquad\mathbf{\neg E} \: #1 \\} \def\ni#1{\qquad\mathbf{\neg I} \: #1 \\} \def\IP#1{\qquad\mathbf{IP} \: #1 \\} \def\x#1{\qquad\mathbf{X} \: #1 \\} \def\DNE#1{\qquad\mathbf{DNE} \: #1 \\} $

The first premise says that something satisfies $A(x)$ and $\neg B(x)$. So, we can start making a substitution instance for it (heading towards the use of Existential Elimination). In my case, is a. Then, the second premise says that everthing satisfies $A(x) \to C(x)$. We can use Universal Elimination and choose that same name a. That decision enables the use of the other rules of inference.

As a next step, you will need to provide proofs of $C(a)$ and $\neg B(a)$.

$ \fitch{ 1.\, \exists x(A(x) \land \neg B(x))\\ 2.\, \forall x(A(x) \to C(x)) }{ \fitch{3.\, A(a) \land \neg B(a)}{ 4.\,A(a) \to C(a) \Ae{2} \vdots\\ k.\,C(a)\\ \vdots\\ l.\, \neg B(a)\\ \vdots }\\ m. \exists x(C(x) \land \neg B(x)) } $

Can you see how to fill the blanks ?

F. Zer
  • 2,325
  • 1
  • 8
  • 21
0

  1. $\exists x(A(x) \wedge \neg B(x))$ premise

  2. $\forall x(A(x) \rightarrow C(x))$ premise

  3. $A(k) \wedge \neg B(k)$ by existential instantiation, 1

  4. $A(k) \rightarrow C(k)$ by universal instantiation, 2

  5. $A(k)$ by conjunction elimination, 3

  6. $C(k)$ by modus ponens, 4,5

  7. $\neg B(k) \wedge A(k)$ by commutativity, 3

  8. $\neg B(k)$ by conjunction elimination, 7

  9. $C(k) \wedge \neg B(k)$ by conjunction introduction, 6,8

  10. $\exists x(C(x) \wedge \neg B(x))$ by existential generalization, 9

RyRy the Fly Guy
  • 5,950
  • 1
  • 11
  • 27