Given formulas $P$, $Q$ and a variable $x$, define the operators $\wedge,\vee$ and the quantifier $\exists$ in terms of the operators $\lnot,\implies$ and the quantifier $\forall$.

$1)$ $$\qquad P\wedge Q \quad = \quad \lnot \left( P \implies \lnot Q \right)$$

$2)$ $$ \qquad P\vee Q \quad = \quad \lnot P \implies Q$$

$3)$ $$ \qquad P\iff Q \quad = \quad P\implies Q \;\wedge \;Q\implies P$$

$4)$ $$\exists\, x : P(x) \quad = \quad \lnot \forall\, x : \lnot P(x) $$

Are these correct? What is the best way to prove this without the use of truth tables?

  • 4
    $\begingroup$ $\exists xP(x)\equiv \neg \forall x \neg P(x)$ $\endgroup$ – Reveillark Jan 27 '17 at 21:43
  • 1
    $\begingroup$ The third one isn't right, as $P\iff Q$ isn't a tautology, whereas $P\land Q \implies Q \land P$ is. You must've mistaken $\land $ and $\implies$ ;) The fourth one should be $\exists x, P$ if and only if $\neg \forall x, \neg P$ $\endgroup$ – Max Jan 27 '17 at 21:44
  • 1
    $\begingroup$ @TheStrikeofRunningWater, use $A \to B \iff \neg A \vee B$ in 1),2),3).. $\endgroup$ – mle Jan 27 '17 at 21:56
  • 1
    $\begingroup$ Seems fine to me. Though be careful that these are only true in classical logic (e.g. not in intuitionistc logic) $\endgroup$ – Max Jan 27 '17 at 22:03
  • 1
    $\begingroup$ Use truth tables to convince you that the first three are correct. $\endgroup$ – miracle173 Jan 28 '17 at 7:09

The first, second & fourth are fine; however the third is in need of brackets.

It should instead be written


While $\ref{3}$ may be correct under some order of operations defined in your textbook; it is usually better to use brackets, because there is no agreed upon order of operations in logic.

The best way to prove each of these are correct without the use of truth tables is to simply use properties of each operator & Demorgan's Laws.

Negation of For all

  • $¬[\forall x\ P(x)] = \exists x\ ¬P(x)$

Equivalence of Implication

  • $A \to B = ¬A \lor B$

Demorgan's Law

  • $¬(A \lor B)=¬A \land ¬B$

Interestingly, (4) cannot be proved with truth tables.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy