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

💬 (0)

12.03.2024

Сборник необходимой теории и практики к заданию №2 ЕГЭ 2024 по информатике «Анализ таблиц истинности логических выражений».

• Вся теория по информатике для ЕГЭ
• Тренировочные варианты ЕГЭ по информатике

Формулировка задания №2 ЕГЭ 2024 из демоверсии ФИПИ

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

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

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

Самое необходимое по заданию №2 в формате видеоурока  

Алгебра логики

Алгебра логики (алгебра высказываний) — это формальная логическая теория, раздел математической логики, разработанный в XIX в. в трудах английского математика Джорджа Буля. В алгебре логики используются алгебраические методы для решения логических задач.

• Объектами алгебры логики являются высказывания.

Алгебра логики предоставляет математический аппарат, с помощью которого записывают (кодируют, формализуют), упрощают, вычисляют и преобразовывают логические высказывания.

• Логическое высказывание — это повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. В алгебре логики отвлекаются от содержания (смысла) высказывания и рассматривают лишь его значение.

В булевой алгебре (алгебре логики) возможны только два значения для логических высказываний и логических констант:

• ИСТИНА — обозначается как True или 1;
• ЛОЖЬ — обозначается как False или 0.

Примеры высказываний: «сегодня теплое утро», «√5 — иррациональное число».

Не являются высказываниями следующие предложения:

• «пойдет ли сегодня дождь?» — вопросительное предложение, не имеющее
  своим значением ИСТИНА или ЛОЖЬ;
• «сделайте домашнее задание» — повелительное предложение; невозможно определить значение высказывания — истинно оно или ложно;
• «это предложение ложно» — противоречивое утверждение.

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

Например: А — для высказывания «Андрей Иванов — врач», В — «Андрей Иванов — шахматист», x1 — «этот карандаш красного цвета», х2 — «этот карандаш синего цвета».

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

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

В алгебре логики существуют три основные операции. 

Логическое отрицание (инверсия, логическое НЕ)

Смысл операции: результат меняется на противоположный (вместо истины — ложь, вместо лжи — истина).

Обозначается: ¬A, Ā, not A, не A.

Высказывание ¬A истинно при ложном A и ложно при истинном A. 

Логическое сложение (дизъюнкция, логическое ИЛИ)

Смысл операции: результат — истина, если хотя бы один операнд — истина.

• Операнд — то значение или та переменная, над которым (которой) осуществляется операция.

Обозначается: A ∨ B, A + B, A or B, A или B.

Высказывание A ∨ B ложно тогда и только тогда, когда оба высказывания A и B ложны.

Логическое умножение (конъюнкция, логическое И)

Смысл операции: результат — истина, если оба операнда — истина.

• Операнд — то значение или та переменная, над которым (которой) осуществляется операция.

Обозначается: A ∧ B, A ⋅ B, A & B, A and B, AB, A и B.

Высказывание A ∧ B истинно тогда и только тогда, когда оба высказывания A и B истинны.

Остальные операции алгебры логики выражаются через первые три операции — отрицание, конъюнкцию, дизъюнкцию. Перечислим их.

Логическое следование (импликация)

Смысл операции: из лжи может следовать что угодно, а из истины — только истина.

Обозначается: A → B, A ⇒ B.

Высказывание A → B ложно только тогда, когда A истинно, а B ложно.

Важно: в операции импликации посылка А не обязана быть истинной, в отличие от логического оператора в языках программирования «если A то B».

Импликация выражается через дизъюнкцию и отрицание: A → B = ¬A ∨ B. 

Эквивалентность (равносильность, необходимость, необходимость и достаточность)

Смысл операции: результат — истина, если операнды одинаковы.

Обозначается: A ⇔ B, A ≡ B.

Высказывание A ⇔ B истинно тогда и только тогда, когда значения A и B совпадают.

Эквивалентность выражается через отрицание, дизъюнкцию и конъюнкцию: A ⇔ B = (¬A ∨ B) ∧ (¬B ∨ A).

Исключающее ИЛИ (сложение по модулю 2, строгая дизъюнкция)

Смысл операции: результат — истина, если операнды различны.

Обозначается: A ⊕ B, A ≠ B, A XOR B.

Высказывание A ⊕ B истинно, когда A и B не равны.

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

Порядок выполнения логических задаётся круглыми скобками. При отсутствии скобок порядок выполнения операций следующий:

• отрицание,
• конъюнкция,
• дизъюнкция,
• исключающее ИЛИ,
• импликация,
• эквивалентность.

Логическая формула и логическая функция

Составное высказывание (логическая формула) состоит из нескольких высказываний, соединённых логическими операциями. Исходные высказывания могут быть логическими переменными или логическими константами (имеющими постоянное значение ИСТИНА или ЛОЖЬ).

Логическая функция определяется на множестве логических переменных и логических констант, принимающих значение ИСТИНА или ЛОЖЬ. Значение функции вычисляется в результате выполнения логических операций с (или над) логическими операндами.

Например: F(A, B, C) = A ∧ (¬B ∨ C); F(x1, x2, x3) = ¬x1 v x2 ∧ ¬x3.

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

Таблицы истинности простейших логических функций

 

Основные законы алгебры логики

Закон	Для ИЛИ	Для И
Коммутативный (переместительный): логические переменные можно менять местами	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Ассоциативный (сочетательный): логические переменные в дизъюнкциях и конъюнкциях можно объединять в группы	(A ∨ B) ∨ C = A ∨ (B ∨ C)	(A ∧ B) ∧ C = A ∧ (B ∧ C)
Дистрибутивный (распределительный): одинаковые переменные в дизъюнкциях и конъюнкциях можно выносить за скобки	(A ∨ B) ∧ C = (A ∧ C) ∨ (B ∧ C)	(A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C)
Закон непротиворечия: высказывание может быть только истинным или ложным, третьего не дано		A ∧ ¬A = 0
Закон исключения третьего: либо высказывание, либо его отрицание должно быть истинным	A ∨ ¬A = 1
Правила де Моргана	¬ (A ∨ B) = ¬A ∧ ¬B	¬ (A ∧ B) = ¬A ∨ ¬B
Законы склеивания	(A ∧ B) ∨ (¬A ∧ B) = B	(A ∨ B) ∧ (¬A ∨ B) = B
Закон двойного отрицания: двойное отрицание исключает отрицание	¬¬A = A
Закон рефлексивности (идемпотентности)	A ∨ A = A	A ∨ A = A
Контрапозиции	A → B = ¬B → ¬A
Снятие импликации	A → B = ¬A ∨ B
Снятие эквивалентности	A ↔ B = (A ∧ B) ∨ (¬A ∧ ¬B) A ↔ B = (A ∨ ¬B) ∧ (¬A ∨ B)
Свойства логических констант 1 и 0	A ∧ 0 = 0, A ∧ 1 = A, A ∨ 0 = A, A ∨ 1 = 1
Закон поглощения	A ∨ (A ∧ C) = A	A ∧ (A ∨ C) = A

Построение таблиц истинности для логических выражений

Таблица истинности логической формулы (функции) выражает соответствие между всеми возможными наборами значений логических переменных и значением функции.

Для функции от двух переменных существует 2² = 4 комбинации наборов значений переменных; для функции трёх переменных – 2³ = 8; для функции четырёх переменных – 2⁴ = 16 комбинаций значений наборов переменных. 

В общем случае для функции от N переменных количество строк M в таблице истинности вычисляется по формуле: M = 2^N. 

Последовательность построения таблицы истинности:

1. определить количество N используемых переменных в логическом выражении;
2. вычислить количество всевозможных наборов значений переменных M = 2^N, равное количеству строк в таблице истинности;
3. подсчитать количество логических операций в логическом выражении и определить число столбцов в таблице, которое равно сумме числа переменных и количества логических операций;
4. озаглавить столбцы таблицы названиями переменных и названиями логических операций;
5. заполнить столбцы логических переменных наборами значений, например, от 0000 до 1111 с шагом 0001 в случае для четырёх переменных;
6. заполнить таблицу истинности по столбцам со значениями промежуточных операций слева направо;
7. заполнить окончательный столбец значений для функции F.

Как решать задание №2?

Пример 1 (первый способ решения):

Пример 1 (второй способ решения):

Пример 2:

Пример 3: 

Примеры заданий №2

Пример 1. Миша заполнял таблицу истинности логической функции F

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

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

				F
1	1			0
		1	0	0
0	1	1	0	0

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

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

Пример 2. Миша заполнял таблицу истинности логической функции F

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

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

				F
		0	0	1
1	0	0	1	1
1	0			1

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

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

Пример 3. Миша заполнял таблицу истинности логической функции F

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

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

				F
0		0		1
0				1
	0			1

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

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

Пример 4. Миша заполнял таблицу истинности логической функции F

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

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

				F
1		0	0	1
	1			1
1	0	1	0	1

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

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

Ответы к примерам заданий

1. zyxw; 2. wzyx; 3. zyxw; 4. zyxw.

Ниже представлены замечательные материалы, подготовленные Поляковым Константином Юрьевичем, доктором технических наук. В них вы найдёте всё самое полезное для себя — теория, решения заданий и практика. Все материалы для ЕГЭ по информатике: https://kpolyakov.spb.ru/school/ege.htm. 

Смотреть в PDF:

Для просмотра установите Adobe Reader и обязательно вернитесь для просмотра файла :).

Или прямо сейчас: cкачать в pdf файле.