Справочный материал Тема: Построение и преобразование логических выражений
Учебные материалы


Справочный материал Тема: Построение и преобразование логических выражений



Карта сайтаprostitutkipitera.name
Справочный материал

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


Справочный материал



  • Условные обозначения логических операций:

¬ A, , не A -

отрицание, инверсия,

A  B, А*В, A и B -

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

A  B, А + В, A или B -

логическое сложение, дизъюнкция,

A

B -

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

  • Операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A

B = ¬ A  B

или в других обозначениях

A

B =



  • Если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация».

  • Законы де Моргана :

¬ (A  B) = ¬ A  ¬ B


¬ (A  B) = ¬ A  ¬ B


Пример 1


Укажите, какое логическое выражение равносильно выражению

A  ¬(¬B  C)

.
1)

¬A  ¬B  ¬C

2)

A  ¬B  ¬C

3)

A  B  ¬C

4)

A  ¬B  C


Решение (вариант 1, использование законов де Моргана):



  1. Перепишем заданное выражение и ответы в других обозначениях:
    заданное выражение
    ответы: 1) 2) 3) 4)

  2. Посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана,

а затем используем закон двойного отрицания по которому :

  1. таким образом, правильный ответ – 3 .

Решение (вариант 2, через таблицы истинности):



  1. Перепишем заданное выражение в других обозначениях:
    заданное выражение
    ответы: 1) 2) 3) 4)

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

  3. Здесь 3 переменных, каждая из которых принимает два возможных значения (всего 8 вариантов, которые в таблице истинности записывают по возрастанию двоичных кодов).

  4. Исходное выражение истинно только тогда, когда и , то есть только при . (в таблице истинности одна единица, остальные – нули).

  5. Выражение истинно, если хотя бы одна из переменных равна нулю, то есть, оно будет ложно только при (в таблице истинности один нуль, остальные – единицы).

  6. Аналогично выражение ложно только при , а в остальных случаях – истинно.

  7. Выражение истинно только при , а в остальных случаях – ложно.

  8. Выражение истинно только при , а в остальных случаях – ложно.

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

A

B

C






0

0

0

0

1



1



0

0

0

0

1

0

1



1



0

0

0

1

0

0

1



1



0

0

0

1

1

0

1



0

0

0

1

0

0

0

1



1



0

0

1

0

1

0

1



1



0

1



1

1

0

1



1



1



1



0

1

1

1

0

0

1



0

0


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

  2. Таким образом, правильный ответ – 3 .

Пример 2


^ Укажите, какое логическое выражение равносильно выражению

¬(A  ¬B) ¬(A  B) A  B


1)

¬B  A

2)

A  B  ¬B

3)

A  B  ¬A

4)

¬A


Решение (вариант 1, использование законов де Моргана):



  1. Перепишем заданное выражение в других обозначениях:
    заданное выражение
    ответы: 1) 2) 3) 4)

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


  1. Выносим за скобки в первых двух слагаемых и используем закон исключения третьего :


  1. Наконец, применяем распределительный закон для операции «И» и еще раз закон исключения третьего :


  1. Дальше уже не упрощается…

  2. Теперь замечаем, что такого ответа нет среди предложенных вариантов. Это означает, что ответы тоже можно упростить; упрощаем ответы 2 и 3, применяя распределительный закон и закон исключения третьего

ответы: 2)
3)

  1. Видим, что упрощенное выражение для ответа 3 совпало с упрощенным исходным выражением.

  2. Таким образом, правильный ответ – 3.

Пример 3


Каково наибольшее целое число X, при котором истинно высказывание

(50 < X·X)

(50 > (X+1)·(X+1))


Решение 1:



  1. Это операция импликации между двумя отношениями и

  2. Попробуем сначала решить неравенства

,

  1. Обозначим эти области на оси X:

на рисунке фиолетовые зоны обозначают область, где истинно выражение , голубая зона – это область, где истинно

  1. Вспомним таблицу истинности операции «импликация»:

    A

    B

    A → B

    0

    0

    1

    0

    1

    1

    1

    0

    0

    1

    1

    1

  2. Согласно таблице, заданное выражение истинно везде, кроме областей, где и ; область истинности выделена зеленым цветом.

  3. Поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее , то есть, 7

  4. Таким образом, верный ответ – 7 .

Решение (вариант 2, преобразование выражения):



  1. Сначала можно преобразовать импликацию, выразив ее через «ИЛИ» и «НЕ»:


  1. Это значит, что выражение истинно там, где или

  2. Дальнейшие действия точно такие же, как и в варианте 1.

Пример 4.


Сколько различных решений имеет уравнение

((K  L)

(L  M  N)) = 0


где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение:



  1. Перепишем уравнение, используя более простые обозначения операций:

((K + L)

(L · M · N)) = 0



  1. Из таблицы истинности операции «импликация» следует, что это равенство верно тогда и только тогда, когда одновременно

K + L = 1

и

L · M · N = 0



  1. Из первого уравнения следует, что хотя бы одна из переменных, K или L, равна 1 (или обе вместе); поэтому рассмотрим три случая.

  2. Если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем

    4

    разных решения.

  3. Если K = 1 и L = 1, то второе равенство выполняется при М

    ·

    N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще

    3

    решения.

  4. Если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М

    ·

    N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще

    3

    решения .

  5. Таким образом, всего получаем 4 + 3 + 3 = 10 решений.

Пример 5


Укажите значения переменных К, L, M, N, при которых логическое выражение

(¬(М  L)  К)

(¬К  ¬М)  N)


ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.

Решение:



  1. Запишем уравнение, используя более простые обозначения операций (условие «выражение ложно» означает, что оно равно логическому нулю):


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

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

и



  1. Первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда

    и

    ;

    отсюда следует

    (логическая сумма равна нулю), что может быть только при

    ; таким образом, три переменных мы уже определили.

  2. Из второго условия, , при и получаем

    .



  3. Таким образом, правильный ответ – 1000.

Пример 6


A, B и С – целые числа, для которых истинно высказывание

¬(А = B)  ((A > B)

(B > C))  ((B > A)

(С > B))


Чему равно В, если A = 45 и C = 43?.

Решение:



  1. Обратим внимание, что это сложное высказывание состоит из трех простых

¬(А = B)


(A > B)

(B > C)


(B > A)

(С > B)



  1. Эти простые высказывания связаны операцией

    (И, конъюнкция), то есть, они должны выполняться одновременно.

  2. Из

    ¬(А = B)=1

    сразу следует, что

    А  B



  3. Предположим, что

    A > B

    , тогда из второго условия получаем

    1

    (B > C)=1

    ; это выражение может быть истинно тогда и только тогда, когда

    B > C = 1



  4. Поэтому имеем

    A > B > C

    , этому условию соответствует только число 44.

  5. На всякий случай проверим и вариант

    A < B

    , тогда из второго условия получаем 0 →

    (B > C)=1

    ; это выражение истинно при любом

    B

    .

  6. Теперь смотрим третье условие: получаем

    1

    (С > B)=1

    ; это выражение может быть истинно тогда и только тогда, когда

    C > B

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

    C > B > A.



  7. Таким образом, правильный ответ – 44.



edu 2018 год. Все права принадлежат их авторам! Главная