Trusted answers to developer questions

Ayesha Kanwal

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

The **prenex normal form **is a method to deal with formulas so that the quantifiers are moved in front of the expression.

The prenex normal form is written as:

In this form **prefix**, whereas **matrix**.

A formula with no quantifiers is called a **trivial case **of the prenex normal form.

We'll follow the steps below to convert any expression into PNF:

- We eliminate all the occurrences of
$\rightarrow$ and$↔$ from the formula. - We move all the negations inwards to appear only as a part of the literal.
- Standardize the variables apart if it is necessary.
- PNF is obtained by moving the quantifiers to the front of the formula.

To remove the conditional

$A \rightarrow B \equiv \neg A \vee B$ $A ↔ B \equiv (\neg A \vee B) \wedge (A \vee \neg B)$ $A ↔ B \equiv (A \wedge B) \vee (\neg A \wedge \neg B)$

We'll now try to move all the negations close to the literals instead of the negations occurring as a whole. We convert the

$\neg \neg A \equiv A$ $\neg \forall xA(x) \equiv \exists x \neg A(x)$ $\neg \exists xA(x) \equiv \forall x \neg A(x)$ - De Morgan's law

Renaming of the variables is called the **standardizing of the variables apart. **To achieve step 3, we use the following theorem to rename the variables to make them distinct.

Suppose we get

In this step, we'll shift all the

$A \vee \forall xF(x) \equiv \forall x(A \vee F(x))$ where$x$ does not occur in$A$ .$A \vee \exists xF(x) \equiv \exists x(A \vee F(x))$ where$x$ does not occur in$A$ .$A \wedge \forall xF(x) \equiv \forall x(A \wedge F(x))$ where$x$ does not occur in$A$ .$A \wedge \exists xF(x) \equiv \exists x(A \wedge F(x))$ where$x$ does not occur in$A$ .

Let's consider the following expression:

To convert it into PNF, we follow the steps mentioned above.

We'll eliminate

We'll move the negations inwards.

We'll standardize the variables.

We'll now move the quantifiers to the front, and this gives us:

In conclusion,

This is the final PNF form of the expression.

RELATED TAGS

theoretical cs

CONTRIBUTOR

Ayesha Kanwal

Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Keep Exploring

Related Courses