Convert a logical expression to conjunctive normal form

You're going to hate me....

Mathematica, 23 bytes

#~BooleanConvert~"CNF"&

The input will use True and False instead of and , but otherwise will look very similar to the notation of the question: all of the characters ¬, , , , and are recognized in Mathematica (when input with UTF-8 characters 00AC, F523, 29E6, 2227, and 2228, respectively), and parentheses act as you would expect.

By default, the output will use Mathematica's preferred symbols: for example, the last test case will output (! P || ! Q || R) && (! P || Q || ! R) instead of ((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R))). However, changing the function to

TraditionalForm[#~BooleanConvert~"CNF"]&

will make the output look pretty and conforming to these usual symbols:

traditional form


JavaScript (ES6), 127 bytes

f=(s,t='',p=s.match(/[A-Z]/),r=RegExp(p,'g'))=>p?'('+f(s.replace(r,1),t+'|'+p)+')&('+f(s.replace(r,0),t+'|!'+p)+')':eval(s)?1:0+t

I/O format is as follows (in order of precedence):

  • (: (
  • ): )
  • : 1
  • : 0
  • ¬: !
  • : <=
  • : ==
  • : &
  • : |

Examples:

P&(P<=R) -> ((1)&(0|P|!R))&((0|!P|R)&(0|!P|!R))
P==(!P) -> (0|P)&(0|!P)
(!P)|(Q==(P&R)) -> (((1)&(0|P|Q|!R))&((0|P|!Q|R)&(1)))&(((1)&(1))&((1)&(1)))

The function is trivially rewritten to produce disjunctive normal form:

f=(s,t='',p=s.match(/[A-Z]/),r=RegExp(p,'g'))=>p?'('f(s.replace(r,1),t+'&'+p)+')|('+f(s.replace(r,0),t+'&!'+p)+')':eval(s)?1+t:0

8 bytes could be saved from this version if I was allowed to assume the above precedence on output too, which would remove all the parentheses from the output examples:

P&(P<=R) -> ((1&P&R)|(0))|((0)|(0))
P==(!P) -> (0)|(0)
(!P)|(Q==(P&R)) -> (((1&P&Q&R)|(0))|((0)|(1&P&!Q&!R)))|(((1&!P&Q&R)|(1&!P&Q&!R))|((1&!P&!Q&R)|(1&!P&!Q&!R)))