Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
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? –  user12205 Sep 14 '11 at 13:09
    
@Jeroen: Sorry, edited the question its CNF not DNF. –  Fahad Uddin Sep 14 '11 at 13:16
2  
Edit the title, too, if that is what you want. –  GEdgar Sep 14 '11 at 13:26

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
Sometimes the definitions forbid use of constants, so Asaf's method is slightly better. –  Gadi A Sep 14 '11 at 18:28
    
@Gadi: except that Asaf's method is also not allowed. (Since all letters must be distinct in a clause.) –  Grumpy Parsnip Sep 14 '11 at 18:49

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

share|improve this answer
    
that's not a tautology but a contradiction –  user12205 Sep 14 '11 at 13:21
1  
@GEdgar: Note, also that on the last which you have quoted there is a [citation needed] tag. –  Asaf Karagila Sep 14 '11 at 14:23
1  
There is that pesky clause: no two of which involve the same statement letter; but here p and ¬p do both involve p. –  GEdgar Sep 14 '11 at 18:21
1  
Asaf, you might want to add parenthesis so it will be obvious this is a CNF clause and not 2 DNF clauses –  Gadi A Sep 14 '11 at 18:29
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. –  Gadi A Sep 14 '11 at 18:59

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.

share|improve this answer
3  
Have you actually found anyone else that writes $ppNA$ ever? –  Mariano Suárez-Alvarez Sep 14 '11 at 18:29
    
@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. –  Doug Spoonwood Sep 14 '11 at 20:01
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! –  Mariano Suárez-Alvarez Sep 14 '11 at 20:24
    
@Mariano You didn't have such a sentence. Polish notation has, and still does get used, as evidenced by here 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 a –  Doug Spoonwood Sep 14 '11 at 21:20
1  
You must be a great success as parties... –  Mariano Suárez-Alvarez Sep 14 '11 at 22:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.