Chapterبەش 7 · Lectureوانە 7.3

De Morgan's Theoremsسەلمێنراوەکانی دی مۆرگان

How to remove a NOT bar that covers a whole AND or OR: De Morgan's two theorems with truth-table proofs, the rule “break the bar, change the sign”, more variables, bars over groups, the gate pictures (NAND = negative-OR, NOR = negative-AND), the same law for sets and for conditions in programs, and the lecture's eight exercises.

چۆن هێڵێکی NOT لادەبەیت کە هەموو ANDـێک یان ORـێک دادەپۆشێت: هەردوو لەگەڵ سەلماندنیان بە ، یاسای «هێڵەکە بشکێنە، نیشانەکە بگۆڕە»، زیاتر، هێڵ لەسەر گرووپ، وێنەی (NAND = ، NOR = )، هەمان یاسا بۆ و بۆ لە بەرنامەکاندا. لە کۆتاییدا هەشت ڕاهێنانەکەی وانەکە.

13 min read15 خولەک خوێندنەوە · 16 stepsهەنگاو

What you will learnچی فێر دەبیت

State De Morgan's two theorems in words and as formulas, and prove them with a truth table.
Apply “break the bar, change the sign” to expressions with many variables, groups and double bars.
Explain why a NAND gate equals an OR gate with inverted inputs and a NOR gate equals an AND gate with inverted inputs.
Recognise the same law for sets and for conditions in programs.

هەردوو بە وشە و بە هاوکێشە بڵێیت و بە بیانسەلمێنیت.
یاسای «هێڵەکە بشکێنە، نیشانەکە بگۆڕە» لەسەر چەند ، گرووپ و هێڵی دووانە جێبەجێ بکەیت.
ڕوون بکەیتەوە بۆچی یەکسانە بە کە پێچەوانەکراون و یەکسانە بە کە پێچەوانەکراون.
هەمان یاسا لە و لە بەرنامەکاندا بناسیتەوە.

A bar over a whole groupهێڵێک لەسەر هەموو گرووپێک

In Boolean algebra a bar over a letter means NOT. A short bar over one letter is easy: $\overline{A}$ is the complement of A. But often one long bar covers a whole group: $\overline{AB}$ means “NOT (A AND B)” and $\overline{A+B}$ means “NOT (A OR B)”. You cannot simply copy the long bar onto each letter: $\overline{AB}$ is not the same as $\overline{A}\,\overline{B}$ . De Morgan's two theorems tell you exactly what a long bar turns into.

لە هێڵێک لەسەر پیتێک واتە NOT. هێڵێکی کورت لەسەر یەک پیت ئاسانە: $\overline{A}$ Aـیە. بەڵام زۆرجار یەک هێڵی درێژ هەموو گرووپێک دادەپۆشێت: $\overline{AB}$ واتە «⁦NOT (A AND B)⁩» و $\overline{A+B}$ واتە «⁦NOT (A OR B)⁩». ناتوانیت هێڵە درێژەکە بە سادەیی بخەیتە سەر هەر پیتێک: $\overline{AB}$ هەمان $\overline{A}\,\overline{B}$ نییە. ڕێک پێت دەڵێن هێڵە درێژەکە دەبێتە چی.

Definitionپێناسە

Two rules for the complement of AND and OR: $\overline{AB} = \overline{A} + \overline{B}$ and $\overline{A + B} = \overline{A}\,\overline{B}$ . In short: break the bar and change the sign.

دوو یاسان بۆ AND و OR: $\overline{AB} = \overline{A} + \overline{B}$ و $\overline{A + B} = \overline{A}\,\overline{B}$ . بە کورتی: هێڵەکە بشکێنە و نیشانەکە بگۆڕە.

The theorems carry the name of Augustus De Morgan, a British mathematician who wrote them down in 1847, the same year George Boole published his first book on the algebra of logic. Today they are used every day: to redraw circuits with cheaper gates, to simplify expressions and to rewrite conditions in programs.

ناوی ئۆگەستەس دی مۆرگانیان لەسەرە، بیرکارزانێکی بەریتانی کە لە ساڵی ⁦1847⁩ نووسینی، هەمان ساڵ کە جۆرج بوول یەکەم کتێبی خۆی لەسەر لۆجیک بڵاو کردەوە. ئەمڕۆ هەموو ڕۆژێک بەکار دەهێنرێن: بۆ دووبارە کێشانەوەی بە هەرزانتر، بۆ کورتکردنەوەی و بۆ نووسینەوەی لە بەرنامەکاندا.

A bar over a whole groupهێڵێک لەسەر هەموو گرووپێک

Two orders in the tea houseدوو داواکاری لە چایخانە

Aram tells the waiter: “It is not true that I want tea and sugar.” He does not want the two together, so either he wants no tea, or no sugar, or neither: NOT (tea AND sugar) = (NOT tea) OR (NOT sugar). Shilan says: “I want neither tea nor coffee.” That is NOT (tea OR coffee), and it means no tea AND no coffee. These are exactly De Morgan's two theorems.

ئارام بە چایچییەکە دەڵێت: «وا نییە کە چا و شەکرم پێکەوە بوێت.» ئەو هەردووکیانی پێکەوە ناوێت، کەواتە یان چای ناوێت یان شەکری ناوێت یان هیچیان: NOT (چا AND شەکر) = (NOT چا) ⁦OR (NOT⁩ شەکر). شیلان دەڵێت: «نە چام دەوێت نە قاوە.» ئەوە NOT (چا OR قاوە)ـیە و واتای ئەوەیە: چا نا AND قاوە نا. ئەمانە ڕێک هەردوو .

Where the analogy stops workingسنووری ئەم نموونەیە

Everyday speech is loose: people say “not tea and sugar” for different things. In Boolean algebra the bar shows exactly what is negated, so there is never a doubt.

قسەی ڕۆژانە ورد نییە: خەڵک «چا و شەکرم ناوێت» بۆ مەبەستی جیاواز دەڵێن. لە هێڵەکە ڕێک نیشان دەدات چی نەفی کراوە، بۆیە هەرگیز گومان نامێنێت.

Quick checkپشکنینی خێراShilan wants neither tea nor coffee. With T for tea and C for coffee, which expression describes her order?شیلان نە چای دەوێت نە قاوە. ئەگەر T بۆ چا و C بۆ قاوە بێت، کام داواکارییەکەی وەسف دەکات؟

\overline{T}+\overline{C}

\overline{T}+\overline{C}

T+C

T+C

\overline{T}\,\overline{C}

\overline{T}\,\overline{C}

Theorem 1: NOT of an ANDسەلمێنراوی یەکەم: NOTـی AND

The complement of a product equals the sum of the complements. Said another way: NOT of two or more ANDed variables is the same as the OR of the separate NOTs.

لێکدانێک یەکسانە بە کۆی . بە واتایەکی تر: NOTـی دوو یان زیاتر کە بە AND بەستراون هەمانە لەگەڵ ORـی NOTـی هەر یەکێکیان.

\overline{A \cdot B} = \overline{A} + \overline{B}

Proof by truth table: the two bold columns are equal in every row.سەلماندن بە : دوو ستوونە ئەستوورەکە لە هەموو ڕیزێکدا یەکسانن.
$A$	$B$	$AB$	$\overline{AB}$	$\overline{A}$	$\overline{B}$	$\overline{A}+\overline{B}$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Why is it true? $AB$ is 1 in only one row, where $A = B = 1$ , so $\overline{AB}$ is 0 only in that row. On the other side, $\overline{A}+\overline{B}$ is 0 only when both $\overline{A}$ and $\overline{B}$ are 0, which again means $A = B = 1$ . One single 0 in the same row, and 1 everywhere else.

بۆچی ڕاستە؟ $AB$ تەنها لە یەک ڕیزدا 1ـە، ئەویش کاتێک $A = B = 1$ ، بۆیە $\overline{AB}$ تەنها لەو ڕیزەدا 0ـە. لە لایەکی ترەوە $\overline{A}+\overline{B}$ تەنها کاتێک 0ـە کە $\overline{A}$ و $\overline{B}$ هەردووکیان 0 بن، واتە دیسان $A = B = 1$ . یەک 0 لە هەمان ڕیزدا و لە هەموو شوێنێکی تر 1.

Theorem 2: NOT of an ORسەلمێنراوی دووەم: NOTـی OR

The complement of a sum equals the product of the complements. NOT of two or more ORed variables is the same as the AND of the separate NOTs.

کۆیەک یەکسانە بە لێکدانی . NOTـی دوو یان زیاتر کە بە OR بەستراون هەمانە لەگەڵ ANDـی NOTـی هەر یەکێکیان.

\overline{A + B} = \overline{A} \cdot \overline{B} = \overline{A}\,\overline{B}

Proof by truth table: the two bold columns are equal in every row.سەلماندن بە : دوو ستوونە ئەستوورەکە لە هەموو ڕیزێکدا یەکسانن.
$A$	$B$	$A+B$	$\overline{A+B}$	$\overline{A}$	$\overline{B}$	$\overline{A}\,\overline{B}$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Why? $A+B$ is 0 only when $A = B = 0$ , so $\overline{A+B}$ is 1 only in that row. $\overline{A}\,\overline{B}$ is 1 only when $\overline{A}$ and $\overline{B}$ are both 1, which is again $A = B = 0$ . Notice that the two theorems are mirror images: swap AND with OR in one and you get the other.

بۆچی؟ $A+B$ تەنها کاتێک 0ـە کە $A = B = 0$ ، بۆیە $\overline{A+B}$ تەنها لەو ڕیزەدا 1ـە. $\overline{A}\,\overline{B}$ تەنها کاتێک 1ـە کە $\overline{A}$ و $\overline{B}$ هەردووکیان 1 بن، واتە دیسان $A = B = 0$ . سەرنج بدە کە هەردوو وێنەی ئاوێنەی یەکترن: لە یەکێکیاندا AND و OR جێگۆڕکێ پێ بکە، ئەوی تر دەردەچێت.

3 Ways to Show a Logical Equivalence | Ex: DeMorgan's LawsDr. Trefor Bazett · Englishئینگلیزی · 265K viewsبینین · 4K likesلایک
Proves De Morgan's law for NOT (p OR q) three ways: with a truth table, with known laws and with an everyday sentence.
بۆ NOT (p OR q) بە سێ ڕێگا دەسەلمێنێت: بە ، بە یاسا ناسراوەکان و بە نموونەیەکی ژیانی ڕۆژانە.
Whole video (5:29): truth-table proof of ~(p ∨ q) ≡ ~p ∧ ~q, an everyday check, then both laws used in a short simplification.
هەموو ڤیدیۆکە ⁦(5:29)⁩: $\sim(p \lor q) \equiv \sim p \land \sim q$ بە ، پشکنینێکی ڕۆژانە، پاشان بەکارهێنانی هەردوو یاساکە لە نموونەیەکی کورتی کورتکردنەوەدا.

Break the bar, change the signهێڵەکە بشکێنە، نیشانەکە بگۆڕە

Both theorems are one single move. Break the long bar into short bars, one over each piece, and change the sign where the bar broke: · becomes +, and + becomes ·. Watch the move for three variables, first under an OR and then under an AND:

هەردوو یەک جووڵەن. هێڵە درێژەکە بشکێنە بۆ چەند هێڵێکی کورت (یەکێک لەسەر هەر پارچەیەک). پاشان لەو شوێنەی هێڵەکە شکا نیشانەکە بگۆڕە: · دەبێتە + و + دەبێتە ·. سەیری ئەم جووڵەیە بکە بۆ سێ ، یەکەم لە ژێر ORـدا و پاشان لە ژێر ANDـدا:

Animation. One long bar covers A + B + C. Cracks appear above both plus signs, the bar breaks into three short bars over A, B and C, and each plus sign turns into a dot: the result is A-bar · B-bar · C-bar. Then the same happens to a long bar over A · B · C: the bar breaks and each dot becomes a plus, giving A-bar + B-bar + C-bar. The last frame shows both equations under the words “Break the bar, change the sign”. — De Morgan's theorems in one move: break the bar, change the sign. لە یەک جووڵەدا: هێڵەکە بشکێنە، نیشانەکە بگۆڕە.CêIT

The move also works backwards: short bars joined by one sign can be joined into one bar while the sign changes, for example $\overline{A}+\overline{B} = \overline{AB}$ . Designers use this direction to turn an expression into NAND or NOR gates.

ئەم جووڵەیە بە پێچەوانەشەوە کار دەکات: چەند هێڵێکی کورت کە بە یەک نیشانە بەستراون دەتوانرێت بکرێنە یەک هێڵ و نیشانەکەش بگۆڕدرێت، بۆ نموونە $\overline{A}+\overline{B} = \overline{AB}$ . دیزاینەران ئەم ئاراستەیە بەکار دەهێنن بۆ ئەوەی بکەنە یان .

Three, four or more variablesسێ، چوار یان زیاتر گۆڕاوی بوولی

The theorems are not limited to two variables. Any number of ANDed variables under one bar becomes the OR of the separate complements, and any number of ORed variables becomes the AND of the separate complements:

تەنها بۆ دوو نین. هەر ژمارەیەک کە لە ژێر یەک هێڵدا بە AND بەستراون دەبێتە ORـی . هەر ژمارەیەکیش کە بە OR بەستراون دەبێتە ANDـی :

\begin{aligned} \overline{ABC\cdots} &= \overline{A}+\overline{B}+\overline{C}+\cdots \\ \overline{A+B+C+\cdots} &= \overline{A}\,\overline{B}\,\overline{C}\cdots \end{aligned}

Why does it still work? Treat a group as one letter and use the two-variable theorem twice. For $\overline{ABC}$ , think of $BC$ as one variable:

بۆچی هێشتا کار دەکات؟ گرووپێک وەک یەک پیت دابنێ و بۆ دوو دوو جار بەکاربهێنە. بۆ $\overline{ABC}$ ، $BC$ وەک یەک دابنێ:

\overline{A\,(BC)} = \overline{A} + \overline{BC} = \overline{A} + \overline{B} + \overline{C}

Quick checkپشکنینی خێرا

\overline{A+B+C+D}

equals …

\overline{A+B+C+D}

یەکسانە بە …

\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}

\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}

\overline{ABCD}

\overline{ABCD}

\overline{A}+\overline{B}+\overline{C}+\overline{D}

\overline{A}+\overline{B}+\overline{C}+\overline{D}

Bars over groups and double barsهێڵ لەسەر گرووپ و هێڵی دووانە

Real expressions mix AND and OR, and bars can sit on top of other bars. Three habits keep you safe:

AND و OR تێکەڵ دەکەن و هێڵەکان دەتوانن لەسەر هێڵی تر بن. سێ خوو بە سەلامەتی دەتهێڵنەوە:

Break one bar at a time, starting with the longest one.
Whatever sits under one piece of the bar is one block. Keep it in brackets, so the order of AND and OR does not change.
Two bars over exactly the same thing cancel: $\overline{\overline{X}} = X$ (rule 9).

هەر جارە یەک هێڵ بشکێنە و لە درێژترینیانەوە دەست پێبکە.
هەرچی لە ژێر یەک پارچەی هێڵدایە یەک بلۆکە. لە ناو کەوانەدا بیهێڵەوە تا ڕیزبەندیی AND و OR نەگۆڕێت.
دوو هێڵ لەسەر ڕێک هەمان شت یەکتر لادەبەن: $\overline{\overline{X}} = X$ (یاسای 9).

Worked exampleنموونەی شیکراوە

Start with $\overline{\overline{P}Q + R}$ . The longest bar covers an OR of two blocks, $\overline{P}Q$ and $R$ . Break it and change + into · (theorem 2):
بە $\overline{\overline{P}Q + R}$ دەست پێبکە. درێژترین هێڵ ORـی دوو بلۆک دادەپۆشێت، $\overline{P}Q$ و $R$ . بیشکێنە و + بگۆڕە بۆ · ( دووەم):
$\overline{\overline{P}Q + R} = \overline{\overline{P}Q}\cdot\overline{R}$
The first block still has a bar over an AND. Break it and change · into + (theorem 1):
بلۆکی یەکەم هێشتا هێڵێکی لەسەر ANDـێکە. بیشکێنە و · بگۆڕە بۆ + ( یەکەم):
$\overline{\overline{P}Q} = \overline{\overline{P}} + \overline{Q}$
The two bars over P cover exactly the same thing, so they cancel (rule 9). Put the block back in brackets:
دوو هێڵەکەی سەر P ڕێک هەمان شت دادەپۆشن، بۆیە یەکتر لادەبەن (یاسای ⁦9⁩). بلۆکەکە بگەڕێنەوە ناو کەوانە:
$\overline{\overline{P}Q + R} = (P + \overline{Q})\,\overline{R}$

Quick checkپشکنینی خێراApply De Morgan's theorems to

\overline{(A+\overline{B})C}

. لەسەر

\overline{(A+\overline{B})C}

جێبەجێ بکە.

(\overline{A}+B)\,\overline{C}

(\overline{A}+B)\,\overline{C}

\overline{A}\,\overline{B} + \overline{C}

\overline{A}\,\overline{B} + \overline{C}

\overline{A}B + \overline{C}

\overline{A}B + \overline{C}

De Morgan in gatesدی مۆرگان لە گەیتەکاندا

Each theorem is also a fact about gates. The left side of theorem 1, $\overline{AB}$ , is a NAND gate. The right side, $\overline{A}+\overline{B}$ , is an OR gate with a bubble (a NOT) on each input, called a negative-OR. So a NAND gate is the same as an OR gate with inverted inputs. In the same way theorem 2 says that a NOR gate is the same as an AND gate with inverted inputs, a negative-AND. De Morgan's theorems prove what you saw in Negative-OR and negative-AND.

هەر ڕاستییەکیشە دەربارەی . لای چەپی یەکەم، $\overline{AB}$ ، . لای ڕاستی، $\overline{A}+\overline{B}$ ، کە (NOTـێک) لەسەر هەر هەیە و پێی دەوترێت . کەواتە هەمان کە پێچەوانە کراونەتەوە. بە هەمان شێوە دووەم دەڵێت هەمان کە پێچەوانە کراونەتەوە، واتە . ئەوە دەسەلمێنن کە لە گەیتی Negative-OR و گەیتی Negative-AND بینیت.

NAND = negative-OR (theorem 1) and NOR = negative-AND (theorem 2).NAND = ( یەکەم) و NOR = ( دووەم).CêIT

Why does it matter? In CMOS chips a NAND or NOR gate needs fewer transistors than an AND or OR gate (an AND is a NAND followed by a NOT). De Morgan's theorems let designers redraw a circuit with these gates without changing what it does, as in the NAND-NAND circuit.

بۆچی گرنگە؟ لە CMOSـەکاندا یان پێویستی بە کەمترە لە یان (AND لە ڕاستیدا NANDـێکە و NOTـێکی بە دوادا دێت). ڕێگە بە دیزاینەران دەدەن بەم دووبارە بکێشنەوە بێ ئەوەی کارەکەی بگۆڕێت. نموونەیەکی: سووڕی لۆجیکیی ⁦NAND-NAND⁩.

De Morgan in gatesدی مۆرگان لە گەیتەکاندا

Pushing bubblesجووڵاندنی بازنەکان

Circuit designers use De Morgan as a rule for moving bubbles. Push a bubble through a gate and the gate changes shape: AND becomes OR and OR becomes AND, while the bubble moves to the other side (from the output onto every input, or back). And two bubbles on the same wire cancel, because $\overline{\overline{A}} = A$ .

دیزاینەرانی دی مۆرگان وەک یاسایەک بۆ جووڵاندنی بەکار دەهێنن. بە ناو تێپەڕێنە و شێوەی دەگۆڕێت: AND دەبێتە OR و OR دەبێتە AND، لە کاتێکدا بازنەکە دەچێتە لایەکەی تر (لە بۆ سەر هەموو ، یان بە پێچەوانەوە). هەروەها دوو بازنە لەسەر هەمان وایەر یەکتر لادەبەن، چونکە $\overline{\overline{A}} = A$ .

Start withدەستپێک	Push the bubble(s) throughبازنەکان تێپەڕێنە	Same gate drawn asهەمان بەم شێوەیە
NAND (AND with an output bubble)⁦NAND (AND⁩ بە بازنەیەک لەسەر )	to the inputsبۆ	OR with input bubbles (negative-OR)OR بە بازنە لەسەر ()
NOR (OR with an output bubble)⁦NOR (OR⁩ بە بازنەیەک لەسەر )	to the inputsبۆ	AND with input bubbles (negative-AND)AND بە بازنە لەسەر ()
AND with input bubblesAND بە بازنە لەسەر	to the outputبۆ	NOR
OR with input bubblesOR بە بازنە لەسەر	to the outputبۆ	NAND

Quick checkپشکنینی خێراYou push the output bubble of a NOR gate back onto its two inputs. What do you get?بازنەی سەر دەگوازیتەوە بۆ سەر هەردوو . چی دەردەچێت؟An OR gate with a bubble on each inputگەیتێکی OR بە بازنەیەک لەسەر هەر نێوخستەیەکA plain AND gateگەیتێکی AND بێ بازنەAn AND gate with a bubble on each inputگەیتێکی AND بە بازنەیەک لەسەر هەر نێوخستەیەک

The same law for setsهەمان یاسا بۆ کۆمەڵەکان

De Morgan's laws hold in set theory too, and they look the same. For sets, NOT is the complement $A^c$ (everything in the universal set U that is not in A), OR is the union ∪ and AND is the intersection ∩. Sets and these operations are taught in Set Operations.

یاساکانی دی مۆرگان لە تیۆری ڕاستن و هەمان شێوەیان هەیە. بۆ ، NOT $A^c$ (هەموو ئەوەی لە U دایە و لە Aـدا نییە)، OR ∪ و AND ∩. زیاتر دەربارەی لە وانەی کارەکانی کۆمەڵە فێر دەبیت.

\begin{aligned} (A\cup B)^c &= A^c \cap B^c \\ (A\cap B)^c &= A^c \cup B^c \end{aligned}

De Morgan's laws for sets: each pair shades the same region.یاساکانی دی مۆرگان بۆ : هەر جووتێک هەمان ناوچە ڕەنگ دەکات.CêIT

Check with numbers: $U = \{1,\dots,8\}$ , $A = \{1,2,3,4\}$ , $B = \{3,4,5,6\}$ . $A\cup B = \{1,\dots,6\}$ , so $(A\cup B)^c = \{7,8\}$ . $A^c = \{5,6,7,8\}$ and $B^c = \{1,2,7,8\}$ , and their intersection is also $\{7,8\}$ .

بە ژمارە پشکنینی بکە: $U = \{1,\dots,8\}$ ، $A = \{1,2,3,4\}$ ، $B = \{3,4,5,6\}$ . $A\cup B = \{1,\dots,6\}$ ، بۆیە $(A\cup B)^c = \{7,8\}$ . $A^c = \{5,6,7,8\}$ و $B^c = \{1,2,7,8\}$ . $\{7,8\}$ ـە.

Quick checkپشکنینی خێراWith the same sets, what is

A^c \cup B^c

?بە هەمان ،

A^c \cup B^c

چییە؟

\{1,2,5,6,7,8\}

\{1,2,5,6,7,8\}

\{7,8\}

\{7,8\}

\{3,4\}

\{3,4\}

De Morgan in programsدی مۆرگان لە بەرنامەکاندا

Programmers meet the same theorems in conditions. NOT (a AND b) is the same as (NOT a) OR (NOT b), whatever programming language you use: in Python not (a and b) equals (not a) or (not b), and in PHP, C or Java !(a && b) equals !a || !b. A shop is closed when it is not (a weekday and working hours):

بەرنامەسازان هەمان لە دەبینن. ⁦NOT (a AND b)⁩ هەمانە لەگەڵ ⁦(NOT a) OR (NOT b)⁩، هەر بەکاربهێنیت: لە Pythonـدا not (a and b) یەکسانە بە (not a) or (not b). لە PHP، C یان Javaـدا !(a && b) یەکسانە بە !a || !b. دووکانێک داخراوە کاتێک وا نەبێت کە (ڕۆژی کار و کاتی کار) بێت:

TEXT

closed = NOT (isWeekday AND isWorkingHour)
       = (NOT isWeekday) OR (NOT isWorkingHour)

The second line is often easier to read: the shop is closed on the weekend, or outside working hours. More about conditions in code: logical operators in Python and logical operators in PHP.

دێڕی دووەم زۆرجار ئاسانتر دەخوێنرێتەوە: دووکانەکە لە پشووی هەفتەدا یان لە دەرەوەی کاتی کاردا داخراوە. زیاتر دەربارەی لە کۆددا: کارپێکەرە لۆجیکییەکان لە Pythonـدا و کارپێکەرە لۆجیکییەکان لە PHPـدا.

Common mistakesهەڵە باوەکان

Mistakeهەڵە	Fixچارەسەر
Breaking the bar but keeping the sign: $\overline{AB} \to \overline{A}\,\overline{B}$ .شکاندنی هێڵەکە بەبێ گۆڕینی نیشانەکە: $\overline{AB} \to \overline{A}\,\overline{B}$ .	Always do both: $\overline{AB} = \overline{A}+\overline{B}$ . Test $A = 1$ , $B = 0$ : $\overline{AB} = 1$ but $\overline{A}\,\overline{B} = 0$ .هەمیشە هەردووکیان بکە: $\overline{AB} = \overline{A}+\overline{B}$ . $A = 1$ ، $B = 0$ تاقی بکەرەوە: $\overline{AB} = 1$ بەڵام $\overline{A}\,\overline{B} = 0$ .
Changing the sign but keeping one long bar: $\overline{A+B} \to \overline{AB}$ .گۆڕینی نیشانەکە و هێشتنەوەی یەک هێڵی درێژ: $\overline{A+B} \to \overline{AB}$ .	The bar must break where the sign changes: $\overline{A}\,\overline{B}$ .لەو شوێنەی نیشانەکە دەگۆڕێت هێڵەکە دەبێت بشکێت: $\overline{A}\,\overline{B}$ .
Breaking every bar at once: $\overline{(A+B)C} \to \overline{A}+\overline{B}+\overline{C}$ .شکاندنی هەموو هێڵەکان پێکەوە: $\overline{(A+B)C} \to \overline{A}+\overline{B}+\overline{C}$ .	Outer bar first, keeping the block: $\overline{A+B}+\overline{C}$ ; then the inner bar: $\overline{A}\,\overline{B}+\overline{C}$ .یەکەم هێڵی دەرەوە و بلۆکەکە بهێڵەوە: $\overline{A+B}+\overline{C}$ ؛ پاشان هێڵی ناوەوە: $\overline{A}\,\overline{B}+\overline{C}$ .
Cancelling bars that do not cover the same thing: $\overline{\overline{A}+\overline{B}} \to A+B$ .لابردنی هێڵگەلێک کە هەمان شت داناپۆشن: $\overline{\overline{A}+\overline{B}} \to A+B$ .	Break the long bar first: $\overline{\overline{A}}\,\overline{\overline{B}} = AB$ .یەکەم هێڵە درێژەکە بشکێنە: $\overline{\overline{A}}\,\overline{\overline{B}} = AB$ .
Reading $\overline{A}\,\overline{B}$ (two short bars) as $\overline{AB}$ (one long bar).خوێندنەوەی $\overline{A}\,\overline{B}$ (دوو هێڵی کورت) وەک $\overline{AB}$ (یەک هێڵی درێژ).	Two short bars = NOR; one long bar = NAND. Write the gap between short bars clearly.دوو هێڵی کورت = NOR؛ یەک هێڵی درێژ = NAND. بۆشایی نێوان هێڵە کورتەکان بە ڕوونی بنووسە.

Exercisesڕاهێنانەکان

These are the lecture's eight exercises. Try each one on paper first, then open the answer.

ئەمانە هەشت ڕاهێنانەکەی وانەکەن. یەکەم جار هەر یەکێکیان لەسەر کاغەز هەوڵ بدە، پاشان وەڵامەکە بکەرەوە.

ExerciseڕاهێنانExercise 1ڕاهێنانی 1

Apply De Morgan's theorems to $\overline{XYZ}$ .

لەسەر $\overline{XYZ}$ جێبەجێ بکە.

Show answerوەڵامەکە پیشان بدە

\overline{XYZ} = \overline{X}+\overline{Y}+\overline{Z}

Three ANDed variables: three short bars, and both dots become +.

سێ کە بە AND بەستراون: سێ هێڵی کورت دادەنرێن و هەردوو · دەبنە +.

ExerciseڕاهێنانExercise 2ڕاهێنانی 2

Apply De Morgan's theorems to $\overline{X+Y+Z}$ .

لەسەر $\overline{X+Y+Z}$ جێبەجێ بکە.

Show answerوەڵامەکە پیشان بدە

\overline{X+Y+Z} = \overline{X}\,\overline{Y}\,\overline{Z}

Three ORed variables: three short bars, and both + signs become AND.

سێ کە بە OR بەستراون: سێ هێڵی کورت دادەنرێن و هەردوو + دەبنە AND.

ExerciseڕاهێنانExercise 3ڕاهێنانی 3

Apply De Morgan's theorems to $\overline{ABCD}$ .

لەسەر $\overline{ABCD}$ جێبەجێ بکە.

Show answerوەڵامەکە پیشان بدە

\overline{ABCD} = \overline{A}+\overline{B}+\overline{C}+\overline{D}

Four ANDed variables: four short bars, and every AND becomes +. Check: the left side is 0 only when $A = B = C = D = 1$ , and so is the right side.

چوار کە بە AND بەستراون: چوار هێڵی کورت و هەموو ANDـێک دەبێتە +. پشکنین: لای چەپ تەنها کاتێک 0ـە کە $A = B = C = D = 1$ ، لای ڕاستیش هەروایە.

ExerciseڕاهێنانExercise 4ڕاهێنانی 4

Apply De Morgan's theorems to $\overline{A+B+C+D}$ .

لەسەر $\overline{A+B+C+D}$ جێبەجێ بکە.

Show answerوەڵامەکە پیشان بدە

\overline{A+B+C+D} = \overline{A}\,\overline{B}\,\overline{C}\,\overline{D}

Four ORed variables: four short bars, and every + becomes AND. Both sides are 1 only when $A = B = C = D = 0$ .

چوار کە بە OR بەستراون: چوار هێڵی کورت و هەموو نیشانەیەکی + دەبێتە AND. هەردوو لا تەنها کاتێک 1ـن کە $A = B = C = D = 0$ .

Exercisesڕاهێنانەکان

More exercises: double bars and groupsڕاهێنانی زیاتر: هێڵی دووانە و گرووپ

ExerciseڕاهێنانExercise 5ڕاهێنانی 5

Apply De Morgan's theorems to $\overline{WXYZ}$ .

لەسەر $\overline{WXYZ}$ جێبەجێ بکە.

Show answerوەڵامەکە پیشان بدە

\overline{WXYZ} = \overline{W}+\overline{X}+\overline{Y}+\overline{Z}

The same shape as exercise 3 with other letters. The names of the variables do not matter; only the bar and the signs do.

هەمان شێوەی ڕاهێنانی 3ـە بە پیتی تر. ناوی گرنگ نییە؛ تەنها هێڵەکە و نیشانەکان گرنگن.

ExerciseڕاهێنانExercise 6ڕاهێنانی 6

Apply De Morgan's theorems to $\overline{\overline{W}+\overline{X}+\overline{Y}+\overline{Z}}$ .

لەسەر $\overline{\overline{W}+\overline{X}+\overline{Y}+\overline{Z}}$ جێبەجێ بکە.

Show answerوەڵامەکە پیشان بدە

Start with the given expression:
بە دراوەکە دەست پێبکە:
$\overline{\overline{W}+\overline{X}+\overline{Y}+\overline{Z}}$
Theorem 2: break the long bar, every + becomes AND.
دووەم: هێڵە درێژەکە بشکێنە، هەموو نیشانەیەکی + دەبێتە AND.
$= \overline{\overline{W}}\;\overline{\overline{X}}\;\overline{\overline{Y}}\;\overline{\overline{Z}}$
Rule 9: each double bar cancels.
یاسای 9: هەر هێڵێکی دووانە لادەچێت.
$= WXYZ$

Break the long bar first. Only then does each letter carry two bars over exactly the same thing, and they cancel.

یەکەم هێڵە درێژەکە بشکێنە. تەنها ئەو کاتە هەر پیتێک دوو هێڵی لەسەر ڕێک هەمان شت دەبێت و یەکتر لادەبەن.

ExerciseڕاهێنانExercise 7ڕاهێنانی 7

Apply De Morgan's theorems to $\overline{\overline{W}\,\overline{X}\,\overline{Y}\,\overline{Z}}$ .

لەسەر $\overline{\overline{W}\,\overline{X}\,\overline{Y}\,\overline{Z}}$ جێبەجێ بکە.

Show answerوەڵامەکە پیشان بدە

Start with the given expression:
بە دراوەکە دەست پێبکە:
$\overline{\overline{W}\,\overline{X}\,\overline{Y}\,\overline{Z}}$
Theorem 1: break the long bar, every AND becomes +.
یەکەم: هێڵە درێژەکە بشکێنە، هەموو ANDـێک دەبێتە +.
$= \overline{\overline{W}}+\overline{\overline{X}}+\overline{\overline{Y}}+\overline{\overline{Z}}$
Rule 9: each double bar cancels.
یاسای 9: هەر هێڵێکی دووانە لادەچێت.
$= W+X+Y+Z$

ExerciseڕاهێنانExercise 8ڕاهێنانی 8

Apply De Morgan's theorems to $\overline{(A+B+C)D}$ .

لەسەر $\overline{(A+B+C)D}$ جێبەجێ بکە.

Show answerوەڵامەکە پیشان بدە

Start with the given expression:
بە دراوەکە دەست پێبکە:
$\overline{(A+B+C)D}$
Theorem 1 on the AND of the two blocks $(A + B + C)$ and D.
یەکەم لەسەر ANDـی دوو بلۆکی $(A + B + C)$ و D.
$= \overline{A+B+C}+\overline{D}$
Theorem 2 on the bar over the block $A + B + C$ .
دووەم لەسەر هێڵەکەی سەر بلۆکی $A + B + C$ .
$= \overline{A}\,\overline{B}\,\overline{C}+\overline{D}$

Break the outer bar first and keep the block together; then break the bar over the block.

یەکەم هێڵی دەرەوە بشکێنە و بلۆکەکە پێکەوە بهێڵەوە؛ پاشان هێڵەکەی سەر بلۆکەکە بشکێنە.

ExerciseڕاهێنانYour own: a mixed expressionهی خۆت: دەربڕینێکی تێکەڵ

Apply De Morgan's theorems to $\overline{AB + C}$ and to $\overline{A(B + C)}$ .

لەسەر $\overline{AB + C}$ و لەسەر $\overline{A(B + C)}$ جێبەجێ بکە.

Hintئاماژە

Break the longest bar first and treat AB and $B + C$ as blocks.

یەکەم درێژترین هێڵ بشکێنە و AB و $B + C$ وەک بلۆک دابنێ.

Show answerوەڵامەکە پیشان بدە

\begin{aligned} \overline{AB + C} &= \overline{AB}\,\overline{C} = (\overline{A}+\overline{B})\,\overline{C} \\ \overline{A(B + C)} &= \overline{A} + \overline{B+C} = \overline{A} + \overline{B}\,\overline{C} \end{aligned}

Keep the brackets in the first answer: $(\overline{A}+\overline{B})\overline{C}$ is not $\overline{A}+\overline{B}\,\overline{C}$ .

لە وەڵامی یەکەمدا کەوانەکان بهێڵەوە: $(\overline{A}+\overline{B})\overline{C}$ هەمان $\overline{A}+\overline{B}\,\overline{C}$ نییە.

ExerciseڕاهێنانProve it with a truth tableبە خشتەی ڕاستی بیسەلمێنە

Show with an 8-row truth table that $\overline{A+B+C} = \overline{A}\,\overline{B}\,\overline{C}$ .

بە 8 ڕیزی پیشانی بدە کە $\overline{A+B+C} = \overline{A}\,\overline{B}\,\overline{C}$ .

Show answerوەڵامەکە پیشان بدە

$ABC$	$A+B+C$	$\overline{A+B+C}$	$\overline{A}\,\overline{B}\,\overline{C}$
000	0	1	1
001	1	0	0
010	1	0	0
011	1	0	0
100	1	0	0
101	1	0	0
110	1	0	0
111	1	0	0

The last two columns match in all 8 rows: both are 1 only for $A = B = C = 0$ .

دوو ستوونی کۆتایی لە هەر 8 ڕیزەکەدا وەک یەکن: هەردووکیان تەنها بۆ $A = B = C = 0$ 1ن.

Summaryپوختە

Theorem 1: $\overline{AB} = \overline{A}+\overline{B}$ . NOT of an AND is the OR of the NOTs.
Theorem 2: $\overline{A+B} = \overline{A}\,\overline{B}$ . NOT of an OR is the AND of the NOTs.
One move does both: break the bar, change the sign. It works for any number of variables and also backwards.
Break one bar at a time, longest first; keep blocks in brackets; two bars over the same thing cancel.
In gates: NAND = negative-OR and NOR = negative-AND. Pushing a bubble through a gate swaps AND and OR.
The same laws hold for sets, $(A\cup B)^c = A^c\cap B^c$ , and for conditions in programs.

یەکەم: $\overline{AB} = \overline{A}+\overline{B}$ . NOTـی AND یەکسانە بە ORـی NOTـەکان.
دووەم: $\overline{A+B} = \overline{A}\,\overline{B}$ . NOTـی OR یەکسانە بە ANDـی NOTـەکان.
یەک جووڵە هەردووکیان دەکات: هێڵەکە بشکێنە، نیشانەکە بگۆڕە. بۆ هەر ژمارەیەک و بە پێچەوانەشەوە کار دەکات.
هەر جارە یەک هێڵ بشکێنە، درێژترین یەکەم؛ بلۆکەکان لە ناو کەوانەدا بهێڵەوە؛ دوو هێڵ لەسەر هەمان شت یەکتر لادەبەن.
لە : NAND = و NOR = . تێپەڕاندنی بازنەیەک بە ناو AND و OR جێگۆڕکێ پێ دەکات.
هەمان یاساکان بۆ ڕاستن، $(A\cup B)^c = A^c\cap B^c$ . هەروەها بۆ لە بەرنامەکاندا.

Review questionsپرسیارەکانی پێداچوونەوە

Why is

\overline{AB}

not equal to

\overline{A}\,\overline{B}

?بۆچی

\overline{AB}

یەکسان نییە بە

\overline{A}\,\overline{B}

؟

Try $A = 1$ , $B = 0$ : $\overline{AB} = \overline{0} = 1$ but $\overline{A}\,\overline{B} = 0 \cdot 1 = 0$ . The correct form is $\overline{A}+\overline{B}$ .

$A = 1$ ، $B = 0$ تاقی بکەرەوە: $\overline{AB} = \overline{0} = 1$ بەڵام $\overline{A}\,\overline{B} = 0 \cdot 1 = 0$ . شێوە دروستەکە $\overline{A}+\overline{B}$ ـە.

Which gate is an AND gate with a bubble on every input?کام گەیت وەک گەیتێکی AND وایە کە بازنەیەک لەسەر هەموو نێوخستەکانی هەیە؟

A NOR gate: $\overline{A}\,\overline{B} = \overline{A+B}$ .

: $\overline{A}\,\overline{B} = \overline{A+B}$ .

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

boolean algebra بوولیان ئەلجێبرا بەشی یەکەمAram Rafeq · Kurdish (Sorani)کوردی (سۆرانی) · 6.4K viewsبینین · 180 likesلایک · Partبەشی 10:30–16:59 (ofلە 16:59)
Kurdish (Sorani): commutative, associative and distributive laws with gate drawings, the 12 rules in the lesson's order, then De Morgan's theorems.
بە کوردیی سۆرانی: ، و بە وێنەی ، دوازدە یاساکە بە ڕیزبەندیی وانەکە، پاشان .
10:30-end: De Morgan's theorems and examples with double bars over groups.
لە ⁦10:30⁩ـەوە تا کۆتایی: و نموونە کە دوو هێڵیان لەسەر کۆمەڵەیەک هەیە.

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Simplifying Boolean Expressionsکورتکردنەوەی دەربڕینە بوولییەکان

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

Wikipedia: De Morgan's laws
Wikipedia: Boolean algebra (laws, duality)
MIT 6.004 Computation Structures, notes: Combinational logic (bubble pushing, NAND/NOR in CMOS)
T. L. Floyd, Digital Fundamentals, 11th ed., §4-3 DeMorgan's Theorems (Pearson, 2015) — topics only

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.