какое логическое выражение равносильно выражению avb vc

Какое логическое выражение равносильно выражению avb vc

Логическая функция F задаётся выражением (x ∨ ¬y) ∧ ¬(w ≡ z) ∧ w.

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

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Рассмотрим данное выражение. Преобразуем логическое выражение (x ∨ ¬y) ∧ ¬(w ≡ z) ∧ w и получим систему, при которой оно истинно:

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

Значения переменных w и z не могут быть равны. Из второй строки заключаем, что столбец четыре не может соответствовать переменным z и y. Следовательно, четвёртый столбец соответствует переменной x.

Рассмотрим первую строку таблицы. Переменная x равна 0, значит, для истинности выражения переменная y должна принимать значение 0. Переменная w равна 1, значит, для истинности выражения переменная z должна принимать значение 0. Следовательно, во втором столбце в первой строке должен быть 0.

Поскольку строки в таблице не повторяются, в третьей строке в третьем и четвёртом столбцах могут стоять значения 10 и 11. Поскольку переменная w не должна быть равна z, переменная z соответствует второму столбцу. Следовательно, переменная y соответствует третьему столбцу.

Таким образом, ответ: wzyx.

Приведем другое решение.

Составим таблицу истинности для выражения (x ∨ ¬y) ∧ ¬(w ≡ z) ∧ w и выпишем те наборы переменных, при которых данное выражение равно 1. В наборах переменные запишем в порядке х, y, z, w. Получим следующие наборы:

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

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

Вторая строка таблицы соответствует набору (1, 0, 0, 1), в котором единичное значение принимает переменная x, следовательно, переменной x соответствует четвертый столбец таблицы.

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

Логическая функция F задаётся выражением (¬x ∨ ¬y) ∧ ¬(x ≡ z) ∧ w.

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

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Рассмотрим данное выражение. Преобразуем логическое выражение (¬x ∨ ¬y) ∧ ¬(x ≡ z) ∧ w и получим систему, при которой оно истинно:

Заметим, что переменная w должна принимать значение 1, иначе выражение будет ложным. Значит, переменная w соответствует первому столбцу.

Значения переменных x и z не могут быть равны. Из второй строки заключаем, что столбец четыре не может соответствовать переменным x и y. Следовательно, четвёртый столбец соответствует переменной z.

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

Поскольку строки в таблице не повторяются, в третьей строке в третьем и четвёртом столбцах могут стоять значения 10 и 11. Поскольку переменная x не должна быть равна z, переменная x соответствует второму столбцу. Следовательно, переменная y соответствует третьему столбцу.

Таким образом, ответ: wxyz.

Приведем другое решение.

Составим таблицу истинности для выражения (¬x ∨ ¬y) ∧ ¬(x ≡ z) ∧ w и выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные запишем в порядке х, y, z, w. Получим следующие наборы:

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

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

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

Приведем программу Михаила Глинского для построения таблицы истинности.

Программа на языке Паскаль выводит на экран наборы переменных, при которых значение заданного выражения равно 1.

for var x:=false to true do

for var y:=false ro true do

for var z:=false to true do

for var w:=false to true do

if (not(x) or not(y)) and (x<>z) and w then writeln(ord(x), ord(y), ord(z), ord(w));

— Логическая функция F задаётся выражением (x ≡ ¬y) → (z ≡ (y ∨ w)).

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

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Рассмотрим данное выражение. Преобразуем логическое выражение (x ≡ ¬y) → (z ≡ (y ∨ w)) и получим систему, при которой оно ложно:

Заметим, что третий и четвёртый столбцы таблицы истинности это y и x. Из условия следует, что первому столбцу таблицы истинности соответствует переменная z. Следовательно, второму столбцу таблицы истинности соответствует w.

Приведем другое решение.

Составим таблицу истинности для выражения (x ≡ ¬y) → (z ≡ (y ∨ w)) и выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные запишем в порядке х, y, z. Получим следующие наборы:

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

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

Заметим, что переменная z принимает нулевое значение в трех из имеющихся четырех наборах, а остальные переменные — только в двух, следовательно, первый столбец таблицы соответствует переменной z.

Первая строка таблицы может соответствовать только набору (1, 0, 0, 1), где переменные y и z принимают нулевые значения, следовательно, третья строка соответствует набору (0, 1, 0, 1), в котором нулевое значение принимает переменная x. Тогда x — это четвертый столбец, а w — второй столбец.

Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w.

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

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Рассмотрим данное выражение. Преобразуем логическое выражение (x ∧ ¬y) ∨ (y ≡ z ) ∨ ¬w и получим систему, при которой оно ложно:

Заметим, что второй столбец таблицы истинности это w. Из условия следует, что переменные z и y соответствуют третьему и четвёртому столбцам таблицы истинности. Следовательно, первому столбцу таблицы истинности соответствует переменная x.

Примечание. Вариант xwyz не подходит, поскольку в третьей строке таблицы истинности функция F будет истинной, что не удовлетворяет условию задания.

Приведем другое решение.

Составим таблицу истинности для выражения (x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w и выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные запишем в порядке х, y, z, w. Получим следующие наборы:

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

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

Вторая строка таблицы соответствует набору (0, 1, 0, 1), следовательно, четвертый столбец таблицы соответствует переменной у.

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

Логическая функция F задаётся выражением (x ∨ y) ∧ ¬(y ≡ z) ∧ ¬w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Рассмотрим данное выражение. Преобразуем логическое выражение (x ∨ y) ∧ ¬(y ≡ z) ∧ ¬w и получим систему, при которой оно истинно:

Значение выражения всегда ложно тогда, когда переменная w равна 1, следовательно, столбцы, в которых содержится единица, не могут соответствовать переменной w, то есть переменной w соответствует четвёртый столбец.

Значения переменных y и z не могут быть равны. Из второй строки заключаем, что столбец один не может соответствовать переменным y и z. Следовательно, первый столбец соответствует переменной x.

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

Таким образом, ответ: xzyw.

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Для какого наибольшего целого числа А формула

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Преобразуем выражение по законам алгебры логики:

Х + (Y → Z) = Х + (¬Y + Z) = Х + Z + ¬Y = Y → (X + Z) = (Y → X) + (Y → Z).

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Заметим, что первое слагаемое логической суммы является импликацией Z₄₁ → Z₅₁, которая не является истинной для всех х (см. ниже). Тогда необходимо и достаточно, чтобы второе слагаемое логической суммы было тождественно истинным.

Действительно, например, для х = 2 поразрядная конъюнкция с числом 41 дает 0, а с числом 51 дает 2. Поэтому импликация (2&41) → (2&51) принимает вид 1 → 0 — ложь.

2&41: 000000, то есть 2&41 = 0. Высказывание 2&41 = 0 истинно.

2&51: 000010 = 2, то есть 2&51 = 2. Высказывание 2&51 = 0 ложно.

Итак, импликация Z₄₁ → Z_A должна быть тождественно истинной. Запишем число 41 в двоичной системе счисления: 41₁₀ = 101001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, третий и пятый биты (как обычно, считая справа налево, начиная с нуля).

Тем самым, наибольшее А = 101001₂ = 41₁₀.

Ответ 45 не подходит. Пусть A = 45, а x = 22₁₀ = 10110₂, тогда:

51&22: 010010₂, т.е. высказывание 22&51 = 0 ложно.

41&22: 000000₂, т.е. высказывание 22&41 ≠ 0 ложно.

51&22: 000100₂, т.е. высказывание 22&45 = 0 ложно.

Следовательно, при x = 22 и A = 45 логическое выражение ложно.

Приведем другое решение.

Выражение x&51 = 0 ∨ (x&41 = 0 → x&А = 0) должно быть истинным для любого х. Возьмем такое х, в котором установлены все биты, кроме тех, которые установлены в числе 41, например, для однобайтового представления х = 11010110₂.

Выражение x&51 = 0 будет ложно, поскольку и в числе х, и в числе 51 установлен первый бит (биты считаем справа налево, начиная с нуля).

Следовательно, истинной должна быть импликация во второй скобке. Но левая часть импликации x&41 = 0 истинна, поскольку ни один из битов, установленных в числе 41, в числе х не установлен.

Тогда истинной должна быть и правая часть импликации x&А = 0. Следовательно, в числе А могут быть установлены только те биты, которые не установлены в числе х, то есть нулевой, третий и пятый биты. Таким образом, наибольшее А = 101001₂ = 41₁₀.

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

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 63 do begin

if not (((x and 51) = 0) or ((x and 41) <> 0) or ((x and (63-A)) = 0)) then

Приведём аналогичное решение на языке Python.

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 41 и 51 хватит шести разрядов. Программа выведет ответ 41.

Логическая функция F задаётся выражением (x ≡ ( w ∨ y)) ∨ ((w → z ) ∧ (y → w)).

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

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Рассмотрим данное выражение. Преобразуем логическое выражение (x ≡ ( w ∨ y)) ∨ ((w → z ) ∧ (y → w)) и получим систему, при которой оно ложно:

Заметим, что первый и четвёртый столбцы таблицы истинности это y и w. Из условия следует, что переменная x соответствует второму столбцу таблицы истинности. Следовательно, третьему столбцу соответствует переменная z.

Приведем другое решение.

Составим таблицу истинности для выражения (x ≡ ( w ∨ y)) ∨ ((w → z ) ∧ (y → w)) и выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные будем записывать в порядке х, y, z, w. Получим следующие наборы: (0, 0, 0, 1), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0).

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

Первая строка таблицы (как минимум две единицы) может соответствовать либо набору (0, 1, 0, 1), либо набору (0, 1, 1, 0).

Третья строка таблицы также может соответствовать одному из этих двух наборов.

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

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

Следовательно, переменной х соответствует второй столбец.

Логическая функция F задаётся выражением ((x → y ) ≡ (z → w)) ∨ (x ∧ w).

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

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Рассмотрим данное выражение. Преобразуем логическое выражение ((x → y ) ≡ (z → w)) ∨ (x ∧ w) и получим систему, при которой оно ложно:

Заметим, что четвёртый столбец таблицы истинности это w, тогда первый столбец таблицы истинности это переменная z. Из условия следует, что переменная x соответствует третьему столбцу таблицы истинности, а переменная y соответствует второму столбцу таблицы истинности.

Приведем другое решение.

Составим таблицу истинности для выражения ((x → y ) ≡ (z → w)) ∨ (x ∧ w) и выпишем те наборы переменных, при которых данное выражение равно 0. В наборах будем записывать переменные в порядке х, y, z, w. Получим следующие наборы: (0, 0, 1, 0), (0, 1, 1, 0), (1, 0, 0, 0) и (1, 1, 1, 0).

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

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

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

Источник

• ← какое изобретение спасло эйфелеву башню
• на каких работах можно работать подросткам →