Задание 2 15097 егэ информатика

Здравствуйте, дорогие друзья! Сегодня разберём, как решать второе задание из ЕГЭ по информатике 2020.

Во втором задании ЕГЭ по информатике у нас обычно есть логическая функция, которая зависит от логических переменных. Логические переменные могут принимать только два значения: 0 (Ложь) или 1 (Истина).

С логическими переменными можно производить логические операции. При решении второго задания из ЕГЭ по информатике необходимо твёрдо знать каждую логическую операцию, и давайте рассмотрим их.

Порядок выполнения логических операций:

1. () — операции в скобках
2. ¬ — логическое отрицание
3. ∧ — логическое умножение
4. ∨ — логическое сложение
5. ⟶ — следование
6. ≡ — равнозначность

Передём к решению задач из ЕГЭ по информатике

Задача 1 (лёгкая)

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

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

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

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

Решение:

Видим, что у функции основным действием является логическое умножение. По таблице видно, что функция имеет значение только 1 . Логическое умножение даёт 1 (единицу) тогда, когда каждое выражение равно 1 (единице). Значит каждое выражение в нашей функции должно равняться единице.

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

Осталось определить положение w и x. Здесь делаем предположение, что в третьем столбце стоит w, а в 4-ом x. Проверяем построчно и видим, что во второй строчке при таком расположении из 1 следует 0, что в итоге приводит выражение (w → x) в 0, а у нас это выражение всегда должно быть 1 (единицей). Значит, мы предположение сделали неверное, и получается x — это третий столбец, а w — четвёртый.

Ответ: zyxw

Задача 2 (средний уровень)

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

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

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

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

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

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

Решение:

Определяем главную логическую операцию («главную скрипку»), которая соединяет разные выражения. Видим, что это логическое сложение.

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

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

Следующим слабым звеном является равносильность. Она должна «выдавать» 0 (ноль). Равносильность «выдаёт» 0 (ноль), когда переменные разные!

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

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

Таким образом, y и z (или z и y) будут столбцы первый и четвёртый! И теперь можно расставить недостающие значения в этих столбцах. Расставляем, чтобы были разные значения, а второй столбец получается x.

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

Тогда ответ будет равен yxwz.

Ответ: yxwz

Мощнейший метод для решения второго задания из ЕГЭ по информатике

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

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

Решение:

«Главной скрипкой» в нашей функции является логическое сложение, потому что соединяет два выражения ((x → y ) ∧ (y → w)) и (z ≡ ( x ∨ y)).

Тогда каждое выражение должно равняться 0(нулю).

Теперь кульминация мощнейшего метода. У нас всего 4 переменных. Выпишем все комбинации для 4-х переменных. Таблица будет точно такая же, как мы писали в первом задании (её очень легко составить). Всего получается 16 комбинаций (16 = 2⁴).

Теперь отметим зелёным плюсом те строчки, которые обращают выражение ((x → y ) ∧ (y → w)) в 0(ноль). Следующий шаг: Отметим галочкой те строчки, которые обращают в ноль второе выражение (z ≡ ( x ∨ y)) (Мы должны искать среди тех, которые уже отмечены плюсом).

При небольшой тренировке анализ подобных выражений занимает сущие секунды!

У нас получается 4 строчки, которые удовлетворяют нашей функции:

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

Переменная w имеет только одну 1(единицу). Значит, её ставим во второй столбец, потому что в первом и четвёртом уже по 2 единицы минимум, а третий уже занят z.

Теперь находим строчку c 1(единицей) в переменной w (Таблица данная в условии задачи) Кто в этой строчке будет иметь единицу (кроме w) — будет x! Это четвёртый столбец! Значит, x — это четвёртый столбец. Переменной y — достаётся первый столбец

Ответ: ywzx.

На этом всё! Сегодня рассмотрели теорию и основные методы для эффективного решения второго задания из ЕГЭ по информатике!

Пока!

Канал видеоролика: Физика Информатика

08.12.2021

Задача 1

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool f(int A, int B, int C, int D, int E, int F){
    return (!(!A || F) && B && !C && (!D || E));
}
int main() {
    int count = 0;
    for (int A = 0; A <= 1; ++A)
        for (int B = 0; B <= 1; ++B)
            for (int C = 0; C <= 1; ++C)
                for (int D = 0; D <= 1; ++D)
                    for (int E = 0; E <= 1; ++E)
                        for (int F = 0; F <= 1; ++F)
                            if (f(A, B, C, D, E, F) == false)
                                count++;
    cout << count;
    return 0;
}



  


                       
  

Задача 2

Задача 3

Задача 4

bool f(int x, int y, int z, int w){
    return (((x && z) || !x) && !w && y);
}
int main() {
    cout << "x y z w F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                for (int w = 0; w <= 1; ++w)
                    if (f(x, y, z, w) == true)
                        cout << x << " " << y << " "
                            << z << " " << w << " " << f(x, y, z, w) << endl;
    return 0;
}

Задача 5

bool f(int x, int y, int z, int w){
    return ((!y || w) || (!x && z));
}
int main() {
    cout << "x y z w F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                for (int w = 0; w <= 1; ++w)
                    if (f(x, y, z, w) == false)
                        cout << x << " " << y << " "
                            << z << " " << w << " " << f(x, y, z, w) << endl;
    return 0;
}



  


                       
  

Задача 6

Задача 7

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool f(int x, int y, int z){
    return ((x || y) && (!z || y));
}
int main() {
    cout << "x y z F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                    if (f(x, y, z) == false)
                        cout << x << " " << y << " "
                            << z << " " << f(x, y, z) << endl;
    return 0;
}

Задача 8

Задача 9

Задача 10

Задача 11

Задача 12

Основная тема задания №2 — алгебра логики. С неё и начнём. Для успешного решения номера вам важно знать 3 теоретических момента:

1. Основные логические операции

2. Порядок логических операций

3. Законы логики

Основные логические операции

1. Инверсия «НЕ»
Логическое отрицание
Обозначения: ¬А, Ā
Меняет значение на противоположное

2. Конъюнкция «И»
Логическое умножение

Обозначения: А∧В, А & В, А и В, AB

Принимает значение «истина», когда все значения единицы.

Хотя бы один 0 обнуляет всё.

3. Дизъюнкция «ИЛИ»
Логическое сложение

Обозначения: А∨В, А | В, А или В

Принимает значение «истина», когда хотя бы одна единица. «Ложь», когда все нули.

4. Импликация «Если, то»
Следование

Обозначения: А→В, А => В

Из истины следует истина, из лжи что угодно

5. Эквивалентность «Равны»
Тождество

Обозначения: А≡В, А В

Иcтина, когда значения одинаковы. Ложь, когда различны

Порядок логических операций

1. Действия в скобках
2. Инверсия
3. Конъюнкция
4. Дизъюнкция
5. Импликация
6. Эквивалентность

Законы логики

Законов логики существует огромное количество, но именно для ЕГЭ достаточно знать 10 законов из данной таблицы. Некоторые из них очевидные, некоторые придётся выучить.

Практика

Основных вариантов решения два: логические рассуждения, либо построение таблицы истинности. Иногда проще решать первым методом, иногда вторым.

Первый метод. Логические рассуждения.

Пример:

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

Решение:

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

Вывод:
y = 1
(x → z) = 1
¬w = 1,а значит w = 0

y всегда 1, такой столбик лишь один: y — переменная 4
w всегда 0, такой столбик лишь один: w — переменная 2

Для x и z остаётся переменная 1 и переменная 3. Осталось определится с порядком.
(x → z) = 1, значит не может быть набора, когда x = 1, а z = 0.
Во второй строчке перем1 = 1, а перем3 = 0. Следовательно, z — переменная 1, x — переменная 3.

z — переменная 1
w — переменная 2
x — переменная 3
y — переменная 4
Ответ: zwxy

Второй метод. Таблица истинности

Пример:

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

Решение:

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

y → w = 0

¬x ∧ z = 0

Объединяем все переменные в одну таблицу:

Соотносим её с таблицей из условия:
y — переменная 4
w — переменная 2
x — переменная 1
z — переменная 3
Ответ: xwzy

Консультация по английскому языку

Английский | Сегодня, 10:14

Разработчики экзаменационных материалов, учителя и выпускники, расскажут, как подготовиться к экзамену, об особенностях заданий в ЕГЭ и ответят на вопросы старшеклассников.

Этапы закрепощения крестьян в России

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

Задания 12-18 досрочного ЕГЭ по математике

3 примера по каждому заданию. Досрочный ЕГЭ по математике прошёл 28 марта.

Решение задания 2. Демоверсия ЕГЭ 2018 информатика:

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

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

 Видеоразбор

Показать решение:

Содержание:

• Объяснение задания 2 ЕГЭ по информатике
  • Таблицы истинности и порядок выполнения логических операций
• Решение заданий 2 ЕГЭ по информатике
  • Задания для тренировки

2-е задание: «Таблицы истинности»

Уровень сложности

— базовый,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 3 минуты.

  
Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы

Таблица истинности операции НЕ

Таблица истинности операции И (конъюнкция)

Таблица истинности операции ИЛИ (дизъюнкция)

Таблица истинности операции Импликация (если…, то…)

Таблица истинности операции Эквивалентность (тогда и только тогда, …)

Задание 2_11: Решение 2 задания ЕГЭ по информатике:

Логическая функция F задается выражением

(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w)

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

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

В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.

✎ Способ 1. Электронные таблицы Excel + Логические размышления:

• Отобразим перебор всех значений использующихся в выражении переменных (всю таблицу истинности). Поскольку в выражении используются 4 переменных, то строк таблицы будет 2⁴=16:



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

xwzy

✎ Способ 2. Программирование:
Язык python:

print('x y z w')
for x in 0, 1:
  for y in 0, 1:
    for z in 0, 1:
      for w in 0, 1:
        F = (not(x) or y or z) and (x or not(z) or not(w))
        if not(F):
          print(x, y, z, w)

• В результате будут выведены значения для F=0:

x y z w
0 0 1 1
0 1 1 1
1 0 0 0
1 0 0 1

• Сопоставив их с исходной таблицей, получим результат:

xwzy

  Язык pascalAbc.net:

begin
  writeln('x':7, 'y':7, 'z':7,'w':7);
  for var x:=false to true do
    for var y:=false to true do
      for var z:=false to true do
        for var w:=false to true do
          if not((not x or y or z) and (x or not z or not w)) then
            writeln(x:7, y:7, z:7,w:7);
end.

• В результате будут выведены значения для F=0:

      x      y      z      w
  False  False   True   True
  False   True   True   True
   True  False  False  False
   True  False  False   True

• Где false = 0, True = 1
• Сопоставив их с исходной таблицей, получим результат:

Ответ:

xwzy

✎ Способ 3. Логические размышления:
• Внешняя операция выражения — конъюнкция (∧). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:

(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w) = 1 когда:
1. (¬x ∨ y ∨ z) = 1 
И 
2. (x ∨ ¬z ∨ ¬w) = 1

• Общая идея дальнейшего решения такова: поскольку внешняя операция — конъюнкция, и результат ее истинен, когда оба сомножителя в скобках будут истинны (=1), то нам необходимо сначала составить все наборы таблицы истинности для обоих сомножителей в скобках. Затем, так как конъюнкция подразумевает пересечение, необходимо сопоставить обе таблицы истинности и выбрать для каждого подходящего набора первого сомножителя подходящий (подходящие) набор (наборы) второго сомножителя. НО! так как у нас в задании известны только наборы для F = 0, то мы сопоставлять будем наборы, которые возвращают ложь. Теперь подробно.
• Разобьём исходное выражение на две части и составим таблицу истинности отдельно для двух частей.
• Для сомножителя (¬x ∨ y ∨ z):

x	y	z	результат
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

• Получили ложь в одном наборе, так как дизъюнкция (∨) ложна только тогда, когда ложны все операнды.
• Для сомножителя (x ∨ ¬z ∨ ¬w):

x	z	w	результат
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

• Соответственно, опять получили ложь в одном наборе, когда ложны все операнды.
• Учтем, что нам нужно выбрать и «пересечь» (так как внешняя операция ∧) из всех наборов только те, которые возвращают ложь (так как по заданию известны только строки, где F = 0):



• Выпишем только пересеченные наборы:

x	y	z	w	F
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0

• Сравнив вторую строку заданной таблицы и вторую строку получившейся таблицы, находим, что x находится в первом столбце.

x	y	z	w	F
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0

x	???	???	???	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

• Сравнив первую и четвертую одинаковые строки получившейся таблицы, находим, что y в обоих случаях равен 0. Значит он находится в 4-м столбце.

x	y	z	w	F
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0

x	???	???	y	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

• Сравнив предпоследнюю и последнюю строки получившейся таблицы, там где x = 1, находим, что z в обоих случаях равен 0, тогда как w принимает значение и 1 и 0. Значит z находится в 3-м столбце.

x	y	z	w	F
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0

• Для w остается второй столбец:

x	w	z	y	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

Результат: xwzy

Задание 2_12: Разбор 2 задания ЕГЭ:

Миша заполнял таблицу истинности функции:

(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w)

но успел заполнить лишь фрагмент из трех различных ее строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z:

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

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.

Подобные задания для тренировки

✎ Способ 1. Логические размышления (бескомпьютерный вариант):

• Решим задание методом построения полной таблицы истинности.
• Посчитаем общее количество строк в таблице истинности и построим ее:

4 переменных -> 24 = 16 строк



• Для начала упростим выражение и выделим в нем две основные части относительно внешней операции (операция, которая выполняется последней).

(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w)
1. Избавимся от импликации:
¬(¬z ∧ ¬(x ≡ y)) ∨ ¬(y ∨ w)
2. Внесем знак отрицания в скобки (закон Де Моргана):
(z ∨ (x ≡ y)) ∨ (¬y ∧ ¬w) = 0
   1 часть = 0     2 часть = 0

* Исходное выражение должно быть = 0. Дизъюнкция = 0, когда оба операнда равны 0.

• Разбили исходное выражение на две части, теперь добавим столбцы для двух частей в таблицу истинности:



• Поясним: в первой части внешняя операция — дизъюнкция (ложна, когда оба операнда ложны). Во второй части внешняя операция — конъюнкция — ложна во всех случаях кроме того, когда оба операнда истинны:

(z ∨ (x ≡ y)) = 0 когда z = 0 и x ≡ y = 0

¬y ∧ ¬w = 0 когда:
1. ¬y = 0  ¬w = 0
2. ¬y = 1  ¬w = 0
3. ¬y = 0  ¬w = 1

• В результирующей таблице истинности получили только три набора значений переменных при которых выражение возвратит ложь.

x	y	w	z	F
0	1	0	0	0
0	1	1	0	0
1	0	1	0	0

• Сравнив их с исходной таблицей истинности, имеем:

y	w	x	z	F
1	1	0	0	0
1	0	0	0	0
0	1	1	0	0

• Таким образом, ответ: ywxz

Результат: ywxz

Язык PascalAbc.net:

begin
  writeln('x':7, 'y':7, 'z':7,'w':7);
  for var x:=false to true do
    for var y:=false to true do
      for var z:=false to true do
        for var w:=false to true do
          if not((not z and (x xor y)) <= not(y or w)) then
            writeln(x:7, y:7, z:7,w:7);
end.

• В результате будут выведены значения для F=0:

      x      y      z      w
  False   True  False  False
  False   True  False   True
   True  False  False   True

• Где false = 0, True = 1

Сопоставив их с исходной таблицей, получим результат: ywxz

Язык Python:

print ('x y z w')
for x in 0,1:
    for y in 0,1:
        for z in 0,1:
            for w in 0,1:
                F=(not z and not(x==y))<=(not(y or w))
                if not F:
                    print (x,y,z,w)

• В результате будут выведены значения для F=0:

x y z w
0 1 0 0
0 1 0 1
1 0 0 1

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

Результат: ywxz

🎦 Доступно видео решения этого задания (бескомпьютерный вариант):

  
📹 здесь
📹 Видеорешение на RuTube здесь

🎦 Видео (решение 2 ЕГЭ в Excel):

 
📹 здесь
📹 Видеорешение на RuTube здесь
📹 Видеорешение на RuTube здесь (Программирование)

Задание 2_10: Решение 2 задания ЕГЭ по информатике:

Логическая функция F задается выражением

¬a ∧ b ∧ (c ∨ ¬d)

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

Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c, d.

В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.

Задание 2_3: Решение задания 2. Демоверсия ЕГЭ 2018 информатика:

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

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

Подобные задания для тренировки

✎ Логические размышления (бескомпьютерный вариант):
• Внешним действием (последним выполняемым) в исходном выражении является дизъюнкция:

¬x ∨ y ∨ (¬z ∧ w)

• Вспомним таб. ист-ти для дизъюнкции (логическое сложение):

x1	x2	F
0	0	0
0	1	1
1	0	1
1	1	1

• Чтобы исходное выражение было истинным, нужно, чтобы хотя бы один из операндов равнялся единице. Т.е. нельзя наверняка сказать, где будет 1, а где 0 (¬x = 1 или 0, y = 1 или 0, ¬z ∧ w = 1 или 0).
• Функция же ложна только в одном случае, — когда все операнды ложны. Поэтому будем искать по признаку лжи.
• В исходной таблице истинности во всех строках функция ложна. Чтобы понять в каком столбце должна находиться та или иная переменная, возьмем за основу строку, в которой только одна единица или только один нуль.
• Строка №1: в ней одна единица — первый столбец. В исходной формуле, чтобы функция была ложна, необходимо, чтобы ¬x = 0, иными словами x = 1. Значит первый столбец соответствует переменной x.

Перем. 1	Перем. 2	Перем. 3	Перем. 4	F
x	???	???	???	F
1	0	0	0	0

• Строка №3: в ней один нуль — четвертый столбец. В исходной формуле, чтобы функция была ложна, необходимо, чтобы y = 0. Значит четвертый столбец соответствует переменной y.

Перем. 1	Перем. 2	Перем. 3	Перем. 4	F
x	???	???	y	F
1	1	1	0	0

• Строка №2: в ней второй столбец равен единице, а третий — нулю. В исходном выражении ¬z ∧ w должно равняться 0, чтобы функция была ложной. Конъюнкция истинна только тогда, когда оба операнда истинны (=1); в нашем случае функция должна быть ложной, но пойдем от обратного. Если ¬z = 1, т.е. z = 0, а w = 1, то это неверно для нашего случая. Значит всё должно быть наоборот: z = 1, а w = 0. Таким образом столбец второй соответствует z, а столбец третий — w.

x	z	w	y	F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

Результат: xzwy

✎ Способ 2. Программирование:
Язык pascalABC.NET:

begin
  writeln('x  ','y  ','z  ','w  ');
  for var x:=false to true do
    for var y:=false to true do
      for var z:=false to true do
        for var w:=false to true do
          if not(not x or y or(not z and w)) then
            writeln(x:7,y:7,z:7,w:7);
end.

Задание 2_13: Разбор досрочного егэ по информатике 2019

Логическая функция F задаётся выражением

(x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w

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

Задание 2_2: Задание 2 ЕГЭ по информатике:

Каждое из логических выражений F и G содержит 5 переменных. В табл. истинности для F и G есть ровно 5 одинаковых строк, причем ровно в 4 из них в столбце значений стоит 1.

Сколько строк таблицы истинности для F ∨ G содержит 1 в столбце значений?

Подобные задания для тренировки

• Поскольку в каждом из выражений присутствует 5 переменных, то эти 5 переменных порождают таблицу истинности из 32 строк: т.к. каждая из переменных может принимать оно из двух значений (0 или 1), то различных вариантов с пятью переменными будет 2⁵=32, т.е. 32 строки.
• Из этих 32 строк и для F и для G мы знаем наверняка только о 5 строках: 4 из них истинны (=1), а одна ложна (=0).
• Вопрос стоит о количестве строк = 1 для таб. истинности F ∨ G. Данная операция — дизъюнкция, которая ложна только в одном случае — если F = 0 и одновременно G = 0
• В исходных таблицах для F и G мы знаем о существовании только одного 0, т.е. в остальных строках может быть 1. Т.о., и для F и для G в 31 строке могут быть единицы (32-1=31), а лишь в одной — ноль.
• Тогда для F ∨ G только в одном случае будет 0, когда и F = 0 и G = 0:

№	F	G	F ∨ G
1	0	0	0
2	0	1	1
…	…	…	1
32	…	…	1

• Соответственно, истинными будут все остальные строки:

32 - 1 = 31

Результат: 31

Задание 2_6: Решение 2 задания ЕГЭ по информатике:

Каждое логическое выражение A и B зависит от одного и того же набора из 7 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы.

Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?

• Полная таблица истинности для каждого из выражений A и B состоит из 2⁷ = 128 строк.
• В четырех из них результат равен единице, значит в остальных — 0.
• A ∨ B истинно в том случае, когда либо A = 1 либо B = 1, или и A и B = 1.
• Поскольку А = 1 только в 4 случаях, то чтобы получить максимальное количество единиц в результирующей таблице истинности (для A ∨ B), расположим все единицы т.и. для выражения A так, чтобы они были в строках, где B = 0, и наоборот, все строки, где B = 1, поставим в строки, где A = 0:

A	B
1	0
1	0
1	0
1	0
0	1
0	1
0	1
0	1
0	0
…	…

• Итого получаем 8 строк.
• Если бы в задании требовалось найти минимальное количество единиц, то мы бы совместили строки со значением = 1, и получили бы значение 4.

Результат: 8

Задание 2_7: Решение 2 задания ЕГЭ по информатике:

Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц.

Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?

• Полная таблица истинности для каждого из выражений A и B состоит из 2⁸ = 256 строк.
• В шести из них результат равен единице, значит в остальных — 0.
• A ∧ B ложно в том случае, когда:

  A ∧ B = 0 если:
  
  1. A = 0, B = 1 
  2. B = 0, A = 1
  3. A = 0 и B = 0
  

• Во всех случаях там где А=1 может стоять B=0, и тогда результат F = 0. Поскольку нам необходимо найти максимально возможное число нулей, то как раз для всех шести А=1 сопоставим B=0, и наоборот, для всех шести возможных B=1 сопоставим A=0

A	B	F
1	0	0
1	0	0
1	0	0
1	0	0
0	1	0
0	1	0
0	1	0
0	1	0
0	0	0
…	…	…

• Поскольку строк всего 256, то вполне возможно, что все 256 из них возвратят в результате 0

Результат: 256

Задание 2_4: 2 задание:

Дан фрагмент таблицы истинности выражения F.

Каким из приведённых ниже выражений может быть F?
1) ¬x1 ∧ x2 ∧ ¬x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
2) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
4) x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7

• В первом внешняя операция (выполняется последней) — конъюнкция. Начнем рассмотрение с нее. Соответственно, проверяем по второй строке таб. ист-ти, там где F = 1, так как в таком случае все аргументы должны быть истинными (см. таб. истинности для конъюнкции).
• Если мы подставим в нее все аргументы выражения, то функция действительно возвращает истину. Т.е. пункт первый подходит:



• Но проверим на всякий случай остальные.
• Второй пункт проверяем по первой и третьей строке, так как основная операция — дизъюнкция — ложна только в том случае, если все аргументы ложны (см. таб. истинности для дизъюнкции). Проверяя по первой строке, сразу видим, что x1 в ней равен 1. В таком случаем функция будет = 1. Т.е. этот пункт не подходит:



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



• Четвертый пункт проверяем по первой и третьей строкам. В первой — x1 = 1, т.е. функция должна быть равна 1. Т.е. пункт тоже не подходит:



• Таким образом, ответ равен 1.

Результат: 1

Задание 2_8: Решение 2 задания ЕГЭ по информатике:

Дано логическое выражение, зависящее от 5 логических переменных:

(¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5)

Сколько существует различных наборов значений переменных, при которых выражение истинно?

1) 0
2) 30
3) 31
4) 32

Подобные задания для тренировки

• Поскольку выражение включает 5 переменных, то таб. ист-ти состоит из 2⁵ = 32 строк.
• Внешней операцией (последней) является конъюнкция (логическое умножение), а внутри скобок — дизъюнкция (логическое сложение).
• Обозначим первую скобку за А, а вторую скобку за B. Получим A ∧ B.
• Найдем сколько нулей существует для таб. истинности:

   A  B  F
1. 0  0  0
2. 0  1  0
3. 1  0  0

Теперь рассмотрим каждый случай отдельно:

• 1 случай. 0 0 : A = 0 и B = 0, то есть:

¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5 = 0
и
x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 = 0.

• Обратим внимание, что во вторых скобках везде стоит инверсия переменных, которые находятся в первых скобках. Таким образом, это невозможно, так как дизъюнкция равна нулю, когда все операнды равны нулю. А если в первых скобках все 0, то из-за инверсий во вторых скобках все 1. То есть этот случай нам не подходит.
• 2 случай. 0 1 : нам он подходит, так как если первая скобка возвратит 0, то вторая вернет 1.
• 3 случай. 1 0 : нам он подходит, так как если вторая скобка возвратит 0, то первая вернет 1.
• Итого получаем два случая, когда исходное выражение вернет 0, т.е. две строки таблицы истинности.
• Тогда получим количество строк, с результатом равным 1:

32 - 2 = 30, что соответствует номеру 2

Результат: 2

Задание 2_5: Решение 2 задания ЕГЭ по информатике:

Дан фрагмент таблицы истинности для выражения F:

Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x3 не совпадает с F.

Подобные задания для тренировки

• Полная таблица истинности будет иметь 2⁶ = 64 строк (т.к. 6 переменных).
• 4 из них нам известны: в них x3 два раза не совпадает с F.
• Неизвестных строк:

 
64 - 4 = 60

• В неизвестных x3 может не совпадать с F, кроме того, в двух известных x3 не совпадает с F. Соответственно максимально возможное число строк с несовпадающими x3 и F, будет:

60 + 2 = 62

Результат: 62

Задание 2_9: Решение 2 задания ЕГЭ по информатике:

Дан фрагмент таблицы истинности для выражения F:

Каким выражением может быть F?
1) x1 ∧ (x2 → x3) ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
2) x1 ∨ (¬x2 → x3) ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
3) ¬x1 ∧ (x2 → ¬x3) ∧ x4 ∧ ¬x5 ∧ x6 ∧ x7
4) ¬x1 ∨ (x2 → ¬x3) ∨ x4 ∨ x5 ∨ x6 ∧ x7

• Рассмотрим отдельно каждый пункт и найдем последнюю операцию, которая должна быть выполнена (внешнюю).

1 пункт:

(((x1 ∧ (x2 → x3) ∧  ¬x4) ∧ x5) ∧ x6)  ∧ ¬x7

• Внешняя операция — конъюнкция. Ее проще проверять по строке, в которой F = 1 (значит все сомножители должны быть равны 1).
• Возьмем 3-ю строку, в ней x4=1. В нашем выражении х4 с отрицанием, т.е. = 0. Для конъюнкции, когда хоть один из сомножителей равен нулю, выражение вернет в результате 0, а у нас в строке 1. Т.е. этот пункт не подходит:


2 пункт:

(((x1 ∨ (¬x2 → x3) ∨  ¬x4) ∨ ¬x5) ∨ x6)  ∨ ¬x7

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


3 пункт:

(((¬x1 ∧ (x2 → ¬x3) ∧  x4) ∧ ¬x5) ∧ x6) ∧ x7

• Последняя операция — конъюнкция. Ее проще проверять по строке, в которой F = 1 (значит все сомножители должны быть равны 1).
• Возьмем 2-ю строку: в ней х7 = 0, в рассматриваем пункте х7 без отрицания, т.е. так и остается равным нулю. При умножении выражение вернет в результате 0. В таблице — 1. Т.е. пункт тоже не подходит:



• Единственным подходящим вариантом остался пункт под номером 4 (на всякий случай всегда стоит проверить и его).

Результат: 4

Задание 2_1: Задание 2 ЕГЭ по информатике:

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

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

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы.

• Сначала необходимо рассмотреть логическую операцию, которую мы будем выполнять в последнюю очередь — это логическое И (конъюнкция) или ∧. То есть внешнюю операцию:

(y → x) ∧ (y → z) ∧ z

• Конъюнкцию легче рассматривать по тем строкам таб. ист-ти, в которых F = 1, т.е. №3, №4, и №8
• Поскольку для конъюнкции функция истинна только тогда, когда все переменные истинны, то необходимо чтобы отдельно каждая скобка была истинна ((y → x) = 1 и (y → z)=1) и переменная z тоже была истинной (=1)

(y → x) ∧ (y → z) ∧ z = 1
   если: 
1. (y → x) = 1
2. (y → z) = 1
3. z = 1

• Поскольку с выражениями в скобках сложней работать, определим сначала какому столбцу соответствует z. Для этого выберем строку (№3), где F = 1, а в остальных ячейках только одна единица, остальные — нули.

№	Перем. 1	Перем. 2	Перем. 3	F
3	0	1	0	1

• Таким образом, делаем вывод, что z находится во втором столбце (отсчет ведем слева):

№	Перем. 1	Перем. 2	Перем. 3	F
_	???	z	???	F

• Дальше нам необходимо рассмотреть две скобки, в которых находится операция импликации: (y → x) и (y → z). Обе эти скобки должны возвращать истину (=1). В таб. истинности для импликации, функция возвращает в результате 1 тогда, когда:
• вторая переменная (заключение) равна 1 (первая при этом может быть любой),
• вторая переменная (заключение) равна 0, а первая обязательно должна быть равна тоже 0.
• Рассмотрим скобку (y → x) и строку 4 таблицы:

№	Перем. 1	z	Перем. 3	F
4	0	1	1	1

• Для этой строки только y может быть равен 0, т.к. если x = 0, тогда y=1, и скобка в результате возвратит ложь (1 → 0 = 0). Соответственно, y находится в первом столбце. А x значит должен стоять в третьем:

Результат: yzx