3

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 ?

  • 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? –  Sep 14 '11 at 13:09
  • @Jeroen: Sorry, edited the question its CNF not DNF. –  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 Answers3

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

Asaf Karagila
  • 393,674
  • that's not a tautology but a contradiction –  Sep 14 '11 at 13:21
  • @Jeroen: Whoops, you are of course right. I have remedied the problem. – Asaf Karagila Sep 14 '11 at 13:22
  • Now it is disjunctive normal form. Is that what the OP wants? – GEdgar Sep 14 '11 at 13:25
  • @GEdgar: CNF is a conjunction of smaller propositions made of variables, negations and disjunction. This is form is CNF as well DNF. – Asaf Karagila Sep 14 '11 at 13:27
  • 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. – GEdgar Sep 14 '11 at 14:07
  • @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. – Asaf Karagila Sep 14 '11 at 14:10
  • 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
  • @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 none – Doug Spoonwood Sep 14 '11 at 18:09
  • 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. – Doug Spoonwood Sep 14 '11 at 18:15
  • 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
  • @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? – Doug Spoonwood Sep 14 '11 at 18:33
  • No CNF is a tautology precisely because of the fact that all letters have to be distinct in a clause. – Cheerful Parsnip Sep 14 '11 at 18:47
  • 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
  • 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. – GEdgar Sep 14 '11 at 21:12
  • @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: – Doug Spoonwood Oct 19 '11 at 03:50
  • "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). – Doug Spoonwood Oct 19 '11 at 03:53
4

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

GEdgar
  • 111,679
1

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.

Doug Spoonwood
  • 11,211
  • 3
    Have you actually found anyone else that writes $ppNA$ ever? – Mariano Suárez-Álvarez 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-Álvarez 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 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 a – Doug Spoonwood Sep 14 '11 at 21:20
  • 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. – Doug Spoonwood Sep 14 '11 at 21:23
  • @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. – Doug Spoonwood Sep 14 '11 at 22:03
  • 1
    You must be a great success as parties... – Mariano Suárez-Álvarez Sep 14 '11 at 22:10
  • 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. – Doug Spoonwood Sep 15 '11 at 00:19