I have to show that the set $C=\{\to , \lor \}$ is not a functionally set. I think that I have to find a connective that is not possible to replicate with the connectives of my set C. But how I can proceed to show it? Sorry for my english, I'm Italian. Thanks for the attention.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Hint: With these connectives you can only produce two of the four possible one-input truth functionals you can produce.
Prove by structural induction that every expression built from $\to$, $\lor$, and a single variable represents one of these two truth functions.
answered Jan 6, 2014 at 15:57
hmakholm left over Monicahmakholm left over Monica
288k24 gold badges433 silver badges696 bronze badges
-
$\begingroup$ sorry but I don't understand in what I have to the induction. For example how is the base of the induction?If I pick one variable, $p \to p $ and $p \lor p$ give me two different truth table...thanks $\endgroup$ Commented Jan 6, 2014 at 16:32
-
$\begingroup$ @andreasvr: The base of structural induction is the simplest possible expression: one variable alone. Yes, $p\to p$ and $p \lor p$ give two different truth tables, but there are two other truth tables that you cannot produce with $\to$ and $\lor$ alone. $\endgroup$ Commented Jan 6, 2014 at 16:39
-
$\begingroup$ Yes yes, sorry but only now I have understand your precious hint...I try to explain what I have understand... The base of the induction show me that picked p that has truth values $(1,0)$, $p \to p$ goes to $(1,1)$ and $p \lor p$ goes to $(1,0)$. $\endgroup$ Commented Jan 6, 2014 at 16:46
-
$\begingroup$ @andreasvr: Yes. So what you have to prove for the induction step is that if $\varphi(p)$ and $\psi(p)$ each have one of those two truth tables, then so do $\varphi(p)\to\psi(p)$ and $\varphi(p)\lor\psi(p)$. $\endgroup$ Commented Jan 6, 2014 at 16:49
-
$\begingroup$ Sorry but only now I understood your precious hint. I try to explain... The base of the induction show me that picked p with truth values $(1,0)$, $p \to p$, $p \lor p$ go respectively to $(1,1)$,$(1,0)$. Now let's $\alpha$ a formula with n+1 connectives of types $\to$ or $\lor$. I assume for inductive hypotesis that for n connectives my truth table is $(1,1)$ or $(1,0)$. So $\alpha=\psi \to p$ or $\alpha= \psi \lor p$. Proceeding by induction the truth table of $\psi$ is $(1,1)$ or $(1,0)$.I have only to show that $\psi \to p$ or $\alpha= \psi \lor p$ goes to $(1,1) or (1,0)$. $\endgroup$ Commented Jan 6, 2014 at 17:02