ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 1379
Скачиваний: 9
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Ещё пример задания:
Р-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 |
-
перепишем выражение, раскрыв импликацию по формуле
: 
-
сначала предположим, что
; в этом случае получаем
-
так как
, получим 
; при этом значение y может быть любым (1 или 0) -
теперь пусть
, тогда получаем
-
используем распределительный закон:
, так что
и 
– единственный вариант!
-
этот единственный вариант, для которого
, ОБЯЗАТЕЛЬНО должен быть в приведённой таблице, потому что иначе мы не сможем различить столбцы z и x; это может быть только последняя строчка, куда нужно добавить две единицы:
z
?
?
?
F
0
0
1
1
0
1
0
0
1
0
1
1
1
1
-
в остальных строчках должно вполняться равенство
, значит x – точно не второй столбец (не подходит вторая строка) -
предположим, что x – третий столбец, и в свободной ячейке – нуль:
z
?
x
?
F
0
0
0
1
1
0
1
0
0
1
0
1
1
1
1
-
при этом для остальных двух столбцов в этих строчках должно выполняться условие
, а оно не может выполняться – при любом варианте в одной строке сумма 
равна 0; значит x – последний столбец, и в первой строке z = 1:
z
?
?
x
F
1
0
0
1
1
0
1
0
0
1
0
1
1
1
1
-
чтобы разобраться с поcледними двумя столбцами снова вспомним, что при должно выполняться условие ; это возможно только тогда, когда второй столбец – это y, а третий - w -
Ответ: zywx
Решение (А.Н. Носкин, заполнение исходной ТИ и анализ полной таблицы истинности для F = 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 |
-
подставим набор значений логических переменных и удалим все решения, которые не дают в ответе 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 |
-
В ТИ решений только одна строка имеет три нуля, тогда сравнивая с ТИ исходной функции видим, что 1 соответствует Y.
| ? | Y | ? | ? | F |
| | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | | | 1 | 1 |
-
ДОЗАПОЛНИМ таблицу истинности исходной функции (желтая заливка) на основе анализа ТИ решений, а именно т.к больше строк с тремя «0» нет, то в первой строке в пустой ячейке будет «1». И раз нет больше строк с двумя «0», то в третьей строке пустые ячейки равны «1».
| ? | Y | ? | ? | F |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
-
Анализируя 1ю строку выше приведенной таблице и ТИ решений видим, что строка с двумя «0» всего одна, из которых один нуль известен - это Y, тогда второй это – W;
| ? | Y | W | ? | F |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
-
Далее рассуждая видим, что в ТИ решений (кроме столбца Y) один «0» имеет – Х, тогда последний столбец – это Х, а первый столбец – Z. -
Ответ: zywx