Question

1. Represent the compound propositions \({\bf{\neg }}\left( {{\bf{p}} \wedge {\bf{q}}} \right) \leftrightarrow \left( {{\bf{\neg p}} \vee {\bf{\neg q}}} \right)\) and \(\left( {{\bf{\neg p}} \wedge \left( {{\bf{q}} \leftrightarrow {\bf{\neg p}}} \right)} \right) \vee {\bf{\neg q}}\) using ordered rooted trees.Write these expressions in
2. prefix notation.
3. postfix notation.
4. infix notation.

Short answer

a.T he binary trees of the given expressions are

Tree (1):

Tree (2):

b. The prefix forms of the given expressions are \( \leftrightarrow {\bf{\neg }} \wedge {\bf{pq}} \vee {\bf{\neg p\neg q}}\) and \( \vee \wedge {\bf{\neg p}} \leftrightarrow {\bf{q\neg p\neg q}}\).

c. The postfix forms of the given expressions are \({\bf{pq}} \wedge {\bf{\neg p\neg q\neg }} \vee \leftrightarrow \) and \({\bf{p\neg qp\neg }} \leftrightarrow \wedge {\bf{q\neg }} \vee \).

d. The infix forms of the given expressions are \(\left( {\left( {{\bf{\neg }}\left( {{\bf{p}} \wedge {\bf{q}}} \right)} \right) \leftrightarrow \left( {\left( {{\bf{\neg p}}} \right) \vee \left( {{\bf{\neg q}}} \right)} \right)} \right)\) and \(\left( {\left( {\left( {{\bf{\neg p}}} \right) \wedge \left( {{\bf{q}} \leftrightarrow \left( {{\bf{\neg p}}} \right)} \right)} \right) \vee \left( {{\bf{\neg q}}} \right)} \right)\).

Step-by-step solution

General form

Preorder traversal:

Let T be an ordered rooted tree with root r. If Tconsists only of r, then r is the preorder traversal of T. Otherwise, suppose that \({{\bf{T}}_{\bf{1}}}{\bf{,}}{{\bf{T}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{T}}_{\bf{n}}}\) arethe subtrees at r from left to right in T. The preorder traversal begins by visiting r. It continues by traversing \({{\bf{T}}_{\bf{1}}}\) in preorder, then \({{\bf{T}}_{\bf{2}}}\) in preorder, and so on, until \({{\bf{T}}_{\bf{n}}}\) is traversed in preorder.

Postorder traversal:

Let T be an ordered rooted tree with rootr. If Tconsists only of r, then r is the postorder traversalof T. Otherwise, suppose that \({{\bf{T}}_{\bf{1}}}{\bf{,}}{{\bf{T}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{T}}_{\bf{n}}}\) are the subtrees at r from left to right. The postorder traversal begins by traversing \({{\bf{T}}_{\bf{1}}}\) in postorder, then \({{\bf{T}}_{\bf{2}}}\) in postorder, …, then \({{\bf{T}}_{\bf{n}}}\) in postorder, and ends by visiting r.

Inorder traversal:

Let T be an ordered rooted tree with rootr. If Tconsists only of r, then r is the inorder traversalof T. Otherwise, suppose that \({{\bf{T}}_{\bf{1}}}{\bf{,}}{{\bf{T}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{T}}_{\bf{n}}}\) are the subtrees at r from left to right. The inorder traversal begins by traversing \({{\bf{T}}_{\bf{1}}}\) in inorder, then visiting r. It continues by traversing \({{\bf{T}}_{\bf{2}}}\) in inorder, and so on, until \({{\bf{T}}_{\bf{n}}}\) is traversed in inorder.

Note: Since the prefix, postfix and infix form of this expression are founded by traversing this rooted tree in preorder, post order and inorder (including parentheses), respectively.

Represent the given expression using binary tree

Given that, the expressions are \({\bf{\neg }}\left( {{\bf{p}} \wedge {\bf{q}}} \right) \leftrightarrow \left( {{\bf{\neg p}} \vee {\bf{\neg q}}} \right)\) and \(\left( {{\bf{\neg p}} \wedge \left( {{\bf{q}} \leftrightarrow {\bf{\neg p}}} \right)} \right) \vee {\bf{\neg q}}\).

Now, represent the expressions using binary trees.

Tree 1:

Tree 2:

Convert the given propositions in prefix forms.

Refer the binary trees to find the prefix form.

So, the prefix forms are \( \leftrightarrow {\bf{\neg }} \wedge {\bf{pq}} \vee {\bf{\neg p\neg q}}\) and \( \vee \wedge {\bf{\neg p}} \leftrightarrow {\bf{q\neg p\neg q}}\).

Convert the given expressions in postfix forms.

Refer the binary tree to find the postfix form.

So, the postfix forms are \({\bf{pq}} \wedge {\bf{\neg p\neg q\neg }} \vee \leftrightarrow \) and \({\bf{p\neg qp\neg }} \leftrightarrow \wedge {\bf{q\neg }} \vee \).

Convert the given expressions in infix forms.

Refer the binary tree to find the infix form.

Here, we need to add the parentheses to indicate that the product occurs before the subtraction and brackets at the starting and ending of the expression.

So, the infix forms are \(\left( {\left( {{\bf{\neg }}\left( {{\bf{p}} \wedge {\bf{q}}} \right)} \right) \leftrightarrow \left( {\left( {{\bf{\neg p}}} \right) \vee \left( {{\bf{\neg q}}} \right)} \right)} \right)\) and \(\left( {\left( {\left( {{\bf{\neg p}}} \right) \wedge \left( {{\bf{q}} \leftrightarrow \left( {{\bf{\neg p}}} \right)} \right)} \right) \vee \left( {{\bf{\neg q}}} \right)} \right)\).