СОДЕРЖАНИЕ РАЗДЕЛА

  1. Логические выражения и логические операции
  2. Законы логики и преобразование логических выражений
  3. Конъюнкция - логическое умножение
  4. Дизъюнкция - логическое сложение
  5. Инверсия - отрицание
  6. Логическое следование (импликация)
  7. Эквивалентность (логическое тождество)
  8. Построение таблиц истинности и логических функций
  9. Построение логической функции по ее таблице истинности
  10. Основы математической логики.
  11. Пример 1 (упрощение формул)
  12. Пример 2 (упрощение формул)
  13. Вопросы для самопроверки

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

 Исследования в алгебре логики связаны с изучением высказываний. Высказывание — это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности.
 Простым высказыванием называют повествовательное предложение, относительно которого имеет смысл говорить, истинно оно или ложно. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.
Примеры высказываний:
  1. 1)  Площадь круга равна S = π·r2, где r есть радиус круга (высказывание истинно);
  2. 2)  Волга впадает в Каспийское море (высказывание истинно);
  3. 3)  Число 12 является простым числом (высказывание ложно).
  4. 4)  Выражение x + 1 = x + 1 является уравнением (высказывание ложно).
  5. 5)  Уравнения x2 = x и x = 1 является равносильными (высказывание ложно).
  6. 6)  Уравнения sin x = cos x и tg x = 1 является равносильными (высказывание истинно).
  Предложения "Я сегодня позвоню тебе", "Ты сегодня позвонишь мне ?", "2·x = 4" не являются высказываниями, так как они не обладают свойством быть истинным или ложным.
 С помощью высказываний устанавливаются свойства, взаимосвязи между объектами. Высказывание истинно, если оно адекватно отображает эту связь, в противном случае оно ложно.
 В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1. Если высказывание истинно, то его значение равно 1, если ложно - 0.
 Простые высказывания назвали логическими переменными, а сложные - логическими функциями. Значения логической функции также только 0 или 1. Для простоты записи высказывания обозначаются латинскими буквами А, В, С. Понятие истинности и ложности высказывания определяется и ограничивается знаниями о высказываемом "на данный момент". И это одпереляет относительность понятия истинности или ложности.
 Простым высказываниям ставятся в соответствие логические переменные, значение которых равно 1, если высказывание истинно, и 0, если высказывание ложно. Обозначаются логические переменные, большими буквами латинского алфавита.

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

 Существуют разные варианты обозначения истинности и ложности логических переменных:
Истина И True T 1
Ложь Л False F 0
 Сложные (составные) высказывания представляют собой набор простых высказываний (по крайней мере двух) связанных логическими операциями.
 С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением).
 Логическое выражение - это символическая запись высказывания, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).
 Связки "НЕ", "И", "ИЛИ" заменяются логическими операциями инверсия, конъюнкция, дизъюнкция. Это основные логические операции, при помощи которых можно записать любое логическое выражение.

Конъюнкция - логическое умножение

 Введем перечисленные логические операции.
 Конъюнкция - логическое умножение:  Конъюнкция - это логическая операция, ставящая в соответствие каждым двум простым (или исходным) высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Если хотя бы одно из составляющих высказываний ложно, то и полученное из них с помощью союза «И» сложное высказывание также считается ложным.
 В алгебре множеств конъюнкции соответствует операция пересечения множеств, т.е. множеству получившемуся в результате умножения множеств А и В соответствует множество, состоящее из элементов, принадлежащих одновременно двум множествам.
Таблица истинности Диаграмма Эйлера-Венна
A B A & B
1 1 1
1 0 0
0 1 0
0 0 0
Два высказывания соединены союзом "И", то полученное сложное высказывание истинно тогда и только тогда, когда истинны оба исходных высказывания.

Дизъюнкция - логическое сложение

 Дизъюнкция - логическое сложение:  Дизъюнкция - это логическая операция, которая каждым двум простым (или исходным) высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны и истинным, когда хотя бы одно из двух образующих его высказываний истинно.
 В алгебре множеств дизъюнкции соответствует операция объединения множеств, т.е. множеству получившемуся в результате сложения множеств А и В соответствует множество, состоящее из элементов, принадлежащих либо множеству А, либо множеству В.
Таблица истинности Диаграмма Эйлера-Венна
A B A+B
1 1 1
1 0 1
0 1 1
0 0 0
Два высказывания соединены союзом "ИЛИ", то полученное сложное высказывание истинно, когда истинно хотя бы одно из составляющих высказываний. Рассмотренные выше операции были двуместными (бинарными), т.е. выполнялись над двумя операндами (высказываниями).

Инверсия - отрицание

 Инверсия - отрицание:  Отрицание - логическая операция, которая с помощью связки «не» каждому исходному высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.
 В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества, т.е. множеству получившемуся в результате отрицания множества А соответствует множество, дополняющее его до универсального множества.
Таблица истинности Диаграмма Эйлера-Венна
A ¬ A
1 0
0 1
Если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным.

Логическое следование (импликация)

 Высказывание, составленное из двух высказываний при помощи связки "если ..., то ...", называется логическим следованием, импликацией. Обозначается символом –>: запись A –> B означает " из А следует В".
A B A –> B
1 1 1
1 0 0
0 1 1
0 0 1
 Новое высказывание, полученное с помощью импликации, является ложным тогда и только тогда, когда условие (посылка А) - истинно, а следствие (заключение В) - ложно и истинно во всех остальных случаях.
 Пример. Дано сложное высказывание: "Если тело перестаёт двигаться равномерно и прямолинейно, то это результат воздействия на тело двугих тел". Требуется записать его в виде логической формулы. Обозначим через А простое высказывание "тело перестаёт двигаться равномерно", через В - "тело перестаёт двигаться прямолинейно", С - "это результат воздействия на тело двугих тел". Тогда логической формулой этого сложного высказывания будет : A & B –> C.

Эквивалентность (логическое тождество)

 Высказывание, составленное из двух высказываний при помощи связки "тогда и только тогда, когда", называется эквивалентностью, A <–> B (A равносильно B).
A B A<–>B
1 1 1
1 0 0
0 1 0
0 0 1
 Пример. Рассмотрим высказывание "при изменении состояния идеального газа его объём, масса, давление не меняются, значит этот процесс изменения является изотермическим". Введём простейшие высказывания: при изменении состояния идеального газа В этом случае высказывание можно записать в виде формулы m & T & И <–> S.

Построение таблиц истинности и логических функций

 Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений.
 Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой части - соответствующие значения логической функции. При построении таблицы истинности необходимо учитывать порядок выполнения логических операций.
Порядок выполнения логических операций в сложном логическом выражении:
  1. инверсия;
  2. конъюнкция;
  3. дизъюнкция;
  4. импликация;
  5. эквивалентность.
Для изменения указанного порядка выполнения операций используются скобки.
 Алгоритм построения таблиц истинности для сложных выражений:
  1. Определить количество строк (количество строк = 2n + строка для заголовка, n – количество простых высказываний.
  2. Определить количество столбцов (количество столбцов = количество переменных + количество логических операций);
    • Определить количество переменных (простых выражений).
    • Определить количество логических операций и последовательность их выполнения.
  3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
 Пример. Составить таблицу истинности логического выражения: D = ¬ А & (B + C).
 Решение.
  1. Определим количество строк: на входе три простых высказывания: А, В, С поэтому n = 3 и количество строк = 23 + 1 = 9.
  2. Определим количество столбцов:
    • простые выражения (переменные): А, В, С;
    • промежуточные результаты (логические операции):
      ¬ А - инверсия (обозначим через E);
      B + C - операция дизъюнкции (обозначим через F);
      а также искомое окончательное значение арифметического выражения: D = ¬ А & (B + C). т.е. D = E & F - это операция конъюнкции.
  3. Заполним столбцы с учетом таблиц истинности логических операций
A B C E F D
0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 1 1 1
0 1 1 1 1 1
1 0 0 0 0 0
1 0 1 0 1 0
1 1 0 0 1 0
1 1 1 0 1 0

Построение логической функции по ее таблице истинности

 Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции
X Y Z
0 0 1
0 1 0
1 0 1
1 1 0
Составить логическую функцию для заданной таблицы истинности.
  1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
  2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
  3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
  4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.
Решение.
  1. В первой и третьей строках таблицы истинности значение функции равно 1.
  2. Так как строки две, получаем дизъюнкцию двух элементов: X + Y.
  3. Каждый логический элемент в этой дизъюнкции запишим в виде конъюнкции аргументов функции X и Y: (X & Y) + (X & Y).
  4. Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию: Z (X, Y) =(¬ X & ¬ Y) + (X & ¬ Y).

Основы математической логики

  1. Закон двойного отрицания (двойное отрицание исключает отрицание): ¬ (¬ A) = A.
  2. Переместительный (коммутативный) закон:
    • для логического сложения: А + B = B + A;
    • o для логического умножения: A & B = B & A.
    Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.
  3. Сочетательный (ассоциативный) закон:
    • для логического сложения: (А + B) + C = A + (B + C);
    • для логического умножения: (A & B) & C = A & (B & C).
    При одинаковых знаках скобки можно ставить произвольно или вообще опускать.
  4. Распределительный (дистрибутивный) закон:
    • для логического сложения: (А + B) & C = (A & C) + (B & C);
    • для логического умножения: (A & B) + C = (A + C) & (B + C).
    Закон определяет правило выноса общего высказывания за скобку.
  5. Закон общей инверсии (законы де Моргана):
    • для логического сложения: ¬ (A + B) = (¬ A) & (¬ B);
    • для логического умножения: ¬ (A & B) = (¬ A) + (¬ B);
  6. Закон идемпотентности (равносильности):
    • для логического сложения: А + A = A;
    • для логического умножения: A & A = A .
    Закон означает отсутствие показателей степени.
  7. Законы исключения констант:
    • для логического сложения: А + 1 = 1, А + 0 = A;
    • для логического умножения: A & 1 = A, A & 0 = 0.
  8. Закон противоречия: A & (¬ A) = 0.
    9. Невозможно, чтобы противоречащие высказывания были одновременно истинными.
  9. Закон исключения третьего: A + (¬ A) = 1.
    10. Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.
  10. Закон поглощения:
    • для логического сложения: А + (A & B) = A;
    • для логического умножения: A & (A + B) = A.
 Знание законов логики позволяет проверять правильность рассуждений и доказательств. Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.
 Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), другие - основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
 Нарушения законов логики приводят к логическим ошибкам и вытекающим из них противоречиям.

Пример 1 (упрощение формул)

 Упростить формулу (А + В) & (А + С).
 Решение.
  1. Раскроем скобки: (А + В) & (А + С) = A & A + A & C + B & A + B & C;
  2. По закону идемпотентности A & A =A, следовательно,
    3. A & A + A & C + B & A + B & C = A + A & C + B & A + B & C;
  3. В высказываниях А и А & C вынесем за скобки А и используя свойство А + 1 = 1, получим
    4. A + A & C + B & A + B & C = A & (1 + C) + B & A + B & C = A + B & A + B & C;
  4. Аналогично предыдущему пункту вынесем за скобки высказывание А
    5. A + B & A + B & C = A & (1 + B) + B & C = A + B & C.
Таким образом, доказан закон дистрибутивности.
 Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний - все отрицания будут применяться только к простым высказываниям.

Пример 2 (упрощение формул)

Упростить выражения
  1. X = ¬ (A & B ) + (¬ B):
    2. Решение. X = ¬ A + (¬ B)+ (¬ B ) = ¬ A + (¬ B )
  2. Y = ¬ ((¬ B & C )+ C).
    3. Решение. Y = (B + (¬ C) )& (¬ C) = ¬ C
  3. Z = ¬ (¬ A&C)+(B&(¬C))
    4. Z = A+(¬ C) +(B&(¬ C)) = A +( ¬ C)

Вопросы для самопроверки

  1. Составьте таблицы истинности логических выражений:
    • A + (¬ B & C);
    • ¬ (A + B ) & (A & ¬ B);
    • (А + B) + (C & B) .
  2. Составьте логическую функцию F (X, Y, Z) для заданной таблицы истинности:
    3. X Y Z F
    0 0 1 0
    0 1 1 0
    1 0 0 1
  3. Упростите выражение (¬ ( ¬ А) & С) + B & (¬ C)