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:
- Some random logic expressions based on common negation of three given variables
- 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
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}