Теоретические основы информатики · 1 балл
Таблицы истинности
Восстановить порядок переменных по фрагменту таблицы истинности логической функции.
Алгебра логики: логические операции, таблицы истинности, выражения и тождества.
Основание: проект спецификации и кодификатора КИМ 2027. Открыть документы
Теория
Задание 2 проверяет умение работать с логической функцией: прочитать выражение, построить таблицу истинности и восстановить, какой переменной соответствует каждый столбец. В 2027 году формат прежний: 1 первичный балл, раздел «Теоретические основы информатики».
Минимум для задания 2
В задании 2 используются пять операций. Для каждой достаточно помнить единственный случай, когда результат отличается от очевидного.
A → B = ¬A ∨ BA ≡ B = (A ∧ B) ∨ (¬A ∧ ¬B)A ≡ B = ¬(A ∧ ¬B) ∧ ¬(¬A ∧ B)Если скобок нет, операции выполняются в таком порядке. Импликация и эквивалентность — самые слабые, поэтому в записи без скобок их выполняют последними.
Для n переменных полная таблица содержит 2^n строк: у четырёх переменных — 16, у пяти — 32. В условии дают только фрагмент, причём строки в нём не повторяются.
Упрощение выражения часто делает очевидным, при каких наборах F = 1 или F = 0. Эти формулы стоит держать в голове.
¬(A ∧ B) = ¬A ∨ ¬B¬(A ∨ B) = ¬A ∧ ¬BA → B = ¬A ∨ BПрежде чем перебирать, поищите во фрагменте закономерности: они часто дают ответ без вычислений.
Ответ зависит от формулировки, и проверяется он автоматически, поэтому важна каждая буква.
Разбор примера
Дана функция F = (a → b) ∧ (b → ¬c) ∧ (¬c → d) и фрагмент таблицы, в котором все строки имеют F = 1. Восстановим столбцы.
| ? | ? | ? | ? | F |
|---|---|---|---|---|
| 1 | · | · | · | 1 |
| 1 | · | 1 | · | 1 |
| 1 | · | 1 | 1 | 1 |
| a | b | c | d | F |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
Ответdcba
Способы решения
Методы собраны по решениям задания 2 из базы Kompege. Начните с того, что именно нужно найти в условии.
когда во всех строках одно и то же F
Когда использовать: Фрагмент содержит только строки с F = 1 или только с F = 0, а выражение разбирается по частям: конъюнкции, дизъюнкции, импликации.
Пример
В задаче № 9905 F = (x → y) ∧ (y → z) ∧ (z → w). Конъюнкция импликаций истинна только при x ≤ y ≤ z ≤ w, то есть на наборах 0000, 0001, 0011, 0111 и 1111. Первая и последняя строки не подходят под фрагмент, остаются 0001, 0011 и 0111: в них w всегда 1, а x всегда 0. Значит, первый столбец — w, второй — x. Строка (1, 0, 1, 0) соответствует набору 0011, поэтому третий столбец — z, четвёртый — y.
Ответwxzy.
По мотивам задачи № 9905 (база Kompege).
когда наборы уже выписаны
Когда использовать: Есть список наборов, где F = 1 или F = 0, и нужно быстро разложить их по столбцам фрагмента.
Пример
В задаче № 14297 F = ¬i ∧ (f → o) ∧ n истинна на трёх наборах: 0100, 0101 и 0111 в порядке i, n, f, o. Значит, n равна 1 три раза, o — два раза, f — один раз, i — ни разу. Во фрагменте третий столбец содержит три единицы, второй — две, первый — одну, а четвёртый не содержит единиц вовсе: получаем f, o, n, i.
Ответfoni.
По мотивам задачи № 14297 (база Kompege).
когда переменных три или четыре
Когда использовать: Нужно увидеть все строки функции целиком: так проще отсеять наборы, которых во фрагменте быть не может.
Пример
В задаче № 11220 F = (x → y) ∧ z ∧ ¬w. Из F = 1 сразу следует z = 1 и w = 0, поэтому подходят только наборы 0010, 0110 и 1110 в порядке x, y, z, w. В третьей строке фрагмента три единицы: (0, 1, 1, 1). Среди наборов только 1110 содержит три единицы, а единственный нуль в нём — это w, значит, первый столбец — w. Первая строка (0, 1, ·, 1) не может совпасть с третьей, поэтому она равна 0110: третий столбец — x, четвёртый — y. Вторая строка даёт 0010 и подтверждает, что второй столбец — z.
Ответwzxy.
По мотивам задачи № 11220 (база Kompege).
универсальный способ
Когда использовать: Сложное выражение, 4–5 переменных и много пустых ячеек: вручную разбор получается долгим.
Пример
Шаблон для учебного примера: шесть неизвестных ячеек, четыре переменные.
from itertools import product, permutations
def f(a, b, c, d):
return (a <= b) and (b <= (not c)) and ((not c) <= d)
for a1, a2, a3, a4, a5, a6 in product([0, 1], repeat=6):
table = [(1, a1, a2, a3), (1, a4, 1, a5), (1, a6, 1, 1)]
if len(table) != len(set(table)):
continue
for p in permutations("abcd"):
if all(f(**dict(zip(p, row))) for row in table):
print(*p, sep="")Ответdcba
Шаблон по мотивам решений задач № 11220, 11606, 16249 и 27964.
когда формула громоздкая
Когда использовать: Выражение содержит импликации, эквивалентности и отрицания целых скобок — после преобразования видно, когда F = 0.
Пример
В задаче № 20919 нужно найти набор, при котором (K ∨ M) → (M ∨ ¬L ∨ N) ложно. Импликация ложна только при истинной левой и ложной правой части: K ∨ M = 1, а M = 0, L = 1, N = 0. Отсюда K = 1.
Ответ1100.
По мотивам задачи № 20919 (база Kompege).
когда ответ — не строка букв
Когда использовать: Спрашивают количество вариантов, значения неизвестных или добавляют условие на столбцы и строки.
По мотивам задач № 6837, 10915, 11680, 12643, 13974 и 14497.
Шпаргалка: формулировка → метод
| В условии | Что делать |
|---|---|
| «какому столбцу соответствует переменная» | сопоставить картину 0/1 или перебрать permutations |
| все строки с F = 1 | выписать наборы, где функция истинна, и вложить их во фрагмент |
| есть пустые ячейки | перебор неизвестных через product |
| «сколько вариантов расстановки» | посчитать подходящие перестановки |
| «значения a, b, c, d» | перебор неизвестных, ответ цифрами подряд |
| «значения строк возрастают» | сравнивать строки как двоичные числа |
| переменных больше четырёх | полная таблица на 32 строки, перебор обязателен |
| ответ — буквы | без пробелов и запятых, слева направо |
Видеоразборы по теме
Видеоразборы открытого курса КомпЕГЭ; для заданий 8–12 и 27 — дополнительные разборы демоверсии 2027.
По базе Kompege: 1 069 задач, 36 решений (29 программных и 7 текстовых) и 208 видеоразборов по заданию 2. При подготовке методов использованы решения задач № 6837, 9905, 10915, 11220, 11606, 11680, 12643, 13974, 14297, 14497, 16249 и 20919; примеры переработаны в учебные.
Разборы из видео
Условия и код показаны в кадре в конце соответствующего фрагмента. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие.
разбор из видео · 2024
Логическая функция F = (y ∨ x) ≡ ((y → w) ∨ ¬z). Дан фрагмент таблицы истинности с неповторяющимися строками. Определите, какому столбцу соответствует каждая переменная.
from itertools import *
def f(x, y, w, z):
return (y or x) == ((y <= w) or (not z))
t = [(1, 0, 0, 0), (0, 1, 0, 0), (1, 0, 1, 0)]
for p in permutations('xywz'):
if [f(**dict(zip(p, r))) for r in t] == [0, 0, 0]:
print(p)Ответzwyx
Полный архив
По одному пункту на каждую главу: условие или код из кадра, ответ и ссылка. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие; номер берётся из кадра. Текст с экрана распознан автоматически, служебные строки и артефакты удалены; если текст нечитаем, остаются название, таймкод и ссылка.
Логическая функция F задаётся выражением (x > у) л (y > 2). Ha рисунке приведён фрагмент таблицы истинности функции F. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных, у, 2. т о т о F Г т 133) Логическая функция F задаётся выражением (-хлул2) v (7x л 2). На рисунке приведён "фрагмент таблицы истинности функции Е, содержащий все наборы аргументов, при которых функция F истинна.
В этом фрагменте — теория или пояснение; решение показано в видео.
В этом фрагменте — теория или пояснение; решение показано в видео.
В этом фрагменте — теория или пояснение; решение показано в видео.
Определите какому столбцу таблицы соответствует каждая из переменных w X; Z В ответе напишите буквы w x; в котором идут соответствующие им столбцы (сначала буква соответствующая первому столбЦу: затем буква соответствующая второму столбцу; и тд ) Буквы ответе пишите подряд никаких разделителей между буквами ставить не нужно
Определите, какому столбцу таблицы соответствует каждая из переменных W, X, у, 2. В ответе напишите буквы W, х, у, 2 В ТОМ порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, ницаких разделителей между буквами ставить не нужно.
какому столбцу таблицы истинности Функции соответствует каждая мэ переменных 1; затем буква соответствующая 2-му столбцу: затем буква соответствующая 3 му столбцу) Буквы ответе пишите подряд никаких разделителей между буквами ставить не нужно
В ответе напишите буквы " 1; 9, = в том порядке котором идут соответствующие им сТОлбцы: Буквы ответе пишите подряд никаких разделителей между буквами ставить не нужно.
Логическая функция F задаётся следующим выражением (—a \/ 6) л (е + a) ^ (Ел а ел —). На рисунке "приведён частично заполненный фрагмент таблицы истинности функции Р", содержащий неповторяющиеся строки. "Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных а, 5, c, 1. В ответе напишите буквы a,b,c, в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд. никаких разделителей между буквами ставить He нужно.
Определите какому столбцу таблицы истинности функции F соответствует каждая из переменных u, b c ! В ответе напишите буквы d.b c t в том порядке котором идут соответствующие им столбцы: Буквы ответе пишите подряд никаких разделителей между буквами ставить не нужно:
(А Богданов) Миша заполнял таблицу истинности логической функции w \/ (у — =) Л =, HO успел заполнить лишь фрагмент из трёх различных её строк даже He указав, какому столбцу таблицы соответствует каждая из переменных и, г, у, 2. "Фрагмент таблицы истинности Функции Е содержит неповторяющиеся строки. Определите, какому столбцу таблицы истинности "функции F соответствует каждая из переменных w, 2, у, =.
for x in
for y in
for m in 0,1:
for z in 0,1:
print(x,y,w,z)Логическая функция F задаётся выражение: строки таблицы истинности функции Е. Определите, какому столбцу таблицы истинности соответствует каждая из В ormere напишите буквы м, х у, 2 в том порядке, в котором идуг соответствующие им столбцы (сначала буква, соответствующая первому столбцу, затем буква, соответствующая второму столбцу, и т.д). Буквы вответе пишите подряд, никаких разделителей между буквами ставить
В этом фрагменте — теория или пояснение; решение показано в видео.
Логическая функция F задаётся выражением (x > у) л (y > 2). Ha рисунке приведён фрагмент таблицы истинности функции F. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных, у, 2. т о т о F Г т 133) Логическая функция F задаётся выражением (-хлул2) v (7x л 2). На рисунке приведён "фрагмент таблицы истинности функции Е, содержащий все наборы аргументов, при которых функция F истинна.
A 146) Логическая функция F задаётся выражением (x > у) A (> 2). Ha рисунке приведён фрагмент a таблицы истинности функции Р. Определите, какому столбцу таблицы истинности функции F (yd ale, Е соответствует каждая из переменных, у, 2.
A 146) Логическая функция F задаётся выражением (x > у) л (> 2). Ha рисунке приведён фрагмент таблицы истинности функции F. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных, у, 2. "фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна.
from itertools import *
def F(x,y,z):
return (xeey)and(y<=2)
table = [(1,0,0),(1,0,1)]
for p in permutations('xyz'):
if [f(+xdict(zip(p,row))) for row in table]==[0,1]:
print(p)
table = [(0,0,0),(1,0,0),(1,1,0)]
for p in permutations(*xyz’):16) Логическая функция Р задаётся выражением уху (С2лм). На рисунне приведён gparmenr (W's 'X') "2", "У") a таблицы истинности функции F, содержащий все наборы аргументов, при ноторых функция Роботы
164) Логическая функция F задаётся выражением yx v (2 AW) Ha рисунке приведён фрагмент "таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F приведён фрагмент таблицы истинности финцции, содержащий наборы аргументов, при которых функция Е истинна.
from itertools import *
return (not y) or x or ((not z) and w)
table = [(0,0,0,4),(0,0,1,1),(1,0,1,1)]
print(p)
for p in permutations( ‘abcd’ ):196) Логическая фуниция Е задаётся выражением ((y—>x) v ("z A w)) я (и =х). Ha рисунке приведён "частично заполненный фрагмент таблицы истинности функции Г, содержащий неповторяющиеся роки, Определите, какому столбцу таблицы истинности функции F соответствует каждая из Boreete напишите буквы 7, y, = W 8 ТОМ порядке, в котором идут соответствующие им столбцы. Буквы в отоете пишите подряд, никаких разделителей между буквами ставить не нужно. 193) Логическая функция F задаётся выражением (x =—y) —> ((x Aw) =2). На рисунке приведён "частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует
from itertools import *
def f(x,y,wyz)t
return ((y<=x)or((not 2) and w))==(w==x)
if len(table)==len(set(table)):
for p in permutations( 'xywz'):
if [f(eedict(zip(p,r))) for r in table]=
print(p)Определите, какому столбцу таблицы истинности фучиции F соответствует каждая из переменных, К И ОСИ ПОСЛ И то о [т ооо С i Boroere напишите буквы x, = W 8 ТОМ NOpRAKE, в КОТОРОМ идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить ме нужно.
Функция F задана выражением x Vy Vz, а фрагмент таблицы истинности имеет вид: В этом случае переменные можно расставить любым способом, значит, ответом будет число 6. Шубинкин) Логическая функция F задаётся выражением x A (> 2) vw. Ниже приведён частично заполненный фрагмент таблицы истинности этой функции, содержащий неповторяющиеся строки. Сколькими способами можно поставить в соответствие переменные W, Пример.
Шубинкин) Логическая функция F задаётся выражением (х= y)— (== w). Ниже приведён частично заполненный фрагмент таблицы истинности этой функции, содержащий "неповторяющиеся строки, Сколькими способами можно поставить в соответствие переменные Ww, 3 2 столбцам таблицы истинности функции F, опираясь на информацию из данного фрагмента? Функция F задана выражением x Vy Vz, а фрагмент таблицы истинности имеет вид: В этом случае переменные можно расставить любым способом, значит, ответом будет число 6. Шубинкин) Логическая функция F задаётся выражением x A (> 2) Ум. Ниже приведён "частично заполненный фрагмент таблицы истинности этой функции, содержащий неповторяющиеся строки.
from itertools import *
def f(x,y,w,z):
table = [(0,0,0,1),(1,1,1,0)]
for p in permutations( 'xywz'):Джобс) Логическая функция F задаётся выражением (у Vx) = (у— +) У -2. На рисунке приведён фрагмент таблицы истинности функиии F, содержащий неповторяюшиеся строки. Буквы в ответе шишите подряд, никаких разделителей между буквами ставить не нужно.
Джобс) Логическая функция Е задаётся фрагмент таблицы истинности функции Е, содержащий неповторяющиеся строки. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
from itertools import *
def f(x,y,w,z):
return (y or x) == ((y<=w) or (not z))
t = [(1,0,0,0),(0,1,0,0),(1,0,1,0)]
for p in permutations( 'xywz'):
print(p)Шубинкин) Логическая функция F задаётся выражением (x= у) — (2 = ). частично заполненный фрагмент таблицы истинности этой функции, содержащий "неповторяющиеся строки, Сколькими способами можно поставить в соответствие переменные W, ху Z столбцам таблицы истинности функции F, опираясь на информацию из данного фрагмента? Функция F задана выражением x Vy Vz, а фрагмент таблицы истинности имеет вид: В этом случае переменные можно расставить любым способом, значит, ответом будет число 6.
from itertools import *
table = [(0,0,0,1),(1,1,1,0)]
for p in permutations( 'xywz'):
return (x and (y<=z)) or wШубинкин) Логическая функция F задаётся выражением (x частично заполненный фрагмент таблицы истинности этой функции, содержащий
A → B = ¬A ∨ BA ≡ B = (A ∧ B) ∨ (¬A ∧ ¬B)Навигатор и методические рекомендации опубликованы в 2026 году: номера заданий в них могут отличаться от нумерации 2027 года. Ориентируйтесь на тему.