Discrete Mathematics | Propositional Logic | Test 1 | Question: 12

Question

 The atomic propositional variables $p_0,p_1,...$ are $\textit{formulas},$ called $\textit{prime formulas},$ also called $\textit{atomic}$ formulas, or simply $\textit{primes}.$    
        
Prime formulas and negations of prime formulas are called $\textit{literals.}$  A disjunction $\alpha_1 \vee \alpha_2 \vee...\vee \alpha_n,$ where each $\alpha_i$ is a conjunction of literals, is called a $\textit{disjunctive normal form},$ a $\textit{DNF}$  for short.     
         
Similarly, A conjunction $\beta_1 \wedge \beta_2 \wedge...\wedge \beta_n,$ where each $\beta_i$ is a disjunction of literals, is called a $\textit{conjunctive normal form},$ a $\textit{CNF}$  for short.     
       
Which of the following statement(s) is/are correct?      
       

• A. $p \vee (\neg p \wedge q)$ is a DNF.    
          
• B. $p \vee q$ is at once a DNF and a CNF     
        
• C. $p \vee q \vee \neg (\neg p \wedge q)$ is neither a DNF nor a CNF.     
        
• D. $p \vee \neg (\neg p \wedge q)$ is either a DNF or a CNF.

Comments

In normal forms, each term should have one literal from each variable, isn’t it? Like canonical forms in digital logic as opposed to standard forms.

---

Some authors might follow what you said and  the reason why definitions of CNF and DNF are added here to avoid these things.

---

Please explain B.

---

@mili_dhara

$p \vee q$ is DNF because each $p$ and $q$ is a conjunction of a sequence of one literal i.e. p and q respectively and we can remove the repeated literals. $p \vee q$ is a disjunction of one literal clauses i.e. p and q.

$p \vee q$ is CNF because $(p \vee q)$ is considered as $\beta_1$ here (single clause).

---

@ankitgupta.1729 

i got it thank you

---

@Deepak Poonia sir please provide some explaination for this

 

---

@JayRathi, All the deifinitons are already given.

Basically DNF same as is “Sum-of-Product” which we study in digital logic. CNF same as is “Product-of-Sum”.

See THIS question, it will make these terms clear. After that, solve the given question. 

---

thank you sir got it