How to prove a prepositional formula operator statement.

63 Views Asked by At

We have a three-digit operator $<X,Y,Z>$. Let $\phi_1, \phi_2,\phi_3 \in \text{AL}$ be an arbitrary prepositional formula and let $\beta$ be an assignment that matches these three formulas. The semantics of our new operator are defined as follows: $$ [\![ <\phi_1, \phi_2,\phi_3> ]\!] = \begin{cases} 1 & \text{if $[\![ \phi_1 ]^{}\!]$}^{\beta} = 1\ \text{and} \ \text{min}([\![ \phi_2]\!]^{\beta},[\![\phi_3 ]\!]^{\beta})=0, \ \text{or} \ \text{if $[\![ \phi_1 ]^{}\!]$}^{\beta} = 0\ \text{and} \ [\![ \phi_2 ]^{}\!]^{\beta}=[\![ \phi_3 ]^{}\!]^{\beta} \\ 0 & \text{otherwise} \end{cases} $$

We have that $\phi_1, \phi_2,\phi_3 \in \text{AL}$. How can I show that for every prepositional logic form $\phi \in \text{AL}$ there exists an equivalent form $\phi'$ which only uses the new three-digit operator?

1

There are 1 best solutions below

0
On

HINT

To show this, you need to show that every one of the original propositional logic operators ($\neg, \land, \lor, ...$) can be captured using this new $3$-argument operator. This is, to some extent, a bit of trial and error.

For example, let's see how we can capture the $\neg$. That is, let's try and find a formula that only uses this new $< , , >$ operator that captures $\neg \phi$. Now, first of all, since the $\neg$ works on only one statement $\phi$, we have only this one statement to use in our new formula. So, we can consider formulas like $< \phi, <\phi, \phi, \phi>, \phi>$ or $< <\phi, \phi, \phi>, \phi, <\phi, \phi, <\phi, \phi, \phi>> >$ or ...

But, let's start simple, and first see what $< \phi, \phi, \phi>$ gives us. ... maybe we are lucky, and that one will already give us $\neg \phi$. So, let's see:

Well, if $[\![ \phi ]^{}\!]^\beta = 1$, then $\text{min}([\![ \phi ]^{}\!]^\beta, [\![ \phi ]^{}\!]^\beta)=1$, and so $[\![ <\phi, \phi,\phi> ]\!]^\beta = 0$.

On the other hand, if $[\![ \phi ]^{}\!]^\beta = 0$, then $[\![ \phi ]^{}\!]^\beta = [\![ \phi ]^{}\!]^\beta)$, and so $[\![ <\phi, \phi,\phi> ]\!]^\beta = 1$.

Ha! So we are lucky, as we find that $<\phi, \phi,\phi> $ evaluates to $\neg \phi$ no matter what!

OK, so we now know how we can express $\neg$

Now we should figure out how we can express all other operators $\land$, $\lor$, ... using the new operator as well. For example, you could evaluate $<\phi_1, \phi_2, \phi_2>$, and see what happens. If it captures any of $\phi_1 \land \phi_2$ or $\phi_1 \lor \phi_2$ or $\phi_1 \to \phi_2$, great! If not, try something else. Again, this will take some trial and error.

But, there is some good news. Since we already know that every propositional logic operator can be captured using $\neg $ and $\land$ alone, you are actually done as soon as you find a way to capture the $\land$, since we already have the $\neg$ covered. In fact, $\{ \lor, \neg \}$ and $\{ \to, \neg \}$ are expressively complete as well, so if you find $\lor$ or $\to$, you are done as well.

OK, good luck!

Here, by the way, is my answer:

It turns out that $<\phi_1, \phi_2, \phi_2>$ is equivalent to $\phi_1 \ \text{NAND} \ \phi_2$, and $\{ \text{NAND} \}$ is expressively complete all by itself. So, done!