Анализ таблиц истинности логических выражений. Задание 2

1.

ЗАДАНИЕ 2.
Анализ таблиц истинности
логических выражений.
Уровень: БАЗОВЫЙ
Максимальный балл: 1
Примерное время на выполнение: 3мин

2.

Важно знать:
Обозначения логических операций:
a) отрицание (инверсия, логическое НЕ) : ¬ (например, ¬А);
b) конъюнкция (логическое умножение, логическое И): /\, &
(например, А /\ В либо А & В);
c) дизъюнкция (логическое сложение, логическое ИЛИ): \/, |
(например, А \/ В либо А | В);
d) следование (импликация): → (например, А → В);
e) тождество: ≡ (например, A ≡ B).
f) символ 1 используется для обозначения истины
(истинного высказывания); символ 0 – для обозначения
лжи (ложного высказывания).

3.

Таблицы истинности логических
операций
a b a b a b a b
a
b
a
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
0
1
0
0
1
1
0
1
1
1
1

4.

Из таблицы видим:
• логическая сумма A + B + C + … равна 0 (выражение
ложно) тогда и только тогда, когда все слагаемые
одновременно равны нулю, а в остальных случаях
равна 1 (выражение истинно)
• логическое произведение A · B · C · … равно 1
(выражение истинно) тогда и только тогда, когда все
сомножители одновременно равны единице, а в
остальных случаях равно 0 (выражение ложно)
• логическое следование (импликация) А→В равна 0
тогда и только тогда, когда A (посылка) истинна, а B
(следствие) ложно
• эквивалентность А B равна 1 тогда и только тогда,
когда оба значения одновременно равны 0 или
одновременно равны 1

5.

Основные формулы алгебры логики
Закон де Моргана
a b a b
a b a b
Импликация
a b a b
a b a b
Эквивалентность (тождественность)
a b ( a b) ( a b)
a b a b a b
a b a b a b
a b (a b) (b a )

6.

Важно знать:
• если в выражении нет скобок, сначала выполняются
все операции «НЕ», затем – «И», затем – «ИЛИ»,
«импликация»,
и
самая
последняя
–
«эквивалентность»
• таблица истинности выражения определяет его
значения при всех возможных комбинациях исходных
данных
• если известна только часть таблицы истинности,
соответствующее логическое выражение однозначно
определить нельзя, поскольку частичной таблице
могут соответствовать несколько разных логических
выражений (не совпадающих для других вариантов
входных данных);

7.

Важно знать:
• количество
разных логических выражений,
удовлетворяющих полной таблице истинности,
равно
2n, где n – число переменных в
выражении;
например,
полная
таблица
истинности выражения с пятью переменными
содержит 25=32 строчки.

8.

Важно знать:
• количество
разных логических выражений,
удовлетворяющих
неполной
таблице
истинности, равно
2k, где k – число
отсутствующих строк; например, полная
таблица истинности выражения с тремя
переменными содержит 23=8 строчек, если
заданы только 6 из них, то можно найти
28-6=22=4 разных логических выражения,
удовлетворяющие этим 6 строчкам (но
отличающиеся в двух оставшихся)

9.

10.

Решение с помощью MS Exel
• заполняем первую часть таблицы, перечисляя все
комбинации переменных в порядке возрастания двоичного
кода:
Удобно использовать для
заполнения
правило половин:
1ст – 50/50
2ст – 25/25/25/25
и тд, до 1/1/….
!!!Все переборы начинаются с «0»

11.

• для каждой строчки определяем выражения,
входящие в логическое произведение, а затем –
значение функции:
¬ = НЕ(_)
˅ = ИЛИ(_)
˄ = И(_)
→ = ИЛИ(НЕ(А);В)
≡ = ↔ =СОВПАД(_;_)
СОВПАД(_) - строковая
функция (совпадение по
всем символам)

12.

• сортируем строки таблицы по столбцу H по убываниию
• удаляем строки, где функция равна 0; можно также
скрыть вспомогательные столбцы E, F, G
• дальше рассуждаем, сравнивая столбцы и строки
таблицы из задания и получившейся
Ответ: zyxw.

13.

Python
∧
конъюнкция
and
(для языков, где логическое значение True
воспринимается как 1, а False – как 0, можно
использовать обычное умножение *)
∨
дизъюнкция
or
¬
отрицания
not()
≡
тождество
==
⊕
строгая дизъюнкция !=
→
импликация –выполняем преобразование:
not(a)or b, not a or b или a <= b
В Python if F: #
тоже самое, что
"if F == True:"

14.

Решение с помощью программы (Python) перебор
print('x y z w')
for x in 0, 1:
for y in 0, 1:
for z in 0, 1:
for w in 0, 1:
F = (x or y) and not(y == z)\\
and not(w)
if F:
print(x, y, z, w)
после запуска программы получаем все интересующие нас строки:
x y z w
0 1 0 0
1 0 1 0
1 1 0 0

15.

16.

заполнение исходной ТИ и анализ
полной таблицы истинности для F = 1
• в выражении 4 логических переменных,
тогда всех решений будет 16 (24).
• подставим набор значений логических
переменных и удалим все решения,
которые не дают в ответе F = 1:
x
0
0
1
1
1
1
1
y
0
1
0
0
1
1
1
w
0
0
0
1
0
1
1
z
0
0
1
1
1
0
1
x
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
y
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
w
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

17.

• Получаем 7 решений. Анализируя
ТИ исходной функции видим, что
набора 0 0 0 0 и 1 1 1 1 нет. Уберем
их из ТИ решений.
• В ТИ решений только одна строка
имеет три нуля, тогда сравнивая с
ТИ исходной функции видим, что 1
соответствует Y.
?
0
0
?
0
1
?
0
0
?
1
0
1
F
1
1
1
?
0
0
Y
0
1
x
0
1
1
1
1
y
1
0
0
1
1
w
0
0
1
0
1
?
0
0
?
1
0
1
F
1
1
1
z
0
1
1
1
0

18.

• ДОЗАПОЛНИМ таблицу истинности
исходной функции (желтая заливка)
на основе анализа ТИ решений, а
именно т.к больше строк с тремя
«0» нет, то в первой строке в пустой
ячейке будет «1». И раз нет больше
строк с двумя «0», то в третьей
строке пустые ячейки равны «1».
1ю
строку
выше
приведенной таблице и ТИ решений
видим, что строка с двумя «0» всего
одна, из которых один нуль
известен - это Y, тогда второй это –
W;
• Ответ: zywx
?
1
0
0
Y
0
1
1
?
0
0
1
?
1
0
1
F
1
1
1
?
1
0
0
Y
0
1
1
W
0
0
1
?
1
0
1
F
1
1
1
• Анализируя

19.

print ('x y w z') # заголовок таблицы (в алфавитном
порядке)
k = 0, 1
# k - кортеж констант (0 - False, 1 - True)
for x in k:
for y in k:
for w in k:
for z in k:
if (x and not y or (not w or z)) == (z == x):
# или:
# if (x and not y or (w <= z)) == (z == x):
print(x, y, w, z) # если F = 1

20.

Демо 2022
Миша заполнял таблицу истинности логической функции F
¬(y → (x ≡ w))˄(z → x),
но успел заполнить лишь фрагмент из трёх различных её
строк, даже не указав, какому столбцу таблицы
соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует
каждая из переменных w, x, y, z.
Ответ: wxyz