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 StructureThe 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:
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))
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))
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))
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