# Элементы алгебры логики Информатика · 8 класс · Элементы математической логики Источник: https://razlozheno.ru/subject/informatika/8/elementy-algebry-logiki Как устроена логика, на которой работает компьютер: высказывания, операции И, ИЛИ, НЕ, таблицы истинности, законы упрощения и логические элементы. ## Чему научишься - Определять, является ли предложение высказыванием, и находить значение составного высказывания - Строить таблицу истинности логического выражения с учётом приоритета операций - Упрощать выражения по законам логики и читать схему из логических элементов ## С чего начать Ты ищешь в интернете «кошки И собаки», а потом «кошки ИЛИ собаки». Во втором случае страниц окажется намного больше. Почему? И как кусок железа, в котором есть только 0 и 1, умеет принимать такие решения? ## 1. Высказывания и три операции *Что можно проверить на правду и как склеивать такие утверждения* Скажи вслух два предложения: «Москва — столица России» и «Какой чудесный день!». Первое можно проверить: правда или ложь. Со вторым нельзя ни согласиться, ни поспорить по-честному, это эмоция. Алгебра логики работает только с предложениями первого типа. **Высказывание** **Высказывание** — предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное. Вопрос «Который час?» и приказ «Закрой дверь!» высказываниями не являются: истинными или ложными их не назовёшь. А $2 + 2 = 5$ — высказывание: оно ложное, но однозначно проверяется. **Проверь себя:** «Число 7 чётное» — это высказывание? **Ответ:** Да. Оно ложное, но однозначно проверяется. Высказывание не обязано быть правдой, оно обязано быть проверяемым. **Переменные и значения** **Логические переменные** — буквы, которыми в алгебре логики обозначают высказывания. Например, $A$ и $B$. **Логические значения** — значения 0 и 1, обозначающие истинность (1) или ложность (0) логических переменных. То есть высказывание «Москва — столица России» можно записать как $A = 1$, а «$2 + 2 = 5$» — как $B = 0$. **Простое и составное** **Простое высказывание** — высказывание, никакая часть которого сама не является высказыванием. **Составное (сложное) высказывание** — высказывание, строящееся из простых высказываний с помощью логических операций. Лего-аналогия: простые высказывания — кубики, логические операции — способ их соединять. Операций всего три, и каждая — это слово из обычной речи. - **И**: «Я возьму зонт, **и** надену куртку». Честно выполнено, только если сделано оба дела. - **ИЛИ**: «Куплю яблоки **или** груши». Хватит любого из двух (и обоих тоже не запрещено). - **НЕ**: «Дверь **не** закрыта». Просто переворачивает смысл. **Выключатели: И — подряд, ИЛИ — рядом** Представь лампочку и два выключателя. Если они стоят **друг за другом** на одном проводе, ток дойдёт только когда замкнуты оба: это **И**. Если провода **параллельны**, хватит любого одного: это **ИЛИ**. Как быстро вспомнить результат: **И — строгая**, один 0 и всё равно 0. **ИЛИ — добрая**, одной 1 достаточно, чтобы получить 1. *Рисунок: Две схемы с лампочкой и двумя выключателями: слева выключатели друг за другом, справа на параллельных проводах* **Конъюнкция (И)** **Конъюнкция** — логическая операция, ставящая в соответствие двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны (логическое умножение). **Дизъюнкция (ИЛИ)** **Дизъюнкция** — логическая операция, которая двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны (логическое сложение). **Инверсия (НЕ)** **Инверсия** — логическая операция, которая высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному (логическое отрицание). Если $A = 1$, то $\overline{A} = 0$, и наоборот. Одна и та же операция в разных книгах пишется по-разному. - Конъюнкция: $\&$, $\land$, $\cdot$, $\times$, «И». - Дизъюнкция: $\lor$, $|$, $+$, «ИЛИ». - Инверсия: $\neg$, черта над переменной ($\overline{A}$), «НЕ». В этом уроке пишем $\&$, $\lor$ и черту над переменной. **Результаты двух операций для всех пар значений** | $A$ | $B$ | $A \& B$ | $A \lor B$ | | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | | 0 | 1 | 0 | 1 | | 1 | 0 | 0 | 1 | | 1 | 1 | 1 | 1 | Теперь вернёмся к поиску. Каждый овал на рисунке — множество веб-страниц: в овале $A$ страницы со словом про кошек, в овале $B$ — со словом про собак. *Рисунок: Большой круг с двумя пересекающимися овалами A и B* Запрос с **И** требует, чтобы страница лежала и в $A$, и в $B$, то есть в пересечении. Это узкая область. *Рисунок: Большой круг с голубой заливкой в области пересечения овалов A и B* **Пример: Значение составного высказывания** 1. Берём высказывание: «Москва — столица России, и $2 + 2 = 5$». 2. Простые части: первая истинна (1), вторая ложна (0). 3. Конъюнкция даёт 1 только при двух единицах. Здесь $1 \& 0 = 0$, значит всё высказывание ложно. 4. Заменим И на ИЛИ: $1 \lor 0 = 1$, высказывание истинно: хватает одной истинной части. ### Проверь себя **Что представляет собой высказывание в алгебре логики?** - Предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное. — верно - Побудительное или вопросительное предложение, обращенное к пользователю. - Предложение, выражающее субъективное мнение или эстетическую оценку автора. - Любое повествовательное предложение, содержащее математические знаки или переменные. > Логическое высказывание характеризуется возможностью однозначно установить его истинность или ложность. **Какое из приведенных предложений является высказыванием?** - Число $376$ — чётное и трёхзначное. — верно - Запишите домашнее задание. - Компьютерная графика — самая интересная тема в школе. - Переменная $X$ меньше двенадцати. > Данное утверждение является повествовательным и однозначно истинным. **Почему предложение «Это предложение является ложным» не считается высказыванием?** - Его значение зависит от субъективного восприятия читателя. - Оно относится к побудительным предложениям русского языка. - Попытка определить его истинность или ложность неизбежно приводит к логическому противоречию. — верно - Оно содержит неопределённую математическую переменную. > Принятие этого утверждения как истинного делает его ложным, а принятие как ложного — истинным, что противоречит определению высказывания. **Предложение с переменной (например, «$X < 12$») становится высказыванием при условии, что:** - Оно записывается в виде таблицы истинности. - Переменная заменяется конкретным значением. — верно - Выражение объединяется с другим неравенством знанием «или». - Переменная $X$ принимает только положительные значения. > Подстановка конкретного числа позволяет однозначно проверить истинность получившегося неравенства. **Каким образом в алгебре логики обозначаются значения логических переменных?** - Буквами $T$ и $F$ без использования двоичных кодов. - Любыми положительными числами для истинных и нулём для ложных. - Единицей ($1$) для истинного высказывания и нулём ($0$) для ложного. — верно - Числами $1$ для истинного и $-1$ для ложного. > В двоичной алгебре логики истине соответствует $1$, а лжи — $0$. **Какая логическая операция связывает два высказывания союзным союзом «и» и является истинной только тогда, когда истинны оба высказывания?** - Дизъюнкция - Инверсия - Конъюнкция — верно - Эквивалентность > Конъюнкция (логическое умножение) даёт истинный результат исключительно при одновременной истинности всех операндов. **В каком из приведенных случаев дизъюнкция $A \lor B$ принимает значение $0$?** - Когда $A = 0$ и $B = 1$. - Когда $A = 0$ и $B = 0$. — верно - Когда $A = 1$ и $B = 1$. - Когда $A = 1$ и $B = 0$. > Дизъюнкция (логическое сложение) ложна тогда и только тогда, когда оба исходных высказывания ложны. **Какое второе название носит логическая операция «инверсия»?** - Логическое сложение - Логическое отрицание — верно - Логическое умножение - Логическое следование > Инверсия меняет значение высказывания на противоположное, поэтому её называют логическим отрицанием. **Чему равно значение логического выражения $(X < 3) \& (X < 2)$ при $X = 0$?** - Выражение не имеет смысла. - $1$ — верно - $2$ - $0$ > При $X = 0$ оба неравенства $(0 < 3)$ и $(0 < 2)$ истинны ($1$), а конъюнкция $1 \& 1 = 1$. **Чему равно значение выражени $1 \lor A \& 0$ при любом значении переменной $A$?** - $A$ - $1$ — верно - $0$ - $\overline{A}$ > Сначала выполняется конъюнкция $A \& 0 = 0$, а затем дизъюнкция $1 \lor 0 = 1$. **Какое из следующих высказываний является грамотным отрицанием к высказыванию «Все юноши 8-х классов — отличники»?** - «Все девушки 8-х классов — отличники». - «Ни один юноша 8-го класса не является отличником». - «Не все юноши 8-х классов — отличники». — верно - «Все юноши 8-х классов — двоечники». > Правильное отрицание общего утверждения указывает на то, что оно неверно хотя бы для части объектов. **Чему равно значение выражения $((1 \lor 0) \& 1) \& \overline{1}$?** - $1$ - $2$ - $0$ — верно - Неопределенность > Так как $\overline{1} = 0$, то конечное логическое умножение на $0$ дает $0$. ## 2. Логические выражения и таблицы истинности *Порядок действий и как не пропустить ни одного случая* Когда высказываний несколько и операций тоже, нужна строгая запись. Её и называют логическим выражением. **Логическое выражение и таблица истинности** **Логическое выражение** — выражение, содержащее логические переменные, знаки логических операций и скобки. **Таблица истинности** — таблица, показывающая, какие значения принимает логическое выражение при всех наборах значений входящих в него переменных. В какой последовательности считать? Так же, как в арифметике: в выражении $2 + 3 \cdot 4$ сначала умножение, потом сложение. Конъюнкция — это «логическое умножение», дизъюнкция — «логическое сложение», поэтому И сильнее ИЛИ. **Приоритет операций** Порядок выполнения: 1. Инверсия 2. Конъюнкция 3. Дизъюнкция Скобки, как и в арифметике, меняют порядок: то, что в скобках, считается первым. **Пример: Вычисляем выражение** 1. Дано $A \lor B \& \overline{C}$ при $A = 0$, $B = 1$, $C = 0$. 2. Сначала инверсия: $\overline{C} = \overline{0} = 1$. 3. Потом конъюнкция: $B \& \overline{C} = 1 \& 1 = 1$. 4. Потом дизъюнкция: $A \lor 1 = 0 \lor 1 = 1$. Ответ: 1. Чтобы выражение проверить при **всех** возможных значениях, делают таблицу. Сколько в ней будет строк, не считая шапки? Это зависит от числа переменных. **Число строк таблицы** $m = 2^n$ где $n$ — число переменных в логическом выражении, $m$ — число строк в таблице истинности (не считая шапки таблицы). **Монетки** Одна переменная — как одна монетка: 2 исхода (0 или 1). Бросаем вторую монетку, и каждый прежний исход делится на два: 4 исхода. Третья снова удваивает: 8. Каждая новая переменная **удваивает** число строк, отсюда степень двойки. Самопроверка: две переменные — 4 строки, три — 8. Если написал иначе, где-то потерял набор. **Проверь себя:** Сколько строк (без шапки) в таблице истинности выражения с тремя переменными? **Ответ:** $m = 2^3 = 8$ строк. Наборы значений удобно писать как двоичный счёт: для двух переменных $00$, $01$, $10$, $11$. Так ни один случай не потеряется и не повторится. Дальше для каждой операции заводим свой столбец, в порядке приоритета. **Пример: Числовой пример: 5 000 000 веб-страниц** 1. Пусть всего проанализировано 5 000 000 веб-страниц. На 4 800 страницах встречается слово $A$, на 4 500 страницах — слово $B$, а на 7 000 страницах встречается $A \lor B$, то есть хотя бы одно из двух слов. 2. Найдём страницы, где нет ни $A$, ни $B$. Это отрицание объединения: $\overline{A \lor B}$. Из общего числа вычитаем страницы с $A \lor B$: $5\,000\,000 - 7\,000 = 4\,993\,000$. 3. Найдём страницы, где есть одновременно $A$ и $B$. По правилу подсчёта объединения $A \lor B$ состоит из страниц с $A$, страниц с $B$, но пересечение посчитано дважды. Поэтому $4\,800 + 4\,500 - 7\,000 = 2\,300$. 4. Теперь найдём страницы с $A \& \overline{B}$: слово $A$ есть, а слова $B$ нет. Из 4 800 страниц с $A$ убираем 2 300 страниц, где есть и $A$, и $B$: $4\,800 - 2\,300 = 2\,500$. 5. Итак, $\overline{A \lor B}$ встречается на 4 993 000 страницах, $A \& B$ — на 2 300 страницах, а $A \& \overline{B}$ — на 2 500 страницах. Это показывает на числах, как объединение и пересечение связаны с логическими операциями. **Пример: Таблица для $F = A \& \overline{B}$** 1. Переменных две, значит $m = 2^2 = 4$ строки. 2. Выписываем наборы $A$ и $B$: 00, 01, 10, 11. 3. Первый дополнительный столбец — инверсия $\overline{B}$: 1, 0, 1, 0. 4. Второй — конъюнкция $A \& \overline{B}$: единица только там, где $A = 1$ и $\overline{B} = 1$. 5. Итог: $F$ равна 0, 0, 1, 0. Единица только при $A = 1$, $B = 0$. **Готовая таблица для $F = A \& \overline{B}$** | $A$ | $B$ | $\overline{B}$ | $A \& \overline{B}$ | | --- | --- | --- | --- | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 0 | *Рисунок: Большой круг с голубой заливкой внутри овала A вне области пересечения с B* Эта закрашенная область — картинка того же выражения $A \& \overline{B}$: «есть $A$, но нет $B$». Единственная единица в таблице — как раз эта область. **Пример: Логическая задача: соревнования** 1. На соревнованиях участвовали команды $A$, $B$ и $C$. Известно: если команда $A$ заняла первое место, то команда $B$ заняла второе; команда $B$ не заняла второе место. 2. Запишем условия: $A \rightarrow B$ и $\overline{B}$. Если бы $A$ было истинным, из первого условия следовало бы $B$. 3. Но $B$ ложно. Значит, предположение $A = 1$ невозможно. 4. Ответ: команда $A$ не заняла первое место, то есть $A = 0$. ### Проверь себя **Каков порядок выполнения операций в сложнoм логическом выражении без скобок?** - Инверсия, дизъюнкция, конъюнкция. - Конъюнкция, дизъюнкция, инверсия. - Инверсия, конъюнкция, дизъюнкция. — верно - Дизъюнкция, конъюнкция, инверсия. > Высший приоритет имеет инверсия, за ней следует конъюнкция (умножение), а наименьший приоритет у дизъюнкции (сложения). **Сколько строк (не считая шапки) будет содержать таблица истинности для логического выражения с $3$ переменными?** - $6$ - $8$ — верно - $9$ - $4$ > Число строк рассчитывается по формуле $m = 2^n$, где $n = 3$, что дает $2^3 = 8$. **Как определяется общее количество столбцов в таблице истинности для сложного логического выражения?** - Число строк $2^n$, делённое на количество переменных. - Сумма количества входных переменных и количества логических операций. — верно - Количество логических операций плюс единица. - Произведение количества переменных на количество операций. > Каждая переменная и каждая выполняемая операция требуют отдельного столбца в таблице. **Что означает, если последний столбец таблицы истинности полностью совпадает со столбцом переменной $A$ (например, для $A \lor A \& B$)?** - Выражение является тождественно ложным. - Таблица истинности составлена с ошибкой. - Переменная $B$ не влияет на приоритет операций. - Логическое выражение равносильно логической переменной $A$. — верно > Полное совпадение значений во всех строках говорит о логической равносильности выражения и этой переменной. **Какова последовательность двухразрядных двоичных чисел, принятая при заполнении наборов входных переменных в таблице истинности?** - $00, 01, 10, 11$ — верно - $00, 11, 01, 10$ - $11, 10, 01, 00$ - $01, 10, 11, 00$ > Наборы входных переменных записываются как целые $n$-разрядные двоичные числа в порядке возрастания от $0$ до $2^n - 1$. ## 3. Законы алгебры логики *Как упрощать выражения и сравнить И с ИЛИ* Длинное выражение можно сократить без всяких таблиц, если знать законы. Это такие же правила, как «от перемены мест слагаемых сумма не меняется». **Переместительный и сочетательный законы** $A \& B = B \& A$ $A \lor B = B \lor A$ $(A \& B) \& C = A \& (B \& C)$ $(A \lor B) \lor C = A \lor (B \lor C)$ **Спутники: переместительный и сочетательный** **Переместительный**: представь очередь из двух дел — «И» не важно, что назвать первым: результат тот же. Зацепка: **поменяли местами — смысл не поменяли**. **Сочетательный**: представь три шага, которые объединяют в две пары. Можно сначала соединить первые два или последние два — результат тот же. Зацепка: **поменяли скобки, но не порядок элементов**. Коротко: **места можно менять, группы можно менять**. **Распределительный закон** $A \& (B \lor C) = (A \& B) \lor (A \& C)$ $A \lor (B \& C) = (A \lor B) \& (A \lor C)$ **Спутник: распределительный закон** **Распределительный**: представь, что $A$ — общий пропуск, а $B$ и $C$ — два входа. Если пропуск нужен для входа через $B$ **или** через $C$, он должен появиться в обоих вариантах: $A$ «раздаётся» внутрь скобок. Зацепка: **распределяй общий элемент, как раздаёшь каждому по одному экземпляру**. В отличие от переместительного и сочетательного законов здесь элементы не просто меняют места или группировку — один элемент **раскладывается по двум вариантам**. **Отрицание, повторение, нули и единицы** $\overline{\overline{A}} = A$ $A \& \overline{A} = 0$ $A \lor \overline{A} = 1$ $A \& A = A$ $A \lor A = A$ $A \& 0 = 0$ $A \& 1 = A$ $A \lor 0 = A$ $A \lor 1 = 1$ **Отрицание составных выражений** $\overline{A \& B} = \overline{A} \lor \overline{B}$ $\overline{A \lor B} = \overline{A} \& \overline{B}$ **Почему это работает и как запомнить** - Двойное «не» — как двойной разворот: «не бывает, чтобы дверь не закрыта» значит «закрыта». - $A \& \overline{A} = 0$: нельзя быть одновременно дома и не дома. $A \lor \overline{A} = 1$: дома или не дома — верно всегда. - «Неправда, что оба дома» значит «хотя бы один не дома». Поэтому отрицание И превращается в ИЛИ из отрицаний. Зацепки: **ноль гасит И, единица включает ИЛИ** ($A \& 0 = 0$, $A \lor 1 = 1$). **Черта ломает знак**: проносишь отрицание через скобку, И меняется на ИЛИ и наоборот. Самопроверка: распределительный закон для ИЛИ в арифметике не работает, в логике работает. **Парные законы: у И и ИЛИ всё зеркально** | Закон | Для И ($\&$) | Для ИЛИ ($\lor$) | | --- | --- | --- | | Переместительный | $A \& B = B \& A$ | $A \lor B = B \lor A$ | | Повторение | $A \& A = A$ | $A \lor A = A$ | | С нулём | $A \& 0 = 0$ | $A \lor 0 = A$ | | С единицей | $A \& 1 = A$ | $A \lor 1 = 1$ | | С отрицанием | $A \& \overline{A} = 0$ | $A \lor \overline{A} = 1$ | **Проверь себя:** Чему равно $A \lor 1$ при любом $A$? **Ответ:** Единице: $A \lor 1 = 1$. Одной истинной части хватает для ИЛИ. **Пример: Упрощаем выражение** 1. Дано $A \& B \lor A \& \overline{B}$. 2. Выносим $A$ за скобки по распределительному закону: $A \& (B \lor \overline{B})$. 3. Применяем $B \lor \overline{B} = 1$: получаем $A \& 1$. 4. Применяем $A \& 1 = A$. Ответ: $A$. Длинное выражение оказалось просто $A$. **Как доказать закон** Любой закон проверяется таблицей истинности: считаем левую и правую части при всех наборах. Если столбцы совпали, закон верен. Например, для $\overline{A \& B}$ и $\overline{A} \lor \overline{B}$ при двух переменных (4 строки) оба выражения дают 1, 1, 1, 0. ### Проверь себя **Какое из приведенных равенств выражает распределительный (дистрибутивный) закон для логического сложения?** - $A \lor (B \& C) = (A \lor B) \& (A \lor C)$ — верно - $(A \lor B) \lor C = A \lor (B \lor C)$ - $A \& (B \lor C) = (A \& B) \lor (A \& C)$ - $A \lor B = B \lor A$ > Этот закон показывает, как логическое сложение распределяется относительно логического умножения. **Чему равно значение выражения $A \lor \overline{A}$ согласно закону исключённого третьего?** - $1$ — верно - $0$ - $\overline{A}$ - $A$ > Из двух противоречивых высказываний одно всегда истинно, поэтому их дизъюнкция равна $1$. **Какое выражение вернет значение $0$ при любом значении логической переменной $A$?** - $A \lor 0$ - $A \lor 1$ - $A \& 1$ - $A \& 0$ — верно > Логическое умножение на $0$ всегда дает $0$ независимо от значения $A$. **Какая формула выражает закон общей инверсии (закон де Моргана) для логического умножения?** - $\overline{A \& B} = \overline{A} \lor \overline{B}$ — верно - $\overline{A \lor B} = \overline{A} \& \overline{B}$ - $\overline{A \& B} = \overline{A} \& \overline{B}$ - $\overline{\overline{A}} = A$ > Отрицание конъюнкции эквивалентно дизъюнкции отрицаний операндов. **В секторе сети из $5\,000\,000$ страниц $A \lor B$ истинно для $7000$ страниц. Для скольких страниц будет истинно выражение $\text{НЕ } (A \text{ ИЛИ } B)$?** - $4\,993\,000$ — верно - $2300$ - $7000$ - $5\,007\,000$ > Инверсия истинна на всех страницах, где исходная дизъюнкция ложна: $5\,000\,000 - 7000 = 4\,993\,000$. **Какая формула описывает закон повторения для логического сложения?** - $A \lor A = A$ — верно - $A \& A = A$ - $A \lor 0 = A$ - $A \lor \overline{A} = 1$ > Закон повторения (идемпотентности) утверждает, что дизъюнкция переменной с самой собой равна этой переменной. ## 4. Логические элементы *Как операции превращаются в детали компьютера* Компьютер не понимает слов «и», «или». Внутри него сигнал либо есть (1), либо нет (0). Значит, операции нужно сделать из деталей, которые обрабатывают такие сигналы. **Логический элемент** **Логический элемент** — дискретный преобразователь, который выдаёт после обработки двоичных сигналов значение одной из логических операций. **Три основных элемента** **Конъюнктор** — логический элемент И, реализующий операцию логического умножения. **Дизъюнктор** — логический элемент ИЛИ, реализующий операцию логического сложения. **Инвертор** — логический элемент НЕ, реализующий операцию логического отрицания. На схемах элементы рисуют прямоугольниками с входами слева и выходом $F$ справа. Конъюнктор подписан знаком $\&$. *Рисунок: Прямоугольный блок с входами A и B, выходом F и обозначением &* У дизъюнктора внутри стоит «1». *Рисунок: Прямоугольный блок с входами A и B и выходом F, внутри обозначена 1* Инвертор отличается кружком на выходе: кружок и означает «перевернуть сигнал». *Рисунок: Прямоугольный блок с входом A и выходом F, на выходе маленький кружок* **Проверь себя:** Какой элемент выдаёт 1 только тогда, когда на обоих входах 1? **Ответ:** Конъюнктор (элемент И). Элементы соединяют друг с другом, и получается схема для любого логического выражения. Выражение $A \& \overline{B}$ собирается так: вход $B$ идёт через инвертор, потом оба сигнала попадают на конъюнктор. *Рисунок: Вход A подан на блок &, вход B на отдельный блок с инверсией выхода, соединённый с блоком &; выход F* Проверим схему на всех наборах сразу. На входы подаём столбцы таблицы: $A$ — 0011, $B$ — 0101. На выходе получается 0010. Это тот же столбец, который мы получили в таблице для $A \& \overline{B}$. *Рисунок: Схема с входами A 0011 и B 0101, элементом & и выходом 0010 F* ### Проверь себя **Как называется логический элемент, реализующий операцию логического умножения?** - Инвертор - Повторитель - Дизъюнктор - Конъюнктор — верно > Логический элемент «И», выполняющий логическое умножение, называется конъюнктором. **При каком условии на выходе логического элемента ИЛИ (дизъюнктора) появится сигнал $1$?** - Если хотя бы на одном входе будет сигнал $1$. — верно - Только когда на всех входах будут сигналы $1$. - Только когда на всех входах будут сигналы $0$. - Если количество единиц на входах чётно. > Дизъюнктор выдает единицу при наличии единичного сигнала на любом из его входов. **Какой логический элемент обозначается прямоугольником с графическим символом «&» внутри?** - Элемент И (конъюнктор) — верно - Элемент НЕ (инвертор) - Элемент ИЛИ (дизъюнктор) - Исключающее ИЛИ > Знак «&» (амперсанд) является общепринятым обозначением конъюнкции и элемента И на схемах. ## Ключевые термины - **Высказывание** — Предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное. - **Логические переменные** — Буквы, которыми в алгебре логики обозначают высказывания. - **Простое высказывание** — Высказывание, никакая часть которого сама не является высказыванием. - **Составное (сложное) высказывание** — Высказывание, строящееся из простых высказываний с помощью логических операций. - **Конъюнкция** — Логическая операция, ставящая в соответствие двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны (логическое умножение). - **Дизъюнкция** — Логическая операция, которая двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны (логическое сложение). - **Инверсия** — Логическая операция, которая высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному (логическое отрицание). - **Логическое выражение** — Выражение, содержащее логические переменные, знаки логических операций и скобки. - **Таблица истинности** — Таблица, показывающая, какие значения принимает логическое выражение при всех наборах значений входящих в него переменных. - **Логический элемент** — Дискретный преобразователь, который выдаёт после обработки двоичных сигналов значение одной из логических операций. ## Итог - Высказывание — предложение, которое однозначно истинно (1) или ложно (0). Вопросы и эмоции высказываниями не являются. - Три операции: конъюнкция (И) истинна только при двух единицах, дизъюнкция (ИЛИ) ложна только при двух нулях, инверсия (НЕ) переворачивает значение. - Порядок действий: инверсия, конъюнкция, дизъюнкция; скобки считаются первыми. - В таблице истинности $m = 2^n$ строк, где $n$ — число переменных. - Законы упрощают выражения; логические элементы (конъюнктор, дизъюнктор, инвертор) реализуют операции в компьютере. ## Шпаргалка ### Законы и число строк - **$m = 2^n$** — число строк таблицы истинности - **$\overline{\overline{A}} = A$** — двойное отрицание снимается - **$A \& \overline{A} = 0$** — противоречие всегда ложно - **$A \lor \overline{A} = 1$** — всегда истинно - **$A \& 0 = 0$** — ноль гасит конъюнкцию - **$A \lor 1 = 1$** — единица включает дизъюнкцию - **$\overline{A \& B} = \overline{A} \lor \overline{B}$** — отрицание И: знак меняется на ИЛИ - **$\overline{A \lor B} = \overline{A} \& \overline{B}$** — отрицание ИЛИ: знак меняется на И ### Операции и приоритет - **Конъюнкция** — 1 только если оба значения 1 - **Дизъюнкция** — 0 только если оба значения 0 - **Инверсия** — меняет значение на противоположное - **Приоритет** — инверсия, конъюнкция, дизъюнкция; скобки первыми ### Таблица истинности 1. **Строки** — посчитай $m = 2^n$ 2. **Наборы** — выпиши значения переменных двоичным счётом 3. **Порядок** — расставь действия по приоритету 4. **Столбцы** — заведи столбец на каждое действие 5. **Ответ** — последний столбец — значение выражения ### И и ИЛИ | | Конъюнкция | Дизъюнкция | | --- | --- | --- | | Другое название | логическое умножение | логическое сложение | | Элемент | конъюнктор | дизъюнктор | | Истинна | только при двух единицах | при хотя бы одной единице | | Ложна | при хотя бы одном нуле | только при двух нулях | ## Любопытное - Одна и та же операция пишется по-разному: конъюнкция — $\&$, $\land$, $\cdot$, $\times$ или «И»; дизъюнкция — $\lor$, $|$, $+$ или «ИЛИ». Не пугайся, увидев другой значок в другой книге. - Распределительный закон для ИЛИ, $A \lor (B \& C) = (A \lor B) \& (A \lor C)$, в обычной арифметике не работает, а в логике верен. - Таблица истинности для 10 переменных содержит $2^{10} = 1024$ строки, поэтому вручную такие таблицы не строят, и на помощь приходят законы.