2.02 Частично заполненный фрагмент таблицы

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

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

Операция эквивалентности ложна, если одно высказывание ложно, а другое истинно.

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

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

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

Когда то и В первой строке (где есть три нуля и одно неизвестное значение в четвертом столбце. Мы уже определили, что этой строке соответствует набор = (0, 0, 0, 1), значит, четвертому столбцу соответствует Тогда третьему столбцу соответствует (такой вывод мы сделали из рассуждений в первом абзаце), а — второму.

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

def f(x, y, z, w):
    return y or (x and w) or (w == z)

print(’x y z w’)
for x in range(2):
    for y in range(2):
        for z in range(2):
            for w in range(2):
                if f(x, y, z, w) == 0:
                    print(x, y, z, w)

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

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

(1)

(2)

Чтобы операция эквивалентности (1) была ложна, одно высказывание должно быть ложным, а другое истинным. Тогда и или и

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

Видим, что для следующих наборов : (0, 1, 0), (0, 0, 1), (0, 1, 1).

Проверим, ложно ли при данных значениях

Конъюнкция (2) ложна, если хотя бы одно высказывание, входящее в нее, ложно, значит, и/или Импликация ложна, если из истины следует ложь и истинна во всех остальных случаях. Подставим первый набор = (0, 1, 0) в (2): Чтобы одно из высказываний, входящих в конъюнкцию, было ложно, (иначе Значит, нам подходит такой набор = (0, 0, 1, 0). Подставим второй набор (0, 0, 1) в (2): Так как истинно при любом то есть еще два подходящих набора: (1, 0, 0, 0) и (1, 0, 0, 1). Наконец, подставим третий набор (0, 1, 1): Если то Еще один подходящий набор (1, 0, 1, 0). Если то что нам не подходит.

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

Выпишем строки таблицы истинности, где

Таблица (*).

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

Также заметим, что в фрагменте таблицы истинности из условия во всех столбцах, кроме второго и третьего, по две единицы. Если посмотреть на таблицу (*), то увидим, что только в одной строке. Так как второй столбец — это то третий - это

Мы можем определить, что третья строка фрагмента соответствует второй строке таблицы (*) (так как там

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

Тогда — это первый столбец.

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

def f(x, y, z, w):
    return (y == (z or x)) or ((z <= w) and (x <= z))

print(’x y z w’)
for x in range(2):
    for y in range(2):
        for z in range(2):
            for w in range(2):
                if f(x, y, z, w) == 0:
                    print(x, y, z, w)

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

2. Посмотрим на третью строчку. В ней а это значит, что в этой строке, чтобы конъюнкция во второй скобке была ложной. Получается, что в третьей ячейке третьей строки находится 0. И этот столбец занят переменной А первый столбец отводится под переменную

Аналитическое решение:

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

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

Программное решение:

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

После запуска программы получаем результат:

Для начала заметим, что только в одной строке присутствует две единицы, а значит можем однозначно определить, что на первом месте. В тех строчках, где , у второй переменной должны стоять 0 и 1, значит на втором месте - , на третьем - .

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

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

Программное решение

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

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

Для ложности функции каждая из скобок должна быть ложной. Первая скобка ложна в случае, если Следовательно, переменная занимает третий столбец. Так как принимает значение 0, то должен принимать значение 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 (y) and (w <= x) and z) == True:
                    print(x, y, z, w)

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

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 (w and (x or not(y)) and not(w == z)) == True:
                    print(x, y, z, w)

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

Если то

Мы уже знаем, что Тогда чтобы операция эквивалентности была ложна, должна быть равна 0 (операция эквивалентности ложна, если одно высказывание, входящее в нее, ложно, а другое истинно). Тогда — это второй или третий столбец, потому что первый — это уже а в четвертом во второй строке содержится единица.

Рассмотрим вторую строчку. Её удобно рассматривать, так как нам известно, что в первом столбце будет единица (так как он соответствует значит, нам известны все значения в этой строке. Таким образом, в этой строке две единицы и два нуля. Если то (так как в строке всего две единицы, которые при таком предположении уже соответствуют и Но тогда Такое нам не подходит, ведь функция должна быть истинна. Значит, должна быть равна 1. Она будет соответствовать четвертому столбцу.

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

Нам сказано, что в приведенном фрагменте таблицы истинности содержатся неповторяющиеся строки. Если то третья строка будет совпадать со второй. Если то третья строка будет совпадать с первой. Значит, наше предположение было неверным. Тогда второй столбец — это а третий — это

Тогда таблица будет выглядеть так:

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

Значит, итоговая таблица будет выглядеть так:

В приведенном фрагменте во всех строках Функция представляет из себя два операнда дизъюнкции. Так как дизъюнкция ложна, если ложны все высказывания, входящие в нее, то ( = 0 и

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

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

Если то Значит, Тогда при любом Составим таблицу истинности для и

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

Мы разобрали все случаи, при которых функция ложна. Выпишем строки таблицы истинности, где

Таблица 1.

Сопоставим таблицу 1 и фрагмент, приведенный в условии. Рассмотрим данную строку:

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

Аналогично и с этой строкой:

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

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

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

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

В результате работы программы получим следующую таблицу:

В первом столбце должно быть три единицы, значит это однозначно буква . Во втором столбце точно должно быть минимум две единицы, если посмотреть на строки, где истина, то на второе место однозначно подходит только . Так как в третьем столбце должна быть хотя бы одна единица, туда однозначно встаёт только . Ответ - zyxw.

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

Операция эквивалентности истинна, если оба высказывания ложны или оба истинны, и ложна, если одно высказывание истинно, а другое ложно.

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

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

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

Рассмотрим первую строку. Так как среди оставшихся двух наборов нет наборов, в которых все переменные равны 1, то на месте вопросительных знаков будет стоять 0. Тогда эта строка соответствует набору Из этого мы можем сделать вывод, что третий столбец — это Методом исключения первый столбец —

Напишем программу, которая выведет значения x, y и z при которых значение выражение равно 0:

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

Программа выводит следующий результат:

Очевидно, что четвертому столбцу соответствует переменная w, так как в остальных столбцах есть нули.

Также однозначно можно определить что третьему столбцу соответствует y так как только в нем есть два нуля. В строке с двумя нулями один пренадлежит y, а второй тогда x, тогда второй столбец это x. Остается только первый столбец – это переменная z. Тогда ответ zxyw.

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

2. Рассмотрим теперь вторую строчку. Мы поняли, что одновременно нулями все переменные быть не могут, быть единицей может только (в то время как остальные переменные равны нулю). Значит, первую и вторую ячейку занимает единица. Теперь рассмотрим, когда Но тогда а значит, Значит импликация будет истинной при этом. Остаётся вариант, когда Данный вариант удовлетворяет условиям, так Следовательно, занимает второй столбец, а занимает третий.

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

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

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

2. Обратимся к третьей строке, в ней значит, Тогда

3. Теперь обратимся ко второй строчке. Предположим, что в ней Тогда а значит, занимает второй столбец. Но тогда что не подходит для второй строки. Значит в ней Тогда а значит, либо В первом случае строка совпадет с первой строкой, значит подойдёт второй вариант. Таким образом, занимает второй столбец, а занимает первый.

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

Заметим, что для ложности функции должен принимать значение . Следовательно, занимает третий столбец. Также должен иметь значение , а значит, второй столбец занят переменной а все ячейки столбца содержат единицы. Первую ячейку второй строки должна занимать , так как иначе строка совпала бы с первой строкой. Заметим, что ложно во всех случаях, кроме Именно поэтому не может занимать четвёртый столбец, а первый (судя по второй строке). Это значит, что находится в четвёртом столбце, а в первом. Отсюда следует, что в первой и четвёртой ячейках третьей строки находятся единицы.

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

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

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

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

2. Как мы поняли из первой строки, среди набора переменных только одна переменная может принимать значение , в то время как другие переменные равны . Следовательно, третья ячейка третьей строки равна .

3. Осталось разобраться со второй строкой. Если вторая ячейка принимает значение , то строка совпадёт с первой строкой. Значит, в этой ячейке находится . Предположим, что Но тогда а значит, . Остаётся вариант, когда . При этих значениях . Значит второй столбец занимает , а третий столбец занимает .

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

2. Рассмотрим теперь вторую строчку. Мы поняли, что одновременно нулями все переменные быть не могут, быть единицей может только (в то время как остальные переменные равны нулю). Значит, первую и вторую ячейку занимает единица. Теперь рассмотрим, когда Но тогда а значит, Значит импликация будет истинной при этом. Остаётся вариант, когда Данный вариант удовлетворяет условиям, так Следовательно, занимает второй столбец, а занимает третий.

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

Предположим, что занимает первый столбец.

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