2
$\begingroup$

I have a tautology and I need to write its CNF(Conjunction Normal Form). Since its a tautology CNF will not have any element. So should I write 1 in it or 0 ?

  • 0
    Your question seems a little vague, could you be more clear about "since it's a tautology it will not have any element"? Maybe also give the tautology you are trying to put in DNF?2011-09-14
  • 0
    @Jeroen: Sorry, edited the question its CNF not DNF.2011-09-14
  • 2
    Edit the title, too, if that is what you want.2011-09-14

3 Answers 3

0

A conjunctive normal form qualifies as a well-formed formula, or equivalently formula. Does your language allow "1" or "T" as formal symbols? If so, then GEdgar's response works. If not, then (p∨¬p) probably will work if you're using a language with an infix notational scheme. If you use Polish notation, you'd write ApNp, and in reverse Polish notation you'd write ppNA. Gadi's comment on Asaf's post indicates these might work, though I don't know precisely the definition of a cnf needed here.

  • 3
    Have you actually found anyone else that writes $ppNA$ *ever*?2011-09-14
  • 0
    @Mariano What's your point? I mean, who cares if anyone else has written it out by hand? Why not write a book or article on logic in reverse Polish notation, since so many computer languages already use such a schematic? The pair of elements comes first always, so if you look at tables to do computations by hand, and you read left to right usually, you immediately see which elements to find in the table before finding the entry where they intersect in the table. You don't have to look around operation symbols, the elements appear on the left first in order. So, some advantage exists.2011-09-14
  • 2
    My point is, your "If you use Polish notation..." sentence is quite irrelevant (and hence not helpful in the context of you answering this specific question) You surely do not think anyone uses that notation!2011-09-14
  • 0
    @Mariano You didn't have such a sentence. Polish notation has, and still does get used, as evidenced by here http://web.ics.purdue.edu/~dulrich/Home-page.htm. Since cnfs are statement forms, how you write a cnf other than "1" comes as local to how you've defined a statement form. Also, the use of *reverse* Polish notation (RPN) can make derivation of some theorems simpler. For instance, in RPN, pqC==pqNKN, where C indicates the material conditional, N negation, and K connjuction. So, for any theorem with a "C" in it, we can mechanically replace any instance of "C" by "NKN" and obtain a2011-09-14
  • 0
    theorem. We can't do this in infix notation, because of the need for parentheses. Your initial response had a sentence concerning *reverse* Polish notation.2011-09-14
  • 0
    @Mariano You can also find people who still use RPN calculators, and speak about their advantages. Doesn't it seem probable that such people might actually like a logic book or article if it got written in RPN? And people already have actually used the scheme in mathematics in certain places, just not all over the place, see the Schaum's outline of Group Theory, or Gratzer's Universal Algebra, or Cohn's book on universal algebra. So though I may not have seen ppNA used by someone else before, I simply don't see why you think that relevant. If Asaf's answer works, ppNA is a cnf somewhere.2011-09-14
  • 1
    You must be a great success as parties...2011-09-14
  • 0
    I don't go to parties all that often, and I certainly don't talk about this sort of thing in the very rare cases that I do.2011-09-15
4

Recall that $\varphi$ is in CNF if $\varphi = \varphi_1\land\cdots\land\varphi_k$ where $\varphi_i$ is a disjunction of atomic propositions and their negations.

Suppose $p$ is an atomic proposition (e.g. a propositional variable)

$$(p\lor\lnot p)$$

  • 0
    that's not a tautology but a contradiction2011-09-14
  • 0
    @Jeroen: Whoops, you are of course right. I have remedied the problem.2011-09-14
  • 0
    Now it is disjunctive normal form. Is that what the OP wants?2011-09-14
  • 0
    @GEdgar: CNF is a conjunction of smaller propositions made of variables, negations and disjunction. This is form is CNF as well DNF.2011-09-14
  • 0
    Wikipedia: *In Boolean logic, a formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals, where a literal and its complement cannot appear in the same clause.*2011-09-14
  • 0
    @GEdgar: When I was taught about CNF in my freshman year; and when I was a TA in a course covering this material - we did not introduce that last rule.2011-09-14
  • 1
    @GEdgar: Note, also that on the last which you have quoted there is a [citation needed] tag.2011-09-14
  • 0
    @GEdgar The Schaum's Outline of Boolean Algebra, written by Elliott Mendelson whom I think a rather authoritative source here, on p. 22 reads "By a *fundamental disjunction* we mean either (i) a literal or (ii) a disjunction of two or more literals no two of which involve the same statement letter. One fundamental disjunction A is said to be *included* in another B if all the literals of A are also literals of B. A statement form A is in *conjunctive normal form* (cnf) if either (i) A is fundamental disjunction or (ii) A is a conjunction of two or more fundamental disjunction of which none2011-09-14
  • 0
    is included in another." Other than the issue that Asaf's p∨¬p isn't actually a "statement form" (wff or formula), which I feel sure he could quickly fix here, what he means does qualify as a fundamental disjunction and thus does lie in cnf. In other words (p∨¬p) does qualify as a fundamental disjunction, and thus does lie in cnf under Mendelson's definition at least.2011-09-14
  • 1
    There is that pesky clause: *no two of which involve the same statement letter*; but here p and ¬p do both involve p.2011-09-14
  • 1
    Asaf, you might want to add parenthesis so it will be obvious this is a CNF clause and not 2 DNF clauses2011-09-14
  • 0
    @GEdgar You're right. I missed that. (p∨¬p) is not a cnf under this definition then. So, if you don't have "1" or "T" in the language, can you have a cnf of a tautology, or a dnf of a contradiction?2011-09-14
  • 0
    No CNF is a tautology precisely because of the fact that all letters have to be distinct in a clause.2011-09-14
  • 2
    That seems to be to be a matter of definition. Usually in complexity theory (where CNF's arise naturally in the SAT problem) the "no two" restriction is useless and bothersome and so is not used. See for example Sipser of Arora-Barak.2011-09-14
  • 0
    Yes, the Schaum definition says a fundamental disjunction or a conjunction of two or more fundamental disjunctions... So a tautology has no CNF. Better would be to allow a finite conjuction of fundamental disjunctions, and remembering that zero is finite. Then the CNF is the empty conjunction as in my answer.2011-09-14
  • 0
    @GEdgar I'm not so sure The Schaum's definition is that authoritative. See the post here for more details: http://dougspoonwood.blogspot.com/2011/09/is-apnp-conjunctive-normal-form.html (Hilbert no doubt read Bernays thesis in the original language and they both were native German speakers). I'd classify Asaf's (p∨¬p) as a CNF. "1" or "T" only qualify as CNFs on the condition that they qualify as formulas (wffs) in the first place, and that's at least not always the case. Also, consider Merrie Bergmann's definition as follows from An Introduction to Many-Valued and Fuzzy Logic:2011-10-19
  • 0
    "We define a clause as: 1. A literal is a clause. 2. If P and Q are clauses, so is (P v Q), and conjunctive normal form as: 1. Every clause is in conjunctive normal form. 2. If P and Q are in conjunctive normal form, so is (P^Q).2011-10-19
3

CNF for a tautology presumably is a conjunction of no terms. So just write $1$ for it. Or $T$. Depending on your notation.

  • 0
    Sometimes the definitions forbid use of constants, so Asaf's method is slightly better.2011-09-14
  • 0
    @Gadi: except that Asaf's method is also not allowed. (Since all letters must be distinct in a clause.)2011-09-14