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:
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)))