Таблица истинности
Спор, который не кончался словами, укладывается в четыре строки
Таблица истинности позволяет вычислить значение сложного высказывания при всех комбинациях значений его переменных: n переменных дают 2ⁿ строк. Строится она по связкам изнутри наружу, и итоговый столбец полностью описывает высказывание. По таблице проверяют эквивалентность, тавтологичность и логическое следование.
forall x: Calgary, гл. 9 «Characteristic truth tables» и гл. 11 «Complete truth tables». Дж. Буль, «Математический анализ логики», 1847 · 24 мин · обновлено 06.09.2026
После урока вы сможете
- Выписывать все случаи, которые различает высказывание, и не терять ни одного
- Считать столбцы от букв к целому, не пропуская промежуточных
- Находить главную связку и понимать, что делают скобки
- Видеть, почему таблица удваивается с каждой новой буквой
В общем чате делят дежурство. Аня пишет: «Давайте так. Если выйду я, то Боря пусть не выходит. Кто-то из нас двоих выйти должен. И вдвоём выходить незачем».
Боря отвечает: «Ты сама себе противоречишь, так не бывает». Аня: «Бывает». Дальше они спорят десять минут и не сдвигаются ни на шаг, и каждый повторяет своё чуть громче. Спор кончится не тем, кто прав, а тем, кто устал. А между тем у него есть точный ответ, и получить его можно за две минуты. Смотрите. Участников двое, и про каждого известно одно: вышел или не вышел, значит, всего вариантов четыре.
Вышли оба. Вышла только Аня. Вышел только Боря. Не вышел никто. Больше им взяться неоткуда, и осталось проверить на каждом варианте все три условия Ани, и спор кончится.
Спор про дежурство выбран для примера, но устроен он как множество других. Условия акции, пункты договора, правила конкурса, расписание на двоих. Везде несколько требований сразу, и везде возникает вопрос, уживаются ли они между собой. Отвечают на него обычно на глаз, а дальше идёт способ отвечать не на глаз.
Четыре случая, выписанных подряд
Проверяем по очереди. Условий три, вариантов четыре.
Вышли оба. Первое условие нарушено: Аня вышла, а Боря всё-таки вышел тоже. Дальше можно не смотреть, этот вариант отпал.
Вышла только Аня. Первое условие: Аня вышла, Боря не вышел, как и просили. Второе: кто-то вышел, да. Третье: вдвоём не выходили, так и есть. Все три сошлись.
Вышел только Боря. Первое условие говорит о том, что бывает, когда выходит Аня. Аня не вышла, и упрекнуть её не в чем. Второе условие выполнено, третье тоже.
Не вышел никто. Второе условие нарушено: выйти должен был хоть кто-нибудь.
Спор решён: условия Ани выполнимы, и ровно двумя способами. Выходит один из двоих, но не оба, и Боря был неправ. Заметьте, чем именно он решён: не красноречием, не авторитетом и не тем, что кто-то громче. Перебором. Мы выписали все случаи, какие бывают, и посмотрели каждый, а случаев оказалось четыре, и это не много. Такой перебор, записанный по строкам, и называется таблицей истинности, и она у нас уже построена, просто пока словами, а не значками.
Про Аню в этом споре важно ровно одно: вышла или не вышла. Не «почти вышла», не «вышла с опозданием». Логика высказываний знает про каждое высказывание только два значения (истинно и ложно), и потому случаев у двух высказываний четыре, а не бесконечность. Это и есть та цена, за которую покупается перебор.
То же самое, но короче
Писать «вышла Аня» в каждой клетке долго, так что введём буквы. Пусть 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→¬B ¬(A∧B)
И И | Л Л Л
И Л | И И И
Л И | Л И И
Л Л | И И И
У A → ¬B ложь стоит в одной строке: там, где Аня вышла, а ¬B ложно, то есть в первой. В остальных трёх либо антецедент ложен, либо консеквент истинен, значит, истина. Столбец вышел Л И И И, и он совпал со столбцом ¬(A ∧ B) во всех четырёх строках. Первое условие Ани требует ровно того же, что и третье, только другими словами, потому оно к итогу ничего и не добавило. Это не случайность и не фокус: в уроке 9 у такого совпадения появится имя, и наша пара там встретится снова.
Разбор по шагам: откуда взялся каждый столбец
Теперь медленно: как считалась эта таблица, столбец за столбцом.
Шаг 1. Выписать буквы и строки. Разных букв две, значит строк четыре. Порядок: сверху вниз, начиная с двух истин.
Шаг 2. Столбец A ∨ B. Смотрим только на два столбца слева. «Или» ложно в одном случае: когда обе части ложны. Это последняя строка. В остальных трёх стоит истина.
Шаг 3. Столбец A ∧ B. Снова смотрим только на буквы. «И» истинно в одном случае: когда истинны обе части. Это первая строка.
Шаг 4. Столбец ¬(A ∧ B). А вот здесь на буквы уже не смотрим вовсе. Отрицание берёт готовый столбец шага 3 и переворачивает его: где было И, стало Л.
Шаг 5. Итоговый столбец. Связка «и» между столбцом шага 2 и столбцом шага 4. Истина там, где истинны оба: во второй и третьей строках.
Обратите внимание на устройство работы: каждый следующий столбец смотрит только на уже посчитанные. Своей собственной работы в нём нет, только два готовых значения и одна связка. Поэтому длина формулы не делает задачу труднее, а делает её длиннее, и это разные вещи, причём разница здесь на нашей стороне.
Связка, которая считается последней, называется главной. В нашей формуле это «и»: сначала посчитались обе половины, потом они соединились. Главная связка и даёт столбец всего высказывания.
Скобки решают больше, чем кажется
Две фразы. Первая: «Неверно, что Аня и Боря вышли оба». Вторая: «Аня не вышла, а Боря вышел». На слух обе про то, что вдвоём не получилось, так что запишем их и сравним столбцы. Первая записывается как ¬(A ∧ B) и читается: неверно, что оба. Вторая записывается как ¬A ∧ B и читается: Аня не вышла, и Боря вышел.
A B | ¬(A∧B) ¬A∧B
И И | Л Л
И Л | И Л
Л И | И И
Л Л | И Л
Столбцы расходятся в двух строках из четырёх, и это не оттенок и не мелочь: половина случаев разошлась. Разница вся в скобках: в первой формуле отрицание накрывает всё выражение, во второй оно накрывает только букву A. Чтобы не ставить скобки в каждом месте, договорились о старшинстве связок: отрицание применяется раньше «и», «и» раньше «или», «или» раньше стрелок.
Поэтому ¬A ∧ B без скобок значит «не-A, и B», а чтобы отрицание накрыло всю конъюнкцию, скобки обязательны. Одно правило курс держит строго: у стрелок скобки ставятся всегда, даже там, где формально можно без них. Причина простая. Запись P → Q → R читается двумя разными способами: «если P, то верно, что если Q, то R» и «если из P следует Q, то R». Какое из двух чтений имеется в виду, решает соглашение, которое читатель не обязан помнить, и незачем требовать этого от него ради экономии двух знаков.
Скобки служат не украшением записи, а частью высказывания. ¬(A ∧ B) и ¬A ∧ B расходятся в двух строках из четырёх, то есть в половине случаев. В обычной речи ту же роль играют интонация и порядок слов, и потому она эту разницу теряет постоянно: «не все пришли» и «все не пришли» звучат почти одинаково, а значат разное.
Сколько строк бывает
Строк в таблице ровно столько, сколько случаев различает высказывание. Одна буква даёт две строки, две буквы дают четыре, три дают восемь. Правило видно сразу: новая буква удваивает таблицу, потому что каждая старая строка распадается надвое, ведь новое высказывание может быть в ней истинным или ложным.
Общая запись выглядит как 2ⁿ, где n обозначает число разных букв. Читается: два в степени эн. Дальше числа растут неприятно: четыре буквы дают шестнадцать строк, это ещё терпимо, а десять букв дают тысячу двадцать четыре строки. Тысячу строк не считают руками, и это не придирка к усидчивости: за сутки такую таблицу не проверить ни одному человеку.
Отсюда два следствия, и оба важны. Первое: таблица остаётся методом для маленьких задач. Тренажёр ниже строит таблицы до четырёх букв, и это не скупость, а честная граница читаемости. Второе: нужен другой способ, который не перебирает все случаи. Такой способ есть, он называется выводом, и ему посвящён модуль IV. Урок 10 начнётся ровно с этого счёта строк.
Порядок строк, кстати, ничего не значит: сверху истины, снизу лжи, правый столбец меняется в каждой строке, а следующий через одну. Так удобно не сбиться и не потерять случай. Другая книга расставит строки иначе, и ни один результат от этого не изменится.
Зачем считать то, что и так ясно
Тут возникает законное возражение: про Аню и Борю всё было понятно и без таблицы, зачем расписывать четыре строки? Затем, что понятно было именно про Аню и Борю: двое участников, три коротких условия, спор в чате. Стоит добавить третьего дежурного, и строк станет восемь, а ясность пропадает раньше, чем кончается терпение.
Есть и вторая причина, поважнее первой: ощущение «и так ясно» появляется независимо от того, ясно на самом деле или нет. Боря ведь тоже был уверен, и он не бросался словами и не хитрил: он посмотрел на условия, почувствовал противоречие и сказал то, что почувствовал. Ошибся он не в старании, а в методе.
Таблица тем и хороша, что не спрашивает про ощущения: она даёт один и тот же ответ уставшему и бодрому, заинтересованному и постороннему. Отсюда рабочая привычка: считать не тогда, когда трудно, а тогда, когда цена ошибки выше цены четырёх строк.
Чего таблица не видит
У метода есть граница, и о ней честнее сказать сразу. Таблица смотрит только на связки, а внутрь буквы не заглядывает вовсе. Возьмите высказывание «все люди смертны»: для таблицы это одна буква, дальше нечленимая. Она знает про неё ровно одно: бывает истинной, бывает ложной.
Поэтому рассуждения со словами «все» и «некоторые» таблица не берёт вовсе: «все кошки суть животные, Мурка есть кошка, значит Мурка есть животное» для неё три никак не связанные буквы. Ограничение снимается, но не здесь: в модуле V появится язык, который умеет заглядывать внутрь высказывания. Пока же стоит держать в голове рабочее правило. Если в споре всё держится на словах «и», «или», «не», «если», таблица разберёт. Если же дело в словах «все», «некоторые», «каждый», таблица не разберёт и притворяться не будет.
Что дальше
Тренажёр ниже принимает свою формулу и строит таблицу сразу целиком или по одному столбцу. Стоит начать с кнопки «по одному столбцу» и на каждом шаге предсказывать вслух, что получится. Не угадали, значит нашли место, где механика ещё не стала своей.
Урок 8 берёт ту же таблицу и задаёт ей другой вопрос: не «истинна ли формула», а «следует ли одно из другого», и там, наконец, закроется долг третьего урока. Напомню, в чём он состоял. Контрпример мы искали воображением: нашёл, значит доказал, не нашёл, значит не доказал ничего. Таблица перебирает случаи все разом, и эта разница снимается.
Своя формула, своя таблица
Введите любую формулу, и тренажёр построит таблицу по столбцам, от простого к целому, и скажет, тавтология это, противоречие или обычное высказывание.
Откуда это и кто доказал
| Джордж Буль, «Математический анализ логики» | 1847 | Логические связки впервые взяты как действия, которые можно вычислять, а не только обсуждать. Отсюда идёт мысль, что значение сложного высказывания получают счётом из значений частей. |
Ловушки и теоремы
Естественное ощущение «и так понятно» здесь неверно. Столбцы ¬(A ∧ B) и ¬A ∧ B расходятся в двух строках из четырёх, то есть в половине случаев. Обычная речь эту разницу передаёт интонацией и потому теряет её постоянно.
Не всегда. Возьмите условия «Кто-то из двоих выйдет», «Аня не выйдет», «Боря не выйдет». Каждое из них выполнимо по отдельности, а вместе они не выполнимы ни в одной из четырёх строк. Проверяется это не спором, а перебором: выписать все случаи и посмотреть, есть ли среди них строка, где истинны сразу все.
Ни один результат от них не зависит. В других книгах пишут 1 и 0 или T и F, строки расставляют в обратном порядке, а скобки у стрелок ставят по другому правилу. Соглашения выбраны ради того, чтобы человек не сбился при счёте, и меняются свободно, лишь бы внутри одной книги они были одни и те же.
Счёт держится на одном шаге: новая буква удваивает таблицу, потому что каждая прежняя строка распадается надвое, ведь новое высказывание может быть в ней истинным или ложным. Отсюда право сказать «случаев больше нет»: строки выписаны заранее, и просмотр кончается. Условия два: букв конечное число, значений у каждой ровно два. Оговорка тут важнее самого счёта: перебираются все случаи, которые различает язык связок, а не все случаи вообще. И тот же счёт назначает цену: десять букв дают 1024 строки, двадцать дают больше миллиона.
Термины
- таблица истинностиtruth table
- Запись всех случаев, которые различает высказывание: строк 2ⁿ по числу разных букв, столбцы идут от букв к целому. Каждая строка отвечает одному случаю, а каждый столбец отвечает одной части высказывания.
- строка таблицыvaluation
- Одно распределение значений И и Л по буквам высказывания. Это тот же случай из урока 2, только записанный не словами, а значениями.
- случайcase
- Мыслимое положение дел, в котором каждое из рассматриваемых утверждений истинно или ложно. Проверка правильности сводится к вопросу о существовании случая определённого вида.
- главная связкаmain connective
- Связка, которая применяется последней и потому даёт столбец всего высказывания. Находится по скобкам и старшинству: отрицание раньше «и», «и» раньше «или», «или» раньше стрелок.
- старшинство связокorder of precedence
- Соглашение о том, какая связка применяется раньше, когда скобок нет. Позволяет писать «¬A ∧ B» вместо «(¬A) ∧ B». У стрелок курс скобки ставит всегда.
- перебор случаевexhaustive check
- Способ доказать отсутствие контрпримера: выписать все мыслимые случаи и убедиться, что провального среди них нет. Возможен, только когда случаев конечное число.
- логическая формаlogical form
- То, что остаётся от аргумента, когда из него выброшено содержание и оставлено устройство: «все A суть B, x есть A, значит x есть B».
Практикум · Свести собственный спор к четырём строкам
Нужен спор, где кто-то ставит несколько условий сразу: расписание, договорённость о встрече, условия конкурса, правила чата. Задача не в том, чтобы выиграть спор, а в том, чтобы свести его к таблице и посмотреть, что получится.
- Выпишите условия по одному, отдельными строками, ничего не приглаживая. Условий берите не больше трёх, и простых высказываний в них тоже не больше трёх.
- Назначьте буквы: каждому простому высказыванию своя. Рядом запишите ключ: «A значит Аня вышла», «B значит Боря вышел». Ключ пригодится в конце, когда результат придётся переводить обратно на русский.
- Запишите каждое условие формулой и прочитайте её вслух словами. Затем проверка урока 5: назовите случай, где условие и формула расходятся по истинности. Нашёлся, значит записана не та мысль, и чинить это надо сейчас, а не после таблицы.
- Постройте таблицу: сначала строки (их 4 или 8), потом столбцы от простых частей к целому. Промежуточные столбцы не пропускайте, даже если ответ кажется ясным.
- Посмотрите на итоговый столбец. Если И нет ни в одной строке, условия несовместимы. Назовите вслух, какие именно два спорят. Если И есть, выпишите все подходящие строки по ключу обычными словами: это и есть полный список выходов из спора.
Вопросы для самопроверки
Чем различаются высказывания «¬(A ∧ B)» и «¬A ∧ B»?
- Ничем: скобки на значение не влияют
- Только удобством чтения, столбцы у них одинаковые
- Это разные высказывания: их столбцы расходятся в двух строках из четырёх
- Второе высказывание записано с ошибкой и значения не имеет
Сколько строк в таблице для высказывания с четырьмя разными буквами?
- 16: две в четвёртой
- 8: каждая буква добавляет к таблице по две строки
- 4: число строк задаётся не буквами, а числом связок
- Зависит от того, какие связки в него входят
Чему равно «¬(P ∨ Q)», когда P ложно, а Q истинно?
- Истинно, потому что P ложно
- Значение не определено, нужны обе части истинными
- Истинно, потому что отрицание переворачивает ложь
- Ложно
Какая связка главная в высказывании «(P → Q) ∧ ¬R»?
- Стрелка: главной считают ту связку, которая стоит в записи левее
- «И»: обе половины считаются раньше, а соединяются последними
- Отрицание: оно старше всех связок, а значит и главное в записи
- Главной связки тут нет, высказывание составлено из двух самостоятельных
Что таблица показала в споре Ани и Бори?
- Что Аня противоречит себе, как и утверждал Боря
- Что условия проверить нельзя, пока не сказано, кто дежурит на самом деле
- Что условия выполнимы, и ровно двумя способами: выходит один из двоих, но не оба
- Что условий слишком много для четырёх строк
Ответы и разбор открываются в самопроверке урока: она считает результат и отмечает урок пройденным. Пройти самопроверку.
Что читать
- Тренажёр «Таблица истинности» на этой странице: Полезнее всего режим «по одному столбцу»: он не даёт проскочить промежуточные вычисления. Заодно стоит проверить формулы <code>P ∨ ¬P</code> и <code>P ∧ ¬P</code>. Вердикт по ним пригодится в уроке 9.
- forall x: Calgary, гл. 9 «Characteristic truth tables» и гл. 11 «Complete truth tables»: Упражнения стоит сделать целиком: десять посчитанных руками формул дают больше, чем любое объяснение. Отдельно разобран порядок столбцов там, где скобки вложены в скобки.