SP1775 BOOLE - Boolean Logic

Propositions are logical formulas consisting of proposition symbols and connecting operators. They are recursively defined by the following rules: 1. All proposition symbols (in this problem, lower-case alphabetic characters, e.g., `a` and `z`) are propositions. 2. If `P` is a proposition, `(!``P``)` is a proposition, and `P` is a direct subformula of it. 3. If `P` and `Q` are propositions, `(``P``&``Q``)`, `(``P``|``Q``)`, `(``P``-->``Q``)`, and `(``P````Q``)` are propositions, and `P` and `Q` are direct subformulas of them. 4. Nothing else is a proposition. The operations `!`, `&`, `|`, `-->`, and `` denote logical negation, conjunction, disjunction, implication, and equivalence, respectively. A proposition `P` is a subformula of a proposition `R` if `P=R` or `P` is a direct subformula of a proposition `Q` and `Q` is a subformula of `R`. Let `P` be a proposition and assign boolean values (i.e., `0` or `1`) to all proposition symbols that occur in `P`. This induces a boolean value to all subformulas of `P` according to the standard semantics of the logical operators: negation conjunction disjunction implication equivalence `!``0`=`1` `0``&``0`=`0` `0``|``0`=`0` `0``-->``0`=`1` `0````0`=`1` `!``1`=`0` `0``&``1`=`0` `0``|``1`=`1` `0``-->``1`=`1` `0````1`=`0` `1``&``0`=`0` `1``|``0`=`1` `1``-->``0`=`0` `1````0`=`0` `1``&``1`=`1` `1``|``1`=`1` `1``-->``1`=`1` `1````1`=`1` This way, a value for `P` can be calculated. This value depends on the choice of the assignment of boolean values to the proposition symbols. If `P` contains `n` different proposition symbols, there are `2 $ ^{n} $ ` different assignments. To evaluate all possible assignments we may use truth tables. A truth table contains one line per assignment (i.e., `2 $ ^{n} $ ` lines in total). Every line contains the values of all subformulas under the chosen assignment. The value of a subformula is aligned with the proposition symbol, if the subformula is a proposition symbol, and with the center of the operator otherwise.

N/A

N/A