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?
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