Решение (метод исключения, С.Н. Лукин, г. Москва):
1) всего возможно 6 вариантов решения задачи:
| x | y | z |
| x | z | y |
| y | x | z |
| y | z | x |
| z | x | y |
| z | y | x |
В процессе решения будем вычеркивать лишние варианты, пока не останется один-единственный. Также будем по возможности заполнять пустые клетки таблицы (по принципу «Чем меньше неопределенностей, тем лучше»).
2) используем следующее свойство импликации: выражение a®b равно нулю тогда и только тогда, когда a=1 и b=0. В нашем примере a это левая скобка, b – правая.
3) теперь рассуждаем от противного. Пусть в пустой клетке первой строки таблицы истинности стоит ноль:
| ? | ? | ? | F |
| 0 | 0 | 0 | 0 |
4) Тогда в любом из 6 вариантов решения получится x = 0 и y = 0, а значит (x Ú y)=0, что противоречит упомянутому свойству импликации. Значит, там стоит единица:
| ? | ? | ? | F |
| 0 | 0 | 1 | 0 |
| 0 | 0 |
5) По той же причине в левых двух столбцах первой строки не могут находиться одновременно x и y. Это позволяет нам вычеркнуть два из шести вариантов решения:
    | | |
| | | |
Остаются 4 варианта:
| x | z | y |
| y | z | x |
| z | x | y |
| z | y | x |
6) Идем дальше. По упомянутому свойству импликации вторая скобка должна равняться 0, а значит y и z не должны совпадать. Это позволяет нам, погдядев на первую строку таблицы истинности, вычеркнуть еще два варианта решения:
| | | |
| | | |
Остаются 2 варианта:
| x | z | y |
| z | x | y |
7) Получается, что в правом столбце обязательно стоит y. Начало положено.
|
|
|
8) Попробуем заполнить пустые клетки во второй строке таблицы истинности. Способов заполнения четыре: 00, 01, 10, 11. Первый из них мы рассмотрели выше, он отпадает. Второй отпадает, так как в этом случае две строки таблицы истинности будут совпадать, что противоречит условию задачи. Третий и четвертый способы приказывают нам иметь во втором столбце единицу. Спасибо и на этом:
| ? | ? | y | F |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 |
9) Теперь рассмотрим первый из двух оставшихся вариантов решения (xzy), подставив сначала в пустую клетку ноль. Но ноль отпадает, так как x и y не могут одновременно равняться нулю. А единица отпадает, так как y и z не должны совпадать. Значит, отпадает и сам вариант решения xzy. Следовательно, решением задачи является единственный невычеркнутый вариант: zxy.
10) Из тех же соображений, что y и z не должны совпадать, в оставшуюся пустую клетку ставим единицу:
| z | x | y | F |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
11) А теперь проверьте решение, подставив в выражение (x Ú y) ® (y º z) значения переменных из каждой строки таблицы.
12) Ответ: zxy.
Решение (метод инверсии, А.Н. Носкин, г. Москва):
1) Известно, что если F = 0, то обратная её функция 
=1.
2) Применим закон де Моргана и упростим:
|
|
|
3) тогда при тех же значениях аргументов функция истинна
| ? | ? | ? |
|
| 0 | 0 | 1 | |
| 0 | 1 |
4) анализ формулы 
показывает, что для истинности функции необходимо, чтобы значение в каждой скобке были равны 1.
5) Кроме того, этот анализ показывает, что в первой строке таблицы, в ее последнем столбце, не может быть 0, так как тогда значение функции не будет равно 1. На основе этого анализа таблица примет вид:
| ? | ? | ? |
|
| 0 | 0 | 1 | 1 |
| 0 | 1 |
6) Анализ первой строки данной таблицы показывает, что в первых двух ячейках не может быть одновременно ни x, ни y. В этих ячейках рядом может быть только x и z, значит y находится в последней ячейке.
7) Во второй ячейке, второй строки не может быть 0, так как должны быть неповторяющиеся строки, а все нули быть не могут (не выполнится условие =1). Значит в данной ячейке строго 1.
| ? | ? | y |
|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 |
8) Значит в оставшейся ячейке может быть только 0 или 1, а именно, во второй строке возможен набор 010 или 011. Простой анализ с учетом того, что в последнем столбце y, дает итоговый ответ – набор 011 .
9) Ответ: zxy.
Ещё пример задания:
Р-17. Логическая функция F задаётся выражением x Ú y Ú (z Ù w). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
|
|
|
| ? | ? | ? | ? | F |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение:
1) запишем выражение в более понятной форме: 
2) анализ формулы показывает, что для того, чтобы функция F была ложна, необходимо, чтобы x всегдабыл равен 1, а y всегдабыл равен 0; поэтому x – это последний столбец в таблице, а y – первый:
| y | ? | ? | x | F |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
3) остается разобраться с двумя средними столбцами; обратим внимание на вторую строчку таблицы, в которой одна из оставшихся переменных равна 1, а вторая – 0; так как функция равна 0, то 
, откуда следует, что z = 1 и w = 0 (иначе произведение будет равно 1)
4) Ответ: yzwx.
Дата добавления: 2022-11-11; просмотров: 115; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!