Решение (построение таблицы с помощью электронных таблиц, П.Е. Финкель, г. Тимашевск)
Базовый уровень, время – 3 мин)
Тема: Анализ таблиц истинности логических выражений.
Что проверяется:
Умение строить таблицы истинности и логические схемы.
1.5.1. Высказывания, логические операции, кванторы, истинность высказывания
1.1.6. Умение строить модели объектов, систем и процессов в виде таблицы истинности для логического высказывания
Про обозначения
К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (Ù,Ú, ), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает Ù и Ú. Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (Ù,Ú, ), что еще раз подчеркивает проблему.
Что нужно знать:
· условные обозначения логических операций
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) = A Ù B
· если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», «импликация», и самая последняя – «эквивалентность»
· таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных
· если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);
· количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти 28-6=22=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)
· логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
· логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)
|
|
· логическое следование (импликация) А→В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно
· эквивалентность АºB равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1
Пример задания:
Р-22 (демо-2021). Логическая функция F задаётся выражением
(x Ú y) Ù (y º z) Ù w.
На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
? | ? | ? | ? | F |
1 | 1 | 1 | ||
0 | 1 | 0 | 1 | |
1 | 1 | 0 | 1 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение (построение таблицы истинности для F = 1):
1) перепишем выражения в виде
2) поскольку имеем логическое произведение значение w обязательно должно быть равно 0, то есть, в столбце w таблицы должны быть все нули; это возможно только в последнем столбце:
|
|
? | ? | ? | w | F |
1 | 1 | 0 | 1 | |
0 | 1 | 0 | 1 | |
1 | 1 | 0 | 1 |
3) теперь определим все комбинации переменных, для которых функция равна 1 (их не должно быть много!)
4) чаще всего в выражении встречается переменная y, поэтому мы сначала примем y = 0, а затем – y = 1.
5) при y = 0 (и w = 0) получаем , что справедливо только при x = 1и z = 1:
x | y | z | w | F |
1 | 0 | 1 | 0 | 1 |
6) при y = 1 (и w = 0) получаем , что справедливо при z = 0 и любом x, это даёт ещё два варианта:
x | y | z | w | F |
0 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
7) объединим три полученных строки:
x | y | z | w | F |
1 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
8) видим, что в столбце z должна быть одна единица и два нуля, это возможено только в первой строке исходной таблицы:
z | ? | ? | w | F |
1 | 1 | 0 | 1 | |
0 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 |
9) при z = 1нужно, чтобы y = 0, поэтому второй столбец – это y, а третий – x:
z | y | x | w | F |
1 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 |
10) Ответ: zyxw.
Решение (построение таблицы с помощью электронных таблиц, П.Е. Финкель, г. Тимашевск)
1) поскольку во время компьютерного экзамена есть возможность использовать электронные таблицы, можно построить таблицу истинности с их помощью
|
|
2) заполняем первую часть таблицы, перечисляя все комбинации переменных в порядке возрастания двоичного кода:
3) для каждой строчки определяем выражения, входящие в логическое произведение, а затем – значение функции:
4) сортируем строки таблицы по столбцу H по убываниию:
5) удаляем строки, где функция равна 0; можно также скрыть вспомогательные столбцы E, F, G:
6) дальше рассуждаем так же, как и при теоретическом решении
7) Ответ: zyxw.
Решение (построение таблицы с помощью программы, А.С. Гусев, г. Москва, https://youtu.be/RRL1Wal9ImU):
1) поскольку во время компьютерного экзамена есть возможность использовать среды программирования, для построения частичной таблицы истинности (всех строк, при которых F=1) можно написать переборную программу на Python
2) перебор выполняем во вложенном цикле:
for x in 0, 1:
for y in 0, 1:
for z in 0, 1:
for w in 0, 1:
Вычисление функции F
# вывод ( x , y , z , w ), если F =1
3) для вычисления значения функции необходимо понимать, как логические операторы записываются на языке программирования; в Python их можно реализовать следующим образом:
∧ конъюнкция and
∨ дизъюнкция or
отрицания not()
≡ тождество ==
⊕ строгая дизъюнкция !=
→ импликация – для импликации в python оператора нет, но импликацию можно преобразовать в дизъюнкцию; например, a → b можно записать как a ∨ b, а это в свою очередь записать как not(a)or b
4) Запишем нашу функцию на языке программирования:
F = (x or y) and not(y == z) and not(w)
5) чтобы выводить не полную таблицу истинности, а только те строки, в которых функция равна 1, добавим условие вывода:
if F : # то же самое, что " if F == True:"
Print(x, y, z, w)
6) Приведём полную программу:
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)
7) после запуска программы получаем все интересующие нас строки:
X y z w
0 1 0 0
1 0 1 0
1 1 0 0
8) дальше рассуждаем так же, как и в приведённом выше теоретичеком решении
9) Ответ: zyxw.
Решение (прямой перебор, А. Богданов):
1) в принципе, можно написать программу, которая сразу выдает решение этого задания прямым перебором вариантов
2) Часть 1: https://www.youtube.com/watch?v=yX5oSYtM5E0
3) Часть 2: https://www.youtube.com/watch?v=eSkrt4KrsmU
4) Ответ: zyxw.
Ещё пример задания:
Р-21. Логическая функция F задаётся выражением
((x Ù y) Ú (w ® z)) º (z º x).
На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
? | ? | ? | ? | F |
0 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение (построение таблицы истинности для F = 1):
1) перепишем выражение, раскрыв импликацию по формуле :
2) сначала предположим, что ; в этом случае получаем
3) так как , получим ; при этом значение y может быть любым (1 или 0)
4) теперь пусть , тогда получаем
5) используем распределительный закон: , так что
, откуда сразу следует и – единственный вариант!
6) этот единственный вариант, для которого , ОБЯЗАТЕЛЬНО должен быть в приведённой таблице, потому что иначе мы не сможем различить столбцы z и x; это может быть только последняя строчка, куда нужно добавить две единицы:
z | ? | ? | ? | F |
0 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
7) в остальных строчках должно вполняться равенство , значит x – точно не второй столбец (не подходит вторая строка)
8) предположим, что x – третий столбец, и в свободной ячейке – нуль:
z | ? | x | ? | F |
0 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
9) при этом для остальных двух столбцов в этих строчках должно выполняться условие , а оно не может выполняться – при любом варианте в одной строке сумма равна 0; значит x – последний столбец, и в первой строке z = 1:
z | ? | ? | x | F |
1 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
10) чтобы разобраться с поcледними двумя столбцами снова вспомним, что при должно выполняться условие ; это возможно только тогда, когда второй столбец – это y, а третий - w
11) Ответ: zywx
Решение (А.Н. Носкин, заполнение исходной ТИ и анализ полной таблицы истинности для F = 1):
1) в выражении 4 логических переменных, тогда всех решений будет 16 (24).
x | y | w | z |
0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 |
2) подставим набор значений логических переменных и удалим все решения, которые не дают в ответе F = 1
x | y | w | z |
0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 |
Получаем 7 решений. Анализируя ТИ исходной функции видим, что набора 0 0 0 0 и 1 1 1 1 нет. Уберем их из ТИ решений.
x | y | w | z |
0 | 1 | 0 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
3) В ТИ решений только одна строка имеет три нуля, тогда сравнивая с ТИ исходной функции видим, что 1 соответствует Y.
? | Y | ? | ? | F |
0 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 |
4) ДОЗАПОЛНИМ таблицу истинности исходной функции (желтая заливка) на основе анализа ТИ решений, а именно т.к больше строк с тремя «0» нет, то в первой строке в пустой ячейке будет «1». И раз нет больше строк с двумя «0», то в третьей строке пустые ячейки равны «1».
? | Y | ? | ? | F |
1 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
5) Анализируя 1ю строку выше приведенной таблице и ТИ решений видим, что строка с двумя «0» всего одна, из которых один нуль известен - это Y, тогда второй это – W;
? | Y | W | ? | F |
1 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
6) Далее рассуждая видим, что в ТИ решений (кроме столбца Y) один «0» имеет – Х, тогда последний столбец – это Х, а первый столбец – Z.
7) Ответ: zywx
Ещё пример задания:
Р-20. Логическая функция F задаётся выражением
((x Ù y) Ú (y Ù z)) º ((x ® w) Ù (w ® z)).
На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
? | ? | ? | ? | F |
0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | |
0 | 1 | 0 | 1 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение (построение таблицы истинности для F = 1):
1) запишем выражение в более понятной форме:
2) попробуем найти все сочетания переменных, при которых функция равна 1 (их должно быть не очень много)
3) при x = 0 получаем ; импликация с нулём в левой части всегда истинна (из лжи следует всё, что угодно), поэтому
4) пусть теперь ещё z = 0, тогда , что истинно при w = 1 и при любом y;
5) пусть теперь x = 0 и z = 1, тогда , что истинно при y = 1 и при любом w;
6) из 4 и 5 получаем такие строки в таблице истинности исходной функции:
x | y | z | w | F |
0 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
7) остаётся рассмотреть случай, когда x = 1, при этом
8) учитываем, что и ; получаем
9) преобразуем импликацию , так что
10) для y = 0 это выражение истинно при (w, z) = (0,0), (0,1) и (1,0), а для y = 1 – только при w = z = 1, это даёт ещё 4 строки в таблице истинности
x | y | z | w | F |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
11) итак, у нас есть 8 строк в таблице истинности, где функция равна 1:
x | y | z | w | F |
0 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
попробуем сопоставить их с заданными в условии строками:
? | ? | ? | ? | F |
0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | |
0 | 1 | 0 | 1 |
12) замечаем, что есть одна характерная строка с тремя единицами; кроме того, поскольку все строки различны, в одной из пустых ячеек должен стоять 0, а во второй – 1
13) в полученной нами таблице видим единственную строку с тремя единицами, что сразу позволяет определить, что первый столбец – это x, который всегда равен 0:
x | y | z | w | F |
0 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
14) теперь из оставшихся двух строк остаётся найти 2 строки, значения которых различаются только в одном столбце; под это условие подходит только пара двух верхних строк, они различаются в столбце y – из исходной таблицы видим, что это 4-й столбец
15) также из исходной таблицы видим, что во втором столбце в этих двух строках единицы – это w, тогда третий столбец – это z
16) Ответ: xwzy.
Решение (А.Н. Носкин, построение таблицы истинности для F = 1):
1) запишем выражение в более понятной форме:
2) вынесем y за скобки: F = (y*(x+z) ≡ ((x→w)*(w→z))
3) F = 1, при 0=0 и 1=1. Тогда составим ТИ для левой части выражения равные 0 и 1.
y | x | z |
0 | 0 | 0 |
0 | 0 | 1 |
0 | 1 | 0 |
0 | 1 | 1 |
1 | 0 | 0 |
y | x | z |
1 | 0 | 1 |
1 | 1 | 0 |
1 | 1 | 1 |
4) Объединим эти таблицы, подключим переменную w и уберем из таблицы строки, при которых F=0 после подключения переменной w.
y | x | z | w |
0 | 0 | 0 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 |
5) Получилось 8 всевозможных решений.
6) Обратим внимание, что по условию у нас нет повторяющихся строк, но в таблице есть строки с тремя одинаковыми ячейками, тогда можно ДОЗАПОЛНИТЬ таблицу истинности исходной функции (желтая заливка) в одну из них вставив 0, в другую 1.
? | ? | ? | ? | F |
0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 0 | 1 |
7) Анализ строк таблицы истинности исходной функции показывает:
- строки, состоящей из четырех «1» нет, поэтому ее можно убрать (красная заливка);
- только одна строка имеет в ячейках три единицы и один «0». И в ТИ всех решений (желтая заливка) этот «0» будет соответствовать Х в ТИ исходной функции.
y | x | z | w |
0 | 0 | 0 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 |
8) Так как мы определили, что первый столбец соответствует Х и содержит только «0», то строки ТИ решений с «1» в столбце Х – удалим (синяя заливка)
y | x | z | w |
0 | 0 | 0 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 |
и получим ТИ меньшего размера.
y | x | z | w |
0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
9) Анализ столбцов ТИ исходной функции показывает, что одна «1» в третьем столбце соответствует Z, а в третьей строке ТИ исходной функции две неизвестные переменные противоположны «0» и «1», что соответствует W и Y, так как X и Z уже определены и равны «0» (зеленая заливка)
y | x | z | w |
0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
10) Ответ: xwzy.
Ещё пример задания:
Р-19. Логическая функция F задаётся выражением
((w Ú y) º x) Ú ((w ® z) Ù (y ® w)).
На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
? | ? | ? | ? | F |
1 | 1 | 0 | ||
1 | 0 | |||
1 | 1 | 0 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение:
1) запишем выражение в более понятной форме:
2) попробуем найти все сочетания переменных, при которых функция равна 0 (их должно быть не очень много)
3) выберем для начальной подстановки переменную, которая чаще всего встречается в выражении и поэтому подстановка её значения даст наибольшую информацию; у нас это переменная w
4) подставим сначала w = 0, а затем w = 1, и таким образом построим все строки таблицы истинности, где функция равна нулю
5) при w = 0 получаем
поскольку при всех z, имеем
6) для того, чтобы сумма была равна 0, оба слагаемых должны быть равны 0, так что
7) таким образом, при w = 0 получаем y = 1, x = 0, а значение z может быть любое; это даёт две строки в таблице истинности:
x | y | z | w | F |
0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 |
8) теперь рассмотрим случай, когда w = 1: получаем
поскольку при всех y, имеем
9) для того, чтобы сумма была равна 0, оба слагаемых должны быть равны 0, так что
10) таким образом, при w = 1 получаем x = 0, z = 0, а значение y может быть любое; добавляем ещё две строки в таблицу истинности:
x | y | z | w | F |
0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 |
0 | 0 | 0 | 1 | |
0 | 1 | 0 | 1 |
11) сравниваем эту таблицу с таблицей в задании:
1 | 2 | 3 | 4 | F |
1 | 1 | 0 | ||
1 | 0 | |||
1 | 1 | 0 |
12) две единицы могут быть только в столбцах y и w, поэтому это столбцы 1 и 4
13) кроме этих столбцов единственная единица может быть в столбце z, поэтому столбец 3 – это z
14) при z = 1 должно быть y = 1, поэтому столбец 1 – это y, а столбец 4 – это w
15) остаётся столбец 2 – это x
16) Ответ: yxzw.
Дата добавления: 2022-11-11; просмотров: 35; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!