How can I convert a clause of size 3 that is made of 2 OR gates


(x1 OR x2 OR x3 )

to one or more clauses of size 4 made only of NAND gates and not gates? So without parentheses inside the clauses.


(x1 NAND x2 NAND x3 NAND x4) 
(not x1 NAND x2 NAND not x3 NAND not x4) AND (x1 NAND x2 NAND x3 NAND x4)

additional notes: The original question asked is to prove that 4-SATCNF (A CNF expression that can be satisfied, with clauses of size 4 and with NAND gates between the 4 terms.) is NP-Complete by showing the polynomial reduction of 3-SAT <=p 4-SATCNF. I'm stuck at the part where I need to find a function for the reduction. I suppose the function should be something around the form showed above, if not can somebody helped me find the good function?

Thank You

Articles that I consulted so far:

3-Sat to 4-sat polynomial conversion: https://www.csie.ntu.edu.tw/~lyuu/complexity/2012/20121106s.pdf

NAND Conversion: https://en.wikipedia.org/wiki/NAND_logic

  • $\begingroup$ What have you tried? Can you express your example (x1 OR x2 OR x3) in the desired form? If not, keep trying. Note that you can introduce extra variables if you want... $\endgroup$
    – D.W.
    Commented Nov 27, 2017 at 22:45
  • $\begingroup$ That's the problem I can't find a way to express (x1 OR x2 Or x3) in the desired form. I found a paper talking about polynomial reduction of 3SAT to 4SAT which does state that I can use a 4th variable and 2 clauses liked by a AND, but since I can't find a solution to converting the 2 OR gates into NAND I'm not sure if it is useful or not. I read a few articles on NAND conversion so I know that x1 OR x2 == not x1 NAND not x2. With that I can solve the problem if I use parentheses, but I'm not allowed to. From there I tried a bunch of different combination of gates, but none were equivalent. $\endgroup$
    – itachi737
    Commented Nov 27, 2017 at 23:21
  • $\begingroup$ If somebody could help me find the conversion of the exemple or point me towards a similar exemple. I'm pretty confident I could derive the function from it by myself, but I just can't seem to find a solution to the example. @D.W. $\endgroup$
    – itachi737
    Commented Nov 27, 2017 at 23:31
  • $\begingroup$ Start with not (a or b) = (not a) and (not b). Do you really have to consult a paper for this? $\endgroup$
    – gnasher729
    Commented Dec 28, 2017 at 23:42

2 Answers 2


(x1 or x2 or x3) = (not x1 NAND not x2 NAND True NAND not x3)

  • 1
    $\begingroup$ How did you get there? What's the idea? How does one see that it's correct? $\endgroup$
    – Raphael
    Commented Nov 30, 2017 at 7:59
  • $\begingroup$ How I got there? Trial and Error. The way I verified it is by doing all the solutions. you only have 3 variables and 2 possible values per variable so you only have to try 2^3 = 8 combinations. So if x1 = 1 x2 = 1 x3 = 1. You would have not 1 nand not 1 nand 1 nand not 1 = 0 nand 0 nand 1 nand 0 = 1 nand 1 nand 0 = 0 nand 0 = 1 so that true. Do the same thing for the other 7. $\endgroup$
    – itachi737
    Commented Jan 17, 2018 at 15:42

We start with

NAND (a, b) := NOT (a AND b) = (NOT a) or (NOT b)
a = NOT NOT a

a OR b or c = 
a OR (b OR c) = 
(NOT NOT a) OR (NOT NOT (b OR c)) = 
NAND (NOT a, NOT (b OR c)) =
NAND (NOT a, NOT ((NOT NOT b) OR (NOT NOT c))) =
NAND (NOT a, NOT (NAND (NOT b, NOT c))).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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