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

Сначала действия в скобках, затем отрицание, затем конъюнкция (И), затем дизъюнкция (ИЛИ) вместе с исключающим ИЛИ, затем импликация и последней — эквивалентность. Так, ¬A ∧ B ∨ C ∧ D означает ((¬A) ∧ B) ∨ (C ∧ D). Единого правила нет только для цепочки импликаций без скобок: в школьном курсе действия одного приоритета выполняют слева направо, а в математической логике A → B → C читают как A → (B → C). Импликация не ассоциативна, и таблицы получаются разными, поэтому инструмент показывает, как прочитал запись, и даёт переключить.

A → B — это обещание «если A, то B». Нарушено оно только тогда, когда A выполнилось, а B нет, — это единственная строка 1 → 0 = 0. Если A ложно, обещание не проверялось, и оно считается выполненным: импликация равна 1. Поэтому у A → B та же таблица, что у ¬A ∨ B, и именно на эту формулу инструмент заменяет импликацию при упрощении.

СДНФ берёт по конъюнкции всех переменных на каждый набор, где F = 1: если единиц шесть, будет шесть длинных членов. Минимизация склеивает члены, отличающиеся одной переменной: A∧B∧C ∨ A∧B∧¬C = A∧B. На карте Карно такие члены — соседние клетки, и группа из 2, 4 или 8 клеток превращается в один короткий член. Метод Квайна — Мак-Класки делает те же склейки по порядку и выбирает самый дешёвый набор членов, который покрывает все единицы.

Выпишите наборы, на которых F принимает значение из фрагмента, — их обычно немного. Найдите, что у них общего: если при F = 0 всегда y = 1, столбец с нулём в строке с F = 0 не может быть y. Затем возьмите самую «говорящую» строку фрагмента и посмотрите, каким наборам она может соответствовать; строки фрагмента не повторяются, и это отсекает ещё варианты. Режим «ЕГЭ №2» делает ровно это и расписывает каждый шаг.

Полином Жегалкина записывает любую логическую функцию только через И, исключающее ИЛИ и константу 1, и для каждой функции он единственный — по нему удобно сравнивать функции и проверять линейность. Классы Поста отвечают на другой вопрос: можно ли из данного набора элементов собрать любую функцию. По теореме Поста набор полон тогда и только тогда, когда для каждого из пяти классов в нём есть функция вне этого класса. Штрих Шеффера и стрелка Пирса не лежат ни в одном классе — поэтому любую схему можно собрать из одних элементов И-НЕ или ИЛИ-НЕ.