Let us assume that you construct ordered tree to represent the compound…
2016
Let us assume that you construct ordered tree to represent the compound proposition \((\sim (p \wedge q)) \leftrightarrow (\sim p \vee \sim q)\).
Then, the prefix expression and post-fix expression determined using this ordered tree are given as _____ and ______ respectively.
- A.
\(\leftrightarrow \sim \wedge pq \vee \sim \sim pq, pq \wedge \sim p \sim q \sim ∨ \leftrightarrow\) - B.
\(\leftrightarrow \sim \wedge pq \vee \sim p \sim q, pq \wedge \sim p \sim q \sim \vee \leftrightarrow\) - C.
\(\leftrightarrow \sim \wedge pq \vee \sim \sim pq, pq \wedge \sim p \sim \sim q \vee \leftrightarrow\) - D.
\(\leftrightarrow \sim \wedge pq \vee \sim p \sim q, pq\wedge \sim p \sim \sim q \vee \leftrightarrow\)
Attempted by 255 students.
Show answer & explanation
Correct answer: B
Key idea: build the ordered tree with the biconditional at the root, then perform pre-order for prefix and post-order for postfix.
Tree structure: root is ↔; left child is ¬ with child (p ∧ q); right child is ∨ with children ¬p and ¬q.
Pre-order (prefix) traversal: visit root, then left subtree, then right subtree.
Post-order (postfix) traversal: visit left subtree, then right subtree, then root.
Prefix (pre-order traversal): ↔ ¬ ∧ p q ∨ ¬ p ¬ q
Postfix (post-order traversal): p q ∧ ¬ p ¬ q ¬ ∨ ↔
Explanation: for the left subtree ¬(p ∧ q) the postfix is p q ∧ ¬ (negation after the conjunction), and for the right subtree (¬p ∨ ¬q) the postfix is p ¬ q ¬ ∨. Concatenating left-postfix, right-postfix and then the root gives the full postfix above; analogous ordering gives the prefix.