I am new to logic and cannot figure out if there are instances when a given set of binary sequences of equal length is not possible to express as a conjunctive or disjunctive normal form. If such sets exist, does it mean that the sequences do not form some sort of closure? If they exist, how restrictive the requirement that CNF/DNF is possible is? In other words, how likely is it, by means of a true random number generator, to stumble over sets that are not expressible in CNF/DNF form. If a given set can be expressed as CNF, can it also be converted to a DNF and vice versa? Sorry if it is too elementary for this forum.

  • $\begingroup$ How do you go from a "set of binary sequences" to boolean logic? $\endgroup$ May 16 at 14:38
  • $\begingroup$ @JulioDiEgidio, for instance here, page 235: doi.org/10.1016/0004-3702(94)00032-V $\endgroup$
    – MsTais
    May 16 at 17:01
  • $\begingroup$ AND, XOR, NAND... all those are sets of binary sequences of length 3 that can be trivially formed into a boolean formula. One could think of large cardinality sets like that, that also can be expressed in a single boolean sentense. $\endgroup$
    – MsTais
    May 16 at 17:03
  • $\begingroup$ @JulioDiEgidio, thanks for the suggestion. That paper is the motivation. Essentially, the author is building an associative memory, but it is all applied to k-CNF. I have sets that his approach works for, but it doesn't work for any random sequence. This made me think that k-CNF condition on a set is in fact quite restrictive. I just wanted to double-check with those who actually know logic. $\endgroup$
    – MsTais
    May 16 at 17:43


You must log in to answer this question.

Browse other questions tagged .