Все термины, которые используют калькулятор, руководства и упражнения, собраны в одном месте.
Найдите термин, посмотрите его обозначение и откройте пример в калькуляторе, чтобы увидеть его в действии. Термины отсюда подсвечиваются при первом появлении в руководстве.
Все 62 терминов
Наука о том, какие выводы действительно следуют из каких допущений.
Логика изучает форму рассуждения, а не его содержание. Формальная логика заменяет предложения символами, так что вопрос о следовании решается только формой рассуждения и проверяется механически.
Утверждение, которое истинно либо ложно, но не то и другое сразу.
Высказывание — это повествовательное предложение ровно с одним значением истинности. «Идёт дождь» — высказывание; вопрос или приказ им не является, потому что в них нечему быть истинным или ложным.
Одно из двух значений высказывания: истина или ложь.
Классическая логика приписывает каждому высказыванию ровно одно из двух значений истинности, записываемых ⊤ и ⊥ (или 1 и 0). Каждая строка таблицы истинности — это набор значений переменных и результат формулы при них.
Высказывание, внутри которого нет ни одной связки.
Атомарное высказывание нельзя разложить на меньшие: в нём нет ни отрицания, ни конъюнкции, ни другой связки. Всё остальное составное, построено из атомов, и его значение истинности определяется их значениями.
Буква вроде p или A, обозначающая произвольное высказывание.
Пропозициональная переменная — место для любого высказывания. Калькулятор принимает одиночные буквы как переменные и отводит каждой столбец таблицы истинности со строкой для каждого возможного набора значений.
В калькулятореp → qСтрока символов, которую грамматика языка действительно допускает.
Правильно построенная формула строится по правилам: переменная является таковой, и любая формула, полученная из меньших с помощью связки, тоже. «p ∧ ∨ q» — нет, поэтому калькулятор сообщает об ошибке, а не догадывается.
Одно приписывание значений истинности всем переменным формулы.
Интерпретация говорит, чему равна каждая переменная, и тем самым задаёт значение всей формулы. У формулы с n переменными 2ⁿ интерпретаций — ровно строки её таблицы истинности.
Набор посылок, выдвинутых в поддержку заключения.
Рассуждение утверждает, что его заключение следует из посылок. Введите его в калькулятор со знаком следования — посылки до, заключение после — и каждая строка будет проверена на случай, где посылки истинны, а заключение ложно.
В калькулятореp → q, p ⊨ qУтверждение, которое рассуждение принимает, чтобы прийти к заключению.
Посылки — то, с чего начинается рассуждение. Правильность спрашивает лишь, верно ли заключение всюду, где верны все посылки; истинны ли они на деле — отдельный вопрос, который добавляет обоснованность.
В калькулятореp → q, p ⊨ qУтверждение, которое рассуждение стремится обосновать.
Заключение — то, в поддержку чего выдвинуты посылки. В калькуляторе это выражение после знака следования, и рассуждение правильно, когда ни одна интерпретация не делает посылки истинными, а заключение ложным.
В калькулятореp → q, p ⊨ qСимвол, строящий сложное высказывание из более простых.
Связка вроде ¬, ∧, ∨, → или ↔ соединяет высказывания в большее, значение истинности которого зависит только от их значений. Именно эту зависимость и фиксирует таблица истинности, по строке на каждый набор входов.
Меняет значение истинности: ¬p истинно ровно тогда, когда p ложно.
Отрицание — единственная одноместная связка логики высказываний. Записанное ¬p, ~p или !p, оно превращает истину в ложь и ложь в истину, поэтому двойное отрицание возвращает исходное высказывание.
В калькуляторе¬pИстинна только когда обе части истинны: p ∧ q.
Конъюнкция утверждает обе свои части, называемые конъюнктами. Она истинна ровно в одной строке своей таблицы истинности — там, где истинны оба конъюнкта, — и потому самая строгая из двухместных связок.
В калькулятореp ∧ qИстинна, когда истинна хотя бы одна часть: p ∨ q.
В логике дизъюнкция нестрогая: p ∨ q истинно, когда истинно p, когда истинно q и когда истинны оба. Строгое прочтение «или», истинное лишь при различии частей, — отдельная связка.
В калькулятореp ∨ qИстинна, когда истинно ровно одно из двух высказываний.
Строгая дизъюнкция, записываемая ⊕ или XOR, верна, когда её части различны, и неверна, когда совпадают. Это отрицание эквиваленции, и её можно записать как (p ∨ q) ∧ ¬(p ∧ q).
В калькуляторе(p ∨ q) ∧ ¬(p ∧ q)p → q, ложна только когда p истинно, а q ложно.
Материальная импликация говорит лишь «неверно, что антецедент истинен, а консеквент ложен», поэтому она верна всякий раз, когда антецедент ложен. Отсюда эквивалентность p → q и ¬p ∨ q.
В калькулятореp → qp ↔ q, истинна, когда обе части имеют одно значение истинности.
Эквиваленция утверждает каждую сторону при условии другой: она истинна, когда обе части истинны, и когда обе ложны. Эквиваленция, являющаяся тавтологией, как раз и выражает логическую равносильность.
В калькулятореp ↔ qЧасть «если» импликации — p в p → q.
Антецедент — условие, от которого зависит импликация. Когда он ложен, вся импликация истинна независимо от консеквента, и отсюда почти все неожиданности таблицы для →.
В калькулятореp → qЧасть «то» импликации — q в p → q.
Консеквент — то, что импликация объявляет следующим, если верен её антецедент. Истинный консеквент делает импликацию истинной, но не делает истинным антецедент: заключать так — формальная ошибка.
В калькулятореp → qИмпликация с переставленными частями: q → p.
Обратная к p → q — это q → p, и они не равносильны: калькулятор находит строку, где одна верна, а другая нет. Считать их взаимозаменяемыми — значит утверждать консеквент.
В калькулятореq → p¬q → ¬p, всегда с тем же значением истинности, что и p → q.
Контрапозиция отрицает обе части импликации и меняет их местами. В отличие от обратной, она действительно равносильна исходной, и потому доказательство от противного по контрапозиции законно в математике.
В калькуляторе(p → q) ≡ (¬q → ¬p)Отрицание конъюнкции: истинно, кроме случая, когда оба входа истинны.
Штрих Шеффера, записываемый ↑, это ¬(p ∧ q). Он функционально полон: любую другую связку можно построить только из него, поэтому он рабочая лошадка проектирования цифровых схем.
В калькуляторе¬(p ∧ q)Отрицание дизъюнкции: истинно только когда оба входа ложны.
Стрелка Пирса, записываемая ↓, это ¬(p ∨ q). Как и штрих Шеффера, она функционально полна сама по себе, так что схему можно собрать целиком из элементов ИЛИ-НЕ.
В калькуляторе¬(p ∨ q)Какая связка применяется первой, когда скобки опущены.
Сильнее всех связывает отрицание, затем конъюнкция, дизъюнкция, импликация и, наконец, эквиваленция. Так ¬p ∧ q ∨ r читается как ((¬p) ∧ q) ∨ r; скобки отменяют этот порядок, когда нужное прочтение иное.
В калькуляторе¬p ∧ q ∨ rПо строке на каждый набор значений и значение формулы в каждой.
Таблица истинности перечисляет все 2ⁿ интерпретаций n переменных формулы и вычисляет её значение в каждой. Будучи исчерпывающей, она решает любой семантический вопрос логики высказываний: равносильность, правильность, выполнимость и прочие.
В калькулятореp → qФормула, истинная при любой интерпретации.
Тавтология истинна в каждой строке своей таблицы истинности и потому ничего не сообщает о мире: p ∨ ¬p истинно, чем бы ни было p. Две формулы равносильны ровно тогда, когда эквиваленция между ними — тавтология.
В калькулятореp ∨ ¬pФормула, ложная при любой интерпретации.
Противоречие вроде p ∧ ¬p ложно в каждой строке своей таблицы истинности. Вывод противоречия из набора допущений показывает, что они не могут выполняться все сразу, — на этом держится доказательство от противного.
В калькулятореp ∧ ¬pФормула, истинная при одних интерпретациях и ложная при других.
Такая формула не является ни тавтологией, ни противоречием: в её таблице истинности есть хотя бы одна истинная и хотя бы одна ложная строка. Почти всё, что пишут на практике, таково — и потому содержательно.
В калькулятореp ∧ qЕсть ли интерпретация, при которой формула истинна.
Формула выполнима, когда хотя бы одна строка её таблицы истинности истинна, и эта строка — её модель. Решение задачи выполнимости — центральная задача SAT-решателей и через них немалой части автоматического вывода.
В калькулятореp ∧ (p → q)Две формулы с одинаковыми таблицами истинности.
Равносильные формулы совпадают при любой интерпретации, поэтому одну можно всюду заменить другой без изменения смысла. Поставьте знак равенства между двумя выражениями — калькулятор сравнит их столбцы построчно.
В калькуляторе(p → q) ≡ (¬p ∨ q)Заключение верно в каждой интерпретации, где верны посылки.
Записываемое Γ ⊨ φ, логическое следование — это то, на что претендует правильное рассуждение. Проверяют его поиском контрпримера: интерпретации, где все посылки истинны, а заключение ложно. Если такой нет, следование имеет место.
В калькулятореp → q, p ⊨ qНи одна интерпретация не делает посылки истинными, а заключение ложным.
Правильность — свойство формы рассуждения, а не фактов: у правильного рассуждения могут быть ложные посылки и ложное заключение. Чего у него быть не может — истинных посылок при ложном заключении.
В калькулятореp → q, p ⊨ qПравильное рассуждение, посылки которого к тому же истинны.
Обоснованность добавляет к формальному утверждению фактическое: рассуждение правильно и его посылки верны. Первую половину решает одна логика; вторая относится к тому, о чём рассуждение говорит.
Интерпретация, где посылки истинны, а заключение ложно.
Контрмодель доказывает, что рассуждение неправильно, — достаточно одной строки. Калькулятор показывает найденную строку, превращая «это не следует» в конкретный набор значений, который можно проверить вручную.
В калькулятореp → q ⊨ q → pНекоторая интерпретация делает истинными сразу все утверждения набора.
Набор посылок совместен, когда все они могут выполняться вместе. Из несовместных посылок следует всё что угодно, поэтому построенное на них рассуждение формально правильно и ничего не стоит.
В калькулятореp → q, ¬q ⊨ ¬pПеременная или её отрицание, например p или ¬p.
Литералы — атомы нормальных форм: дизъюнкт есть дизъюнкция литералов, а минтерм — их конъюнкция. Литерал положителен, когда переменная стоит без отрицания, и отрицателен, когда она отрицается.
В калькуляторе¬pДизъюнкция литералов, например p ∨ ¬q ∨ r.
Дизъюнкт — одна из скобочных групп, из которых строится конъюнктивная нормальная форма. Поскольку конъюнкция истинна лишь когда истинна каждая часть, формула в КНФ верна ровно тогда, когда верны все её дизъюнкты.
В калькулятореp ∨ ¬q ∨ rИЛИ из И: дизъюнкция конъюнкций литералов.
У всякой формулы есть дизъюнктивная нормальная форма, и её можно прочесть прямо по таблице истинности: по конъюнкции на каждую истинную строку, соединённые ∨. Калькулятор даёт и минимизированную ДНФ — то же самое, но короче.
В калькуляторе(p ∧ q) ∨ (¬p ∧ r)И из ИЛИ: конъюнкция дизъюнктов.
Конъюнктивная нормальная форма читается по ложным строкам таблицы истинности, по дизъюнкту на строку. Это формат входа, которого ждут SAT-решатели, и потому перевод в КНФ — рутинный шаг автоматического вывода.
В калькуляторе(p ∨ q) ∧ (¬p ∨ r)Конъюнкция, задающая ровно одну строку таблицы истинности.
Минтерм упоминает каждую переменную по одному разу, с отрицанием или без, так что его удовлетворяет ровно одна интерпретация. Собрав минтермы истинных строк и соединив их ∨, получаем ДНФ формулы.
В калькулятореp ∧ ¬q ∧ rДизъюнкция, исключающая ровно одну строку таблицы истинности.
Макстерм упоминает каждую переменную по одному разу и ложен ровно при одной интерпретации. Взяв макстерм каждой ложной строки и соединив их ∧, получаем КНФ формулы.
В калькулятореp ∨ ¬q ∨ rОтрицание меняет ∧ на ∨ и ∨ на ∧: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
Законы де Моргана вносят отрицание внутрь конъюнкции или дизъюнкции, меняя связку по пути. Так формулу приводят к нормальной форме и так упрощают отрицания в коде и в схемах.
В калькуляторе¬(p ∧ q) ≡ ¬p ∨ ¬qДвойное отрицание возвращает исходное: ¬¬p ≡ p.
В классической логике двойное отрицание работает в обе стороны, так что ¬¬p и p всегда взаимозаменяемы. Интуиционистская логика сохраняет лишь направление от p к ¬¬p — здесь две системы и расходятся.
В калькулятор嬬p ≡ pАлгебра двух значений с операциями ∧, ∨ и ¬.
Булева алгебра — логика высказываний, записанная как арифметика над 0 и 1, с законами коммутативности, дистрибутивности, поглощения и де Моргана, позволяющими преобразовывать и упрощать выражения. На ней проектируют цифровые схемы.
В калькуляторе(p ∧ q) ∨ (p ∧ ¬q) ≡ pСетка таблицы истинности, на которой видны упрощения.
Карта Карно располагает строки так, что соседние клетки различаются одной переменной, а края смыкаются. Её также записывают как K-карта, K-map или kmap. Прямоугольные группы соседних единиц размером 1, 2, 4 или 8 читаются тогда как слагаемые минимального выражения.
В калькуляторе(p ∧ q) ∨ (p ∧ ¬r)Группа на карте, которую уже нельзя увеличить.
Импликанта — конъюнкция литералов, обращающая формулу в истину; она проста, когда удаление любого литерала это нарушит. На карте Карно простые импликанты — максимальные прямоугольники из единиц.
Единственная простая импликанта, покрывающая данную единицу.
Если единица на карте принадлежит только одной максимальной группе, эта группа должна войти в любое минимальное покрытие и берётся первой. Оставшееся — та часть покрытия, которую действительно нужно искать.
Элемент схемы, вычисляющий одну связку над своими входами.
Элементы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и исключающее ИЛИ — аппаратные двойники связок. Формула и схема — один и тот же объект, нарисованный дважды, поэтому калькулятор может показать выражение схемой элементов.
В калькуляторе(p ∧ q) ∨ ¬rРазрешённый шаг от уже выведенных формул к новой.
Правило вывода — схема вроде modus ponens, применимая всякий раз, когда есть формулы нужного вида. Системы доказательства строятся из горстки таких правил, выбранных так, чтобы выводились только следующие заключения.
Из p → q и p следует q.
Modus ponens — основное правило импликации: имея импликацию и её антецедент, получаем консеквент. Правильность видна в таблице истинности: единственная строка с обеими истинными посылками имеет истинное заключение.
В калькулятореp → q, p ⊨ qИз p → q и ¬q следует ¬p.
Modus tollens проходит импликацию назад: если консеквент ложен, антецедент не мог быть истинным. Это контрапозиция в действии и форма всякого рассуждения, опровергающего гипотезу проверкой её предсказаний.
В калькулятореp → q, ¬q ⊨ ¬pИз p → q и q → r следует p → r.
Условный силлогизм сцепляет импликации, и именно это делает возможными длинные выводы: каждое звено продвигает рассуждение на шаг, не утверждая ни одной посылки.
В калькулятореp → q, q → r ⊨ p → rИз p ∨ q и ¬p следует q.
Разделительный силлогизм отбрасывает исключённый вариант: если верна одна из двух возможностей, а первая неверна, то верна вторая. Это правило стоит за рассуждением методом исключения.
В калькулятореp ∨ q, ¬p ⊨ qДоказательство заключения последовательным применением правил.
Натуральный вывод получает заключение из посылок правилами введения и удаления для каждой связки, позволяя делать временные допущения и затем их снимать. Он доказывает то, что проверяет таблица истинности, не перебирая все строки.
Предположить обратное, вывести противоречие, заключить исходное.
Чтобы доказать φ, принимают ¬φ и выводят нечто вида ψ ∧ ¬ψ. Поскольку ни одна интерпретация не делает противоречие истинным, допущение неверно и φ следует. Так обычно устроены доказательства иррациональности и бесконечности.
В калькулятореp ∧ ¬pНеправильный шаг от p → q и q к p.
Истинный консеквент не обосновывает антецедент: его могло вызвать что-то иное. Калькулятор показывает контрмодель — p ложно, q истинно, — ту самую строку, что отделяет это от modus ponens.
В калькулятореp → q, q ⊨ pНеправильный шаг от p → q и ¬p к ¬q.
Импликация ничего не говорит о том, что происходит при ложном антецеденте, поэтому исключение антецедента оставляет консеквент открытым. Контрмодель — строка, где p ложно, а q истинно.
В калькулятореp → q, ¬p ⊨ ¬qЛогика, заглядывающая внутрь высказываний: объекты и их свойства.
Логика предикатов добавляет предикаты, термы и кванторы, так что «всякое простое число больше двух нечётно» становится формулой, а не одной буквой. Она строго выразительнее логики высказываний, и никакая таблица истинности её не решает.
Символ, говорящий, для скольких объектов верен предикат.
Два классических квантора — ∀ (все) и ∃ (хотя бы один), и каждый есть отрицание другого с отрицанием тела. Переменная, которую связывает квантор, и отличает логику предикатов от логики высказываний.
∀x φ: φ верно для каждого объекта области.
Общее утверждение опровергается единственным контрпримером и пусто выполняется на пустой области. ∀x φ равносильно ¬∃x ¬φ — кванторный аналог законов де Моргана.
∃x φ: φ верно хотя бы для одного объекта области.
Экзистенциальное утверждение обосновывается предъявлением одного свидетеля. ∃x φ равносильно ¬∀x ¬φ, так что каждый квантор определяется через другой вместе с отрицанием.
Логика, расширенная «необходимо» (□) и «возможно» (◇).
Модальная логика оценивает формулы в возможных мирах, а не в одной интерпретации: □φ верно, когда φ верно в каждом достижимом мире, ◇φ — когда в некотором. Разные понимания достижимости дают разные модальные системы.
