Practicing Logical Complexity — Which expression has greater depth?

The depth of p ∧ (q ∨ r) is 2, while the others have only 1.

Complexity of Logical Expressions

Logical expressions can be simple or complex at different levels. To measure complexity, we use several aspects, such as the length of the formula, its depth, and structure.

Length

The length shows how many symbols an expression consists of. The more logical operators and variables, the longer the formula.

This expression has 5 symbols: p, ∨, q, ∧, r.

Depth

The depth indicates the nesting of parentheses. A simple p ∧ q has depth 1, while (p ∧ (q ∨ r)) has depth 2.

Simplification

Often, complex formulas can be simplified using logical identities (e.g., De Morgan's laws, idempotence, distributivity). This reduces both the length and depth.

Example: ¬(p ∧ q) ↔ (¬p ∨ ¬q). The original expression seems longer and deeper, but the identity transforms it into a simpler form.

Why is Complexity Important?

Computer logical circuits are more efficient with simpler formulas.
For understandability, it's important that the expression is as short and clearer as possible.
The difficulty of solving logical problems often depends on the complexity of the expressions.

Summary

Logical complexity consists of three main factors: length, depth, and simplifiability. With these, we can better understand and handle logical formulas.

Practice Exercise

We have reviewed and checked the materials, but errors may still occur. The content is provided for educational purposes only, so use it at your own responsibility and verify with other sources if needed.