Логические операции
Внимание! Все тесты в этом разделе разработаны пользователями сайта для собственного использования. Администрация сайта не проверяет возможные ошибки, которые могут встретиться в тестах.
тест для 10 класса по теме Логические операции учебник Информатика. 10 класс. Углубленный уровень. В 2 ч. Поляков К.Ю., Еремин Е.А. М.: 2013 — Ч.1 — 344с., Ч.2 — 304с.
Система оценки: 5 балльная
Список вопросов теста
Вопрос 1
Какой ученый разработал основы алгебры логики?
Варианты ответов
- Л. Пастер
- Дж. Буль
- Б. Паскаль
- К. Шеннон
- И. Ньютон
Вопрос 2
Какая операция называется «конъюнкцией»?
Варианты ответов
- НЕ
- И
- или
- исключающее ИЛИ
- импликация
Вопрос 3
Какая операция называется «дизъюнкцией»?
Варианты ответов
- не
- и
- или
- исключающее ИЛИ
- импликация
Вопрос 4
Как называется операция, соответствующая связке «тогда и только тогда»?
Варианты ответов
- отрицание
- конъюнкция
- эквивалентность
- дизъюнкция
- импликация
Вопрос 5
Как называется операция, соответствующая связке «если . то»?
Варианты ответов
- отрицание
- конъюнкция
- эквивалентность
- импликация
- дизъюнкция
Вопрос 6
Какие из этих логических выражений равны нулю независимо от значения переменной A? Здесь xor обозначает «исключающее ИЛИ»
Варианты ответов
- A + A
- A * 0
- A xor A
- A xor 0
- A + 1
Вопрос 7
Какие из этих логических выражений истинны независимо от значения переменной A? Здесь xor обозначает «исключающее ИЛИ»
Варианты ответов
- A + 1
- A * 1
- A xor 1
- A xor A
- 1 xor (0 * A)
Вопрос 8
Найдите значение логического выражения
Вопрос 9
Какая операция равносильна выражению
Варианты ответов
- исключающее ИЛИ
- импликация
- эквиваленция
- конъюнкция
- логическое сложение
Логические операции. Базовые логические операции
Операций конъюнкция, дизъюнкция и инверсия достаточно для того, чтобы с их помощью можно было записать любую произвольную логическую операцию. Поэтому эти операции называют базовыми, основными.
В алгебре логики логическая операция полностью задается таблицей истинности, указывающей, какие значения принимает сложное высказывание при всех возможных значениях простых высказываний, входящих в сложное высказывание.
Введем формальным образом логические операции, соответствующие логическим связкам.
Конъюнкция
Высказывание, составленное из двух высказываний путем объединения их связкой «и» называется конъюнкцией.
Например, пусть есть два высказывания: А – «Число 22 четное», В – «Число 22 двузначное», тогда высказывание А и В (формально, F = А ∧ В): «Число 22 четное и двузначное».
Определение. Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны, называется конъюнкцией.
Логическая операция конъюнкция задается следующей таблицей истинности:
| A | B | F = A ∧ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Дизъюнкция
Высказывание, составленное из двух высказываний путем объединения их связкой «или» называется дизъюнкцией.
Например, пусть есть два высказывания: А – «Колумб был на Ямайке», В – «Колумб был на Гаити», тогда высказывание А или В (Формально, F = А ∨ В): «Колумб был на Ямайке или на Гаити».
Определение. Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны, называется дизъюнкцией.
Логическая операция дизъюнкция задается следующей таблицей истинности:
| A | B | F = A ∨ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Инверсия
Высказывание, образованное путем добавления связки «не» к простому высказыванию, называется инверсией (отрицанием).
В русском языке для образования отрицания может также использоваться связка «неверно, что».
Например, пусть высказывание А – «Число 22 простое», тогда высказывание «не» А (формально, F = ¬ A): «Неверно, что число простое»
Определение. Логическая операция, которая каждому высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному, называется отрицанием.
Логическая операция инверсия задается следующей таблицей истинности:
| A | F = ¬ A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Copyright © 2014-2021, Урок информатики
Все права защищены
ЦП Автоматизированные системы управления и промышленная безопасность
В отличие от аналоговых электронных устройств, в цифровых устройствах (ЦУ) входные и выходные сигналы могут принимать ограниченное количество состояний. В соответствии с логическим соглашением (ГОСТ 2.743-82), в зависимости от конкретной физической реализации элементов ЦУ, более положительному значению физической величины, «H» — уровень, соответствует состояние «логическая 1″, а менее положительному значению,»L — уровень» — «логический 0». Такое соглашение называется положительной логикой. Обратное соотношение называется отрицательной логикой. В ГОСТе 19480 — 89 даны наименования, определения и условные обозначения основных параметров и характеристик цифровых микросхем.
Теоретической основой проектирования ЦУ является алгебра-логики или булева алгебра, оперирующая логическими переменными. Для логических переменных, принимающих только два значения, существуют 4 основных операции. Операция логическое «И» (AND) конъюнкция или логическое умножение, обозначается * или /\. Операция логическое «ИЛИ» (OR), дизъюнкция или логическое сложение, обозначается + или \/. Операция логическое «НЕ» (NOT), изменение значения, инверсия или отрицание, обозначается чертой над логическим выражением. Инверсия иногда будет в тексте обозначаться знаком «~». Операция эквивалентности обозначается » MsoNormal» style=»margin-left: 1.0cm; text-align: justify; text-indent: 1.0cm;»>
Высказывание (суждение) – некоторое предложение, которое может быть истинно (верно) или ложно
Утверждение – суждение, которое требуется доказать или опровергнуть
Рассуждение – цепочка высказываний или утверждений, определенным образом связанных друг с другом
Умозаключение – логическая операция, в результате которой из одного или нескольких данных суждений получается (выводится) новое суждение
Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0)
Сложное логическое выражение – логическое выражение, составленное из одного или нескольких простых (или сложных) логических выражений, связанных с помощью логических операций.
Логические операции и таблицы истинности
F = A & B
Логическое умножение КОНЪЮНКЦИЯ — это новое сложное выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И .
F = A + B
Логическое сложение ДИЗЪЮНКЦИЯ — это новое сложное выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений. Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ .
Логическое отрицание ИНВЕРСИЯ — если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
Логическое следование ИМПЛИКАЦИЯ — связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом «следовательно» и выражается словами ЕСЛИ …, ТО …
Логическая равнозначность ЭКВИВАЛЕНТ — НОСТЬ — определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом «эквивалентности».
Порядок выполнения логических операций в сложном логическом выражении:
Для изменения указанного порядка выполнения операций используются скобки.
Построение таблиц истинности для сложных выражений:
Количество строк = 2 n + две строки для заголовка (n — количество простых высказываний)
Количество столбцов = количество переменных + количество логических операций
При построении таблицы надо учитывать все возможные сочетания логических значений 0 и 1 исходных выражений. Затем – определить порядок действий и составить таблицу с учетом таблиц истинности основных логических операций.
ПРИМЕР: составить таблицу истинности сложного логического выражения D = не A & (B+C) (таблица 3).
А, В, С — три простых высказывания, поэтому:
— количество строк = 2 3 +2 = 10 (n=3, т.к. на входе три элеманта А, В, С)
— количество столбцов : 1) А; 2) В; 3) С; 4) не A это инверсия А (обозначим Е); 5) B + C это операция дизъюнкции (обозначим F); 6) D = не A & ( B+C ), т.е. D = E & F это операция конъюнкции.
Таблица 3 — таблица истинности логического выражения D = не A & (B+C)
Какая операция называется конъюнкцией не и или
Рассмотрим более подробно некоторые логические связки, позволяющие конструировать из простых высказываний сложные. В математической логике такие связки называются логическими операциями.
2.3.1. Операция отрицания
Самой простой логической операцией, применяемой только к одному высказыванию, является операция отрицания, которая в русском языке соответствует частице «не». Отрицание высказывания А обозначается Ø А или . Символ читается «не А» или «не верно, что А». Например, если высказывание А – «подсудимый виновен», то — «подсудимый не виновен».
По смыслу, отрицание высказывания – высказывание, противоположное данному. То есть, если высказывание А – истинное, то высказывание — ложное, и наоборот, если А – ложное, то — истинное. Запишем в виде таблицы значения нового, сложного высказывания в зависимости от значений простого А, на основе которого оно построено.
Подобная таблица называется таблицей истинности [1] . Именно эту таблицу берут за определение операции отрицания. Высказывание называется отрицанием высказывания А, если оно истинно, когда А ложно, и ложно, когда А истинно.
2.3.2. Дизъюнкция высказываний
Операция дизъюнкция применяется к двум высказываниям А и В и соответствует соединению их с помощью союза «или». Дизъюнкция обозначается с помощью знака Ú , который ставится между высказываниями: А Ú В , что читается «А или В» или «или А, или В». Например, «Грабеж может быть совершен с применением физического или психического насилия», «Договор может быть заключен в устной или в письменной форме».
Рассмотрим значение составленного сложного высказывания А Ú В. Если одно из высказываний истинно, а другое ложно, то дизъюнкция будет истинной. Если оба простых высказывания А и В ложны, то и дизъюнкция будет ложной. А вот если оба высказывания А и В истинны, то существует два случая. Это связано с тем, что в русском языке союз «или» имеет два значения. Одно из них неисключающее «или», а другое – исключающее. Например, высказывание «Или я выучу этот материал, или получу двойку» при истинных его составляющих будет ложно. Здесь «или» понимается в исключающем смысле. А высказывание «Сейчас идет снег или дождь» – истинно, если оба высказывания «Сейчас идет снег», «сейчас идет дождь» – истинны и в этом случае союз «или» – неисключающий.
В логике высказываний дизъюнкция соответствует неисключающему «или». Можно дать следующее определение этой логической операции. Дизъюнкция А Ú В – сложное высказывание, которое ложно тогда и только тогда, когда оба высказывания А и В одновременно ложны. Таблица истинности операции дизъюнкция будет следующей:
Значения операции А Ú В (кроме первой строчки), как видно из таблицы, получаются простым алгебраическим сложением значений А и В. Поэтому дизъюнкцию также называют логическим сложением и обозначают, также как и в алгебре, знаком «+». Иногда знаком «+» обозначают операцию исключающего «или».
2.3.3. Конъюнкция высказываний
Операция конъюнкция применяется также к двум высказываниям А и В и соответствует соединению их с помощью союза «и». Она обозначается с помощью знака Ù или & , который ставится между высказываниями: А Ù В , что читается «А и В» или «и А, и В». Например, «Юрист должен знать и теорию государства и права, и историю, и информатику и математику». «Это преступление наказывается лишением свободы и конфискацией имущества». «Оскорбление – это унижение чести и достоинства человека. ».
Рассмотрим значение конъюнкции, исходя из смысла союза «и». Если оба высказывания А и В будут истинными, то и конъюнкция А Ù В будет истинной. Если же хотя бы одно из них (или оба) будут ложными, то и конъюнкция также будет ложной. Например, высказывание «3 – нечетное число и 3 делится на 2» будет ложным. Исходя из этого, можно дать следующее определение операции конъюнкция.
Конъюнкция А Ù В – сложное высказывание, которое истинно тогда и только тогда, когда оба высказывания А и В одновременно истинны. Таблица истинности операции конъюнкция такова:
Проанализировав приведенную таблицу, можно заметить, что значения операции А Ù В получаются простым алгебраическим умножением значений А и В. Поэтому конъюнкцию также называют логическим умножением и обозначают, также как и в алгебре, знаком « × » , который, также как и в алгебре, может опускаться.
Рассмотренные операции отрицания, дизъюнкции и конъюнкции называют булевыми операциями. Они играют важную роль в применениях математической логики в электронике, автоматике, теории вычислительных устройств.
2.3.4. Импликация высказываний
Одной из важнейших логических операций является операция импликация. Она соответствует объединению двух высказываний с помощью союза «если …, то …». Импликация обозначается с помощью знака ® , ставящегося между высказываниями: А ® В, что читается «А имплицирует В» или « если А, то В». В научной литературе по логике высказываний также приводятся другие варианты прочтения этой операции: « А влечет В», «из А следует В», « В только если А». А для обозначения импликации применяются знаки Þ , É .
Примеры. Гражданский кодекс РФ: «Если банк отказывает в принятии документов . то он обязан незамедлительно проинформировать об этом получателя средств». « Если новый уголовный закон смягчает наказание за деяние, которое отбывается лицом, то это наказание подлежит сокращению в пределах, предусмотренных новым уголовным законом. Статья 10 УК РФ». «Если осужденный после отбытия наказания вел себя безупречно, то по его ходатайству суд может снять с него судимость до истечения срока погашения судимости. Статья 86 УК РФ». «Если 2*2=4, то 3+2=6».
Операция импликации определяется следующим образом.
Импликация высказываний А и В ( А ® В ) – сложное высказывание, которое истинно всегда, кроме случая когда А – истинно, а В – ложно. Таким образом, таблица истинности импликации такова:
A ® B
Проанализируем соответствие определения импликации с общепринятым значением сложноподчиненного предложения с использованием союза «если . то . ». Рассмотрим следующее сложное высказывание: «Если гражданин Иванов совершил кражу, то он может быть наказан лишением свободы на срок до двух лет». Если оба простые высказывания «гражданин Иванов совершил кражу» и «он может быть наказан лишением свободы на срок до двух лет» истинны, то истинность сложного высказывания не вызывает сомнения. При истинности совершения кражи невозможность применения наказания в виде лишения свободы на срок до двух лет должно быть оценено нами как ложное высказывание, так как такое наказание предусмотрено статьей 158 Уголовного кодекса РФ. При ложном первом высказывании «гражданин Иванов совершил кражу» применение данного вида наказания к Иванову все же может быть осуществимо, если он, например, обвиняется по статье 127 УК РФ («Незаконное лишение свободы») или по статье 139 часть 2 УК РФ («Нарушение неприкосновенности жилища»). Поэтому оценивание сложного высказывания как истинного соответствует истинности импликации при данных значениях простых высказываниях в этих конкретных условиях. И, наконец, при ложности простых высказываний, т.е. истинности противоположных: «гражданин Иванов не совершил кражу» и «он не может быть наказан лишением свободы на срок до двух лет», рассмотренная причинно-следственная связь является истинной.
Рассмотрим следующие высказывания:
· «Волга впадает в Каспийское море» — истинное высказывание;
· «Дон впадает в Каспийское море» — ложное высказывание;
· «Дважды два – четыре» — истинное высказывание;
· «Дважды два – пять » — ложное высказывание.
Составим из этих простых высказываний сложные с помощью союза «если . то . » и, интерпретируя использованный союз как импликацию, оценим значения полученных высказываний.
· «Если Волга впадает в Каспийское море, то д важды два – четыре» — истинное высказывание;
· «Если Волга впадает в Каспийское море, то д важды два – пять» — ложное высказывание;
· «Если Дон впадает в Каспийское море, то д важды два – четыре» — истинное высказывание;
· «Если Дон впадает в Каспийское море, то д важды два – пять» — истинное высказывание.
Эти утверждения не соответствуют привычному для естественного языка употреблению союза «если . то . ». Поэтому импликация лишь до некоторой степени соответствует этому союзу. И математически корректнее операцию А ® В читать не «если А, то В», а «А имплицирует В». Операция импликации А ® В хорошо описывается союзом «если . то . » в случаях:
· описания причинно-следственной связи между А и В. Например, «Если долго мучиться, то что-нибудь получится»;
· выражения логического следования В из А. Например, «Если все люди смертны и Сократ – человек, то Сократ смертен».
В этих высказываниях существует связь между содержанием высказываний А и В, объединенных союзом. В логике высказываний рассматриваются только значения истинности высказываний, а не их содержание. Тем самым логические операции не выражают связь между содержанием высказываний. Логические операции, образующие из простых высказываний сложные, определяют только соотношения между значениями истинности этих высказываний.
2.3.5. Эквивалентность высказываний
Последней введем операцию эквивалентности. Эта операция обозначается символом « , либо ~ . Сложное высказывание А « В читается: «А эквивалентно В«, либо «А равносильно В«, либо «А тогда и только тогда, когда В«, либо «В, если и только если А«. Эквивалентность примерно соответствует употреблению выражения «тогда и только тогда, когда», хотя, как и в случае с импликацией, такое соответствие далеко не полное.
Приведем примеры использования операции эквивалентности. «Два треугольника равны тогда и только тогда, когда три стороны одного треугольника равны соответствующим сторонам другого треугольника». «Деяние кража равносильно тайному хищению чужого имущества». «Распространение заведомо ложных сведений является клеветой, если и только если эти сведения порочат честь и достоинство другого лица или подрывают его репутацию».
Эквивалентность высказываний А и В ( А « В ) – сложное высказывание, которое истинно, когда А и В одновременно либо истинны, либо ложны и ложно во всех других случаях. Эквивалентность определяется следующей таблицей истинности: