Урок 3: таблицы истинности

Введение

Логика в информатике – это направления исследований и отрасли знания, где логика применяется в информатике и искусственном интеллекте.

Современный прогресс, развитие науки и техники, достижения в компьютерных технологиях базируются на знаниях основ алгебры логики. Роль алгебры логики в информатике очень весома, так как принципы работы любого компьютера, его схем и функциональных блоков основаны на ее законах.

Математическая логика нашла широкое применение в языках программирования. Все языки программирования включают в себя базовые логические операции и некоторые логические функции: IMP, EQL, и так далее.

В данной работе будут рассмотрены основные аспекты алгебры логики, понятия, виды логических операций и таблиц истинности, логические формулы, а также законы алгебры логики. Заключительная часть посвящена использованию алгебры логики в компьютерных науках.

В практической части будет построена компьютерная модель решения задачи в среде MS Excel.

Способы решения задач по логике

Многие задачи можно решить, используя инструменты алгебры логики. Чтобы получить результат, можно пойти 3 путями:

рассуждая над условием;
решая логические операции;
используя таблицы истинности.

Логический подход подразумевает перевод условия из естественного языка на язык символов, схем и формул. Для такой формализации высказываний нужно выполнить ряд шагов.

Этапы решения логических задач:

Разобраться с условием на естественном языке, выделив простые высказывания, и дать им символьные обозначения (латиница).
Записать условие в виде формулы. Решить ее поэтапно, упрощая, учитывая приоритеты (( ), ¬, &, V).
Просчитать формулы строчно или при помощи таблиц истинности, учитывая законы алгебры логики.
Проверить, соответствует ли полученный результат условию задачи.

Алгебраические преобразования логических выражений

Любое логическое выражение, как и его переменные (утверждения), принимают два значения: ложь или истина. Ложь обозначается нулём, а истина — единицей. Разобравшись с областью определения и областью допустимых значений, мы можем рассмотреть действия алгебры логики.

Отрицание

Отрицание и инверсия — самое простое логическое преобразование. Ему соответствует частица «не.» Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то «не А» — ложно. Например, утверждение «прямой угол — это угол, равный девяносто градусов» — истина. Тогда его отрицание «прямой угол не равен девяноста градусам» — ложь.

Таблица истинности для отрицания будет такова:

А	не А
Л	И
И	Л

Конъюнкция

Конъюнкция аналогична умножению и соответствует союзу «и». Такое выражение будет верно, только если верны все утверждения, объединённые конъюнкцией. То есть, утверждение «А и Б» будет истинным, только если А — истина и Б — истина. Во всех остальных случаях выражение «А и Б» ложно. Например, высказывание «Земля круглая и плоская» будет ложно, так как первая часть истина, а вторая — ложь.

Таблица истинности конъюнкции

А	Б	А и Б
Л	Л	Л
Л	И	Л
И	Л	Л
И	И	И

Дизъюнкция

Эта операция может быть обычной или строгой, их результаты будут различаться.

Обычная дизъюнкция или логическое сложение соответствует союзу «или». Она будет истинной если хотя бы одно из утверждений, входящих в неё — истина. Например, выражение «Земля круглая или стоит на трёх китах» будет истинным, так как первое утверждение — истинно, хоть второе и ложно.В таблице это будет выглядеть так:

А	Б	А или Б
Л	Л	Л
Л	И	И
И	Л	И
И	И	И

Строгую дизъюнкцию или сложение по модулю также называют «исключающим или». Эта операция может принимать вид грамматической конструкции «одно из двух: либо …, либо …». Здесь значение логического выражения будет ложным, если все утверждения, входящие в него, имеют одинаковую истинность. То есть, оба утверждения либо вместе истинны, либо вместе ложны.

Таблица значений исключающего или

А	Б	либо А, либо Б
Л	Л	Л
Л	И	И
И	Л	И
И	И	Л

Импликация и эквивалентность

Импликация представляет собой следствие и грамматически может быть выражена как «из А следует Б». Здесь утверждение А будет называться предпосылкой, а Б — следствием. Импликация может быть ложной, только в одном случае: если предпосылка истинна, а следствие ложно. То есть, ложь не может следовать из истины. Во всех остальных случаях импликация истинна. Варианты, когда оба утверждения имеют одинаковую истинность, вопросов не вызывают. Но почему верное следствие из неверной предпосылки — истина? Дело в том, что из ложной предпосылки может следовать что угодно. Это и отличает импликацию от эквивалентности.

В математике (и других доказательных дисциплинах) импликация используется для указания необходимого условия. Например, утверждение А — «точка О — экстремум непрерывной функции», утверждение Б — «производная непрерывной функции в точке О обращается в ноль». Если О, действительно, точка экстремума непрерывной функции, то производная в этой точке будет, и вправду, равна нулю. Если же О не является точкой экстремума, то производная в этой точке может быть нулевой, а может не быть. То есть Б необходимо для А, но не достаточно.

Таблица истинности для импликации выглядит следующим образом:

А	Б	из А следует Б
Л	Л	И
Л	И	И
И	Л	Л
И	И	И

Логическая операция эквивалентность, по сути, является взаимной импликацией. «А эквивалентно Б» означает, что «из А следует Б» и «из Б следует А» одновременно. Эквивалентность верна, когда оба утверждения либо одновременно верные, либо одновременно неверные.

А	Б	А эквивалентно Б
Л	Л	И
Л	И	Л
И	Л	Л
И	И	И

В математике эквивалентность используется для определения необходимого и достаточного условия. Например, утверждение А — «Точка О является точкой экстремума непрерывной функции», утверждение Б — «В точке О производная функции обращается в ноль и меняет знак». Эти два утверждения эквивалентны. Б содержит необходимое и достаточное условие для А

Обратите внимание, что в данном примере утверждений Б на самом деле является конъюнкцией двух других: «производная в точке О обращается в ноль» и «производная в точке О меняет знак»

Прочие логические функции

Выше были рассмотрены основные логические операции, которые часто используются. Есть и другие функции, которые используются:

Штрих Шеффера или несовместимость представляет собой отрицание конъюнкции А и Б
Стрелка Пирса представляет сбой отрицание дизъюнкции.

Аксиомы и законы

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

Торжества. Записывается в виде утверждения: А = А. В этом случае таблица будет состоять из двух комбинаций: ложной и правдивой. Бинарная логическая связка «Если А, то А» является материальной импликацией. Для такого варианта всегда можно сказать, что А есть А. Этот закон обозначает то, что нельзя подменять одно понятие другим, иначе возникнут логические ошибки.
Противоречия. Согласно ему, утверждение, что А и НЕ-А, неверно: A & A = 0. Другими словами, если А истинное значение, то его отрицание не может быть ложным. То есть их перемножение будет всегда фальшивой операцией. Этот закон довольно часто применяется для упрощения сложных логических суждений.
Третьего исключённого. Закон записывается в виде A v A = 1 и обозначает, что в один и тот же момент высказывание может быть только правдивым или ложным. То есть третьего не дано.

Эти три закона фундаментальны. Без их соблюдения сделать любое правильное утверждение невозможно.

Для решения логических задач с помощью таблиц истинности используют различные формулы, соответствующие разного вида операциям. Одно из них логическое умножение (конъюнкция). В этом случае считается, что функция истинная лишь тогда, когда оба выражения являются верными: F = A & B. Другое логическое сложение (дизъюнкция). Оно гласит, что если оба выражения ложны, то и логическая функция будет неверной.

Кроме того, используется закон:

инверсии (отрицания) — если логическое высказывание истинно, то отрицание его будет ложным выражением;
импликации (следования) — для всегда истинного сложного логического выражения ложь будет тогда, когда из верности следует отрицание;
эквивалентности (равнозначности) — выражение будет истинным лишь тогда, когда оба высказывания имеют одинаковое значение.

Основные логические операции

Существует три основных логических операции при помощи которых можно записать любое логическое выражение (не пугайтесь)

1. Инверсия2. Конъюнкция3. Дизъюнкция

Конъюнкция, оно же «Логическое И», оно же «Логическое умножение».
Мы выбираем название «Логическое И» – оно чаще встречается в программировании.
Допустим, у нас есть два простых выражения – А и В. Эти выражения могут иметь значения или 1 (истина), или 0 (ложь). При выполнении операции «Логическое И» мы получим сложное выражение которое примет значение 1 (истина) только в том случае если и А, и В имеют значение 1 (истина), во всех других случаях результат будет 0 (ложь).
Операция «Логическое И» имеет обозначения (в языках программирования): И, &&, AND, &.

Дизъюнкция, оно же «Логическое ИЛИ», оно же «Логическое сложение».
Мы выбираем название «Логическое ИЛИ». Кстати, если логически подумать, то можно и догадаться какие результаты будут при выполнении этой операции.
В «Логическом И» результат равен 1, если и А, и В, равны 1, а в «Логическом ИЛИ» результат будет равен 1, если или А, или В, равны единице.
Операция «Логическое ИЛИ» имеет обозначения: ИЛИ, ||, OR, |.

Инверсия, оно же «Логическое НЕ», оно же «Отрицание».
Мы выбираем название «Логическое НЕ».
Операция «Логическое НЕ» имеет обозначения: НЕ, !, NOT.
Тут вообще все просто:
Если А=1 (истина), то после выполнения операции «Отрицание» А примет значение 0, то есть становится ложным. И наоборот.
Есть еще одно название этой операции «Инвертор», а применяется оно в отношении цифровых микросхем.

В программировании часто применяется еще одна логическая операция – симбиоз «Логического И» и «Логического ИЛИ»:Строгая дизъюнкция, оно же «Исключающее ИЛИ», оно же «Логическое сложение, исключающее ИЛИ», оно же «Сложение по модулю 2»
Мы выбираем название «Исключающее ИЛИ»
Операция «Исключающее ИЛИ» имеет обозначения: Искл.ИЛИ, XOR, ^.
В этом случае, при выполнении операции «Исключающее ИЛИ», результат будет истинен (равен 1), если А не равно В. В остальных случаях результат будет равен 0 (ложный).

Логический элемент «ИЛИ»

Следующим простейшим логическим элементом является схема, реализующая операцию логического сложения «ИЛИ»:

F(x₁,x₂) = x₁Vx₂

где символ V обозначает функцию логического сложения. Иногда эта же функция записывается в другом виде:

F(x₁,x₂) = x₁Vx₂ = x₁+x₂ = x₁|x₂.

То же самое действие можно записать при помощи таблицы истинности, приведённой в таблице 4. В формуле, приведенной выше
использовано два аргумента. Поэтому логический элемент, выполняющий эту функцию имеет два входа. Такой элемент обозначается
«2ИЛИ». Для элемента «2ИЛИ» таблица истинности будет состоять из четырех строк (22 = 4).

Таблица 4. Таблица истинности логического элемента «2ИЛИ»

In1	In2	Out
1	1
1	1
1	1	1

Как и в случае, рассмотренном для , воспользуемся для реализации схемы
«2ИЛИ» ключами. На этот раз соединим ключи параллельно. Схема, реализующая таблицу истинности 4, приведена на
рисунке 5. Как видно из приведённой схемы, уровень логической единицы появится на её выходе, как только будет замкнут
любой из ключей, то есть схема реализует таблицу истинности, приведённую в таблице 4.

Так как функция логического суммирования может быть реализована различными принципиальными схемами,
то для обозначения этой функции на принципиальных схемах используется специальный символ «1», как это приведено на
рисунке 6.

Дата последнего обновления файла
29.03.2018

3.2. Какая связь между алгеброй логики и двоичным кодированием

Математический аппарат алгебры логики очень удобен для описания того, как
функционируют аппаратные средства компьютера, поскольку основной системой
счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а
значений логических переменных тоже два: “1” и “0”.

Из этого следует два вывода:

одни и те же устройства компьютера могут применяться для обработки и
хранения как числовой информации, представленной в двоичной системе счисления,
так и логических переменных;
на этапе конструирования аппаратных средств алгебра логики позволяет
значительно упростить логические функции, описывающие функционирование схем
компьютера, и, следовательно, уменьшить число элементарных логических
элементов, из десятков тысяч которых состоят основные узлы компьютера.

1.4. Применение алгебры логики в информатике

После изготовления первого компьютера стало ясно, что при его производстве возможно использование только цифровых технологий – ограничение сигналов связи единицей и нулём для большей надёжности и простоты архитектуры компьютера. Благодаря своей бинарной природе, математическая логика получила широкое распространение в вычислительной технике и информатике. Были созданы электронные эквиваленты логических функций, что позволило применять методы упрощения булевых выражений к упрощению электрической схемы. Кроме того, благодаря возможности нахождения исходной функции по таблице позволило сократить время поиска необходимой логической схемы.

В программировании логика незаменима как строгий язык и служит для описания сложных утверждений, значение которых может определить компьютер.

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: «1» и «0».

Из этого следует два вывода:

1) одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных;

2) на этапе конструирования аппаратных средств алгебра логики позволяет

значительно упростить логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить число элементарных логических элементов, из десятков тысяч которых состоят основные узлы компьютера. Данные и команды представляются в виде двоичных последовательностей различной структуры и длины. Существуют различные физические способы кодирования двоичной информации.

В электронных устройствах компьютера двоичные единицы чаще всего кодируются более высоким уровнем напряжения, чем двоичные нули (или наоборот), например: Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И — НЕ, ИЛИ — НЕ и другие (называемые также вентилями), а также триггер.

С помощью этих схем можно реализовать любую логическую функцию, описывающую работу устройств компьютера. Обычно у вентилей бывает от двух до восьми входов и один или два выхода. Чтобы представить два логических состояния – «1» и «0» в вентилях, соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения. Например, +5 вольт и 0 вольт. Высокий уровень обычно соответствует значению «истина» (1), а низкий — значению «ложь»(0).

Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нём реализована. Это упрощает запись и понимание сложных логических схем. Работу логических элементов описывают с помощью таблиц истинности.

Булевы алгебры находят применение главным образом в теории множеств, в математической логике, в теории вероятностей и в функциональном анализе.

Итак, алгебра логики применяется: 1) для упрощения сложных логических формул и доказательств тождеств; 2) при решении логических задач; 3) в контактных схемах; 4) при доказательствах теорем; 5) в базах данных при составлении запросов.

Табличный способ – этапы, особенности

Таблица истинности – табличное выражение результата логических операций для каждого отдельного набора значений переменных.

Такие таблицы позволяют абстрагироваться от маловажной информации, сосредоточиться только на связях между исходными данными, над происходящими процессами. Таким образом, человек может абстрагироваться от непонятной для него информации, решать неспецифические задачи

Метод таблиц

Чтобы использовать таблицы истинности, необходимо формализовать условие, то есть отойти от деталей задачи, обозначая первоначальную информацию при помощи букв и цифр 0 и 1.

Существует общий алгоритм построения таблиц:

Определить число логических значений/переменных (n) в примере.
Установить вид, число и тип операций

Важно заранее определить очередность действий, выразить это при помощи скобок.
Полученные данные позволяют рассчитать сколько нужно столбцов – это сумма числа переменных и операций.
Нарисовать таблицу, заполнить шапку, записав обозначение переменных и выбранные действия.
Определить, сколько существует наборов логических переменных (т.е. число строчек) по формуле m = 2n+ 1 (шапка).
Заполнить столбцы, вписав наборы значений логических переменных (0 или 1).
Записать результаты логических операций, указанных в шапке для каждой совокупности значений.
Сделать выводы на основании полученных результатов.

Если необходимо перебрать все значения простых выражений, то для задач:

с 2-мя переменными может быть только 4 набора логических переменных;

Если словесно описывать все эти комбинаций, на каждый из примеров понадобится десятки строк текста.

Обязательно учитывают приоритет операций:

Указанные в скобках.
Отрицание.
Логическая конъюнкция чисел.
Дизъюнкция.
Строгая дизъюнкция.
Импликация.
Эквивалентность.

Классификация

Логические уровни

В булевой алгебре данные, будь то входные или выходные, имеют только два возможных уровня. В зависимости от приложения эти два уровня могут иметь разные названия: вкл / выкл, высокий / низкий, один (1) / ноль (0), истина / ложь, положительный / отрицательный, положительный / ноль, разомкнутая цепь / замкнутая цепь, разница. потенциал / нет разницы, да / нет.

В случае электронных схем два уровня представлены двумя уровнями напряжения: «высоким» и «низким». Каждый тип цепи имеет свои собственные уровни напряжения, чтобы обеспечить возможность соединения между входами и выходами цепей. Обычно определяются два очень разных уровня (маловероятно, чтобы они перекрывали друг друга); разница между двумя уровнями колеблется от 0,7 В до 28 В (последнее в случае реле).

Для согласования обозначений эти два уровня будут отмечены здесь 1 и 0.

Элементарные логические функции

По количеству входов двери можно классифицировать:

«Двери» без входа: ИСТИНА, ЛОЖЬ;
двери с одним входом: НЕТ ( НЕ ), ДА ;
вентили с двумя входами: И ( И ), НЕ-И ( И- НЕ ), ИЛИ ( ИЛИ ), НЕ-ИЛИ ( ИЛИ ), исключающее ИЛИ ( XOR ), совпадение (компьютер), также известное как исключающее НЕ-ИЛИ или эквивалентность ( XNOR ), участие ;
С трех входов на количество функций начинает влиять комбинаторный взрыв . Однако отметим наличие: И , ИЛИ и т. Д. более двух подъездов.

Можно восстановить функции НЕ , И и ИЛИ , используя только функцию НЕ-И или функцию ИЛИ . Эта характеристика вызвана понятием универсальности операторов НЕ-ИЛИ и НЕ-И (см. Бинарный соединитель несовместимости, также называемый полосой Шеффера ).

Когда вы связываете два совместимых логических элемента, вы можете соединить два входа вместе или один вход с одним выходом. Ни при каких обстоятельствах нельзя подключать два разных выхода, так как они могут выдавать разные данные; в случае электронных ворот это было бы эквивалентно короткому замыканию .

Логические основы работы компьютера

Знания из области математической логики можно использовать для конструирования электронных устройств. Нам известно, что 0 и 1 в логике не просто цифры, а обозначение состояний какого-то предмета нашего мира, условно называемых «ложь» и «истина». Таким предметом, имеющим два фиксированных состояния, может быть электрический ток.

Логические элементы имеют один или несколько входов и один выход, через которые проходят электрические сигналы, обозначаемые условно 0, если «отсутствует» электрический сигнал, и 1, если «имеется» электрический сигнал.

Базовые логические элементы реализуют три основные логические операции: «И», «ИЛИ», «НЕ».

Логический элемент «НЕ» (инвертор)

Простейшим логическим элементом является инвертор, выполняющий функцию отрицания. Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот.

У этого элемента один вход и один выход. На функциональных схемах он обозначается:

Говорят также, что элемент «НЕ» инвертирует значение входной двоичной переменной.

Проверь соответствие логического элемента «НЕ» логическому элементу «НЕ». Воспользуйся тренажером Логические элементы.xlsx

Логический элемент «И» (конъюнктор)

Логический элемент «И» (конъюнктор) выдает на выходе значение логического произведения входных сигналов.

Он имеет один выход и не менее двух входов. На функциональных схемах он обозначается:

Сигнал на выходе конъюнктора появляется тогда и только тогда, когда поданы сигналы на все входы. На элементарном уровне конъюнкцию можно представить себе в виде последовательно соединенных выключателей. Известным примером последовательного соединения проводников является елочная гирлянда: она горит, когда все лампочки исправны. Если же хотя бы одна из лампочек перегорела, то гирлянда не работает.

Проверь соответствие логического элемента «И» логическому элементу «И». Воспользуйся тренажером Логические элементы.xlsx

Логический элемент «ИЛИ» (дизъюнктор)

Логический элемент «ИЛИ» (дизъюнктор) выдает на выходе значение логической суммы входных сигналов. Он имеет один выход и не менее двух входов. На функциональных схемах он обозначается:

Сигнал на выходе дизъюнктора не появляется тогда и только тогда, когда на все входы не поданы сигналы.

На элементарном уровне дизъюнкцию можно представить себе в виде параллельно соединенных выключателей.

Примером параллельного соединения проводников является многорожковая люстра: она не работает только в том случае, если перегорели все лампочки сразу.

Проверь соответствие логического элемента «ИЛИ» логическому элементу «ИЛИ». Воспользуйся тренажером Логические элементы.xlsx

Пример 1.Составьте логическую схему для логического выражения: F=A \/ B /\ A.

1.Две переменные – А и В.

2.Две логические операции: 1-/\, 2-\/.

3.Строим схему:

Пример 2.Постройте логическую схему, соответствующую логическому выражению F=А/\В\/ ¬(В\/А). Вычислить значения выражения для А=1,В=0.

1.Переменных две: А и В; 1 4 3 2

2.Логических операций три: /\ и две \/; А/\В\/ ¬ (В\/ А).

3.Схему строим слева направо в соответствии с порядком логических операций:

4. Вычислим значение выражения: F=1 /\ 0 \/ ¬(0 \/ 1)=0

Минимизация булевых функций

В данном сервисе для минимизации булевых функций используются метод Квайна и карт Карно-Вейча. После получения минимальной формы имеется возможность заново построить логическую схему. Если исходная схема понадобится в дальнейшем, то ее можно предварительно сохранить (меню Действия/Сохранить).

Kx v K ≡ K — тождество поглощения;
Kx v Kx ≡ K — тождество склеивания;
Kx v Ky ≡ K(xvy) — дистрибутивный закон,

K_i_ii_i

Метод карт Карно

Склеить можно как целиком всю карту, либо только выделенные единицы (меню Операции). ►

Удалить

Операции

Сохранить как docx
Сохранить как png

Количество переменныхСетка

После минимизации можно получить логическую схему функции и построить таблицу истинности (кнопка Далее)
Далее

Этот метод используется для БФ не более, чем с шестью аргументами и основан на тождестве склеивания: Kx v Kx ≡ K — две элементарные конъюнкции (ЭК) склеиваются, если они отличаются только знаком инверсии одного аргумента. Чтобы облегчить нахождение таких пар (четверок, восьмерок,…) склеивающихся ЭК, используют специальное представление БФ в виде таблицы – карты Карно (другое название — диаграмма Вейча). Чтобы заполнить карту Карно необходимо щелкнуть левой кнопкой мышки на соответствующую ячейку.
Карта Карно обладает той особенностью, что две ПЭК, соответствующие соседним клеткам карты, отличаются знаком инверсии только одного аргумента, т.е. их можно склеивать. Причем соседними являются не только клетки, например, с номерами 1 и 3, но и клетки с номерами 12 и 8, 12 и 4, т.е. карту можно «сворачивать» в цилиндр, соединяя горизонтальные (вертикальные) ее границы.
Две единицы «склеиваются» каждый раз, когда они стоят рядом в строке или столбце (карту можно свернуть в цилиндр). В результате склеивания число букв, входящих в ПЭК, уменьшается на единицу.

Алгоритм построения

Таблицы истинности показывают, какой вид может принять выражение при различных входящих в него значениях переменных. Для того чтобы их правильно построить и выполнить вычисление логического выражения нужно придерживаться установленного алгоритма. Построение таблиц выполняют в следующей последовательности:

подсчитывают количество переменных n;
вычисляют число строк для будущей таблицы используя формулу m = 2n+1;
определяют число логических операций;
устанавливают порядок выполнения операций в соответствии со скобками и приоритетами;
строят таблицу с указанием столбцов и наборов значений, заданных логических операций;
заполняют оставшиеся ячейки в таблице.

Булевы функции

Параметры решения►f(x,y,z) = x → y!zx → y!zУпростить выражение

(...) — ввод скобок, x -отрицание (NOT, !, ¬), & — логическое И, AND, ∧, *, v — логическое ИЛИ, OR, ∨, = — эквивалентность, ˜, ≡, , ⊕ — сумма по модулю 2, | — штрих Шеффера, И-НЕ, AND-NOT, ↓ — стрелка Пирса, ИЛИ-НЕ, OR-NOT, ← — обратная импликация.

(…)
x
˅
&
=
→
⊕
|
↓
←
Clear

Для вложенного отрицания необходимо использовать знак !. Например, x v y = !(x v y) или x v y = x v !y
Далее
Построить схему

По найденной таблице истинности можно определить логические значения высказываний, например, при x=0, y=0, z=1
Чтобы проверить высказывание на истинность или ложность, функцию необходимо вводить без знака равно (=). Например, A+B→A&B=1, необходимо ввести A+B→A&B. Если в результате преобразований получится, что f=1, то высказывание истинно, если f=0 — ложно.

булеву функциюдизъюнкцииконъюнкцииотрицания
Область определения БФ E – конечное множество, поэтому БФ можно задать с помощью таблицы истинности, содержащей |E|=2n строк. Столбец значений БФ при этом представляет собой двоичное слово длиной 2n. Поэтому количество различных БФ n переменных равно 22n.

x f
0 1
1 0
x y f
0 0 0
0 1 0
1 0 0
1 1 1
x y f
0 0 0
0 1 1
1 0 1
1 1 1
x y f
0 0 0
0 1 1
1 0 1
1 1 0
x y f
0 0 1
0 1 0
1 0 0
1 1 0
x y f
0 0 1
0 1 0
1 0 0
1 1 1
x y f
0 0 1
0 1 1
1 0 0
1 1 1
x y f
0 0 1
0 1 1
1 0 1
1 1 0

Основные равносильности логики высказываний

Название	Формула
Закон исключенного третьего	X v !X ≡ И
Закон противоречия	X & !X ≡ Л
Закон коммутативности	X & Y ≡ Y & XX v Y ≡ Y v X
Закон ассоциативности	(X & Y)&Z ≡ X&(Y&Z)(X v Y) v Z ≡ X v (Y v Z)
Закон дистрибутивности	X&(Y v Z) ≡ X&Y v X&ZX v Y&Z ≡ (X v Y)&(X v Z)
Закон двойного отрицания	!!X ≡ X
Закон идемпотентности	X&X ≡ X, X v X ≡ X
Законы де Моргана	!(X v Y) ≡ !X & !Y!(X & Y) ≡ !X v !Y
Закон поглощения	X v X&Y ≡ XX&(X v Y) ≡ X
Законы склеивания	(X & Y)v(X & !Y) ≡ X(X v Y)&(X v !Y) ≡ X
Замена импликации	X → Y ≡ !X v Y
Замена эквиваленции	X = Y ≡ X&Y v !X&!Y

Пример. Упростите выражение: (x˅y˅z)→(x˅y)*(x˅z)
Упростим функцию, используя основные законы логики высказываний.
Замена импликации: A → B = !A v B
Для нашей функции:
(x v y v z)→((x v y) (x v z)) = x v y v z v (x v y) (x v z)
Упростим функцию, используя законы де Моргана: !(A v B) = !A & !B
Для нашей функции:
x v y v z = x y z
По закону дистрибутивности:
(x v y) (x v z) = x v x z v y x v y z
получаем:
f = x y z v x v x z v y x v y z
После элементарных преобразований получаем:
f = x y z v x v x z v y x v y z = x y z v x v y z
f = y z v y z v x