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 rules of inference provide the guidelines for constructing valid arguments from the existing statements. Here, we’ll discuss an essential rule of inference for quantified statements, that is, universal transitivity.
Assume that we have three predicates $P$, $Q$, and $R$ for a certain domain, and we are given the following statements:
$\forall x (P(x) \Rightarrow Q(x)).$
$\forall x (Q(x) \Rightarrow R(x)).$
Then, we can conclude $\forall x (P(x) \Rightarrow R(x))$ by universal transitivity.
Let’s see how we reach this conclusion. First, we use universal instantiation to get the following statements:
$P(c) \Rightarrow Q(c).$
$Q(c) \Rightarrow R(c).$
Then, by using hypothetical syllogism, we get:
$P(c) \Rightarrow R(c).$
Finally, universal generalization gives us the following conclusion:
$\forall x (P(x) \Rightarrow R(x)).$
Let’s look at an example below. Consider the set of polygons as the domain:
Define the following predicates:
Now, assume the following statements are true:
$\forall x (P(x) \Rightarrow Q(x))$: Every regular polygon has all sides equal.
$\forall x (Q(x) \Rightarrow R(x))$: Every regular polygon with all sides equal has all angles equal.
We can conclude the following statement by applying universal transitivity:
RELATED TAGS
CONTRIBUTOR
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.