Algebra Boole’a i typ logiczny

24 października 2013 | Dodaj do biblioteki

| Druk | PDF

Tweetnij

Boolean algebra was developed by George Boole in 1854 in his book An Investigation of the Laws of Thought. Boolean algebra is the subarea of algebra in which the values of the variables are only true and false, usually denoted 1 and 0 respectively. The main operations of Boolean algebra are the conjunction (AND) denoted ∧, the disjunction (OR) denoted ∨, and the negation (NOT) denoted ¬.

Boolean algebra has been fundamental in the development of computer science and is yet the basis of the abstract description of digital circuits. It is also used in digital logic, computer programming, set theory, and statistics.

Basic Boolean operations

The basic operations of Boolean algebra are the following:

• AND (conjunction), denoted x∧y (sometimes x AND y, x • y , or Kxy) — yields true when both operands are true
• OR (disjunction), denoted x∨y (sometimes x OR y, x + y, or Axy) — yields true if exactly one operand is true
• NOT (negation), denoted ¬x (sometimes NOT x, Nx, x̅, or !x) — inverts the value of its operand

Derived Boolean operations

Apart from the basic Boolean operations, several other operations can be derived from the basic ones:

• XOR (exclusive OR or exclusive disjunction), denoted XOR , yields true whenever both inputs differ (one is true, the other is false).
• NOR (logical nor or joint denial), denoted ↓ (and NOR) — yields true if and only if both operands are false. In other words, it produces a value of false if and only if at least one operand is true.
• NAND (alternative denial), denoted A | B (or A ↑ B or A NAND B) — yields true, if and only if at least one of the operands is false.

The values of x AND y, x OR y, NOT x, x XOR y, x NAND y, and x NOR y can be presented in truth tables as follows:

Digital logic gates

The fundamental block of digital circuits used to build computer systems are logical gates. Gates are electronic circuits that produce output signals based on performing Boolean operations on their input signals. Each gate can be depicted schematically by a shape indicating the operation. The shapes associated with the gates for conjunction (AND-gates), disjunction (OR-gates), complement (inverters), NAND, NOR, and XOR are as follows.

AND gate

OR gate

NOT gate

NAND gate

NOR gate

XOR gate

The symbols presented here are defined in ANSI/IEEE Std 91. The lines on the left of each gate represent input wires or ports. The value of the input is represented by a voltage on the lead. Logic 0 is represented by a voltage close to zero or "ground" while 1 is represented by a voltage close to the supply voltage; active-low reverses this. The line on the right of each gate represents the output port, which normally follows the same voltage conventions as the input ports.

Complement is implemented with an inverter gate. The triangle denotes the operation that simply copies the input to the output; the small circle on the output denotes the actual inversion complementing the input. The convention of putting such a circle on any port means that the signal passing through this port is complemented on the way through, whether it is an input or output port.

Combinational circuits

Combinational circuit is a set of interconnected gates yielding output that is a function of the present input signals only. The output appears almost immediately after the appearance of input, with the so called gate delay.

Combinational circuits perform Boolean algebra on input signals and on stored data. Practical computer circuits normally contain a mixture of combinational and sequential logic. For example, the part of an arithmetic logic unit, or ALU, that does mathematical calculations is constructed using combinational logic. Other circuits used in computers, such as half adders, full adders, half subtractors, full subtractors, multiplexers, demultiplexers, encoders and decoders are also made by using combinational logic.

Boolean data type

In programming the Boolean or logical data type is a data type, having two values intended to represent the truth values of logic and Boolean algebra. The Boolean data type is the primary result of conditional statements, which allow different actions and change control flow depending on whether a programmer-specified boolean condition evaluates to true or false.

Boolean data type in programming generally

In programming languages that have a built-in Boolean data type, such as Pascal and Java, the comparison operators such as > and ≠ are usually defined to return a Boolean value. Conditional and iterative commands may be defined to test Boolean-valued expressions.

Languages without an explicit Boolean data type, like C90 and Lisp, may still represent truth values by some other data type. Lisp uses an empty list for false, and any other value for true. C uses an integer type, where relational expressions like i > j and logical expressions connected by && and || are defined to have value 1 if true and 0 if false, whereas the test parts of if, while, for, etc., treat any non-zero value as true.

Most programming languages, even those that do not have an explicit Boolean type, have support for Boolean algebraic operations such as conjunction (AND, & , *), disjunction (OR, |, +), equivalence (EQV, =, ==), exclusive or/non-equivalence (XOR, NEQV, ^, !=), and not (NOT, ~, !).

In some languages, like Ruby, Smalltalk, and Alice the "true" and "false" values belong to separate classes — e.g. True and False, resp. — so there is no single Boolean "type. "

Źródła: Wikipedia — Boolean data type, Wikipedia — Boolean algebra oraz Wikipedia — Logic gate (tekst został dostosowany do potrzeb kursu)

Dictionary

Exercises

1. Boolean. Create sentences with these words or expressions
2. Boolean. Choose the best word to complete the sentences
3. Boolean. Fill in the gaps 2
4. Boolean. Translate the following text into Polish
5. Boolean. Translate the sentences into English
6. Boolean. Translate the words in brackets into English
7. Boolean. Fill in the gaps
8. Boolean. Provide English equivalents for these terms
9. Boolean. Provide Polish equivalents for these terms
10. Boolean. Answer the following questions

Grammar corner

Present simple

The present simple tense is used to talk about general truths and permanent or repetitive situations. Look at the example below:

Gates are electronic circuits generally, not only at the moment of speaking (that’s why the present progressive tense hasn’t been used). The same rule applies to the other two sentences.

Read more about the present simple tense.

Licencja: CC-BY-SA 3.0