Find PDNF by constructing its PCNF of (Q ^ V P) -> (~ V R) ^ (~P V ~Q).


Q.) Find PDNF by constructing its PCNF of (Q ^ V P) -> (~ V R) ^ (~P V ~Q).

Subject: Discrete Structure

The given expression is (Q ^ V P) -> (~ V R) ^ (~P V ~Q). To find the PDNF (Product of Disjunctive Normal Form) by constructing its PCNF (Product of Conjunctive Normal Form), we need to follow the steps below:

  1. Convert the given expression into its logical equivalent form without implication (->):

    The logical equivalent of A -> B is ~A V B. So, the given expression can be rewritten as:

    ~(Q ^ V P) V ((~ V R) ^ (~P V ~Q))

  2. Apply De Morgan's Law:

    De Morgan's Law states that ~(A ^ B) is equivalent to ~A V ~B and ~(A V B) is equivalent to ~A ^ ~B. Applying this law, we get:

    (~Q V ~V P) V ((~ V R) ^ (~P V ~Q))

  3. Convert the expression into CNF (Conjunctive Normal Form):

    CNF is a conjunction of one or more clauses, where a clause is a disjunction of literals. So, we need to distribute the OR over AND:

    ((~Q V ~V P) V (~ V R)) ^ ((~Q V ~V P) V (~P V ~Q))

  4. Convert the CNF into DNF (Disjunctive Normal Form):

    DNF is a disjunction of one or more clauses, where a clause is a conjunction of literals. So, we need to distribute the AND over OR:

    ((~Q ^ ~V P) ^ (~ V R)) V ((~Q ^ ~V P) ^ (~P ^ ~Q))

This is the PDNF of the given expression.

Here is a table showing the steps and the transformations:

Step Transformation Expression
1 Remove implication ~(Q ^ V P) V ((~ V R) ^ (~P V ~Q))
2 Apply De Morgan's Law (~Q V ~V P) V ((~ V R) ^ (~P V ~Q))
3 Convert to CNF ((~Q V ~V P) V (~ V R)) ^ ((~Q V ~V P) V (~P V ~Q))
4 Convert to DNF ((~Q ^ ~V P) ^ (~ V R)) V ((~Q ^ ~V P) ^ (~P ^ ~Q))

Please note that the symbols used in the expression are logical operators:

  • ^ : AND
  • V : OR
  • ~ : NOT
  • -> : IMPLIES