Instructions for translators

1. Open this file on GitHub server. If you see https://um.mendelu.cz/... in URL, click View on GitHub to open this file on github.com.
2. If you see this file on GitHub server, you can edit the content of the file. Open the file in an editor. You can use simple editor (pres e on GitHub). However, an advanced VS Code editor (press . on GitHub) is better, since it provides preview how the Markdown code renders. Alternatively press pencil for simple editor or press triangle next to the pencil to get access to VS Code described as github.dev.
3. Fix the keywords in the preamble.
4. Depending on which language version you want to use as a source for your translation, delete either English or Czech version below.
5. Translate to your language. Keep Markdown marking and math notation. If you use a tool to get first version of the translation, make sure that the markup is preserved.
6. In VS Code you can open the preview in another window by pressing Ctrl+V and K. Keep the preview open as you work, or close using a mouse.
7. Instead of saving, you have to commit and push the changes to the repository. Fill the Message under Source control (describe your changes, such as “Polish translation started”) and then press Commit&Push.
8. Make sure that your changes appear in the commit history. In rare cases (if you work with simultaneously with someone else) you have to download /Pull/ and merge his and yours changes. Usualy Sync (Pull & Push) should work.
9. When you finish the translation, change is_finished: False in header to is_finished: True.

Instrukce pro překladatele

1. Otevřete tento soubor na serveru GitHub. Pokud máte soubor otevřen na https://um.mendelu.cz/..., otevřete jej na serveru github.com.
2. Pokud tento soubor vidíte na serveru GitHub, můžete obsah souboru upravit. Otevřete soubor v editoru. Můžete použít jednoduchý editor (stiskněte e na GitHubu). Lepší je však pokročilý editor VS Code (stikněte . na GitHubu), protože poskytuje náhled, jak se kód Markdown interpretuje. Případně stiskněte tužku pro jednoduchý editor nebo stiskněte trojúhelníček vedle tužky, abyste získali přístup k editoru VS Code popsaný jako github.dev.
3. Opravte klíčová slova v preambuli.
4. V závislosti na tom, kterou jazykovou verzi chcete použít jako zdrojový kód pro svůj překladu, odstraňte níže uvedenou anglickou nebo českou verzi.
5. Přeložte do svého jazyka. Ponechte značení Markdown a matematický zápis. Pokud použijete nástroj typu DeepL pro získání první verze překladu, ujistěte se, že zápis matematických výrazů byl zachován.
6. Ve VS Code můžete náhled otevřít v jiném okně stisknutím Ctrl+V. a K. Během práce nechte náhled otevřený nebo jej zavřete pomocí myši.
7. Místo uložení musíte změny zaregistrovat a odeslat do úložiště. Vyplňte zprávu v poli Zpráva (popište své změny, např. “Zahájen překlad do polštiny”) a poté stiskněte tlačítko Commit&Push.
8. Ujistěte se, že se vaše změny objeví v historii revizí. Ve výjimečných případech (pokud pracujete současně s někým jiným) musíte stáhnout /Pull/ a sloučit jeho a vaše změny. Obvykle by synchronizace (Pull & Push) měla fungovat.
9. Po dokončení překladu změňte is_finished: False v záhlaví na is_finished: True.

Czech source

Logické obvody

Které kouzlo dokáže v přetíženém výtahu rozsvítit správnou kontrolku, stiskem tlačítka automatu připravit pomerančovou sodovku, po pár minutách zhasnout rozsvícená světla v chodbě domu nebo pohybovat s postavou na obrazovce počítače? O tyto a celou řadu dalších činností v reálném životě se starají logické obvody, které podrobněji prozkoumáme v následující sérii úloh.

Logické obvody se skládají z tzv. logických členů, které realizují logické operace. V úlohách budeme pracovat pouze se třemi základními logickými členy NOT (negace), AND (konjunkce) a OR (disjunkce). Na obrázku jsou vidět jejich příslušné symboly (dle americké normy ANSI/MIL) v logických obvodech. Jsou orientovány tak, aby směr vstupu byl zleva. Vstupy chápeme jako výroky, výstupy jsou pak výroky složené.

Pravdivostní hodnoty jsou v logických obvodech realizovány napětím, nízké napětí značí pravdivostní hondotu 0, vysoká úroveň napětí značí hodnotu 1. Pokud je např. u členu AND na vstupu A nízká úroveň napětí a na vstupu B vysoká úroveň, je na výstupu nízká úroveň napětí. Konkrétní hodnoty úrovní se liší dle konkrétního využití obvodu. Běžná je třeba nízká úroveň přibližně 0V, vysoká přibližně 5V.

Na dalším obrázku vidíme znázornění jednoho složitějšího logického obvodu. Pro názornost je v obrázku také vyznačeno postupné skládání výroků, což odpovídá vstupům nebo výstupům jednotlivých členů. Černý puntík označuje uzel, ve kterém se logický obvod větví. Výstup jednoho členu tak může být přiveden na více vstupů zároveň.

V následujících úlohách mohou být před vstupy zařazeny spínače nebo tlačítka, za výstupy logického obvodu pak mohou být zařazeny žárovky. Dohodněme se, že na vstupu je logická hodnota rovna 1 právě tehdy, když je spínač sepnut nebo tlačítko stisknuto. Podobně žárovka svítí právě tehdy, když je na příslušném výstupu logická hodnota 1.

Řešení. Označme \(p(\mathrm{X})\) pravdivostní hodnotu výroku \(\mathrm{X}\). Ze zadání víme, že \(p(\mathrm{C})=0\), a ptáme se na hodnoty \(p(\mathrm{A})\) a \(p(\mathrm{B})\) takové, že \(p\left[ \left(\mathrm{C}\wedge \left(\mathrm{A}\vee\mathrm{B}\right)\right)\vee \left( \neg\left(\mathrm{A}\vee\mathrm{B}\right)\right) \right]=1\). Úlohu vyřešíme úvahou.

Jestliže platí \(p(\mathrm{C})=0\), pak nutně i \(p(\mathrm{C}\wedge \left(\mathrm{A}\vee\mathrm{B}\right))=0\). Proto musí být pravdivý výrok \(\neg ( \mathrm{A}\vee \mathrm{B})\), a tedy \(p(\mathrm{A}\vee \mathrm{B})=0\). To je však možné tehdy a jen tehdy, když jsou výroky \(\mathrm{A}\) i \(\mathrm{B}\) nepravdivé. Ani jeden spínač tak nesmí být sepnut.

Řešení. Úlohu budeme řešit užitím tabulky pravdivostních hodnot. Z diagramu v zadání nejprve odvodíme výrok složený z výroků \(\mathrm{A}\), \(\mathrm{B}\) a \(\mathrm{C}\), který bude ekvivalentní výroku \(\mathrm{Z}\), viz obrázek.

Pro složený výrok \(\left( \star \right)\) nyní vytvoříme tabulku pravdivostních hodnot:

Z tabulky vyplývá, že žárovka bude svítit, jestliže bude sepnutý spínač A a zároveň nebude sepnutý spínač B. Na sepnutí spínače C přitom nezáleží.

Úlohu lze řešit také ekvivalentními úpravami výroku \(\left(\star \right)\). Nejprve použijeme distributivní zákon, následně tzv. zákon idempotence \(\mathrm{A}\wedge \mathrm{A}\Leftrightarrow \mathrm{A}\):

\[ \begin{alignat*}{3} &&&\left( \mathrm{A}\wedge\neg\mathrm{B}\right) \wedge \left( \mathrm{A}\vee\mathrm{C} \right) &&\quad\Leftrightarrow\\ &\Leftrightarrow\quad &&\left( \mathrm{A}\wedge\neg\mathrm{B}\wedge\mathrm{A}\right) \vee \left( \mathrm{A}\wedge\neg\mathrm{B}\wedge\mathrm{C}\right) &&\quad\Leftrightarrow\\ &\Leftrightarrow\quad &&\left( \mathrm{A}\wedge\neg\mathrm{B}\right) \vee \left( \mathrm{A}\wedge\neg\mathrm{B}\wedge\mathrm{C}\right). && \tag{$\star\star$} \end{alignat*} \]

Složený výrok \(\left( \star\star \right)\) je však pravdivý právě tehdy, když je pravdivá konjunkce \(\mathrm{A}\wedge\neg\mathrm{B}\), tedy když je \(\mathrm{A}\) pravdivý výrok a \(\mathrm{B}\) nepravdivý výrok. Z toho vyplývá o poloze spínačů stejný závěr, který jsme učinili pomocí tabulky.

Řešení. Označme \(\mathrm{A}\) a \(\mathrm{B}\) výroky představující stav prvního a druhého čerpadla. Hledáme výrok \(\mathrm{Z}\) složený z \(\mathrm{A}\) a \(\mathrm{B}\), jehož tabulku pravdivostních hodnot známe:

Z tabulky jde poznat, že ekvivalentním výrokem je např. \(\neg\left( \mathrm{A} \wedge \mathrm{B}\right)\), kterému odpovídá diagram výsledného obvodu na obrázku:

Úloha má více řešení. Například užitím de Morganova zákona dostáváme z předchozího výsledku ekvivalentní výrok \(\neg\mathrm{A}\vee\neg\mathrm{B}\). Tomuto výroku by odpovídal jiný, ale také správný, obvod (diagram).

Řešení. Podobně jako v předchozí úloze označme \(\mathrm{A}\) a \(\mathrm{B}\) výroky představující stav prvního a druhého čerpadla. Dostaneme tak tabulku pravdivostních hodnot neznámých složených výroků \(\mathrm{Č}\) (červené světlo) a \(\mathrm{Z}\) (zelené světlo):

Je vidět, že sloupec pro výrok \(\mathrm{Č}\) je totožný s výrokem \(\mathrm{Z}\) v předchozí úloze (a tedy můžeme převzít její řešení), a sloupec pro výrok \(\mathrm{Z}\) odpovídá disjunkci \(\mathrm{A}\vee \mathrm{B}\). Využitím uzlů a rozvětvením obvodu tak můžeme zakreslit diagram odpovídajícího logického obvodu:

Podobně jako předchozí úloha má i tato více řešení, jejichž správnost je možné ověřit vždy pomocí tabulky pravdivostních hodnot. Blíže se však vyjádříme ještě k jednomu řešení.

Žáky může napadnout, že místo členu OR je možné vodiče spojit prostým uzlem, jak je znázorněno na obrázku:

Jestliže bude na \(\mathrm{A}\) nebo \(\mathrm{B}\) (popř. na obou) hodnota \(1\), může tato hodnota volně protéct i na výstup \(\mathrm{Z}\,\)? Skutečnost je taková, že nikoliv. V úvodním odstavci jsme si řekli, že pravdivostní hodnota \(1\) se realizuje vysokou úrovní napětí a hodnota \(0\) jeho nízkou úrovní. Bude-li tak např. na vstupu \(\mathrm{A}\) vysoké a na vstupu \(\mathrm{B}\) nízké napětí, dojde v obvodu ke zkratu, neboť jsou vodičem spojeny body s různým napětím. Proto obecně nemůžeme v logických obvodech spojit výstupy různých členů uzly.

Řešení. Abychom mohli obvod sestrojit, potřebujeme nalézt k ekvivalenci \(\mathrm{A}\Leftrightarrow\mathrm{B}\) složený výrok se stejnou tabulkou pravdivostních hodnot, který obsahuje pouze konjunkce, disjunkce nebo negace. Z definice pro ekvivalenci plyne, že je pravdivá právě tehdy, jsou-li výroky \(\mathrm{A}\) a \(\mathrm{B}\) oba pravdivé nebo oba nepravdivé. To znamená, že je pravdivá právě tehdy, když je pravdivá konjunkce \(\mathrm{A}\wedge\mathrm{B}\) nebo je pravdivá konjunkce \(\neg\mathrm{A}\wedge\neg\mathrm{B}\). Tak dostáváme ekvivalenci \[ \left( \mathrm{A}\Leftrightarrow\mathrm{B} \right) \quad \Leftrightarrow \quad \left( \mathrm{A}\wedge\mathrm{B} \right) \vee \left( \neg\mathrm{A}\wedge\neg\mathrm{B} \right), \] jejíž pravá strana je výrok obsahující pouze konjunkce, disjunkci a negace. Můžeme proto sestavit odpovídající diagram:

Jedno z dalších možných řešení můžeme dostat využitím de Morganových zákonů a ekvivalentní úpravou předchozího výsledku na výrok \(\left( \mathrm{A}\wedge\mathrm{B} \right) \vee \neg \left( \mathrm{A}\vee\mathrm{B} \right)\). Technickou výhodou tohoto tvaru je menší počet potřebných logických členů při realizaci obvodu.

Řešení. Označme \(\mathrm{C}\) (kakao, angl. cocoa), \(\mathrm{L}\) (lungo) a \(\mathrm{M}\) (macchiato) výroky představující stav stisknutí příslušného tlačítka a dále označme \(\mathrm{COC}\) (kakaový koncentrát, angl. cocoa concentrate), \(\mathrm{WA}\) (voda, angl. water), \(\mathrm{COF}\) (kávový koncentrát, angl. coffee concentrate) a \(\mathrm{ML}\) (mléko, angl. milk) výroky představující stav otevření příslušné trysky. Z informací v zadání pak sestavme tabulku pravdivostních hodnot:

Řádky, pro něž je v prvních třech sloupcích více než jedna jednička, nebereme v potaz, protože je možné zmáčknout vždy jen jedno tlačítko.

Z tabulky plyne, že ekvivalentní dvojicí výroků je \(\mathrm{COC}\) a \(\mathrm{C}\) a další ekvivalentní dvojicí jsou výroky \(\mathrm{ML}\) a \(\mathrm{M}\). Výrok \(\mathrm{COF}\) je pravdivý právě tehdy, když je pravdivý některý z výroků \(\mathrm{L}\) nebo \(\mathrm{M}\), tedy je ekvivalentní s disjunkcí \(\mathrm{L}\vee\mathrm{M}\). A konečně výrok \(\mathrm{WA}\) je pravdivý právě tehdy, když je některý z trojice výroků \(\mathrm{C}\), \(\mathrm{L}\), \(\mathrm{M}\) pravdivý, tedy je \(\mathrm{WA}\) ekvivalentní s disjunkcí \(\mathrm{C}\vee\mathrm{L}\vee\mathrm{M}\).

Na následujícím obrázku je znázorněn diagram příslušného obvodu - disjunkce \(\mathrm{C}\vee\mathrm{L}\vee\mathrm{M}\) je v něm přitom realizována vnořením dvou členů OR, tj. jako \(\mathrm{C}\vee\left( \mathrm{L}\vee\mathrm{M}\right)\).

Všechny uvedené úlohy je možné názorně ilustrovat na různých simulátorech logických obvodů, např. online simulátoru CircuitVerse. Na posledním obrázku je v tomto simulátoru modelován obvod z Úlohy 2. K ilustraci je také možné využít specializovaných elektronických stavebnic.

Literatura

• Perrin J. P., Denouette M., Daclin E. Logické systémy, díl I. Kombinační logické obvody. Úvod do sekvenčních obvodů. Praha: SNTL. 1972
• Online simulátor CircuitVerse, https://circuitverse.org/simulator

English source

Logic circuits

Which spell can turn on the correct indicator light in an overloaded elevator, prepare an orange soda by pressing the button on a vending machine, turn off the lights in the hallway of a house after a few minutes, or move a character on a computer screen? These and many other real-life activities are handled by logic circuits, which we will explore in more detail in the following series of problems.

Logic circuits consist of so-called logic gates that implement logic operations. We will work only with three basic logic gates, namely NOT (negation), AND (conjunction) and OR (disjunction), in the exercises. The figure shows their respective symbols (according to the American ANSI/MIL standard) in logic circuits. They are oriented so that the input direction is from the left. Inputs are understood as statements, while outputs are compound statements.

The truth values are implemented in logic circuits by voltage. Low voltage indicates a truth value of 0, while a high voltage level indicates a value of 1. For example, if the AND gate has a low voltage level at input A and a high voltage level at input B, the output is a low voltage level. The specific values of the levels vary according to the specific use of the circuit. A low level of approximately 0 V and a high level of approximately 5 V are common.

In the next figure we see a representation of a more complex logic circuit. For clarity, the figure also shows the sequential compounding of statements, which correspond to the inputs or outputs of the individual gates. The black dot indicates the node at which the logic circuit branches. Thus, the output of one gate can be fed to multiple inputs at the same time.

In the following exercises, switches or buttons can be placed in front of the inputs, and light bulbs can be placed behind the outputs of the logic circuit. Let’s agree that the logic value at the input is equal to 1 if and only if the switch is on or the button is pressed. Similarly, a light bulb lights if and only if there is a logic value of 1 at the corresponding output.

Solution. Let \(p(\mathrm{X})\) denote the truth value of the statement \(\mathrm{X}\). We know from the assignment that \(p(\mathrm{C})=0\), and we ask for the values ​​of \(p(\mathrm{A})\) and \(p(\mathrm{B})\) such that \(p\left[ \left(\mathrm{C}\wedge \left(\mathrm{A}\vee\mathrm{B}\right)\right)\vee \left( \neg\left(\mathrm{A}\vee\mathrm{B}\right)\right) \right]=1\). We will solve the exercise by reasoning.

If \(p(\mathrm{C})=0\) holds, then necessarily \(p(\mathrm{C}\wedge \left(\mathrm{A}\vee\mathrm{B}\right))=0\). Therefore the statement \(\neg ( \mathrm{A}\vee \mathrm{B})\) must be true, and therefore \(p(\mathrm{A}\vee \mathrm{B})=0\). However, this is possible if and only if the statements \(\mathrm{A}\) and \(\mathrm{B}\) are both false. Therefore, both switches must remain closed.

Solution. We will solve the problem by using the truth table. From the diagram in the assignment, we first derive a statement consisting of the statements \(\mathrm{A}\), \(\mathrm{B}\) and \(\mathrm{C}\), which will be equivalent to the statement \(\mathrm{Z}\), see figure.

For the compound statement \(\left( \star \right)\) we now create a truth table:

The table shows that the bulb lights if switch A is closed and switch B is not closed at the same time. The position of switch C does not matter.

The problem can also be solved by equivalent modifications of the statement \(\left(\star \right)\). First, we use the distributive law, then the so-called idempotent law \(\mathrm{A}\wedge \mathrm{A}\Leftrightarrow \mathrm{A}\):

\[ \begin{alignat*}{3} &&&\left( \mathrm{A}\wedge\neg\mathrm{B}\right) \wedge \left( \mathrm{A}\vee\mathrm{C} \right) &&\quad\Leftrightarrow\\ &\Leftrightarrow\quad &&\left( \mathrm{A}\wedge\neg\mathrm{B}\wedge\mathrm{A}\right) \vee \left( \mathrm{A}\wedge\neg\mathrm{B}\wedge\mathrm{C}\right) &&\quad\Leftrightarrow\\ &\Leftrightarrow\quad &&\left( \mathrm{A}\wedge\neg\mathrm{B}\right) \vee \left( \mathrm{A}\wedge\neg\mathrm{B}\wedge\mathrm{C}\right). && \tag{$\star\star$} \end{alignat*} \]

However, the compound statement \(\left( \star\star \right)\) is true if and only if the conjunction \(\mathrm{A}\wedge\neg\mathrm{B}\) is true, i.e. if \(\mathrm{A}\) is a true statement and \(\mathrm{B}\) is a false statement. This implies the same conclusion about the position of the switches that we made using the table.

Solution. Let us denote \(\mathrm{A}\) and \(\mathrm{B}\) the statements representing the state of the first and second pumps. We are looking for the statement \(\mathrm{Z}\) composed of \(\mathrm{A}\) and \(\mathrm{B}\), whose truth table we know:

The table shows that the equivalent statement is \(\neg\left( \mathrm{A} \wedge \mathrm{B}\right)\), which corresponds to the diagram of the resulting circuit in the figure:

The problem has more solutions. For example, using de Morgan’s laws, we get from the previous result the equivalent statement \(\neg\mathrm{A}\vee\neg\mathrm{B}\). This statement could be represented by a different, but equally correct, circuit diagram.

Solution. Similar to the previous problem, let us denote by \(\mathrm{A}\) and \(\mathrm{B}\) the statements representing the state of the first and second pumps. Thus we get a truth table of the values ​​of the unknown compound statements \(\mathrm{R}\) (red light) and \(\mathrm{G}\) (green light):

We can see that the column for the statement \(\mathrm{R}\) is identical to the statement \(\mathrm{Z}\) in the previous exercise (and thus we can adopt its solution), and the column for the statement \(\mathrm{G}\) corresponds to the disjunction \(\mathrm{A}\vee \mathrm{B}\). By using nodes and branching the circuit, we can draw a diagram of the corresponding logic circuit:

Similar to the previous problem, this one also has multiple solutions, the correctness of which can always be verified using the truth table. However, we will discuss one of the solutions in more detail.

Students may think that instead of an OR gate, the wires can be connected with a simple node as shown in the figure:

If there is a value of \(1\) on \(\mathrm{A}\) or \(\mathrm{B}\) (or both), can this value flow freely to the output \(\mathrm{G}\,\)? The reality is that it can’t. In the opening paragraph, we noted that the truth value \(1\) is realized by a high voltage level and the value \(0\) by its low level. Thus, for example, if there is a high voltage at the input \(\mathrm{A}\) and a low voltage at the input \(\mathrm{B}\), a short circuit will occur in the circuit, because points with different voltages are connected by a wire. Therefore, in general, we cannot connect the outputs of different gates by nodes in logic circuits.

Solution. In order to construct the circuit, we need to find a compound statement equivalent to \(\mathrm{A}\Leftrightarrow\mathrm{B}\)
with the same truth table that contains only conjunctions, disjunctions, or negations. The definition for equivalence implies that it is true if and only if statements \(\mathrm{A}\) and \(\mathrm{B}\) are both true or both false. That is, it is true if and only if the conjunction \(\mathrm{A}\wedge\mathrm{B}\) is true or the conjunction $ is true. Thus we get the equivalence \[ \left( \mathrm{A}\Leftrightarrow\mathrm{B} \right) \quad \Leftrightarrow \quad \left( \mathrm{A}\wedge\mathrm{B} \right) \vee \left( \neg\mathrm{A}\wedge\neg\mathrm{B} \right), \] whose right-hand side is a statement containing only conjunctions, disjunctions and negations. We can therefore construct the corresponding diagram:

One of the other possible solutions can be obtained by using de Morgan’s laws and by equivalent modifications of the previous result to statement \(\left( \mathrm{A}\wedge\mathrm{B} \right) \vee \neg \left( \mathrm{A}\vee\mathrm{B} \right)\). The technical advantage of this form is the smaller number of necessary logic gates when implementing the circuit.

Solution. Let us denote by \(\mathrm{C}\) (cocoa), \(\mathrm{L}\) (lungo) and \(\mathrm{M}\) (macchiato) statements representing the state of pressing the corresponding button, and further denote \(\mathrm{COC}\) (cocoa concentrate), \(\mathrm{WA}\) (water), \(\mathrm{COF}\) (coffee concentrate) and \(\mathrm{ML}\) (milk) statements representing the opening status of the respective nozzle. From the information in the assignment, let’s create a truth table:

Rows with more than one 1 in the first three columns are not taken into account, since only one button can be pressed at a time.

The table shows that the equivalent pair of statements is \(\mathrm{COC}\) and \(\mathrm{C}\) and another equivalent pair is the statements \(\mathrm{ML}\) and \(\mathrm{M}\). The statement \(\mathrm{COF}\) is true if and only if one of the statements \(\mathrm{L}\) or \(\mathrm{M}\) is true, i.e. it is equivalent to the disjunction \(\mathrm{L}\vee\mathrm {M}\). And finally, the statement \(\mathrm{WA}\) is true if and only if any of the three statements \(\mathrm{C}\), \(\mathrm{L}\), \(\mathrm{M}\) is true, that is \(\mathrm{WA}\) is equivalent to the disjunction \(\mathrm{C}\vee\mathrm{L}\vee\mathrm{M}\).

The following figure shows a diagram of the corresponding circuit - the disjunction \(\mathrm{C}\vee\mathrm{L}\vee\mathrm{M}\) is implemented by inserting two OR terms, i.e. as \(\mathrm{C}\vee\left( \mathrm{L}\vee\mathrm{M}\right)\).

All the mentioned exercises can be illustrated on various logic circuit simulators, e.g. CircuitVerse online simulator. In the last figure, the circuit from Exercise 2 is modeled using this simulator. It is also possible to use specialized electronic kits for illustration.

Literature

• Perrin J. P., Denouette M., Daclin E. Logické systémy, díl I. Kombinační logické obvody. Úvod do sekvenčních obvodů. Praha: SNTL. 1972
• Online simulátor CircuitVerse, https://circuitverse.org/simulator