Про обозначения 4 страница

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

((K + L)→(L · M · N)) = 0

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

K + L = 1иL · M · N = 0

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

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

5) если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3решения

6) если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3решения

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

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

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

((K + L)→(L · M · N)) = 0

2) построим таблицу для логического выражения

X = ((K + L)→(L · M · N))

и подсчитаем, сколько в ней нулей, это и будет ответ

3) наше выражение зависит от четырех переменных, поэтому в таблице будет 2⁴ = 16 строчек (16 возможных комбинация четырех логических значений)

4) подставляем различные комбинации в формулу для X; несмотря на большое количество вариантов, таблица строится легко: достаточно вспомнить, что выражение K + L ложно только при K = L = 0, а выражение L·M·N истинно только при L = M = N = 1.

5) в последнем столбце 10 нулей; это значит, что есть 10 разных комбинаций, при которых выражение X равно нулю, то есть исходное уравнение имеет 10 решений

6) таким образом, всего 10 решений.

Еще пример задания:

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

((М Ú L) Ù К)→(К Ù М Ú N)

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

Решение (вариант 1, анализ исходного выражения):

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

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

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

и

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

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

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

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

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

2) заменим импликацию по формуле :

3) раскроем инверсию сложного выражения по формуле де Моргана :

4) упростим выражение :

5) мы получили уравнение вида «сумма = 0», в нем все слагаемые должны быть равны нулю

6) поэтому сразу находим

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

Еще пример задания:

Составьте таблицу истинности для логической функции

X = (А ↔ B) Ú (A→(B Ú C))

в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В – числа 77, столбец значений аргумента С – числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функции X в десятичную систему счисления.

Решение (вариант 1):

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

2) это выражение с тремя переменными, поэтому в таблице истинности будет 2³=8 строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр

3) переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел

27 = 00011011₂ 77 = 01001101₂ 120 = 01111000₂

4) теперь можно составить таблицу истинности (см. рисунок справа), в которой строки переставлены в сравнении с традиционным порядком[1]; зеленым фоном выделена двоичная записи числа 27 (биты записываются сверху вниз), синим – запись числа 77 и розовым – запись числа 120:

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

6) заполняем столбцы таблицы:

А	В	С					X

значение равно 1 только в тех строчках, где А = В

значение равно 1 только в тех строчках, где В = 1 или С = 1

значение равно 0 только в тех строчках, где А = 1 и В + С = 0

значение – этоинверсия предыдущего столбца (0 заменяется на 1, а 1 – на 0)

результат Х (последний столбец) – это логическая сумма двух столбцов, выделенных фиолетовым фоном

7) чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 10101011₂

8) переводим это число в десятичную систему: 10101011₂ = 2⁷ + 2⁵ + 2³ + 2¹ + 2⁰ = 171

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

Решение (вариант 2, преобразование логической функции):

1) выполним пп. 1-5 так же, как и в предыдущем способе

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

3) раскроем импликацию через операции И, ИЛИ и НЕ ( ):

4) раскроем инверсию для выражения по формуле де Моргана:

5) таким образом, выражение приобретает вид

6) отсюда сразу видно, что Х = 1 только тогда, когда А = В или (А = 1 и В = С = 0):

7) чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 10101011₂

8) переводим это число в десятичную систему: 10101011₂ = 2⁷ + 2⁵ + 2³ + 2¹ + 2⁰ = 171

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

Еще пример задания:

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

(А = B) Ù ((A > B)→(B > C)) Ù ((B > A)→(С > B))

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

Решение (вариант 1):

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

(А = B)

(A > B)→(B > C)

(B > A)→(С > B)

2) эти простые высказывания связаны операцией Ù (И, конъюнкция), то есть, они должны выполняться одновременно

3) из (А = B)=1сразу следует, что А ¹ B

4) предположим, что A > B, тогда из второго условия получаем 1→(B > C)=1; это выражение может быть истинно тогда и только тогда, когда B > C = 1

5) поэтому имеем A > B > C, этому условию соответствует только число 44

6) на всякий случай проверим и вариант A < B, тогда из второго условия получаем
0 →(B > C)=1; это выражение истинно при любом B;
теперь смотрим третье условие: получаем 1→(С > B)=1; это выражение может быть истинно тогда и только тогда, когда C > B, и тут мы получили противоречие, потому что нет такого числа B, для которого C > B > A

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

Решение (вариант 2, интуитивный):

1) заметим, что между A и C расположено единственное число 44, поэтому можно предполагать, что именно это и есть ответ

2) проверим догадку, подставив в заданное выражение A = 45, B = 44 и C = 43

(45 = 44) Ù ((45 > 44)→(44 > 43)) Ù ((44 > 45)→(43 > 44))

3) заменим истинные условия на 1, а ложные – на 0:

(0) Ù (1→1) Ù (0→0)

4) вычисляем по таблице результаты операций (НЕ, отрицание) и → (импликация):