Таблица истинности логических операций - алгоритм построения

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

Любое выражение можно описать формулой, в которую будут включаться переменные, характеризующие состояния, и обозначающие функции знаки логических операций. Поэтому используя язык математики, в частности, алгебры, любое сложное высказывание можно разделить на несколько простых, а затем объединить логической связью.
Обычно значениями истинности описывают логическую функцию, у которой показатели параметров определяют верность. Раздел математики рассматривающий их на правдивость или ложность называется булевым. В 1854 году английский учёный Джордж Буль предложил метод, позволяющий проводить анализ классов и высказываний. Согласно ему, любое значение может принимать одно из двух состояний — истина или ложь.
Эти состояния принято обозначать арабскими цифрами один либо ноль или словами true и false. Это возможно из-за того, что для математики важна только истинность высказываний, а конкретное содержание второстепенно. Простые высказывания принято считать логическими переменными, а сложные — функциями логики. Выражения для упрощения записи обозначают латинскими буквами A, B, C.

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


- AND (И) — применяется для сравнения двух бит. Результатом действия будет единица, но лишь в том случае, если значения двух ячеек одинаковое. При остальных вариантах итог будет иметь устойчивое нулевое состояние.
- OR (ИЛИ) — по сути, операция обратная AND. Результат становится нулевым, если содержимое двух сравниваемых бит одинаковое. В остальных случаях он равный единице.
- XOR (ИЛИ) — если значения, содержащиеся в двух сравниваемых битах противоположны, при выполнении логического действия результат будет равный единице. Во всех остальных случаях он будет равняться нулю.
- NOT (НЕ) — действие, используемое для одного бита. Если первоначально ячейка находилась в нулевом состоянии, то после выполнения над ней операции она станет равной единице и наоборот. Фактические это логическая инверсия.
Эти операции являются основными элементами при составлении таблиц истинности и получения возможного результата. На основании их построена алгебра Буля. Некоторые элементы получаются путём объединения нескольких операций. Так, существует состояние: NAND (И-НЕ) и NOR (ИЛИ-НЕ). Первый элемент является инверсией операции «И», а второй — «ИЛИ». На основании рассмотренных операторов строится работа всех цифровых интегральных схем.
В информатике существует своя терминология, обозначающая то или иное логическое действие. Так, AND называют операцией конъюнкции, OR — дизъюнкции, XOR — сложение по модулю 2, NOT — отрицание. Задача инженера при анализе схем или алгоритма сводится к выполнению булевой арифметики и упрощению выражений. Для этого используют различные правила и положения не требующих доказательства.
Аксиомы и законы
Построение таблиц в удобной форме позволяет определить, когда определённое действие или высказывание принимает верное значение, а в каком случае нет. В верхней строчке записывают логическую форму высказывания, а в столбцах - истинные значения. Некоторые комбинации высказываний всегда будут истинными или ложными, независимо от содержания. Поэтому и были сформулированы следующие законы:

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

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

Кроме того, используется закон:
- инверсии (отрицания) — если логическое высказывание истинно, то отрицание его будет ложным выражением;
- импликации (следования) — для всегда истинного сложного логического выражения ложь будет тогда, когда из верности следует отрицание;
- эквивалентности (равнозначности) — выражение будет истинным лишь тогда, когда оба высказывания имеют одинаковое значение.
При построении таблиц нужно придерживаться установленного порядка выполнения упрощения операций. Вначале считают инверсию и конъюнкцию, а затем дизъюнкцию, импликацию и эквиваленцию. При изменении же порядка выполнения действий в описании логических операций используют скобки.
Алгоритм построения
Таблицы истинности показывают, какой вид может принять выражение при различных входящих в него значениях переменных. Для того чтобы их правильно построить и выполнить вычисление логического выражения нужно придерживаться установленного алгоритма. Построение таблиц выполняют в следующей последовательности:

- подсчитывают количество переменных n;
- вычисляют число строк для будущей таблицы используя формулу m = 2n+1;
- определяют число логических операций;
- устанавливают порядок выполнения операций в соответствии со скобками и приоритетами;
- строят таблицу с указанием столбцов и наборов значений, заданных логических операций;
- заполняют оставшиеся ячейки в таблице.
Для заполнения таблиц нужно упрощать выражения с учётом последовательности выполнения операций. При этом учитывать, что если значение какого-то из аргументов функции в соответствующей строке таблицы будет равное нулю, то записывать его нужно в виде отрицания.
Пример задания
Пусть необходимо построить таблицу для логического выражения F = (A → B) * (A + B). Эта формула состоит из двух логических переменных A и B и нескольких операций. Начинают построение с определения строк. Используя формулу 2n+1 для рассматриваемого примера можно установить, что их число будет: x = 22 + 1 = 5.

Теперь следует определить число столбцов. Для этого используется формула, в которой учитывается количество переменных и операций. Последние можно просто посчитать, сложив количество разных знаков, используемых в записи формулы. Но правильней сначала расставить порядок операций, а затем посчитать. Согласно порядку действия над операциями их нумерацию можно представить в следующей очерёдности:
- Импликация в первой скобке.
- Инверсия во второй скобке переменной A.
- Отрицание во второй скобке неизвестной B.
- Сложение во втором члене.
- Конъюнкция.
В итоге получится, что столбцов будет: Y = 2 + 5 = 7. Теперь нужно построить таблицу 7Х5. В шапку первого и второго столбца вписывают переменные, а затем операции над ними. Затем в строках, соответствующих A и B нужно записать всё, что с ними может произойти. В итоге останется только правильно посчитать последний столбец.

Для этого нужно использовать законы. Необходимо выполнить логическое умножение значений в скобках. Первой и второй строчке будет соответствовать операция произведения один на один, что в ответе даст единицу. Третьей и четвёртой - ноль на один, что в итоге даст ноль. Последний столбец является главным для рассматриваемой логической функции. По нему можно узнать значение логической функции для любых форм переменных A и B.
Это довольно простая задача, содержащая всего две переменных. Но в реальности, например, в программировании, их может быть намного больше. Решать такие задания методом перебора проблематично. Поэтому при решении сложных примеров функцию вначале пытаются упростить.
Например, заданно выражение (x + y + z) * (x + y). По сути, оно записано в совершенно нормальной конъюнктивной форме. Но для приведения его к этому виду нужно, чтобы во втором выражении стояла z. Для того чтобы её добавить необходимо обратить внимание на то, что внутри скобок стоит логическое сложение. Поэтому дописав к нему ноль, результат не изменится. Добавить ноль через z можно, как ноль умножить на НЕ z. В итоге получится выражение (x + y + z) * (x + y + z + z), для которого, используя алгоритм составить таблицу уже не так и сложно.
Вычисления онлайн
В интернете есть сервисы, автоматически строящие таблицы истинности. Такие сайты предлагают свои услуги бесплатно и доступны даже тем, кто слабо ориентируется в теме. С их помощью можно находить таблицы для довольно сложных выражений, решение которых требует скрупулёзности в расчёте. В основе онлайн-вычислений заложены принципы логических законов, поэтому за достоверность результата можно не переживать. Тем более расчёт занимает совсем небольшое количество времени.

Для того чтобы воспользоваться сайтами-калькуляторами пользователю необходимо знать обозначение операций, иметь подключение к интернету и установленный веб-обозреватель, поддерживающий Flash-технологию. Регистрацию, указание личных данных сервисы, предлагающие такого рода услуги, не требуют.
Из различных порталов можно отметить три наиболее популярных калькулятора:
- Allcalc.
- Programforyou.
- Uchim.
Эти сайты имеют интуитивно понятный интерфейс и что довольно полезно, на своих страницах содержат краткую теорию, используемую для составления таблиц истинности и даже примеры решений.
Еще тесты
- Анатомия
- Английский язык
- Астрономия
- Биология
- Литература
- История
- Педсовет
- Естествознание
- Финансы и кредит
- Правоведение
- Товароведение
- Экономика
- Социология
- Маркетинг
- Обществознание
- Культурология
- Математика
- Философия
- Русский язык
- Психология
- Политология
- Делопроизводство
- Бухгалтерия
- ОБЖ
- Орфография
- География
- Биографии
- Физика
- Пунктуация
- Краткие содержания
- Химия
- Менеджмент
- Тест на тему Тест по теме Дыхательная система человека 7 вопросов
- Тест на тему Строение человека - анатомия внутренних органов 7 вопросов
- Тест на тему Гормоны - определение, виды, функции, роль в организме человека 5 вопросов
- Тест на тему Лейкоциты в крови - строение, где образуются и разрушаются, норма содержания 5 вопросов
- Тест на тему Одноклеточные организмы - строение , формы и признаки представителей 8 вопросов
- Тест на тему Бесполое размножение - виды, формы и биологическое значение процесса 9 вопросов
- Тест на тему Синтез АТФ - структура, функции и пути образования аденозинтрифосфорной кислоты 7 вопросов
- Тест на тему Биогеоценоз - определение, структура и свойства 5 вопросов
- Тест на тему Символизм в литературе - основные черты и представители направления 6 вопросов
- Тест на тему "У Лукоморья дуб зеленый" - анализ стихотворения Александра Сергеевича Пушкина 8 вопросов
- Тест на тему Родион Раскольников и Соня Мармеладова - история взаимоотношений в романе Ф. М. Достоевского "Преступление и наказание" 6 вопросов
- Тест на тему Семья Мелеховых в романе М. Шолохова "Тихий дон" 7 вопросов
- Тест на тему Отечественная война 1812 года - причины, основные сражения, итоги 7 вопросов
- Тест на тему Правление Ивана Грозного - внутренняя и внешняя политика 7 вопросов
- Тест на тему Образование СССР - причины, этапы становления, состав, итоги 6 вопросов
- Тест на тему Крещение руси князем Владимиром - причины, история, значение принятия христианства 6 вопросов
- Тест на тему Пищевая цепочка в природе - звенья, схемы и примеры цепей 5 вопросов
- Тест на тему Экологические факторы - классификация, примеры, общие закономерности воздействия 5 вопросов
- Тест на тему Биосфера - определение, состав, свойства, границы 5 вопросов
- Тест на тему Возникновение жизни на земле 6 вопросов
- Тест на тему Права и свободы человека и гражданина 5 вопросов
- Тест на тему Унитарное предприятие - виды, признаки, участники, особенности 7 вопросов
- Тест на тему Формы собственности - типы и виды и их характеристика 7 вопросов
- Тест на тему Предпринимательское право - понятие, принципы, предмет и объект, функции 5 вопросов
- Тест на тему Ликвидность предприятия - определение, виды, формула расчета 7 вопросов
- Тест на тему Процентная ставка - понятие, виды, методы расчета и начисления 5 вопросов
- Тест на тему Финансы - определние, сущность, основные функции, виды 7 вопросов
- Тест на тему Коммерческая деятельность - сущность и содержание 7 вопросов
- Тест на тему Статистическое наблюдение - виды, способы, последовательность этапов 6 вопросов
- Тест на тему Социальный контроль - понятие и функции, формы и методы, значение 5 вопросов
- Тест на тему Анкетирование - правила составления и виды вопросов, оформление результатов 5 вопросов
- Тест на тему Социальная группа — понятие, типы, критерии выделения 8 вопросов
- Тест на тему Деятельность человека - основные виды и характеристики 7 вопросов
- Тест на тему Воздушно-десантные войска (ВДВ) - история создания, подразделения, оснащение 7 вопросов
- Тест на тему Субъекты РФ - количество, виды, правовой статус 7 вопросов
- Тест на тему Социальные нормы - понятие, виды и характеристка, функции, примеры 6 вопросов
- Тест на тему Что такое угол 5 вопросов
- Тест на тему Деление в столбик — подробное описание алгоритма решения задач, примеры 10 вопросов
- Тест на тему Вычитание дробей - правила и примеры с решениями 5 вопросов
- Тест на тему Модуль числа - свойства, действия, как решать уравнения и неравенства с модулем 10 вопросов
- Тест на тему Ислам - история возникновения религии, основные положения 7 вопросов
- Тест на тему Мышление - определение, виды, функции, свойства 5 вопросов
- Тест на тему Что такое мораль, ее категории и функции 6 вопросов
- Тест на тему Буддизм - кратко о религии (история возникновения, основные положения, священные книги) 6 вопросов
- Тест на тему Безличные предложения в русском языке 8 вопросов
- Тест на тему Ударение в словах в русском языке - правила и проверка постановки 5 вопросов
- Тест на тему Морфемный разбор слова - правила выполнения с примерами 5 вопросов
- Тест на тему Сложноподчиненные предложения в русском языке 6 вопросов
- Тест на тему Мотивация - определение, виды и типы в психологии, менеджменте 5 вопросов
- Тест на тему Интеллект - понятие, признаки, как развивать, оценка 5 вопросов
- Тест на тему Социализация личности - понятие и сущность, агенты, примеры 5 вопросов
- Тест на тему Типы темперамента и их психологическая характеристика 5 вопросов
- Тест на тему Органы исполнительной власти РФ - понятие и правовой статус, структура и фунции 7 вопросов
- Тест на тему Европейский союз - история создания, цели, состав 5 вопросов
- Тест на тему Тоталитаризм - определение, характерные черты, плюсы и минусы идеологии 5 вопросов
- Тест на тему Политическая идеология - определение понятия, функции, классификация, особенности 5 вопросов
- Тест на тему Оборотные средства предприятия, их структура, учет и анализ 7 вопросов
- Тест на тему Бюджетная классификация - определение, структура 7 вопросов
- Тест на тему Калькуляция - основные понятия, примеры расчетов себестоимости 7 вопросов
- Тест на тему Бухгалтерский учет материально-производственных запасов на предприятии 8 вопросов
- Тест на тему Пистолет Макарова - шпаргалка по тактико-техническим характеристикам 9 вопросов
- Тест на тему Чрезвычайная ситуация - понятие, типы ЧС, причины возникновения, стадии развития 7 вопросов
- Тест на тему Вооруженные силы Российской Федерации — организационная структура и предназначение 7 вопросов
- Тест на тему ВМФ (Военно-Морской флот) России - структура, история, состав 7 вопросов
- Тест на тему Перу - географическое положение, климат и достопримечательности 9 вопросов
- Тест на тему Климатические пояса Земли - характеристика и особенности 8 вопросов
- Тест на тему Тайга - географическое положение, животный и растительный мир, особенности и характеристика природной зоны 7 вопросов
- Тест на тему Озеро - определение, классификация, признаки 6 вопросов
- Тест на тему Братья Гримм - биография, жизнь и творчество немецких писателей 10 вопросов
- Тест на тему Тамерлан (1336-1405) - биография, жизнь и завоевания великого полководца 10 вопросов
- Тест на тему Максим Горький (1868-1936) - биография, кратко самое важное, интересные факты из жизни писателя 9 вопросов
- Тест на тему Блок Александр Александрович (1880-1921) - биография, жизненный и творческий путь 11 вопросов
- Тест на тему "Ночь перед Рождеством" - краткое содержание повести Н. В. Гоголя 10 вопросов
- Тест на тему "Маленький Мук" - краткое содержание сказки Вильгельма Гауфа 10 вопросов
- Тест на тему "Дворянское гнездо" - краткое содержание романа И.С. Тургенева 8 вопросов
- Тест на тему "Бирюк" - краткое содержание рассказа И.С. Тургенева 10 вопросов
- Тест на тему Серная кислота - химические и физические свойства и реакции 8 вопросов
- Тест на тему Муравьиная кислота - формула, свойства, получение и применение 7 вопросов
- Тест на тему Сложные эфиры - характеристика, классификация и примеры соединений 8 вопросов
- Тест на тему Толуол - формула, свойства и применение химического вещества 8 вопросов
- Тест на тему Оценка персонала - виды, критерии и методы 7 вопросов
- Тест на тему Управление персоналом - задачи, функции, современные подходы 5 вопросов
- Тест на тему Менеджмент предприятий — сущность, виды, задачи и цели 7 вопросов
- Тест на тему Организационная структура предприятия — типы и предназначение 7 вопросов