Algebra Boole’a i typ logiczny

24 października 2013 | LoadingDodaj do biblioteki

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:

Truth tables for Boolean oprations
xyx AND yx OR yx XOR yx NAND yx NOR yNOT x/NOT y
00000111
10011100
01011101
11110000

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.

 

Symbol ANSI bramki AND

AND gate

Symbol bramki or

OR gate

Symbol bramki NOT

NOT gate

Symbol bramki NAND

NAND gate

Symbol bramki NOR

NOR gate

Symbol bramki XOR

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

a mixture of sth
mieszanina czegoś
a set of sth
zbiór czegoś
abstract description
abstrakcyjny opis
algebra
algebra
algebraic operation
działanie algebraiczne
allow different actions depending on sth
umożliwiać wykonywanie różnych działań w zależności od czegoś
AND gate
bramka AND
AND
i
arithmetic logic unit (ALU)
jednostka arytmetyczno-logiczna
Boolean algebra
algebra Boole’a
Boolean data type
logiczny typ danych, Boole’owski typ danych
Boolean operation
działanie logiczne, operacja logiczna, operacja boole’owska
Boolean value
wartość logiczna, wartość boole’owska
boolean-valued
o wartości logicznej
built-in
wbudowany
combinational circuit
układ kombinacyjny
combinational logic
logika kombinacyjna
comparison operator
operator porównywania, operator porównawczy
complement
dopełnienie
condition
warunek
conditional command
polecenie warunkowe
conjunction
koniunkcja
decoder
dekoder
demultiplexer
demultiplekser
developed by
rozwinięty przez, opracowany przez
digital circuit
układ cyfrowy
digital logic
logika cyfrowa
disjunction
alternatywa
electronic circuit
układ elektroniczny
encoder
koder
equivalence
równoważność, ekwiwalencja
explicit
jawny, bezpośredni
false
fałsz
full adder
sumator
full subtractor
subtraktor
function
funkcja
fundamental block of sth
podstawowy blok budowy czegoś
gate delay
opóźnienie bramkowe
ground
masa
half adder
półsumator
half subtractor
półsubtraktor
if and only if
gdy i tylko gdy
input signal
sygnał wejściowy
invert
odwrócić
inverter gate
inwerter
inverter
inwerter
iterative command
polecenie iteracyjne
lead
przewód
list
lista
logic 0
zero logiczne
logic gate
bramka logiczna
logic
logiczny
logical data type
logiczny typ danych
logical expression
wyrażenie logiczne
mathematical calculations
obliczenia matematyczne
multiplexer
multiplekser
NAND (alternative denial)
NAND (dysjunkcja)
NAND gate
bramka NAND
negation
negacja
negation
negacja
non-equivalence
nierównoważność
non-zero value
wartość niezerowa
NOR (logical nor, joint denial)
NOR (nor logiczne, negacja obustronna, binegacja)
NOR gate
bramka NOR
NOT gate
bramka NOT
NOT
nie
operand
argument
OR gate
bramka OR
OR
lub
output port
port wyjściowy
output signal
sygnał wyjściowy
part of sth
część czegoś
port
port
programmer-specified
określony przez programistę
relational expression
wyrażenie relacyjne
respectively
odpowiednio (jak w zdaniu: variables x and y were assigned values 2 and 4 respectively)
sequential logic
logika sekwencyjna
set theory
teoria zbiorów
shape
kształt
statistics
statystyka
subarea
poddziedzina
supply voltage
napięcie zasilania
the main/basic operations of x
główne/podstawowe działania/operacje x
the primary result of sth
główny wynik czegoś
to be fundamental in the development of x
odgrywać kluczową rolę w rozwoju x
to be intended
to być przeznaczonym do
to be the basis of x
być podstawą x
to be used to build
być użytym do budowy
to belong to
należeć do
to copy the input to the output
skopiować dane z wejścia na wyjście
to depict sth schematically
przedstawić coś na schemacie
to derive from sth
otrzymać z czegoś, derywować z czegoś
to do mathematical calculations
wykonywać obliczenia matematyczne
to evaluate to
dawać w wyniku wartość
to follow a convention
postępować zgodnie z konwencją
to make sth by using sth
zrobić coś przy użyciu czegoś
to return
zwrócić
to yield
dać, zwrócić wynik
triangle
trójkąt
true
prawda
truth table
tabela prawdy
voltage
napięcie
wire
przewód, drut
XOR (exclusive OR, exclusive disjunction)
XOR (lub wykluczające, alternatywa wykluczająca)
XOR gate
bramka XOR

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:

[1] Gates are electronic circuits that produce output signals based on performing Boolean operations on their input signals.

[2] The triangle denotes the operation that simply copies the input to the output;

[3] Practical computer circuits normally contain a mixture of combinational and sequential logic.

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

Jeden komentarz

  1. Świetny kurs. Dzięki :+)

    Czy będzie ciąg dalszy?

    Pozdrawiam
    Virtus

Odpowiedz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *