python代写: CSC A48 Assignment 2

CSC A48 Assignment 2

Formula Game

Due: Saturday, March 10, 2018 at 5pm.

⋆ introduction

⃝ boolean variable (or just variable)
A boolean variable is a variable that takes on one of two values, True and False. For convenience, we will use 1 and 0 to denote True and False respectively. Also, all our variable names will consist of a single lower case letter. So we are limited to at most 26 variables.
⃝ boolean formula (or just formula)
A boolean formula is a string made up of the following.
- Boolean variables. I.e., lower case letters.
- The connectives ∧, ∨, ¬, called AND, OR, NOT respectively. For ease of typing a formula on a
  keyboard, we will use the characters *, +, – to denote the symbols ∧, ∨, ¬ respectively.
- Left and right parentheses. I.e., the symbols ( and ).

⊙ rules for formulas
Here are the rules governing what constitutes a valid boolean formula.

Note the recursive nature of these rules.
1. The simplest formula is a string consisting of just one variable.
2. If F1 and F2 are formulas, then so are (F1 ∗ F2), (F1 + F2), and −F1. Using Python syntax, we mean the following strings are formulas.
  • ’(’+F1 +’*’+F2 +’)’ • ’(’+F1 +’+’+F2 +’)’ • ’-’ + F1
  
  Use of parentheses is absolutely required for the first two cases, and not permitted for the last case. These restrictions may seem overly cumbersome, but you’ll thank us when we ask you to write code to work with these formulas! ⌣ ̈
3. Any string that cannot be constructed using the above rules is not a valid formula.
⊙ examples
Here are some valid formulas (shown as Python strings).

• “x”
• “-y”
• “(x*y)”

• “((-x+y)*-(-y+x))”
CSC A48 Winter 2018 Page 1 of 5

Here are some strings that are not formulas.

• “X”
• “x*y”
• “-(x)”
• “(x+(y)*z)” mismatched parentheses

CSC A48

Winter 2018 Page 2 of 5

•

The truth value of a formula (F1 ∗F2) is 1 if both F1 and F2 have truth value 1, and 0 if at least one of F1 and F2 has truth value 0. Thinking of 1 and 0 as integers, we could say that the truth value of (F1 ∗ F2) is the minimum of the truth values of F1 and F2.

The truth value of a formula (F1 +F2) is 1 if at least one of F1 and F2 has truth value 1, and 0 if both F1 and F2 have truth value 0. Thinking of 1 and 0 as integers, we could say that the truth value of (F1 + F2) is the maximum of the truth values of F1 and F2.

The truth value of a formula −F1 is 1 if F1 has truth value 0, and 0 if F1 has truth value 1. Thinking of 1 and 0 as integers, we could say that the truth value of −F1 is one minus the truth value of F1.

variable not lower case letter missing parentheses

extraneous parentheses

⃝ tree representation of a formula

Boolean formulas can be represented by a binary tree in a very natural way. Each leaf node represents a variable. Each internal node represents a connective, called an AND node, an OR node, or a NOT node, depending on the connective represented. A node that represents * or + has 2 child nodes, which in turn represent the two subformulas that are ANDed or ORed to form the larger formula. A node that represents – has one child node, which in turn represents the formula that is NOTed. We draw these trees in a way that requires us to rotate it 90 degrees clockwise to see it with its root at the top. Alternatively we could also turn our head toward our left shoulder. We also draw them without lines (or arrows) betweeen parent and child nodes. As with Python code, parent child relationships can be inferred by the level of indentation. Children of the root are indented 2 spaces. Children of a child of the root are indented 4 spaces, and so on. For example, here is the tree for the formula ((-x+y)*-(-y+x)).

*-+x -y

+y -x

This may seem an awkward way to draw a tree, but you’ll thank us when we ask you to write code to draw such trees! ⌣ ̈

Important: Make sure you understand how formulas are represented by trees. Try writing down a formula, then drawing its corresponding tree. Repeat until it becomes easy for you.

⃝ truth value of a boolean formula
If we assign a truth value (1 or 0) to each variable in a formula, then we can determine the truth value of

that formula in a natural way. Formally, here the rules governing the truth value of a formula.

For a formula consisting of just one variable, the truth value of the formula is the truth value of the variable.
For a formula constructed from smaller formulas F1 and F2, its truth value is as follows.

⃝ formula game

The formula game is a game for two players, called A and E. The game starts with a boolean formula F, along with an ordering of the variables that appear in F, and for each variable, which player gets to choose its truth value. The players take turns choosing the values of the variables one at a time in the specified order. After all the variables in F have been assigned truth values, player A wins if the truth value of F is 0, and player E wins if the truth value of F is 1. I.e., player A is trying to make F false, and player E is trying to make F true.

⊙ example
Consider the following formula, along with information regarding which player gets to choose which vari-

able’s truth value in which order.

For this game, player E first chooses the value of x, then the value of y. Finally player A chooses the value of z. If player E chooses 0 for x and 1 for y, and player A chooses 1 for z, then player A wins. On the other hand, if player E chooses 1 for x and 0 for y, and player A chooses 1 for z, then player E wins.

Please work through the above scenarios and be certain that you understand them.

⃝ formula game configuration
We represent the state of a formula game as it is being played by 4 pieces of information.

⊙ example
From the previous example, here is the initial configuration.

Here is the configuration after the first turn, supposing player E chooses 0 for x.

Here is the configuration after the second turn, supposing player E chooses 1 for y.

Here is the final configuration after the third and last turn, supposing player A chooses 1 for z.
CSC A48 Winter 2018 Page 3 of 5