Погода
Календарь
Январь 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123456
78910111213
14151617181920
21222324252627
28293031  
Страницы сайта

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

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

  • Для выполнения задания рекомендуется повторить следующие темы:
    Преобразование логических операций:
  • операцию импликация можно преобразовать в операции ИЛИ и НЕ:
    A → B = ¬ A ∨ B
    или
    A → B = A + B
  • операцию эквивалентность можно преобразовать:
    A ↔ B = A ⊕ B = A ∧ B ∨ A ∧ B
    или
    A ↔ B = A ⊕ B = A · B + A · B
  • операцию XOR (сложение по модулю 2) можно преобразовать так:
    A ⊕ B = (¬A ∧ B) ∨ (A ∧ ¬B)
    или
    A ⊕ B = (A · B) + (A · B)
    Законы алгебры логики:
  • кроме того, могут пригодиться формулы:
  • Закон двойного отрицания:
    ¬¬ A = A
  • Закон исключения третьего:
    A ∧ ¬ A = 0 или A · A = 0
    A ∨ ¬ A = 1 или A + A = 1
  • Закон повторения (идемпотентности):
    A ∧ A = A или A · A = A
    A ∨ A = A или A + A = A
  • Законы исключения логических констант:
    A ∧ 0 = 0
    A ∧ 1 = A
    A ∨ 0 = A
    A ∨ 1 = 1
  • Переместительный (коммутативный) закон:
    A ∧ B = B ∧ A
    A ∨ B = B ∨ A
  • Сочетательный (ассоциативный) закон:
    (A ∧ B) ∧ C = A ∧ (B ∧ C)
    (A ∨ B) ∨ С = A ∨ (B ∨ С)
  • Распределительный (дистрибутивный) закон:
    (A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C)
    (A ∨ B) ∧ С = (A ∧ С) ∨ (B ∧ С)
    и наоборот:
    (A ∨ B) ∧ (A ∨ C) = A ∨ (B ∧ C)
    (A ∧ B) ∨ (A ∧ C) = A ∧ (B ∨ C)
  • Закон общей инверсии (Законы де Моргана):
    ¬ (A ∧ B) = ¬ A ∨ ¬ B
    ¬ (A ∨ B) = ¬ A ∧ ¬ B
    упрощать выражения можно с помощью формул: Закон поглощения:
    A ∨ A ∧ B = A
    A ∧ (A ∨ B) = A
    A ∨ ¬A ∧ B = A ∨ B
  • Порядок выполнения логических операций:
    1. выражения в скобках,
    2. операции «НЕ»,
    3. операции «И»,
    4. операции «ИЛИ»,
    5. операции «импликация»
    6. операции «эквиваленция»
  • последовательность из операций импликации выполняется слева направо (при этом соблюдается принцип «операции с одинаковым приоритетом выполняются слева направо»):
    A → B → C → D = ((A → B) → C) → D

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ МНОЖЕСТВ

  • пересечение множеств соответствует логическому умножению, а объединение – логическому сложению;
  • пересечением двух множеств называется новое множество, состоящее из элементов, принадлежащих одновременно обеим множествам:

Пример:

объединением двух множеств называется новое множество, состоящее из элементов, принадлежащих отдельно каждому из множеств (без повторений);

Пример

  • пустое множество  – это множество, в котором не содержится ни одного элемента; пустому множеству в теории множеств соответствует 0;
  • универсальное множество U (на кругах Эйлера обозначается в виде прямоугольника) – это множество, содержащее все возможные элементы определенного типа (например, все вещественные числа):


универсальное множество
  • универсальное множество соответствует логической единице: для любого множества целых чисел Xсправедливы равенства:
    X ∨ U = U и X ∧ U = X
    разностью двух множеств A и B называется новое множество, элементы которого принадлежат A, но не принадлежат B:
разность двух множеств

Пример разности множеств:

пример разности множеств
  • дополнение множества X – это разность между универсальным множеством U и множеством X(например, для целых чисел ¬ X – все целые числа, не входящие в X)
  • пусть требуется выбрать множество A так, чтобы выполнялось равенство A ∨ X = I; в этом случае множество A должно включать дополнение ¬ X, то есть A ≥¬ X (или A ⊇¬ X), то есть Amin = ¬ X
  • пусть требуется выбрать множество A так, чтобы выполнялось равенство ¬ A ∨ X = I, в этом случае множество ¬ A должно включать дополнение ¬ X, то есть ¬ A ⊇ ¬ X; отсюда A ⊆ X, то есть Amax = X

ЗАДАНИЯ С ОТРЕЗКАМИ И ДЕЛ

Для решения заданий необходимо знать рассмотренную тему о множествах.

Для упрощения решений можно пользоваться следующими законами.

1. Если в задании формула тождественно истинна (равна 1), и
2. после упрощения A  без отрицания
то используется закон:
Amin = ¬B
где B — известная часть выражения.

1. Если в задании формула тождественно истинна (равна 1), и
2. после упрощения A с отрицанием
то используется закон:
Amax = B
где B — известная часть выражения.

1. Если в задании формула тождественно ложна (равна 0), и
2. после упрощения A без отрицания
то используется закон:
Amin = B
где B — известная часть выражения.

Top