Question

[III.4] You are given a boolean expression consisting of a string of the symbols 'true', 'false', and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there is only 1 way to parenthesize 'true and false xor true' such that it evaluates to true. Complete the following tasks.  

[III.4a] Show the parenthesization of the example such that evaluate to true.   'true and false xor true' 

[III.4b] Show the optimal substructure of the problem (describe in your own words or derive an equation.)   Then recursively define the optimal solution.  

Answer 1

As per HOMEWORKLIB POLICY, I will answer III.4 and III.4a

ANSWER TO III.4

As you can see, out of 16 possibilities, 8 will result in a true expression.

ANSWER TO III.4a

The answer to this would be (true and false) xor true

Steps to evaluate the above:

1) true and false will give false

2) false xor true gives true.