·таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция»
·операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
A→B= ¬AÚB
·операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:
A↔B= ¬AÙ¬ BÚAÙB
·если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
·логическое произведениеA∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
·логическая суммаA+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
·правила преобразования логических выражений
Пример задания:
Каково наибольшее целое число X, при котором истинно высказывание
(50 < X·X) → (50 > (X+1)·(X+1))
Решение (вариант 1):
1)это операция импликации между двумя отношениями A=(50<X2) и B=(50>(X+1)2)
2)попробуем сначала решить неравенствf
3)вспомним таблицу истинности операции «импликация»:
A
B
A→B
0
0
1
0
1
1
1
0
0
1
1
1
4)согласно таблице, заданное выражение истинно везде, кроме областей, где A=1 и B=0
5)поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее 7.1 , то есть, 7
6)таким образом, верный ответ – 7 .
Решение (вариант 2, преобразование выражения):
1)сначала можно преобразовать импликацию, выразив ее через «ИЛИ» и «НЕ»:A→B = не A + B
2)это значит, что выражение истинно там, где A=0 или B=1
3)дальнейшие действия точно такие же, как и в варианте 1.
Еще пример задания:
Сколько различных решений имеет уравнение
((KÚL) → (LÙMÙN)) = 0
где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.
Решение (вариант 1):
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 решений.
Еще пример задания:
Укажите значения переменных К, L, M, N, при которых логическое выражение
(¬(МÚL)ÙК) → (¬КÙ¬М)ÚN)
ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.
Решение (анализ исходного выражения):
1)запишем уравнение, используя более простые обозначения операций (условие «выражение ложно» означает, что оно равно логическому нулю):
(не(M + L) . K)→(не K . не M + N) = 0
2)из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных
3)из таблицы истинности операции «импликация» (см. первую задачу) следует, что это выражение ложно тогда и только тогда, когда одновременно
(не(M + L) . K) = 1и(не K . не M + N) = 0
4)первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда K=1и не(M +L)=1 ; отсюда следует M + L=0 (логическая сумма равна нулю), что может быть только при M = L = 0 ; таким образом, три переменных мы уже определили
5)из второго условия,(не K . не M + N) = 0 , при K=1и M=1 получаем N=0
6)таким образом, правильный ответ – 1000.
Еще пример задания:
Составьте таблицу истинности для логической функции
X= (А ↔ B)Ú¬(A→ (BÚC))
в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В – числа 77, столбец значений аргумента С – числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функцииXв десятичную систему счисления.
Решение (вариант 1):
1)запишем уравнение, используя более простые обозначения операций:
X = (A↔ B) + не(A→ (B + C))
2)это выражение с тремя переменными, поэтому в таблице истинности будет 23=8 строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр
А
В
С
X
0
0
0
0
1
1
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
1
1
0
3)переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел
27 =000110112 77 = 010011012 120 = 011110002
4)теперь можно составить таблицу истинности (см. рисунок справа), в которой строки переставлены в сравнении с традиционным порядком; зеленым фоном выделена двоичная записи числа 27 (биты записываются сверху вниз), синим – запись числа 77 и розовым – запись числа 120:
5)вряд ли вы сможете сразу написать значения функции Х для каждой комбинации, поэтому удобно добавить в таблицу дополнительные столбцы для расчета промежуточных результатов (см. таблицу ниже)
6)заполняем столбцы таблицы:
А
В
С
A↔ B
B + C
A→(B + C)
не(A→(B + C))
X
0
0
0
1
0
1
0
1
0
1
1
0
1
1
0
0
0
0
1
1
1
1
0
1
1
0
1
0
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
0
1
0
0
0
0
0
1
1
1
1
0
1
1
1
0
1
значениеA↔ Bравно 1 только в тех строчках, где А = В
значение B+Cравно 1 только в тех строчках, где В = 1 или С = 1
значение A→(B + C)равно 0 только в тех строчках, где А = 1 и В + С = 0
значение не(A→(B + C))–это инверсия предыдущего столбца (0 заменяется на 1, а 1 – на 0)
результат Х (последний столбец) – это логическая сумма двух столбцов, выделенных фиолетовым фоном
7)чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 101010112
8)переводим это число в десятичную систему: 101010112 = 27 + 25 + 23 + 21 + 20 = 171
9)таким образом, правильный ответ – 171.
(Проверьте, что обычно (когда комбинации располагаются по возрастанию соответствующих двоичных чисел), столбец значений аргумента А представляет собой двоичную запись числа 15 = 11112, столбец значений аргумента В – числа 51 = 1100112, столбец значений аргумента С – числа 85 = 101010102.)
Решение (вариант 2, преобразование логической функции):
1)выполним пп. 1-5 так же, как и в предыдущем способе
2)запишем уравнение, используя более простые обозначения операций:X= (А ↔ B)Ú¬(A→ (BÚC))
3)раскроем импликацию через операции И, ИЛИ и НЕ ( А ↔ B = неA + B):A→ (BÚC) = неA + B + C
4)раскроем инверсию для выраженияA→ (BÚC) = неA + B + Cпо формуле де Моргана:
не(A→ (BÚC)) = не(неA + B + C) = A . неB . неC
5)таким образом, выражение приобретает вид X =(А ↔ B) + A . неB . неC
6)отсюда сразу видно, что Х = 1 только тогда, когда А = В или (А = 1 и В = С = 0):
А
В
С
X
Примечание
0
0
0
1
А = В
0
1
1
0
0
0
1
1
А = В
1
0
1
0
1
1
1
1
А = В
0
1
0
0
1
0
0
1
А = 1, В = С = 0
1
1
0
1
А = В
7)чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 101010112
8)переводим это число в десятичную систему: 101010112 = 27 + 25 + 23 + 21 + 20 = 171
9)таким образом, правильный ответ – 171.
Задачи для тренировки:
1)Каково наибольшее целое число X, при котором истинно высказывание
(90 < X·X)→ (X < (X-1))
2)Сколько различных решений имеет уравнение
(KÙLÙM)Ú(¬LÙ¬MÙN) = 1
где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.
3)Укажите значения переменных K, L, M, N, при которых логическое выражение
(¬KÚM)→ (¬LÚMÚN)
ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.
4)Каково наименьшее целое положительное числоX, при котором высказывание:
(4 > -(4 +X)·X))→ (30 >X·X)
будет ложным.
5)Каково наибольшее целое положительное числоX, при котором истинно высказывание:
((X- 1) <X)→ (40 >X·X)
6)Укажите значения переменных K, L, M, N, при которых логическое выражение
(¬(MÚL)ÙK)→ ((¬KÙ¬M)ÚN)
ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.
7)Каково наименьшее натуральное числоX, при котором высказывание
¬(X·X< 9)→ (X>(X+ 2))
будет ложным?
8)Укажите значения логических переменных Р, Q, S, Т, при которых логическое выражение
(РÚ¬Q)Ú(Q→ (SÚТ))
ложно. Ответ запишите в виде строки из четырех символов: значений переменных Р, Q, S, T (в указанном порядке).
9)Каково наибольшее целое положительное числоX, при котором высказывание:
((X+ 6)·X+ 9 > 0)→ (X·X> 20)
будет ложным?
10)Составьте таблицу истинности для логической функции
X= (А→ B)Ù(C↔ ¬(BÚA))
в которой столбец значений аргумента А представляет собой двоичную запись числа 226, столбец значений аргумента В – числа 154, столбец значений аргумента С – числа 75. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функцииXв десятичную систему счисления.
11)Составьте таблицу истинности для логической функции
X= ¬(А→ B)Ù(B↔ ¬(C→ A))
в которой столбец значений аргумента А представляет собой двоичную запись числа 216, столбец значений аргумента В – числа 30, столбец значений аргумента С – числа 170. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функцииXв десятичную систему счисления.
