0

For example, can you do something like this in propositional logic?

AND(OR(AND(A, B), AND(C, OR(D, E))), AND(F, OR(G, H)))

Or put more visibly as a tree:

AND
  OR
    AND(A, B)
    AND(C, OR(D, E)))
  AND(F, OR(G, H)))

As propositional logic, it would be something like:

$$(((A ∧ B) ∨ (C ∧ (D ∨ E)) ∧ (F ∧ (G ∨ H)))$$

If not in propositional logic, then in predicate logic? If neither, what is the reason you can't do this, does it not make sense for some reason?

If you can do this in prepositional logic, do they need to be simplified to a flattened list somehow? Or is it okay that they are arbitrarily deep trees?

Lance
  • 3,698
  • 4
    Yes. There’s no problem with this, just like there’s no nesting limit for expressions with numbers. – Mark Saving Jan 24 '22 at 23:43
  • 2
    Nesting propositional operations is fine. See the paragraph headed "Closure under operations" here. – Rob Arthan Jan 24 '22 at 23:43
  • Yes, you can have arbitrary nestings of conjunctions and disjunctions. You can always flatten them into a disjunction of conjunctions (and in classical logic also into a conjunction of disjunctions) using de-Morgan rules, but you don't have to. – Jonas Frey Jan 24 '22 at 23:44
  • Well good to know, pretty much ever example I have seen shows only 1 level of nesting max, so I didn't know if it was forbidden or something, or doesn't describe something realistic. – Lance Jan 24 '22 at 23:44

1 Answers1

1

To answer your question, why don't we take a look at a few basic things in mathematical logic.

A logical systems is required to have a few things:

  • An alphabet
  • A grammar
  • Axioms (formulas that are true without needing to be proved)
  • Rules that assign truth values to formulas
  • Inference rules

By an alphabet we mean a set of symbols classified into three categories:

  • Propositional variables: letters such as $P, Q, S$, or $R$ that stand for propositions.
  • Connectives: $\land, \lor, \lnot, \rightarrow$, and $\leftrightarrow$
  • Grouping symbols: (, ), [, ], and so on.

(We do not need to worry about the 3 other components of a logical system besides grammar which we'll cover in a minute since the rest are irrelevant to our discussion)

Moreover, we call a finite sequence of combinations of characters in the alphabet a string. A string can be anything even like $PPP\land \lor Q \lnot$. Since any nested conjunctions or disjunctions will be strings over the alphabet, they do exist in propositional logic, and in fact, any (nonempty) finite combination of characters from the alphabet would form a string over the alphabet, which would legitimately exist. However, I suppose this is not what you are asking about (although this would the answer if I take your question literally).

You are asking if we can nest disjunctions and conjunctions, which is the same as asking do expressions such as $P\land (Q\land (R\lor S))$ represent anything or carry any meaning in propositional logic. In the above example, all the letters ($P, Q, R,$ and $S$) are propositional variables, which means that they legitimately exist and carry meaning in propositional logic, but it does not guarantee the combination of them by nested conjunctions or disjunctions would mean anything. This is what motivated us to come up with the concept called formula.

A formula is a nonempty string over the alphabet that follow the rules below. A system of determining propositions for our study (which are called formulas) is called the grammar of the logical system.

  • Every propositional variable is a formula
  • $\lnot p$ is a formula if $p$ is a formula
  • $(p\land q), (p\lor q), (p\rightarrow q)$, and $(p\leftrightarrow q)$ are formulas if both $p$ and $q$ are formulas.

By definition, the example I just gave, $P\land (Q\land (R\lor S))$, would be considered as a formula since all of the propositional variables are formulas and the whole expression can be shown to be a formula by applying the third rule three times.

Now why am I bringing this thing up in my response to this seemingly shallow question? Because the familiar truth values can only be assigned to formulas, thus formulas are the only ones that would carry any meaning in propositional logic! The truth values of each of $\lnot p, (p\land q), (p\lor q), (p\rightarrow q)$, and $(p\leftrightarrow q)$ is assigned in the following way where $\mathsf{v}(p)$ is the truth value assignment of the formula $p$:

  • $\mathsf{v}(\lnot p)= \begin{cases} \text{T} & \text{if } \mathsf{v}(p)=\text{F}\\ \text{F} & \text{otherwise} \end{cases}$

  • $\mathsf{v}(p\land q)= \begin{cases} \text{T} & \text{if } \mathsf{v}(p)=\text{T} \text{ and } \mathsf{v}(q)=\text{T}\\ \text{F} & \text{otherwise} \end{cases}$

  • $\mathsf{v}(p\lor q)= \begin{cases} \text{T} & \text{if } \mathsf{v}(p)=\text{T} \text{ or } \mathsf{v}(q)=\text{T}\\ \text{F} & \text{otherwise} \end{cases}$

  • $\mathsf{v}(p\rightarrow q)= \begin{cases} \text{F} & \text{if } \mathsf{v}(p)=\text{T} \text{ and } \mathsf{v}(q)=\text{F}\\ \text{T} & \text{otherwise} \end{cases}$

  • $\mathsf{v}(p\leftrightarrow q)= \begin{cases} \text{T} & \text{if } \mathsf{v}(p)=\mathsf{v}(q)\\ \text{F} & \text{otherwise} \end{cases}$

It should be evident to you right now that the nested conjunctions or disjunctions are called formulas and can thus get assigned truth value. Therefore, they do carry meaning.

ps: the rules stated above for assigning truth values to formulas is actually a component of a logical system mentioned earlier.

Hope this helps. Have a good day :)

William Wei
  • 127