1

$$\begin{array}{cc|c} P & Q & P!Q \\ \hline T & T & F \\ T & F & T \\ F & T & F \\ F & F & F \end{array}$$

I think this should be proved using induction but I have no idea where to start.. Thanks

ZZS14
  • 819
  • 1
    What does adequate mean in ths context? – Hagen von Eitzen Feb 20 '14 at 14:17
  • A set S of connectives is adequate if and only if there are formulas involving only connectives from S which are logically equivalent to (p1^p2), (p1vp2) and (-p1) [not p] – ZZS14 Feb 20 '14 at 14:21
  • I showed how to do this kind of induction proof over here: http://math.stackexchange.com/questions/670531/show-that-s-wedge-leftrightarrow-are-not-an-adequate-set-of-connectives/670931#670931 – rhenderson Feb 20 '14 at 14:26
  • I don't follow it. – ZZS14 Feb 20 '14 at 14:38

2 Answers2

3

The $False!False \rightarrow False$ is where you should encounter problems. Any formula with just $!$, when you plug in all values $False$, will return $False$. This means you cannot express all truth tables with just $!$.

5xum
  • 123,496
  • 6
  • 128
  • 204
1

Suppose that $E$ is any expression built up from $!$ and from $p$. You can show, by induction, that when $p$ is false, $E$ is also false. But then $E$ is not equivalent to $\lnot p$, because $\lnot p$ is true when $p$ is false. So no expression built up from just $!$ and $p$ can express $\lnot p$, and therefore $!$ is not adequate.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • how would i use induction for this? – ZZS14 Feb 20 '14 at 17:44
  • Let's say that an expression is "good" if it has the property that it is false whenever all its atoms are false. For example $A\land B$ is good, but $\lnot A$ is not good. Let $P(n)$ be the claim that every expression with $n$ or fewer $!$ operators is good. $P(0)$ is true because an expression with no operators is an atom, and atomic expressions are good. Then using induction to prove $P(n)$ for all $n$. – MJD Feb 20 '14 at 17:56