Логические значения, операции, выражения - Обработка информации - ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ

Конспект

Введение

В окружающем нас мире мы постоянно сталкиваемся с утверждениями. Например, “Маша — молодец”, “Дважды два — пять”, “Идёт дождь”, “Завтра будет хорошая погода”. Если про утверждение можно сказать, истинно оно или ложно, такое утверждение называется логическим утверждением.

Например, среди приведённых утверждений:

“Маша — молодец”	Не является логическим утверждением, потому что подобная оценка (молодец) субъективна.
“Дважды два — пять”	Является логическим утверждением. Про него можно сказать, что это — ложь
“Идёт дождь”	Является логическим утверждением, если в этот момент видно, какая в настоящий момент погода (идёт дождь или нет). Соответственно, если дождь идёт, то это истинное логическое утверждение, а если не идёт — ложное логическое утверждение.
“Завтра будет хорошая погода”	Не является логическим утверждением, потому что проверить его в настоящий момент нельзя.

Результаты логических утверждений (истину и ложь) обычно обозначают:

Истина	Да	True	1
Ложь	Нет	False	0

В информатике, как правило, используются обозначения 1 и 0. Это удобно, коротко, наглядно. Позволяет пользоваться математическим аппаратом двоичной системы счисления. Однозначно определяет, как эти значения хранятся в памяти компьютера.

Логические операции

При обработке логических утверждений часто возникает необходимость объединять несколько логических выражений или преобразовывать их. Для этого придуманы специальные логические операции. Мы будем рассматривать только три основные логические операции.

• Логическое И

Также называется логическое умножение или конъюнкция.

Выполняется над двумя логическими операндами.

Операндом называется то, над чем выполняется операция. Например, всем известная операция сложения выполняется над двумя слагаемыми. Слагаемые — это операнды. А операция умножения производится над сомножителями. Сомножители — тоже операнды.

Обозначения: И, AND, &, ∙

То есть, если операция выполняется над двумя логическими операндами А и В, то возможные обозначения:

А И В

A AND В

А & В

А ∙ В

Результат операции истина, если значения обоих логических операнда — истина.

Как вы понимаете, диапазон значений, которые могут принимать логические операнды, ограничен (только истина и ложь, 0 и 1). Поэтому имеется возможность просто перечислить, какое значение будет у логической операции при всех возможных значениях операндов.

Все эти варианты логических операндов и результат для каждого случая логической операции принято записывать в таблицу, которая называется таблица истинности. Так как у операции логическое И всего два операнда и каждый принимает два возможных логических значения, то таблица истинности для этой операции содержит всего 2 ∙ 2 = 4 строки. Для всех комбинаций возможных значений операндов.

Приведём таблицу истинности для операции логического И:

А	В	А И В
0	0	0
0	1	0
1	0	0
1	1	1

Как можно видеть, результат — истина получается только в том случае, если оба операнда — истина.

• Логическое ИЛИ

Также называется логическое сложение или дизъюнкция.

Выполняется над двумя логическими операндами.

Обозначения: ИЛИ, OR, V, +

То есть, если операция выполняется над двумя логическими операндами А и В, то возможные обозначения:

А ИЛИ В

A OR В

A V В

А + В

Результат операции истина, если у хотя бы одного логического операнда значение — истина.

Приведём таблицу истинности для операции логическое ИЛИ:

А	В	А ИЛИ В
0	0	0
0	1	1
1	0	1
1	1	1

Как можно видеть, результат — ложь получается только в том случае, если оба операнда — ложь.

• Логическое НЕ

Также называется отрицание или инверсия.

Выполняется над одним логическим операндом.

Обозначения: НЕ, NOT, ¬, ¯ (последнее обозначение — линия сверху над операндом)

То есть, если операция выполняется над логическим операндом А, то возможные обозначения:

Результат операции меняется на противоположный (из истины — ложь, из лжи — истина).

Приведём таблицу истинности для операции логическое НЕ:

А	НЕ А
0	1
1	0

Так как у операции логическое НЕ всего один операнд, то таблица истинности этой операции содержит всего две строки (для каждого возможного значения операнда).

Как можно видеть, результат — ложь получается только в том случае, если оба операнда — ложь.

Приоритеты логических операций

Часто бывает, что нужно выполнить сразу несколько логических операций и объединить их результаты другими логическими операциями. То есть, выполнить целое логическое выражение. Например, А ИЛИ В И С.

Для того, чтобы понять, какая из этих операций выполняется первой, а какая — второй, придуманы приоритеты логических операций. То есть, порядок, в котором разные операции выполняются в сложном логическом выражении. Вы, конечно, понимаете, что это такое! Ведь ещё с начальной школы все мы знаем, например, что умножение выполняется раньше сложения. Так выражение 2 + 3 ∙ 4 равно выражению 2 + (3 ∙ 4). То есть, сначала выполнится умножение, а потом — сложение. Если же в выражении 2 + 3 ∙ 4 нужно выполнять сначала сложение, а только потом умножение, нужно добавить скобки: (2 + 3) ∙ 4.

Так же и здесь. Логическое умножение (логическое И) выполняется раньше логического сложения (логического ИЛИ). Полностью приоритеты изученных нами логических операций следующие:

0. Выражение в скобках

1. Логическое НЕ

2. Логическое И

3. Логическое ИЛИ

Операции одинакового приоритета выполняются слева направо.

Вычисление логического выражения по таблице истинности

В связи с тем, что количество возможных значений аргументов в логических выражениях ограничено, появляется возможность посчитать значение логического выражения для всех возможных значений аргументов. Мы уже использовали эту технологию для вычисления всех возможных значений логических операций. Точно так же можно сделать для более сложных логических выражений. Это называется таблица истинности. Количество строк в таблице истинности равно числу 2 в степени количества аргументов (переменных). То есть, если в выражении, например, три различных переменных, то количество строк в таблице истинности: 2 ∙ 2 ∙ 2 = 2³ = 8.

Разбор типовых задач

Задача 1. Расставьте, в каком порядке будут выполняться действия в логическом выражении

А ИЛИ НЕ В И НЕ С

Решение

Выражение не содержит скобок, поэтому порядок действий будет строго по правилу НЕ-И-ИЛИ.

Сначала выполнятся оба отрицания (логическое НЕ). Потом выполнится логическое умножение (логическое И). Последним выполнится логическое сложение (логическое ИЛИ). То есть, порядок выполнения действий будет таким:

Задача 2. Расставьте, в каком порядке будут выполняться действия в логическом выражении:

(А И НЕ В) ИЛИ С И НЕ (В ИЛИ НЕ С)

Решение

Выражение содержит скобки, поэтому сначала нужно выполнить все операции в скобках, и только потом — операции вне скобок. Так как в выражении две пары скобок, не вложенных друг в друга, выполним по порядку: в левой скобке, потом — в правой.

В скобках по отдельности и потом — вне скобок, порядок действий будет по тому же правилу НЕ-И-ИЛИ. Сначала выполняется отрицание (логическое НЕ) в левой скобке (НЕ В). Потом — логическое умножение (логическое И) там же, в левой скобке (А И (НЕ В)). После этого левая скобка будет вычислена и можно переходить к вычислению следующей скобки.

В правой скобке выполняется отрицание (логическое НЕ — НЕ С). Потом выполнится логическое сложение (логическое ИЛИ — В ИЛИ (НЕ С)).

Теперь вычисляются операции вне скобок. Как и ранее, сначала выполним отрицание (логическое НЕ) над правой скобкой. Затем — логическое умножение (логическое И) для С И правой скобки. Последним выполним логическое сложение (логическое ИЛИ) для левой скобки и результатом только что полученного логического И. То есть, порядок выполнения действий будет таким:

Задача 3. Построить таблицу истинности выражения:

А И НЕ (В ИЛИ НЕ С)

Решение

Подсчитываем количество различных переменных в выражении. В выражении используются переменные: А, В, С. То есть, три переменных. Значит, в таблице истинности будет 2³ = 8 строк.

Вспоминаем приоритеты и расставляем порядок действий в выражении:

Запишем таблицу истинности. Первые три столбца в ней будут соответствовать переменным А, В, и С. В этих столбцах переберём все возможные значения этих переменных. Далее нарисуем ещё 4 столбца по количеству логических операций в выражении:

			1	2	3	4
А	В	С	НЕ С	В ИЛИ (1)	НЕ (2)	А И (3)
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

В столбцах А, В, С перебрали все возможные значения логических переменных А, В, С. Чтобы не сбиться и не забыть ни одной комбинации мы использовали следующую технологию. В первом столбце сначала записали половину нулей, затем вторую половину — единиц. То есть, в данном случае, получилось 4 нуля и 4 единицы. Во втором столбцы мы сначала написали в два раза меньше нулей (в нашем случае, получилось два нуля), затем столько же единиц, затем снова столько же нулей, затем снова столько же единиц. В третьем столбце мы снова писали вдвое меньшее количество то нулей, то единиц. Это был последний столбец переменных, поэтому получилось по одному нулю и одной единице, чередуясь.

Данная технология хороша несколькими моментами. Во-первых, она позволяет быстро и почти не задумываясь построить таблицу истинности. Во-вторых, полученные таким образом последовательности нулей и единиц в строках являются последовательными двоичными числами. То есть, таким образом можно быстро породить также и необходимое количество кодов первых двоичных чисел (обычно 8 или 16).

Над первой строкой таблицы мы поставили номера логических операций, чтобы в таблице было удобнее вычислять их значения. Так, например, в столбце со второй операцией в действительности вычисляется значение выражения “В ИЛИ НЕ С”. Однако, при такой записи этого выражения не очень наглядно, какая именно операция сейчас вычисляется и над какими аргументами она производится. Вместо этого ввели обозначения (пронумеровали) операции данного выражения. В результате вместо “В ИЛИ НЕС” мы используем обозначение “В ИЛИ (1)”. Где под обозначением (1) имеется ввиду результат операции номер 1 нашей таблицы. Это наглядно демонстрирует, какая именно операция и над какими аргументами (операция ИЛИ над столбцом В и столбцом, подписанным номером 1) сейчас выполняется.

Теперь будем последовательно, столбец за столбцом, заполнять результаты логических операций. В нашем примере первая операция — НЕ С. Её вычисление примитивно — для каждой цифры столбца С пишем в столбец под номером 1 число 1, если в столбце С стоит 0, и число 0, если в столбце С стоит 1.

Теперь вычисляем вторую операцию — В ИЛИ (1). Смотрим последовательно в каждую строчку столбцов В и (1) и, если обнаруживаем в них хотя бы одну единицу, пишем в результирующий столбец (2) единицу. А если оба нуля — пишем 0.

			1	2	3	4
А	В	с	НЕ С	В ИЛИ (1)	НЕ (2)	А И (3)
0	0	0	1	1
0	0	1	0	0
0	1	0	1	1
0	1	1	0	1
1	0	0	1	1
1	0	1	0	0
1	1	0	1	1
1	1	1	0	1

Столбец 3 — НЕ (2) — вычисляем аналогично столбцу 1. То есть, пишем 1, если в столбце 2 стоит 0. И пишем 0, если в столбце 2 стоит 1.

			1	2	3	4
А	В	С	НЕ С	В ИЛИ (1)	НЕ (2)	А И (3)
0	0	0	1	1	0	0
0	0	1	0	0	1	0
0	1	0	1	1	0	0
0	1	1	0	1	0	0
1	0	0	1	1	0	0
1	0	1	0	0	1	1
1	1	0	1	1	0	0
1	1	1	0	1	0	0

Столбец 4 вычисляем, просто перемножая числа, стоящие в столбцах А и (3).

Задача 4. Для какого из приведённых чисел ложно высказывание:

НЕ (число > 50) ИЛИ (число чётное)?

1) 123

2) 56

3) 9

4) 8

Решение

Самый простой (“в лоб”) способ решения этой задачи — подставить в логическое выражение каждое из предлагаемых чисел и посмотреть, в каком случае результат выражения будет ложным.

Удобнее всего (чтобы не ошибиться в уме и ничего не потерять) составить для этого аналог таблицы истинности. Количество строк будет равно количеству вариантов чисел. Для каждого числа мы будем вычислять логические утверждения. В данном случае это “число > 50” и “число чётное”.

После подставим результаты этих логических утверждений в логические операции и вычислим их результат. Проанализируем порядок, в котором будут вычисляться операции данного выражения. Сначала вычислим выражения в скобках, потом — НЕ, последним — ИЛИ.

Получаем следующий порядок:

Составляем “таблицу истинности”:

	1	2	3	4
число	(число > 50)	(число чётное)	НЕ (1)	(3) ИЛИ (2)
123
56
9
8

Заполняем последовательно, столбец за столбцом и строчка за строчкой, эту таблицу.

В частности:

число 123 > 50 ? Да. Пишем в соответствующую ячейку 1.

число 56 > 50 ? Да. Пишем ниже тоже 1. число 9 > 50 ? Нет. Пишем ниже число 0.

И так далее.

Получаем:

	1	2	3	4
число	(число > 50)	(число чётное)	НЕ (1)	(3) ИЛИ (2)
123	1	0	0	0
56	1	1	0	1
9	0	0	1	1
8	0	1	1	1

Результат 0 (ложь) получился только в одной строке таблицы — в строке 1 для числа 123. Указываем его (номер 1) в качестве ответа.

Заметим, что если вы решили вычислять исходное выражение для каждого числа по отдельности, и получили для какого-нибудь из чисел сразу нужный результат (в данном случае, ложь), не спешите сразу считать это правильным ответом. Мы рекомендуем на всякий случай, вычислить значение выражения для всех возможных вариантов ответа, чтобы проверить себя. Потому что, если обнаружится нужный ответ ещё для одного варианта, это будет повод задуматься над тем, что вы, возможно, неверно вычисляете выражение.

Приведённый способ (построение таблицы) хотя и является достаточно медленным, но позволяет свести к минимуму риск ошибки.

Другой способ решения

Можно решать эту задачу аналитически. По условию, выражение НЕ (число > 50) ИЛИ (число чётное) должно быть ложным. Последняя вычисляемая операция этого выражения — ИЛИ. Операция ИЛИ — ложна тогда и только тогда, когда оба её операнда — ложны. То есть, должно быть ложно выражение НЕ (число > 50) и должно быть ложно утверждение (число чётное).

Чтобы выражение НЕ (число > 50) было ложно, нужно, чтобы утверждение (число > 50) было истинно.

А чтобы утверждение (число чётное) было ложно, нужно, чтобы число было нечётное.

Получаем, что все исходное выражение ложно в том случае, если число больше 50 и нечётно.

Ищем среди вариантов ответа нечётное число, большее 50 и находим его (123) под вариантом номер 1.

Ответ: 1.