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 ?

  • 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.

  • 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
    "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
2

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

  • 0
    @Gadi: except that Asaf's method is also not allowed. (Since all letters must be distinct in a clause.)2011-09-14