Binary decision

Last updated

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

Contents

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 Ordered Binary Decision Diagram for the boolean function
f
{\displaystyle f} BDD simple.svg
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:

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 IF-THEN-ELSE-END flowchart.png
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

Related Research Articles

In computer science, test coverage is a measure of the degree to which the source code of a program is executed when a particular test suite is run. A program with high test coverage has more of its source code executed during testing, which suggests it has a lower chance of containing undetected software bugs compared to a program with low test coverage. Many different metrics can be used to calculate test coverage. Some of the most basic are the percentage of program subroutines and the percentage of program statements called during execution of the test suite.

Negation Logical operation

In logic, negation, also called the logical complement, is an operation that takes a proposition to another proposition "not ", written , or . It is interpreted intuitively as being true when is false, and false when is true. Negation is thus a unary logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition is the proposition whose proofs are the refutations of .

Conditional (computer programming) Programming language construct that performs actions according to boolean conditions

In computer science, conditionals are programming language commands for handling decisions. Specifically, conditionals perform different computations or actions depending on whether a programmer-defined boolean condition evaluates to true or false. In terms of control flow, the decision is always achieved by selectively altering the control flow based on some condition.

In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression.

In computer programming, ?: is a ternary operator that is part of the syntax for basic conditional expressions in several programming languages. It is commonly referred to as the conditional operator, inline if (iif), or ternary if. An expression a ? b : c evaluates to b if the value of a is true, and otherwise to c. One can read it aloud as "if a then b otherwise c".

Short-circuit evaluation, minimal evaluation, or McCarthy evaluation is the semantics of some Boolean operators in some programming languages in which the second argument is executed or evaluated only if the first argument does not suffice to determine the value of the expression: when the first argument of the AND function evaluates to false, the overall value must be false; and when the first argument of the OR function evaluates to true, the overall value must be true.

Boolean function Function returning one of only two values

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

In computer science, the Boolean data type is a data type that has one of two possible values which is intended to represent the two truth values of logic and Boolean algebra. It is named after George Boole, who first defined an algebraic system of logic in the mid 19th century. The Boolean data type is primarily associated with conditional statements, which allow different actions by changing control flow depending on whether a programmer-specified Boolean condition evaluates to true or false. It is a special case of a more general logical data type —logic doesn't always need to be Boolean.

In computer programming languages, a switch statement is a type of selection control mechanism used to allow the value of a variable or expression to change the control flow of program execution via search and map.

The syntax of JavaScript is the set of rules that define a correctly structured JavaScript program.

Recursion (computer science) Use of functions that call themselves

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

A binary moment diagram (BMD) is a generalization of the binary decision diagram (BDD) to linear functions over domains such as booleans, but also to integers or to real numbers.

A zero-suppressed decision diagram is a particular kind of binary decision diagram (BDD) with fixed variable ordering. This data structure provides a canonically compact representation of sets, particularly suitable for certain combinatorial problems. Recall the Ordered Binary Decision Diagram (OBDD) reduction strategy, i.e. a node is removed from the decision tree if both out-edges point to the same node. In contrast, a node in a ZDD is removed if its positive edge points to the terminal node 0. This provides an alternative strong normal form, with improved compression of sparse sets. It is based on a reduction rule devised by Shin-ichi Minato in 1993.

A propositional directed acyclic graph (PDAG) is a data structure that is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed acyclic graph of the following form:

S-algol is a computer programming language derivative of ALGOL 60 developed at the University of St Andrews in 1979 by Ron Morrison and Tony Davie. The language is a modification of ALGOL to contain orthogonal data types that Morrison created for his PhD thesis. Morrison would go on to become professor at the university and head of the department of computer science. The S-algol language was used for teaching at the university at an undergraduate level until 1999. It was also the language taught for several years in the 1980s at a local school in St. Andrews, Madras College. The computer science text Recursive Descent Compiling describes a recursive descent compiler for S-algol, implemented in S-algol.

The Conditional operator is supported in many programming languages. This term usually refers to ?: as in C, C++, C#, and JavaScript. However, in Java, this term can also refer to && and ||.

Karnaugh map Graphical method to simplify Boolean expressions

The Karnaugh map is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 logical diagram aka Marquand diagram but with a focus now set on its utility for switching circuits. Veitch charts are therefore also known as Marquand–Veitch diagrams, and Karnaugh maps as Karnaugh–Veitch maps.

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables. In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, logically valid.

In mathematics, an evasive Boolean functionƒ is a Boolean function for which every decision tree algorithm has running time of exactly n. Consequently, every decision tree algorithm that represents the function has, at worst case, a running time of n.

In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0, respectively. Instead of elementary algebra, where the values of the variables are numbers and the prime operations are addition and multiplication, the main operations of Boolean algebra are the conjunction (and) denoted as ∧, the disjunction (or) denoted as ∨, and the negation (not) denoted as ¬. It is thus a formalism for describing logical operations, in the same way that elementary algebra describes numerical operations.

References

  1. Snow, Roberta M.; Phillips, Paul H. (2007), Making Critical Decisions: A Practical Guide for Nonprofit Organizations, John Wiley & Sons, p. 44, ISBN   9780470185032 .
  2. Dixit, J. B. (2009), Computer Fundamentals and Programming in C, Firewall Media, p. 61, ISBN   9788170088820 .
  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   9780262032704 .
  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   9780262022170 .
  6. Kukreja, Jyoti. "Application of Binary Decision Diagram in digital circuit analysis". S2CID   13980719.{{cite journal}}: Cite journal requires |journal= (help)
  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.