The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

2

As also stated in the relevant Wikipedia page, you can do it by using the first two inputs (the control-bit and one of the target bits) as input for the reversible OR, and the third input bit fixed with the value 1. Then, the second output is what you want. To better see this, write the general action of a Fredkin on an input as following: $$\begin{pmatrix}... 2 I'm not sure how general this type of problem is so I can't tell you if this will always be the best approach, but in this case you can move the negation to the top for more clarity.$$\forall x\ \exists y\ \exists t\ [\neg F(x,y,t)]\equiv \forall x\ \exists y\ [\neg\ \forall t F(x,y,t)]\equiv \forall x\ [\neg\ \forall y\ \forall t F(x,y,t)]\equiv \neg [\...

4

Suppose $w$ is a world in an Euclidean frame, and $w\mathbin R v$, then by the Euclidean property $w$ reaches both of the "two" worlds $v$ and $v$ (indeed, the same world), and thus $v\mathbin R v$. So in a Euclidean frame, any world that is reachable from some other world, reaches itself (or every world with an incoming arrow has a reflexive arrow). Now, ...

1

It's true actually. As a hint, the Euclidean property $$xRy \quad\&\quad xRz \implies yRz$$ does not require the $x,y,z$ to be distinct. So for instance it implies $$xRy \quad\&\quad xRy \implies yRy.$$ Try to construct a counterexample model with 4 worlds $w,x,y,z$ where $\phi$ holds only in $z$ and where $wRx, xRy, yRz$.

Top 50 recent answers are included