1
$\begingroup$

The question has already posted here before:
Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)
But I came up with a different proposal for a solution in which I am trying to prove that the given set of connectives is inadequate using a property that is true for every proposition that is built using this set of connectives.
Need to show that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its propositions are $T$.
I noticed that the following property holds :

For every truth assignment $v$ and for every proposition $\phi$ that is built using the given set $\{\lnot ,G\}$ we get that $v(\phi) \neq v^C(\phi)$ when $v^C$ is defined to be the opposite truth assignment

Now I tried to formalize this using structural induction but I got stuck on the inductive step, I'll appreciate any help

$\endgroup$
2
  • $\begingroup$ @Bram28 I mean that for any truth assignment of atomic propositions then the $V^C(\phi) != v(\phi)$ holds for any proposition that is built using the given connectives. $\endgroup$
    – Yarin
    Commented Apr 20, 2023 at 17:50
  • 1
    $\begingroup$ Oh, I see! OK, then yes, that approach totally works! I'll sketch the inductive proof pattern in an Answer momentarily $\endgroup$
    – Bram28
    Commented Apr 20, 2023 at 18:43

1 Answer 1

2
$\begingroup$

Here is the proof that for any $v$ and $\phi$ it is true that $v^C(\phi) \neq v(\phi)$ (i.e. that $v^C(\phi)$ and $v(\phi)$ always have the opposite truth-value).

We take any $v$, and now do structural induction on $\phi$:

Base: $\phi = P$ for some atomic proposition $P$. Given that by definition $v^C(P)$ is the opposite of $v(P)$, we have that $v^C(\phi)$ and $v(\phi)$ have the opposite truth-value as well.

Step: There are two cases to consider:

A. $\phi = \neg \psi$, where by inductive hypothesis we have that $v^C(\psi)$ and $v(\psi)$ have the opposite truth-value. By semantics of $\neg$, we have that $v(\psi)$ and $v(\neg \psi)$ have opposite truth-values, and we also have that $v^C(\psi)$ and $v^C(\neg \psi)$ have opposite truth-values. So, $v^C(\phi) = v^C(\neg \psi)$ has the opposite value of $v^C(\psi)$. But since by inductive hypothesis $v^C(\psi)$ has the opposite value of $v(\psi)$, that means that $v^C(\phi)$ has the same truth-value as $v(\psi)$ .... but that has the opposite truth-value as $v(\phi)$.

B. $\phi = G(\psi_1, \psi_2,\psi_3)$, where by inductive hypothesis we have that $v^C(\psi_i)$ and $v(\psi_i)$ have the opposite truth-value for $1 \leq i \leq 3$. Now, $v^C(\phi)$ evaluates to True iff the majority of $v^C(\psi_i)$ evaluates to True iff (Inductive Hypothesis) the majority of $v(\psi_i)$ evaluates to False iff $v(\phi)$ evaluates to False. (in that last step, we use the fact that $G$ takes an odd number of argument, so there is always either a majority of argument that evaluate to True, or a majority of argument that evaluate to False.). So, $v^C(\phi)$ and $v(\phi)$ will have opposite truth-values.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .