We're given a programming environment in which it is possible to introduce new logical variables and issue logical commands with operations AND, OR and NOT, such as A = (X AND Y) OR Z. However, TRUE and FALSE are not defined, so that it is NOT allowed to write A = X OR TRUE.

At the beginning, we are given three logical variables X, Y and Z, initialized to arbitrary values. We need to make a list of logical commands that in total contains AT MOST TWO operations NOT, so that after the commands are executed the variables X, Y and Z contain their respective negations.

I have tried several times to solve this using these ideas:

  1. Some random logic expressions based on common negation of three given variables
  2. Try to find out when the value of some negation is true based on number of true and false values.

None of these worked for me...

NOTE: I'm not sure if this task is solvable, but even if it has no solution, that has to be proved as well

  • $\begingroup$ Please help, thanks in advance ! $\endgroup$ – Veljko Toljic Feb 10 at 21:21
  • $\begingroup$ How would you solve the problem if TRUE and FALSE were available? $\endgroup$ – jobe Feb 11 at 12:16

The procedure is on the left, and on the right is written a formula equivalent to the one on the left. \begin{array}{rcl|cl} A_{xy}&=& X\land Y \\ A_{xz}&=& X\land Z \\ A_{yz}&=& Y\land Z \\ A_{xyz}&=& X\land Y\land Z \\ B&=&A_{xy}\lor A_{xy}\lor A_{yz} & \equiv& (X\land Y)\lor (X\land Z)\lor (Y\land Z)\\ C&=&\lnot B & \equiv& (\lnot X\lor\lnot Y)\land(\lnot X\lor\lnot Z)\land(\lnot Y\lor\lnot Z)\\ D_x&=& X\land C & \equiv& X\land\lnot Y\land\lnot Z\\ D_y&=& Y\land C & \equiv& \lnot X\land Y\land\lnot Z\\ D_z&=& Z\land C & \equiv& \lnot X\land\lnot Y\land Z\\ E&=&A_{xyz}\lor D_x\lor D_y\lor D_z & \equiv& (X\land Y\land Z)\lor (X\land\lnot Y\land\lnot Z)\ \lor\\&&&& (\lnot X\land Y\land\lnot Z) \lor (\lnot X\land\lnot Y\land Z)\\ F&=&\neg E & \equiv& (\lnot X\lor \lnot Y\lor \lnot Z)\land (\lnot X\lor Y\lor Z)\ \land\\&&&& ( X\lor\lnot Y\lor Z) \land ( X\lor Y\lor\lnot Z)\\ G_{xy} &=& A_{xy}\land F &\equiv & X\land Y\land \lnot Z\\ G_{xz} &=& A_{xz}\land F &\equiv & X\land\lnot Y\land Z\\ G_{yz} &=& A_{yz}\land F &\equiv & \lnot X\land Y\land Z\\ H&=& C\land F &\equiv & \lnot X\land \lnot Y\land \lnot Z\\ I_x&=&D_y\lor D_z\lor G_{yz}\lor H&\equiv &\lnot X\\ I_y&=&D_x\lor D_z\lor G_{xz}\lor H&\equiv &\lnot Y\\ I_z&=&D_x\lor D_y\lor G_{xy}\lor H&\equiv &\lnot Z\\ \end{array}

  • $\begingroup$ Thanks a lot, it works! $\endgroup$ – Veljko Toljic Feb 12 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.