A binary decision is a choice between two alternatives, for instance between taking some specific action or not taking it.[1]

Binary decisions are basic to many fields. Examples include:

Binary decision diagrams

A binary decision diagram (BDD) is a way to visually represent a boolean function. One application of BDDs is in CAD software and digital circuit analysis where they are an efficient way to represent and manipulate boolean functions.[6]

Reduced Order Binary Decision Diagram for f
Reduced Ordered Binary Decision Diagram for the boolean function

The value of a boolean function can be determined by following a path in its BDD down to a terminal, making a binary decision at each node where a solid line is followed if the value of the variable at the node is true and a dotted line if it is false. A BDD is said to be 'ordered' if the order of the variables tested is fixed. A BDD is said to be 'reduced' if the two following conditions are true:

  • Each successor of each node is distinct.
  • There are no two distinct nodes of the same variable with the same successors.[7][8]

BDDs that are ordered and reduced can be called Reduced Ordered Binary Decision Diagrams (ROBDD). An example of a ROBDD is the figure to the right, which represents the function . The order of the variables along any path is always , , then , all nodes have distinct successors, and there are no two nodes of the same variable and the same successors.

Conditional statements

In computer science, conditional statements are used to make binary decisions.[9] A program can perform different computations or actions depending on whether a certain boolean value evaluates to true or false.

The if-then-else construct is a control flow statement which runs one of two code blocks depending on the value of a boolean expression, and its structure looks like this:

if condition then
    code block 1
else
    code block 2
end
Flowchart illustrating the use of else if

The conditional expression is condition, and if it is true, then code block 1 is executed, otherwise code block 2 is executed. It is also possible to combine multiple conditions with the else-if construct:

if condition 1 then
    code block 1
else if condition 2 then
    code block 2
else
    code block 3
end

This can be represented by the flow diagram on the right. If one condition is found to be true, then the rest are skipped, so only one of the three code blocks above can be executed.

A while loop is a control flow statement which executes a code block repeatedly until its boolean expression becomes false, making a decision on whether to continue repeating before each loop. This is similar to the if-then construct, but it can executing a code block multiple times.

See also

References

  1. Snow, Roberta M.; Phillips, Paul H. (2007), Making Critical Decisions: A Practical Guide for Nonprofit Organizations, John Wiley & Sons, p. 44, ISBN 978-0-470-18503-2.
  2. Dixit, J. B. (2009), Computer Fundamentals and Programming in C, Firewall Media, p. 61, ISBN 978-81-7008-882-0.
  3. Yourdon, Edward (March 19, 1975), "Clear thinking vital: Nested IFs not evil plot leading to program bugs", Computerworld: 15.
  4. Clarke, E. M.; Grumberg, Orna; Peled, Doron (1999), Model Checking, MIT Press, p. 51, ISBN 978-0-262-03270-4.
  5. Ben-Akiva, Moshe E.; Lerman, Steven R. (1985), Discrete Choice Analysis: Theory and Application to Travel Demand, Transportation Studies, vol. 9, MIT Press, p. 59, ISBN 978-0-262-02217-0.
  6. Kukreja, Jyoti. "Application of Binary Decision Diagram in digital circuit analysis" (PDF). University of Southern California. S2CID 13980719. Archived from the original (PDF) on 2003-09-28.
  7. Pfenning, Frank (October 28, 2010). "Lecture Notes on Binary Decision Diagrams" (PDF). Carnegie Mellon School of Computer Science. Archived (PDF) from the original on 2014-03-09. Retrieved 26 May 2020.
  8. "Binary Decision Diagrams" (PDF). Dep. Computer Science - University of Verona. Archived (PDF) from the original on 2016-04-18. Retrieved 26 May 2020.
  9. "Programming - Conditionals". www.cs.utah.edu. Retrieved 2020-05-26.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.