Сколько строк в таблице истинности от N переменных и почему именно 2 в степени N?
Когда строю таблицу истинности, всегда непонятно, сколько вообще строк должно получиться. От 2 переменных вроде 4, от 3 — кажется 8. Откуда берётся эта формула и почему это степень двойки? Хочу понять, а не зубрить.
2 ответа
Строк ровно 2^N, где N — число переменных. И вот почему.
Каждая переменная может быть либо 0, либо 1 — 2 варианта. Переменные независимы, поэтому варианты перемножаются:
- 1 переменная: 2 строки (0, 1).
- 2 переменные: 2·2 = 4 строки.
- 3 переменные: 2·2·2 = 8.
- 4 переменные: 16.
- 5 переменных: 32.
Это как замок с N колёсиками, на каждом 2 цифры — всего 2^N комбинаций.
Лайфхак для заполнения столбцов: чтобы не пропустить ни одной комбинации, заполняй их как двоичный счётчик от 0 до 2^N − 1. В последнем столбце чередуй 0101…, в предпоследнем — по два 00110011…, перед ним по четыре и т.д. Тогда точно переберёшь все строки без повторов.
Маленький практический вывод: если в задании 4 переменные — это уже 16 строк, вручную долго и легко ошибиться. Поэтому на КЕГЭ такие штуки гоняют перебором на Python через itertools.product([0,1], repeat=4), а не руками.