Как составить таблицу истинности для импликации

Алгебра логики

Алгебра логики

Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно утверждать, что его содержание истинно или ложно.

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

Кроме двузначной алгебры высказываний, в которой принимаются только два значения — «истинно» и «ложно», существует многозначная алгебра высказываний. В такой алгебре, кроме значений «истинно» и «ложно», употребляются такие истинностные значения, как «вероятно», «возможно», «невозможно» и т. д.

В алгебре логики различаются простые (элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.

Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

Основные операции алгебры логики

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖{-}$) или такими условными обозначениями, как ¬, ‘not’, и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖{-}$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.

Операция, используемая относительно одной величины, называется унарной. Таблица значений данной операции имеет вид

A	¬A
истина	ложь
ложь	истина

или

Высказывание $A↖{-}$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖{-}$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

Таблица истинности операции имеет вид

A	B	A ∧ B
истина	ложь	ложь
ложь	истина	ложь
ложь	ложь	ложь
истина	истина	истина

или

A	B	A ∧ B
1	0	0
0	1	0
0	0	0
1	1	1

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Таблица истинности операции имеет вид

A	B	A ∨ B
истина	ложь	истина
ложь	истина	истина
ложь	ложь	ложь
истина	истина	истина

или

A	B	A ∨ B
1	0	1
0	1	1
0	0	0
1	1	1

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

Таблица истинности операции имеет вид

А	В	А ⊕ B
истина	ложь	истина
ложь	истина	истина
ложь	ложь	ложь
истина	истина	ложь

или

А	В	А ⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если…, то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

Таблица истинности операции имеет вид

А	В	А → В
истина	ложь	ложь
ложь	истина	истина
ложь	ложь	истина
истина	истина	истина

или

А	В	А → В
1	0	0
0	1	1
0	0	1
1	1	1

Для операции импликации справедливо утверждение, что из лжи может следовать все что угодно, а из истины — только истина.

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

А	В	А ∼ В
истина	ложь	ложь
ложь	истина	ложь
ложь	ложь	истина
истина	истина	истина

или

А	В	А ∼ В
1	0	0
0	1	0
0	0	1
1	1	1

Операция эквивалентности противоположна сложению по модулю два и имеет результат «истина» тогда и только тогда, когда значения переменных совпадают.

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

Сложение по модулю два	А ⊕ В	$(A↖{-} ∧B) ∧ (A ∧ B↖{-})$
Импликация	А → В	$A↖{-} ∨ B$
Эквивалентность	А ∼ В	$(A↖{-} ∧ B↖{-}) ∨ (A ∧ B)$

Приоритет выполнения логических операций следующий: отрицание («не») имеет самый высокий приоритет, затем выполняется конъюнкция («и»), после конъюнкции — дизъюнкция («или»).

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

Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

Примеры решения задач

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Решение. Последовательность выполнения операций следующая: сначала выполняются операции сравнения в скобках, затем дизъюнкция, и последней выполняется операция импликации. Операция дизъюнкции ∨ ложна тогда и только тогда, когда оба операнда ложны. Таблица истинности для импликации имеет вид

A	B	A → B
1	0	0
0	1	1
0	0	1
1	1	1

Отсюда получаем:

1) для X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) для X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) для X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

Логические выражения и их преобразование

Под логическим выражением следует понимать такую запись, которая может принимать логическое значение «истина» или «ложь». При таком определении среди логических выражений необходимо различать:

• выражения, которые используют операции сравнения («больше», «меньше», «равно», «не равно» и т. п.) и принимают логические значения (например, выражение а > b , где а = 5 и b = 7, равно значению «ложь»);
• непосредственные логические выражения, связанные с логическими величинами и логическими операциями (например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина).

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

1. вычисление существующих функциональных зависимостей;
2. выполнение алгебраических операций (вначале умножение и деление, затем вычитание и сложение);
3. выполнение операций сравнения (в произвольном порядке);
4. выполнение логических операций (вначале операции отрицания, затем операции логического умножения, логического сложения, последними выполняются операции импликации и эквивалентности).

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

Пример. Найти значение выражения:

$1 ≤ a ∨ A ∨ sin(π/a — π/b) < 1 ∧ ¬B ∧ ¬(b^a + a^b > a + b ∨ A ∧ B)$ для а = 2, b = 3, A = истина, В = ложь.

Решение. Порядок подсчета значений:

1) b^a + a^b > a + b, после подстановки получим: 3² + 2³ > 2 + 3, т. е. 17 > 2 + 3 = истина;

2) A ∧ B = истина ∧ ложь = ложь.

Следовательно, выражение в скобках равно (b^a + a^b > a + b ∨ A ∧ B) = истина ∨ ложь = истина;

3) 1≤ a = 1 ≤ 2 = истина;

4) sin(π/a — π/b)  < 1 = sin(π/2 — π/3) < 1 = истина.

После этих вычислений окончательно получим: истина ∨ А ∧ истина ∧ ¬В ∧ ¬истина.

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

5) ¬В = ¬ложь = истина; ¬истина = ложь;

6) A ∧ истина ∧ истина ∧ ложь = истина ∧ истина ∧ истина ∧ ложь = ложь;

7) истина ∨ ложь = истина.

Таким образом, результат логического выражения при заданных значениях— «истина».

Примечание. Учитывая, что исходное выражение есть, в конечном итоге, сумма двух слагаемых, и значение одного из них 1 ≤ a = 1 ≤ 2 = истина, без дальнейших вычислений можно сказать, что результат для всего выражения тоже «истина».

Тождественные преобразования логических выражений

В алгебре логики выполняются основные законы, позволяющие производить тождественные преобразования логических выражений.

Закон	Для ∨	Для ∧
Переместительный	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Сочетательный	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
Распределительный	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
Правила де Моргана	${A ∨ B}↖{-}$ = $A↖{-} ∧ B↖{-}$	${A ∧ B}↖{-}$ = $A↖{-} ∨ B↖{-}$
Идемпотенции	A ∨ A = A	A ∧ A = A
Поглощения	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Склеивания	(A ∧ B) ∨ (A↖{-} ∧ B) = B	(A ∨ B) ∧ (A↖{-} ∨ B) = B
Операция переменной с ее инверсией	$A ∨ A↖{-}$ = 1	$A ∧ A↖{-}$ = 0
Операция с константами	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
Двойного отрицания	$A↖{=}$ = A

Доказательства этих утверждений производят на основании построения таблиц истинности для соответствующих записей.

Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определенному виду путем использования основных законов алгебры логики. Под упрощением формулы, не содержащей операций импликации и эквивалентности, понимают равносильное преобразование, приводящее к формуле, которая содержит либо меньшее по сравнению с исходной число операций, либо меньшее число переменных.

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т. п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

Для преобразования здесь можно применить закон идемпотенции, распределительный закон; операцию переменной с инверсией и операцию с константой.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Здесь для упрощения применяется закон поглощения.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой

Примеры решения задач

Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .

Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .

Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Ответ: A ∧ B ∧ ¬C.

Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.

Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».

1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;

2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;

3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».

Ответ: А — истина, В — ложь, С — истина.

Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35 < X · X) → (X < (X — 3)) ?

Решение. Запишем таблицу истинности для операции импликации:

A	B	A → B
1	0	0
0	1	1
0	0	1
1	1	1

Выражение X < (X — 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Ответ: X = 5.

Использование логических выражений для описания геометрических областей

Логические выражения могут быть использованы для описания геометрических областей. В этом случае задача формулируется так: записать для заданной геометрической области такое логическое выражение, которое принимает значение «истина» для значений x, y тогда и только тогда, когда любая точка с координатами (x; y) принадлежит геометрической области.

Рассмотрим описание геометрической области с помощью логического выражения на примерах.

Пример 1. Задано изображение геометрической области. Записать логическое выражение, описывающее множество точек, принадлежащих ей.

1) .

Решение. Заданную геометрическую область можно представить в виде набора следующих областей: первая область — D1 — полуплоскость ${x}/{-1} +{y}/{1} ≤ 1$, вторая — D2 — круг с центром в начале координат $x^2 + y^2 ≤ 1$. Их пересечение D1 $∩$ D2 представляет собой искомую область.

Результат: логическое выражение ${x}/{-1}+{y}/{1} ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

Эту область можно записать так: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

Примечание. При построении логического выражения используются нестрогие неравенства, а это значит, что границы фигур также принадлежат заштрихованной области. Если использовать строгие неравенства, то границы учитываться не будут. Границы, не принадлежащие области, обычно изображаются пунктиром.

Можно решить обратную задачу, а именно: нарисовать область для заданного логического выражнения.

Пример 2. Нарисовать и заштриховать область, для точек которой выполняется логическое условие y ≥ x ∧ y + x ≥ 0 ∧ y < 2 .

Решение. Искомая область представляет собой пересечение трех полуплоскостей. Строим на плоскости (x, y) прямые y = x; y = –x; y = 2. Это границы области, причем последняя граница y = 2 не принадлежит области, поэтому ее наносим пунктирной линией. Для выполнения неравенства y ≥ x нужно, чтобы точки находились слева от прямой y = x, а неравенство y = –x выполняется для точек, которые находятся справа от прямой y = –x. Условие y < 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Использование логических функций для описания электрических схем

Логические функции очень удобны для описания работы электрических схем. Так, для схемы, представленной на рис., где значение переменной X — это состояние выключателя (если он включен, значение X — «истина», а если выключен — «ложь»), это значение Y — это состояние лампочки (если она горит — значение «истина», а если нет — «ложь»), логическая функция запишется так: Y = X . Функцию Y называют функцией проводимости.

Для схемы, представленной на рис., логическая функция Y имеет вид: Y = X1 ∪ X2, т. к. достаточно одного включенного выключателя, чтобы горела лампочка. В схеме на рис., для того чтобы горела лампочка, должны быть включены оба выключателя, следовательно, функция проводимости имеет вид: Y = X1 ∧ X2 .

Для более сложной схемы функция проводимости будет иметь вид: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

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

Две схемы называются равносильными, если через одну из них ток проходит тогда, когда он проходит и через другую. Из двух равносильных схем более простой считается схема, функция проводимости которой содержит меньшее число элементов. Задача нахождения наиболее простых схем среди равносильных очень важна.

Использование аппарата алгебры логики при проектировании логических схем

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера. Любая информация при обработке на компьютере представляется в двоичной форме, т. е. кодируется некоторой последовательностью 0 и 1. Обработку двоичных сигналов, соответствующих 0 и 1, выполняют в компьютере логические элементы. Логические элементы, которые выполняют основные логические операции И, ИЛИ, НЕ, представлены на рис.

Условные обозначения логических элементов являются стандартными и используются при составлении логических схем компьютера. С помощью этих схем можно реализовать любую логическую функцию, описывающую работу компьютера.

Технически компьютерный логический элемент реализуется в виде электрической схемы, которая представляет собой соединение различных деталей: диодов, транзисторов, резисторов, конденсаторов. На вход логического элемента, который называют также вентилем, поступают электрические сигналы высокого и низкого уровней напряжения, на выход выдается один выходной сигнал также либо высокого, либо низкого уровня. Эти уровни соответствуют одному из состояний двоичной системы: 1 — 0; ИСТИНА — ЛОЖЬ. Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем. Работу логических схем описывают с помощью таблиц истинности. Условное обозначение на схеме ИЛИ знак «1» — от устаревшего обозначения дизъюнкции как «>=1» (значение дизъюнкции равно 1, если сумма двух операндов больше или равна 1). Знак «&» на схеме И является сокращенной записью английского слова and.

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

Построение таблиц истинности логических выражений

Для логической формулы всегда можно записать таблицу истинности, т. е. представить заданную логическую функцию в табличном виде. В этом случае таблица должна содержать все возможные комбинации аргументов функции (формулы) и соответствующие значения функции (результаты формулы на заданном наборе значений).

Удобной формой записи при нахождении значений функции является таблица, содержащая, кроме значений переменных и значений функции, также значения промежуточных вычислений. Рассмотрим пример построения таблицы истинности для формулы ${X1}↖{-} ∧ X2 ∨ {X1 ∨ X2}↖{-} ∨ X1$.

X1	X2	${X1}↖{-}$	${X1}↖{-}$ X2	X1 ∧ X2	${X1 ∨ X2}↖{-}$	${X1}↖{-}$ ∧ X2 ∨ ${X1 ∨ X2}↖{-}$	${X1}↖{-}$ ∧ X2 ∨ ${X1 ∨ X2}↖{-}$ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

Если функция принимает значение 1 при всех наборах значений переменных, она является тождественно-истинной; если при всех наборах входных значений функция принимает значение 0, она является тождественно-ложной; если набор выходных значений содержит как 0, так и 1, функция называется выполнимой. Приведенный выше пример является примером тождественно-истинной функции.

Зная аналитическую форму логической функции, всегда можно перейти к табличной форме логических функций. С помощью заданной таблицы истинности можно решить обратную задачу, а именно: для заданной таблицы построить аналитическую формулу логической функции. Различают две формы построения аналитической зависимости логической функции по таблично заданной функции.

1. Дизъюнктивно нормальная форма (ДНФ) — сумма произведений, образованных из переменных и их отрицаний для ложных значений.

Алгоритм построения ДНФ следующий:

1. в таблице истинности функции выбирают наборы аргументов, для которых логические формы равны 1 («истина»);
2. все выбранные логические наборы как логические произведения аргументов записывают, последовательно соединив их между собой операцией логической суммы (дизъюнкции);
3. для аргументов, которые являются ложными, в построенной записи проставляют операцию отрицания.

Пример. Построить функцию, определяющую, что первое число равно второму, используя метод ДНФ. Таблица истинности функции имеет вид

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Решение. Выбираем наборы значений аргументов, в которых функция равна 1. Это первая и четвертая строки таблицы (строку заголовка при нумерации не учитываем).

Записываем логические произведения аргументов этих наборов, объединив их логической суммой: X1 ∧ X2 ∨ X1 ∧ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих ложное значение (четвертая строка таблицы; второй набор в формуле; первый и второй элементы): X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Ответ: F(X1, X2) = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

2. Конъюнктивно нормальная форма (КНФ) — произведение сумм, образованных из переменных и их отрицаний для истинных значений.

Алгоритм построения КНФ следующий:

1. в таблице истинности выбирают наборы аргументов, для которых логические формы равны 0 («ложь»);
2. все выбранные логические наборы как логические суммы аргументов записывают последовательно, соединив их между собой операцией логического произведения (конъюнкции);
3. для аргументов, которые являются истинными, в построенной записи проставляют операцию отрицания.

Примеры решения задач

Пример 1. Рассмотрим предыдущий пример, т. е. построим функцию, определяющую, что первое число равно второму, используя метод КНФ. Для заданной функции ее таблица истинности имеет вид

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Решение. Выбираем наборы значений аргументов, в которых функция равна 0. Это вторая и третья строки (строку заголовка при нумерации не учитываем).

Записываем логические суммы аргументов этих наборов, объединив их логическим произведением: X1 ∨ X2 ∧ X1 ∨ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих истинное значение (вторая строка таблицы, первый набор формулы, второй элемент; для третьей строки, а это второй набор формулы, первый элемент): X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Таким образом, получена запись логической функции в КНФ.

Ответ: X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Полученные двумя методами значения функций являются эквивалентными. Для доказательства этого утверждения используем правила логики: F(X1, X2) = X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2 = X1 ∧ ${X1}↖{-}$ ∨ X1 ∧ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ ${X2}↖{-}$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ 0 = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Пример 2. Построить логическую функцию для заданной таблицы истинности:

X1	X2	F(X1, X2)
1	1	1
1	0	0
0	1	1
0	0	0

Решение. Используем алгоритм ДНФ для построения исходной функции:

X1	X2	F(X1, X2)
1	1	1	•	X1 ∧ X2
1	0	0
0	1	1	•	${X1}↖{-}$ ∧ X2
0	0	0

Искомая формула: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 .

Ее можно упростить: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 = X2 ∧ (X1 ∨ ${X1}↖{-}$) = X2 ∧ 1 = X2.

Пример 3. Для приведенной таблицы истинности построить логическую функцию, используя метод ДНФ.

X1	X2	X3	F(X1, X2, X3)
1	1	1	1	•	X1 ∧ X2 ∧ X3
1	0	1	0
0	1	1	1	•	${X1}↖{-}$ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1	•	X1 ∧ X2 ∧ ${X3}↖{-}$
1	0	0	1	•	X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$
0	1	0	0
0	0	0	0

Искомая формула: X1 ∧ X2 ∧ X ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∪ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$.

Формула достаточно громоздка, и ее следует упростить:

X1 ∧ X2 ∧ X3 ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∨ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$ = X2 ∧ X3 ∧ (X1 ∨ ${X1}↖{-}$) ∨ X1 ∧ ${X3}↖{-}$ ∧ (X2 ∨ ${X2}↖{-}$) = X2 ∧ X3 ∨ X1 ∧ ${X3}↖{-}$.

Таблицы истинности для решения логических задач

Составление таблиц истинности — один из способов решения логических задач. При использовании такого способа решения, условия, которые содержит задача, фиксируются с помощью специально составленных таблиц.

Примеры решения задач

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

Решение. Очевидно, что результатом решения будет таблица, в которой искомая функция Y(X1, X2, X3) будет иметь значение «истина», если какие-либо две переменные имеют значение «истина».

X1	X2	X3	Y(X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

Пример 2. Составить расписание уроков на день, учитывая, что урок информатики может быть только первым или вторым, урок математики — первым или третьим, а физики — вторым или третьим. Возможно ли составить расписание, удовлетворив всем требованиям? Сколько существует вариантов расписания?

Решение. Задача легко решается, если составить соответствующую таблицу:

	1-й урок	2-й урок	3-й урок
Информатика	1	1	0
Математика	1	0	1
Физика	0	1	1

Из таблицы видно, что существуют два варианта искомого расписания:

1. математика, информатика, физика;
2. информатика, физика, математика.

Пример 3. В спортивный лагерь приехали трое друзей — Петр, Борис и Алексей. Каждый из них увлекается двумя видами спорта. Известно, что таких видов спорта шесть: футбол, хоккей, лыжи, плавание, теннис, бадминтон. Также известно, что:

1. Борис — самый старший;
2. играющий в футбол младше играющего в хоккей;
3. играющие в футбол и хоккей и Петр живут в одном доме;
4. когда между лыжником и теннисистом возникает ссора, Борис мирит их;
5. Петр не умеет играть ни в теннис, ни в бадминтон.

Какими видами спорта увлекается каждый из мальчиков?

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

Так как видов спорта шесть, получается, что все мальчики увлекаются разными видами спорта.

Из условия 4 следует, что Борис не увлекается ни лыжами, ни теннисом, а из условий 3 и 5, что Петр не умеет играть в футбол, хоккей, теннис и бадминтон. Следовательно, любимые виды спорта Петра — лыжи и плавание. Занесем это в таблицу, а оставшиеся клетки столбцов «Лыжи» и «Плавание» заполним нулями.

	Футбол	Хоккей	Лыжи	Плавание	Бадминтон	Теннис
Петр	0	0	1	1	0	0
Борис			0	0		0
Алексей			0	0

Из таблицы видно, что в теннис может играть только Алексей.

Из условий 1 и 2 следует, что Борис не футболист. Таким образом, в футбол играет Алексей. Продолжим заполнять таблицу. Внесем в пустые ячейки строки «Алексей» нули.

	Футбол	Хоккей	Лыжи	Плавание	Бадминтон	Теннис
Петр	0	0	1	1	0	0
Борис	0		0	0		0
Алексей	1	0	0	0	0	1

Окончательно получаем, что Борис увлекается хоккеем и бадминтоном. Итоговая таблица будет выглядеть следующим образом:

	Футбол	Хоккей	Лыжи	Плавание	Бадминтон	Теннис
Петр	0	0	1	1	0	0
Борис	0	1	0	0	1	0
Алексей	1	0	0	0	0	1

Ответ: Петр увлекается лыжами и плаванием, Борис играет в хоккей и бадминтон, а Алексей занимается футболом и теннисом.

План урока:

Способы решению задач по логике

Табличный способ – этапы, особенности

Сравнение методов решения

Построение таблиц истинности для различных типов задач

Построение электрических схем, реализующих логические операции

Способы решения задач по логике

Многие задачи можно решить, используя инструменты алгебры логики. Чтобы получить результат, можно пойти 3 путями:

• рассуждая над условием;
• решая логические операции;
• используя таблицы истинности.

Логический подход подразумевает перевод условия из естественного языка на язык символов, схем и формул. Для такой формализации высказываний нужно выполнить ряд шагов.

Этапы решения логических задач:

• Разобраться с условием на естественном языке, выделив простые высказывания, и дать им символьные обозначения (латиница).
• Записать условие в виде формулы. Решить ее поэтапно, упрощая, учитывая приоритеты (( ), ¬, &, V).
• Просчитать формулы строчно или при помощи таблиц истинности, учитывая законы алгебры логики.
• Проверить, соответствует ли полученный результат условию задачи.

Табличный способ – этапы, особенности

Таблица истинности – табличное выражение результата логических операций для каждого отдельного набора значений переменных.

Такие таблицы позволяют абстрагироваться от маловажной информации, сосредоточиться только на связях между исходными данными, над происходящими процессами. Таким образом, человек может абстрагироваться от непонятной для него информации, решать неспецифические задачи.

Метод таблиц

Чтобы использовать таблицы истинности, необходимо формализовать условие, то есть отойти от деталей задачи, обозначая первоначальную информацию при помощи букв и цифр 0 и 1.

Существует общий алгоритм построения таблиц:

• Определить число логических значений/переменных (n) в примере.
• Установить вид, число и тип операций. Важно заранее определить очередность действий, выразить это при помощи скобок.
• Полученные данные позволяют рассчитать сколько нужно столбцов – это сумма числа переменных и операций.
• Нарисовать таблицу, заполнить шапку, записав обозначение переменных и выбранные действия.
• Определить, сколько существует наборов логических переменных (т.е. число строчек) по формуле m = 2ⁿ+ 1 (шапка).
• Заполнить столбцы, вписав наборы значений логических переменных (0 или 1).
• Записать результаты логических операций, указанных в шапке для каждой совокупности значений.
• Сделать выводы на основании полученных результатов.

Если необходимо перебрать все значения простых выражений, то для задач:

• с 2-мя переменными может быть только 4 набора логических переменных;

Если словесно описывать все эти комбинаций, на каждый из примеров понадобится десятки строк текста.

 Обязательно учитывают приоритет операций:

• Указанные в скобках.
• Отрицание.
• Логическая конъюнкция чисел.
• Дизъюнкция.
• Строгая дизъюнкция.
• Импликация.
• Эквивалентность.

Обозначение логических операций:

Сравнение методов решения

Метод рассуждений

Он заключается в пошаговом анализе условий с промежуточными выводами на каждом этапе. Выполняется анализ таблицы истинности каждого логического выражения.

Пример №1.

Андрей, Владимир, Георгий и Дмитрий живут на одной улице, они соседи. Они работают по таким специальностям: гитарист, плотник, егерь и стоматолог.

Известно, что:

• дом плотника правее егеря;
• стоматолог проживает левее егеря;
• дом гитариста с самого краю;
• стоматолог живет рядом с гитаристом;
• Владимир не гитарист, и его дом не соседствует с гитаристом;
• дома Дмитрия и егеря соседние;
• здание, в котором прописан Андрей, правее стоматолога;
• между домами Андрея и Дмитрия один дом.

Чтобы рассуждать было проще, добавим изображение зданий, присвоим им номера:

Но стоматолог живет левее егеря, а правее егеря – плотник. Получается, что дом гитариста не может быть последним, а дом стоматолога не может быть предпоследними. То есть, егерь живет в предпоследнем доме:

Между домами Андрея и Дмитрия стоит один дом, значит, дом Андрея не может быть предпоследним, получается номер – 4, что автоматом исключает проживание там Дмитрия и Владимира.

Условие задачи заняло 2 предложения, а рассуждений получилось на 2 страницы.

Такой подход лучше не использовать, если условие сложное или много данных.

Табличный метод

Более удачным подходом к решению задач с большим количеством данных (несколько множеств), считается табличный, или графический (диаграммы).

Чтобы построить таблицу истинности логических выражений, следует:

• Разбить задачу на простейшие утверждения, которые обозначить символами (большие буквы латинского алфавита).
• Записать условие задачи, как составное выражение из символов логических операций.
• Нарисовать таблицу истинности для полученных данных.
• Выбрать такой вариант, при котором полученные значения подходят под условие.
• Проверить соответствие выбранного варианта и условия задачи.

Чтобы преобразовывать условие задачи в логические выражения и операции, удобно пользоваться такой сводной таблицей истинности логических операций:

Рассмотрим тот же пример.

Определяем, что только гитарист может жить в первом доме, далее смотрим на заметки и условия и получаем таких жителей:

Метод компактнее, для некоторых задач нагляднее.

Построение таблиц истинности для различных типов задач

Несмотря на многообразие задач, многие условия повторяются, если оставить сухие формулы, не вникая в имена, места, профессии. Разобравшись с примером один раз, можно решать аналогичные задачи без труда. Рассмотрим несколько любопытных заданий, решив при помощи логически.

Пример 2.

Известно, что если первый студент летал в Англию на стажировку, то и второй тоже летал, но неправда, что если летал третий, то и второй.

Разобьём условие на 3 простые высказывания, присвоим им буквенные обозначения:

А — «Первый студент летал в Англию»;

В — «Второй студент летал в Англию»;

С — «Третий студент летал в Англию».

Запишем выясненные данные при помощи логических операций:

Пример 3.

Есть три 8-ых класса (А, В, С), которые соревнуются между собой за средний бал. Учителя в начале года сделали такие предположения:

• Если А получит максимальный бал, то максимальный бал получат Ви С.
• А и С получат или не получат максимальный бал одновременно.
• Необходимым условием получения высшего бала С класса является получение высшего бала В классом.

По завершении года оказалось, что 2 предсказания оказались верными, а одно – ошибочным.

Выясним, какие же классы добились высшего бала.

Разбиваем условие задачи на элементарные высказывания:

А – «А добьется высшего бала»;

В – «В добьется высшего бала»;

С – «С добьется высшего бала».

Запишем логические операции, описанные в примере:

Мы заполнили таблицу истинности для всех возможных значений исходных данных. В примере говорилось, что только 2 утверждения в конце года казались истинными, а 1- ложным. Такому условию отвечает 3-я строка в таблице.

Пример 4.

Во время знакомства девушка, любительница загадок, сказала, что ее имя узнать легко:

• последняя – гласная (Х1);
• или первая буква согласная (Х2)
• вторая – согласная (Х3).

¬(Х1→Х2)VХ3

Предложенные имена: Арина, Артур, Кэтрин, София.

Решим задачу, используя таблицу.

Сначала решим пошагово, выполняя операции по приоритету:

Указанному условию соответствует первое имя.

Пример 5.

Попробуем решать задачи, в которые нет четких высказываний, истинных или ложных. В них половина информации, правда, половина – ложь, при этом неизвестно, какая именно. Под такой тип задач можно подставить любое условие, но научившись решать его, можно разобраться со всеми аналогичными.

Известно, что в олимпиаде по химии участвовали 4 ученицы 8 класса: Марина, Света, Саша и Галя. Они заняли первые 4 места. Какое место заняла каждая из девочек, если есть их высказывания о победителях, но в них лишь половина информации правдива – первая или вторая половина предложения.

Маша Марина: «Саша заняла второе место, а Света – первое».

Полина Света: «Нет, это не так, Саша – победительница, а Галя, – на втором месте».

Ольга Саша: «Зачем вы всех путаете? Третье место за Мариной, а Света – на четвертом месте».

Составляем таблица для перебора вариантов. Правду обозначаем «1», ложь – «0».

Берем любое (Марины) утверждение и принимаем его первую часть за правду. Значит, Саша – 2 место, тогда Света не 1-ое (вторая половина фразы – ложь), остальных девочек на 2 место ставим «0».

Берем утверждение второй девочки. Так как Саша не может быть победительницей, то в этой фразе первая часть – ложь, а вторая должна быть истинной. Но в нем и вторая часть – неверна (второе место за Сашей, мы так приняли в начале).Уже на второй фразе получается противоречие всему.

Итог: Победительницей олимпиады стала Светлана, на втором месте – Галина, на третьем – Марина, на последнем из четырех – Александра.

 Построение электронных схем, реализующих логические операции

Если рассмотреть электросхемы с точки зрения логики, особенно компьютерные, то их также можно описать при помощи «1» и «0» – электричество идет или не идет по проводам.

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

Электросхема с конъюнктором

 Рассмотрим все варианты:

• Все контакты включены, тогда источник света горит.
• Первый контакт в положении «выключено» – свет не горит.
• Второй контакт выключен – лампа не светит.
• Все контакты отключены – свет не горит.

Заключение – эта электрическая цепь реализует операцию «И».

Дизъюнктор, схема электропитания

Рассмотрим этот вид электрической цепочки:

• Все контакты включены – лампа горит.
• Первый контакт включен, второй выключен – свет горит.
• Обратная ситуация – выключен первый, включен второй – лампа светится.
• Все контакты выключены – света нет.

Заключение – такой вид электросхем соответствует логической операции «ИЛИ».

Инвертор в электросхемах

В этой схеме переключатель не ручной, а автоматический. Здесь процесс обратный – когда ток не идет, контакты замыкаются, горит свет. Если же в сеть подается электричество, пластинка размыкается вследствие электромагнитной индукции, и сеть разъединяется – света нет.

Заключение: схема соответствует логической операции «НЕ».

Умение читать и решать логические операции, строить соответствующие электросхемы, позволяет создавать иерархически более сложные конструкции, которые используются для реализации процессов в современных ПК.

Обозначение логических элементов

Удобно создавать электросхемы в ПО SmartNotebook, которое используется с интерактивной доской.

Если есть два
высказывания А
и В,
то следующие выражения разговорной
речи записываются как импликация
(следование):
«если А,
то В»,
«В,
если А»,
«когда А,
тогда и В»,
«А
только, если В»,
«А
достаточно для В»,
«для А
необходимо В»,
«А
только тогда, когда В»,
«пусть А,
тогда В».
К импликации приводят выражения,
содержащие слова «необходимо» и
«достаточно».

Пример 1.7.
А = Пошел
дождь, В = На
небе тучи.
Новое высказывание «Чтобы
пошел дождь, необходимо на небе наличие
туч»
записывается как
.
Левая часть этого высказывания – посылка
(условие), правая – заключение (следствие).
Говорят, еслиА,
то В;
А
имплицирует В;
А
влечет В;
В
следует из А.

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

Высказывание
«Чтобы пошел
дождь, достаточно на небе туч»
записывается так:
.
Можно сделать вывод, что необходимые
условия записываются в качестве
заключения, справа, а достаточные условия
записываются в формуле слева, в качестве
посылки.

Большинство
математических теорем являются
импликациями.

Таблица 1.6

Таблица истинности функции импликация

а b 0 0 1 0 1 1 1 0 0 1 1 1

Замечание 1.2.
Некоторые выражения разговорного языка
по форме напоминают импликацию, а по
содержанию требуют запись в виде
конъюнкции. Например: «Если
в планиметрии изучают плоские фигуры,
то в стереометрии изучают трехмерные
геометрические тела».

Импликация
также функция двух логических переменных,
например, a
и b.
Операцию, соответствующую функции
импликации, также называют импликацией
и обозначают
(таблица истинности – табл. 1.6).Функция
запрета
(отрицание
импликации)
является
обратной
к функции импликации.

1.3. Законы алгебры логики и правила преобразования логических выражений

1.3.1. Логические константы, переменные, выражения и функции

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

В общем случае в
качестве логических операндов могут
выступать любые объекты, которые могут
принимать одно из двух возможных
значений.

Буквы, обозначающие
высказывания (А,
В,
…), можно рассматривать как имена
логических переменных, так как ими можно
заменить любые высказывания (с любым
содержанием).

Логическое выражение
приА = Вы
пользуетесь последними версиями
антивирусных программ;
В = Вы
регулярно сохраняете
свои файлы
на флэшке;
С = Снижается
вероятность потери данных
превращается в высказывание Е = Если
Вы пользуетесь последними версиями
антивирусных программ или регулярно
сохраняете свои файлы на флэшке, то
снижается вероятность потери данных.

Результат операции
отношения (знаки операций отношения:
>, <, ≤, ≥, =, ≠) принимает значение
ИСТИНА (TRUE
или 1), если условие выполняется, и ЛОЖЬ
(FALSE
или 0), если условие не выполняется.
Отношения можно интерпретировать как
простые высказывания, которые могут
быть истинными или ложными. В качестве
компонент отношения могут выступать
арифметические и символьные выражения.

Порядок выполнения
логических операций
в сложном логическом выражении (приоритеты
операций
приведены в порядке их понижения):

1) отрицание;

2) конъюнкция;

3) дизъюнкция;

4) неравнозначность;

5) эквивалентность;

6) импликация.

В выражении
сначала выполняется конъюнкция, потом
дизъюнкция, а потом уже отрицание, т. к.
отрицание относится к результату
вычисления.

Замечание 1.3.
Порядок выполнения логических операций
может быть изменен скобками.

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

Пример 1.8.
Вычислить значение выражения
приa
= 1, b
= 2, c
= 4.

Порядок выполнения
действий при вычислении значения данного
логического выражения указан цифрами
под фигурными скобками:

1)

2)

3)

4)

5)
;

6)
.

Различные логические
формулы могут быть эквивалентными. Это
можно проверить двумя путями.

Первый путь,
достаточно сложный, заключается в
последовательном преобразовании одной
или обеих формул, используя законы
алгебры логики. Цель преобразований –
привести обе формулы к одному и тому же
виду.

Второй путь более
простой, но при большом количестве
входящих в выражение логических
переменных громоздкий. Он состоит в
построении таблиц истинности для обеих
формул вручную или с использованием
компьютера (с помощью MS
Excel
или какого-либо языка программирования).

Логические функции
могут иметь один, два или более аргументов.
Например, функция
– логическая функция двух переменных,
а– логическая функция трех переменных

Пример 1.9.
Составить таблицу истинности функции
двух логических переменных
.

Порядок выполнения
действий определяется скобками. Сначала
должна выполняться операция отрицания,
затем импликация (результат обозначим
вспомогательной переменной р),
потом эквивалентность (результат – r),
а потом дизъюнкция.

Заполним таблицу
истинности (табл. 1.7). Для этого наборы
значений аргументов a
и b
зададим как двоичные числа в порядке
их возрастания:

Таблица
1.7

Таблица истинности
функции

a	b
0	0	1	1	1	1
0	1	0	1	0	1
1	0	1	1	0	1
1	1	0	0	1	1

Получился интересный
результат: значение функции равно
константе.

Замечание 1.4.
Для таблицы истинности функции трех
переменных надо использовать восемь
наборов исходных данных (2³ = 8),
для функции четырех переменных –
шестнадцать наборов (2⁴ = 16).
Записывать их надо в порядке возрастания
двоичных чисел, которые эти наборы
образуют.

Замечание 1.5.
Число наборов для k
переменных равно 2^k.
Наборы входных переменных, во избежание
ошибок, рекомендуется вводить так:

1) разделить столбец
значений первой переменной пополам и
заполнить верхнюю часть колонки ЛОЖЬ,
а нижнюю – ИСТИНА.

2) разделить столбец
значений второй переменной на четыре
части и заполнить четверти чередующимися
группами ЛОЖЬ и ИСТИНА, начиная с группы
ЛОЖЬ.

3) продолжить
деление столбцов значений последующих
переменных на 8, 16 и т. д. частей и заполнение
их группами ЛОЖЬ и ИСТИНА до тех пор,
пока группа ЛОЖЬ (ИСТИНА) не будет
состоять из одного символа.

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

Для любого «алгебраического» действия над утверждением задаётся правило определения истинности или ложности измененного утверждения, исходя из истинности или ложности исходного утверждения. Эти правила записываются через таблицы истинности выражения. Прежде, чем составлять таблицы истинности, надо поближе познакомиться с алгеброй логики.

Алгебраические преобразования логических выражений

Любое логическое выражение, как и его переменные (утверждения), принимают два значения: ложь или истина. Ложь обозначается нулём, а истина — единицей. Разобравшись с областью определения и областью допустимых значений, мы можем рассмотреть действия алгебры логики.

Отрицание

Отрицание и инверсия — самое простое логическое преобразование. Ему соответствует частица «не.» Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то «не А» — ложно. Например, утверждение «прямой угол — это угол, равный девяносто градусов» — истина. Тогда его отрицание «прямой угол не равен девяноста градусам» — ложь.

Таблица истинности для отрицания будет такова:

Конъюнкция

Конъюнкция аналогична умножению и соответствует союзу «и». Такое выражение будет верно, только если верны все утверждения, объединённые конъюнкцией. То есть, утверждение «А и Б» будет истинным, только если А — истина и Б — истина. Во всех остальных случаях выражение «А и Б» ложно. Например, высказывание «Земля круглая и плоская» будет ложно, так как первая часть истина, а вторая — ложь.

Таблица истинности конъюнкции

А	Б	А и Б
Л	Л	Л
Л	И	Л
И	Л	Л
И	И	И

Дизъюнкция

Эта операция может быть обычной или строгой, их результаты будут различаться.

Обычная дизъюнкция или логическое сложение соответствует союзу «или». Она будет истинной если хотя бы одно из утверждений, входящих в неё — истина. Например, выражение «Земля круглая или стоит на трёх китах» будет истинным, так как первое утверждение — истинно, хоть второе и ложно.В таблице это будет выглядеть так:

А	Б	А или Б
Л	Л	Л
Л	И	И
И	Л	И
И	И	И

Строгую дизъюнкцию или сложение по модулю также называют «исключающим или». Эта операция может принимать вид грамматической конструкции «одно из двух: либо …, либо …». Здесь значение логического выражения будет ложным, если все утверждения, входящие в него, имеют одинаковую истинность. То есть, оба утверждения либо вместе истинны, либо вместе ложны.

Таблица значений исключающего или

А	Б	либо А, либо Б
Л	Л	Л
Л	И	И
И	Л	И
И	И	Л

Импликация и эквивалентность

Импликация представляет собой следствие и грамматически может быть выражена как «из А следует Б». Здесь утверждение А будет называться предпосылкой, а Б — следствием. Импликация может быть ложной, только в одном случае: если предпосылка истинна, а следствие ложно. То есть, ложь не может следовать из истины. Во всех остальных случаях импликация истинна. Варианты, когда оба утверждения имеют одинаковую истинность, вопросов не вызывают. Но почему верное следствие из неверной предпосылки — истина? Дело в том, что из ложной предпосылки может следовать что угодно. Это и отличает импликацию от эквивалентности.

В математике (и других доказательных дисциплинах) импликация используется для указания необходимого условия. Например, утверждение А — «точка О — экстремум непрерывной функции», утверждение Б — «производная непрерывной функции в точке О обращается в ноль». Если О, действительно, точка экстремума непрерывной функции, то производная в этой точке будет, и вправду, равна нулю. Если же О не является точкой экстремума, то производная в этой точке может быть нулевой, а может не быть. То есть Б необходимо для А, но не достаточно.

Таблица истинности для импликации выглядит следующим образом:

А	Б	из А следует Б
Л	Л	И
Л	И	И
И	Л	Л
И	И	И

Логическая операция эквивалентность, по сути, является взаимной импликацией. «А эквивалентно Б» означает, что «из А следует Б» и «из Б следует А» одновременно. Эквивалентность верна, когда оба утверждения либо одновременно верные, либо одновременно неверные.

А	Б	А эквивалентно Б
Л	Л	И
Л	И	Л
И	Л	Л
И	И	И

В математике эквивалентность используется для определения необходимого и достаточного условия. Например, утверждение А — «Точка О является точкой экстремума непрерывной функции», утверждение Б — «В точке О производная функции обращается в ноль и меняет знак». Эти два утверждения эквивалентны. Б содержит необходимое и достаточное условие для А. Обратите внимание, что в данном примере утверждений Б на самом деле является конъюнкцией двух других: «производная в точке О обращается в ноль» и «производная в точке О меняет знак».

Прочие логические функции

Выше были рассмотрены основные логические операции, которые часто используются. Есть и другие функции, которые используются:

• Штрих Шеффера или несовместимость представляет собой отрицание конъюнкции А и Б
• Стрелка Пирса представляет сбой отрицание дизъюнкции.

Построение таблиц истинности

Чтобы построить таблицу истинности для какого-либо логического выражения, надо действовать в соответствии с алгоритмом:

1. Разбить выражение на простые утверждения и обозначить каждое из них как переменную.
2. Определить логические преобразования.
3. Выявить порядок действий этих преобразований.
4. Сосчитать строки в будущей таблице. Их количество равно два в степени N, где N — число переменных, плюс одна строка для шапки таблицы.
5. Определить число столбцов. Оно равно сумме количества переменных и количества действий. Можно представлять результат каждого действия в виде новой переменной, если так будет понятней.
6. Шапка заполняется последовательно, сначала все переменные, потом результаты действий в порядке их выполнения.
7. Заполнение таблицы надо начать с первой переменной. Для неё количество строк делится пополам. Одна половина заполняется нулями, вторая — единицами.
8. Для каждой следующей переменной нули и единицы чередуются вдвое чаще.
9. Таким образом заполняются все столбцы с переменными и для последней переменной значение меняется в каждой строке.
10. Потом последовательно заполняются результаты всех действий.

В итоге последний столбец отобразит значение всего выражения в зависимости от значения переменных.

Отдельно следует сказать о порядке логических действий. Как его определить? Здесь, как и в алгебре, есть правила, задающие последовательность действий. Они выполняются в следующем порядке:

1. выражения в скобках;
2. отрицание или инверсия;
3. конъюнкция;
4. строгая и обычная дизъюнкция;
5. импликация;
6. эквивалентность.

Примеры

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

• Штрих Шеффера.
• Стрелка Пирса.
• Определение эквивалентности.

Штрих Шеффера

Штрих Шеффера — это логическое выражение, которое можно записать в виде «не (А и Б)». Здесь две переменные, и два действия. Конъюнкция в скобках, значит, она выполняется первой. В таблице будет шапка и четыре строки со значениями переменных, а также четыре столбца. Заполним таблицу:

А	Б	А и Б	не (А и Б)
Л	Л	Л	И
Л	И	Л	И
И	Л	Л	И
И	И	И	Л

Отрицание конъюнкции выглядит как дизъюнкция отрицаний. Это можно проверить, если составить таблицу истинности для выражения «не А или не Б». Проделайте это самостоятельно и обратите внимание, что здесь будет уже три операции.

Стрелка Пирса

Рассматривая Стрелку Пирса, которая представляет собой отрицание дизъюнкции «не (А или Б)», сравним её с конъюнкцией отрицаний «не А и не Б». Заполним две таблицы:

А	Б	А или Б	не (А или Б)
Л	Л	Л	И
Л	И	И	Л
И	Л	И	И
И	И	И	Л

А	Б	не А	не Б	не А и не Б
Л	Л	И	И	И
Л	И	И	Л	Л
И	Л	Л	И	И
И	И	Л	Л	Л

Значения выражений совпали. Изучив два эти примера, можно прийти к выводу, как раскрывать скобки после отрицания: отрицание применяется ко всем переменным в скобках, конъюнкция меняется на дизъюнкцию, а дизъюнкция — на конъюнкцию.

Определение эквивалентности

Про утверждения А и Б можно сказать, что они эквивалентны, тогда и только тогда, когда из А следует Б и из Б следует А. Запишем это как логическое выражение и построим для него таблицу истинности. «(А эквивалентно Б) эквивалентно (из А следует Б) и (из Б следует А)».

Здесь две переменных и пять действий. Строим таблицу:

А	Б	В = (из А следует Б)	Г = (из Б следует А)	Д = А эквивалентно Б	Е = В и Г	Д эквивалентно Е
Л	Л	И	И	И	И	И
Л	И	И	Л	Л	Л	И
И	Л	Л	И	Л	Л	И
И	И	И	И	И	И	И

В последнем столбце все значения истинные. Это значит, что приведенное определение эквивалентности верно при любых значениях А и Б. Значит, оно всегда истинно. Именно так с помощью таблицы истинности можно проверить корректность любых определений и логических построений.