2.01 Полностью заполненные фрагменты таблицы истинности

Решение аналитически

Во всех строках приведенного фрагмента таблицы истинности Чтобы конъюнкция была истинна, всегда должна равняться единице (так как конъюнкция будет истинна, если истинны все высказывания, входящие в нее). Этому условию соответствует только второй столбец, т.к. в других присутствует ноль.

Рассмотрим Это высказывание тоже должно быть истинным. Дизъюнкция истинна, если хотя бы одно из высказываний, входящих в нее, истинно. Значит, мы не должны допускать ситуации, когда (или и одновременно. Рассмотрим первый и третий столбец первой строки. Если отвечает за 1 столбец, а за третий, то Этот вариант не подходит, так как дизъюнкция будет ложной. Тогда остается только один вариант: отвечает за 1 столбец, а за третий, получаем

Проверим наше предположение на двух оставшихся строчках.

Рассмотрим вторую строчку. Дизъюнкция будет истинной.

Рассмотрим третью строчку. Дизъюнкция будет истинной. Таким образом, отвечает за третий столбец, а — за первый.

Решение программой

 print(’x y z’)
 for x in range(2):
     for y in range(2):
         for z in range(2):
             if ((not x) or y) and z:
                 print(x, y, z)
 

Увидим соответствие таблице, сопоставим буквы и получим ответ .

Составим таблицу истинности.

Выпишем отдельно те строки, которые нам подходят:

У нас есть две строки, где только одна единица. В роли этих единиц выступают Значит, третья переменная — это

Рассмотрим третью строку. А такая строка у нас только одна. Отсюда однозначно определяем столбцы и пишем в ответ:

Дизъюнкция истинна, если одна из скобок истинна. Первая скобка истинна в случае Это соответствует второй строке. Следовательно, занимает второй столбец. Вторая скобка истинна тогда, когда Используя первую строку, поймём, что занимает первый столбец. Тогда занимает третий.

Дизъюнкция будет ложной тогда, когда обе скобке будут ложными. Заметим, что переменные должны иметь разные значения. Если то При этом для ложности конъюнкции Если же то При этом может быть равен как , так и . Если равен , то данные значения переменных будут соответствовать первой строке. В таком случае займёт третью строку. Обратимся ко второй строке и увидим, что в ней принимает значение , а также во второй ячейке так же находится . Следовательно, второй столбец занимает а первый столбец занимает .

1. Конъюнкция истинна, когда обе скобки будут истинны. Обратим внимание на вторую и третью строчки. Они примечательны тем, что в них тогда, когда две переменные принимают значение 1, а третья переменная значение 0. Заметим, что если то так как первая скобка будет ложной. Используя вторую и третью строчки, мы поймём, что не может занимать первый и второй столбец, следовательно, занимает третий столбец.

2. Обратимся к первой строчке. В ней Следовательно, В таком случае для истинности эквивалентности. Значит, занимает первый столбец, а занимает второй.

1. Заметим, что конъюнкция истинна будет истинна, если каждая из скобок будет истинной. Обратим внимание на первую строку. Предположим, что занимает первый столбец. В таком случае а значит, импликация во второй скобке будет ложной. Если занимает первый столбец эквивалентность в первой скобке будет истинной. Следовательно, первый столбец занят переменной

2. Обратим внимание на вторую строчку. Заметим, что если то импликация во второй скобке будет ложной. Это означает, что тертий столбец может занимать переменная , а второй столбец занимать переменная

1. Заметим, что все переменные не могут быть принимать значение 1 одновременно, так как тогда вторая скобка будет истинной, а значит, импликация будет истинной. Значит в первой ячейке первой строки находится 0. Предположим, что первый столбец занимает Но в таком случае дизъюнкция в первой скобке будет ложной (так как ), а это значит что Если в первом столбце представлена переменная то переменные будут равны, то есть эквивалентность будет истинной, а Значит в первом столбце находится переменная

2. Рассмотрим вторую строчку теперь. Если то (чтобы дизъюнкция была истинной), а Но данный набор не подходит под вторую строку. Значит, во второй строке, (чтобы строки не повторялись). Значит, занимает третий столбец, а занимает второй.

1. Функция истинна, если одна из скобок истинна. Обратимся к первой строке. Если или то функция ложна. Отсюда следует, что занимает второй столбец.

2. Рассмотрим вторую строку. В ней принимает значение 1. Тогда первая скобка из-за отрицания будет ложной. В таком случае должен быть равен 0. Получаем, что занимает первый столбец, а занимает третий.

Решение программой

print("x y z w")
for x in range(0,2):
    for y in range(0,2):
        for z in range(0,2):
            for w in range(0,2):
                if ((w or not(y)) and not(x <= z)) == True:
                    print(x, y, z, w)

Вывод программы:

Решение руками

Для истинности функции обе скобки должны быть истинны. Вторая скобка будет истинна, если импликация будет ложной. Тогда Получается, что занимает второй столбец, а переменная занимает второй. При этом первая скобка тоже будет истинной. Она будет ложной лишь в случае Обратимся ко второй строке и поймём, что для истинности скобки занимает четвёртый столбец, а занимает третий.

1. Рассмотрим первую строчку фрагмента таблицы истинности. Для истинности функции каждая из скобок должна быть истинна. Следовательно, ни одна из импликакий не должна быть ложной, а это означает, что ни ни не равны 1. В таком случае третий столбец занимает переменная .

2. Рассмотрим вторую строчку. Видим, что переменная вновь принимает значение 1. Первая импликация должна быть истинной, а это будет возможно тогда, когда Получается, что занимает второй столбец, а занимает первый.

print(’x y z w’)
a = (0, 1)
for x in a:
    for y in a:
        for z in a:
            for w in a:
                if (not(x) or ((z <= y) and (z or w))) == False:
                    print(x, y, z, w)

1. Для ложности функции переменная должна принимать значение 1. Следовательно, данная переменная занимает второй столбец.

2. Рассмотрим четвёртую строку. Предположим, что занимает третий столбец. В таком случае импликация и дизъюнкция будут истинны, а значит, конъюнкция будет истинна. Если занимает третий столбец, то конъюнкция будет так же истинна. Если же занимает третий столбец, то импликация будет ложной, а значит, и конъюнкция будет ложной. Тогда занимает третий столбец.

3. Рассмотрим вторую строчку. В ней принимает значение 0. Если занимает четвёртый столбец, то дизъюнкция и импликация будут истинны, а значит, конъюнкция будет истинна. Следовательно, занимает первый столбец, а переменная занимает четвёртый.

Во всех трех строках Импликация ложна, если из истины следует ложь. Значит, и Конъюнкция истинна, если все высказывания, входящие в нее, истинны, то есть и то есть

Рассмотрим Это выражение должно быть ложно, значит дизъюнкция должна быть истинна. Дизъюнкция истинна, если хотя бы одно из высказываний, входящих в нее, истинно. Так как то может быть любым.

Так как то первому столбцу соответствует Так как то третьему столбцу соответствует Так как может быть любым, то второму столбцу соответствует

так как если то а если то а

Тогда функция переписывается в таком виде: Во всех трех столбцах Так как конъюнкция истинна, если все высказывания, входящие в нее, истинны, то и Тогда первый столбик — это

Рассмотрим высказывание Оно истинно, когда и/или то есть (так как дизъюнкция истинна, когда хотя бы одно высказывание, входящее в нее, истинно). Рассмотрим третью строку. Как мы определили выше, первый столбец отвечает за Если второй — это то должна быть равна 1 (так как если то есть Но переменная в третьем столбце равна 1, значит, предположение, что второй столбец — это было неверным. Значит, второй столбец — это а третий — это

Проверим это предположение на первой и второй строчках. Подставим соответствующие значения в функцию. Первая строка: Вторая строка: Все верно.

Так как конъюнкция истинна тогда и только тогда, когда все высказывания, входящие в нее, истинны, то и должны быть одновременно истинны. Если то В таком случае соответствует второй столбец (так как только в нем нет ни одной единицы).

Рассмотрим Нам нужно, чтобы данная импликация была истинна. Легче исключить один случай, когда импликация ложна, так как она ложна тогда и только тогда, когда из истины следует ложь, то есть когда a Рассмотрим вторую строку. Видим, что переменная не может соответствовать третьему столбцу, так как тогда и Получается, третьему столбцу соответствует а первому —

1. Упростим

По закону дистрибутивности = (если то если то Тогда

2. Упростим По закону дистрибутивности

3. Получим:

4. Рассмотрим таблицу истинности. Чтобы значение функции было равно 0, (ведь дизъюнкция ложна, если ложны все входящие в нее высказывания) и Тогда второму столбцу соответствует (это единственный столбец, в котором все нули при Теперь рассмотрим случай, когда Хотя бы одно из выражений, входящих в дизъюнкцию, должно быть истинно. Во второй строке (где функция истинна) таблицы истинности значит, Конъюнкция истинна, если истинны все высказывания, входящие в нее, то есть и одновременно, и При = (0, 1, 0) Во второй строке таблицы истинности из условия содержатся два нуля и одна единица. Значит, третьему столбцу соответствует (так как там есть единица), а первому —

1. Так как преобразуем левую часть функции:

2. так как, если то если то

3. После преобразований функция выглядит так: Так как дизъюнкция истинна, если истинно хотя бы одно из высказываний, входящих в нее, то при любых значениях и Чтобы функция была равна должно быть равно 0 (так как конъюнкция ложна, если ложно хотя бы одно из высказываний, входящих в нее). Значит, и (так как дизъюнкция ложна, если ложны все входящие в нее высказывания). Тогда Тогда соответствует второму столбцу, соответствует третьему, а соответствует первому столбцу (переменная может быть любой, так как в упрощенной формуле переменная отсутствует, значит, не влияет на ответ).

По закону дистрибутивности

Тогда функция переписывается в следующем виде:

Конъюнкция истинна, если истинны все высказывания, входящие в нее. Значит,

Если то Так как только в четвертом столбце нет единиц, то четвертому столбцу соответствует

Для удобства составим таблицу истинности. Так как всегда должна быть равна нулю, чтобы то будем составлять таблицу истинности только для трех переменных. В ней будет строчек. Если значение выражения будет истинно, то и вся функция будет истинна.

Есть только 4 строки, в которых Значит, надо сопоставить каждую из них с фрагментом таблицы истинности из условия. В восьмой строке составленной таблицы истинности две единицы и один ноль. В третьей строке фрагмента тоже есть две единицы (в остальных строках или 3 единицы или 1 или их нет вообще). В этой строке ноль — это значение Значит, первому столбцу фрагмента соответствует

Рассмотрим третью строку составленной нами таблицы истинности. Там есть одна единица и два нуля. Во второй строке фрагмента из условия также 3 нуля и одна единица. Эта единица — значение (второй столбец).

Тогда третьему столбцу соответствует

1. Мы можем однозначно определить, что для истинности функции Следовательно, переменная занимает второй столбец.

2. Рассмотрим вторую строчку фрагмента таблицы истинности. Предположим, что - это третий столбец, а — первый. Но в таком случае импликация будет истинна, эквивалентность ложна, а значит, функция ложна. Покажем, что - это первый столбец, а — третий столбец. Тогда импликация будет истинна, эквивалентность истинна, а значит, и конъюнкция будет истинна. Следовательно, переменные расположены в порядке

Импликация ложна в случае, когда первая скобка будет истинной, а вторая скобка будет ложной. Вторая скобка ложна в случае, когда переменные имеют разные значения. Из первой и третьей строчек мы можем сделать вывод о том, что эти переменные могут занимать только первый и третий столбцы. Следовательно, занимает второй столбец. Рассмотрим вторую строку, в ней Так как то Значит занимает третий столбец, а занимает первый.

Рассмотрим, когда Тогда отрицание этого выражения примет значение . Для выполнения этого условия Следовательно, переменная занимает второй столбец. Конъюнкция во второй скобке также должна быть ложной. Она будет истинной в том случае, когда Посмотрев на вторую строку, мы поймём, что для ложности конъюнкции А значит, первый столбец занимает а третий занимает переменная