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

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

Булева алгебра

Алгебра логики основывается на простых логических выражениях, которые связываются между собой операциями, создавая при этом сложные выражения. Следует отметить, что булева алгебра содержит две бинарные операции: умножение и сложение (конъюнкция и дизъюнкция соответственно); одну унарную – инверсия. Все простые выражения (элементы сложного логического выражения) принимают одно из двух значений: «1» или «0», «истина» или «ложь», «+» или «-» соответственно.

Алгебра логики основывается на нескольких довольно простых аксиомах:

• ассоциативности;
• коммутативности;
• поглощения;
• дистрибутивности;
• дополнительности.

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

Правила составления таблицы

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

Для того чтобы правильно составить логическую таблицу, необходимо для начала определиться с количеством строк. Как это сделать? Посчитайте количество переменных, входящих в состав сложного выражения, и воспользуйтесь простой формулой: А=2 в степени n. А – это количество строк в составляемой таблице истинности, n – это количество переменных, которые входят в сложное логическое выражение.

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

Далее мы обращаемся к нашему выражению и определяем порядок выполняемых действий. Лучше для себя порядок пометить карандашом (один, два и так далее).

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

Далее необходимо заполнить шапку нашей таблицы. Ниже вы видите пример этого.

Теперь переходите к заполнению возможных комбинаций. Для двух переменных они будут следующие: 00, 01, 10, 11. Для трех переменных: 000, 001, 010, 011, 100, 101, 110, 111.

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

Пример

Сейчас мы рассмотрим пример построения таблицы истинности логического выражения: инверсия А+В*А.

1. Подсчет переменных: 2. Количество строк: 4+1=5.
2. Порядок выполнения действий: первая инверсия, вторая конъюнкция, третья дизъюнкция.
3. Количество столбцов: 3+2=5.
4. Приступаем к начертанию и заполнению таблицы.

Как правило, задание звучит таким образом: «сколько комбинаций удовлетворяет условию F=0» или «в каких сочетаниях F=1». На первый вопрос ответ – 1, на второй – 00, 01, 11.

Внимательно читайте задание, которое вам дается. Вы можете правильно решить задачу, но ошибиться в написании ответа. Еще раз обращаем ваше внимание на порядок выполнения действий:

• отрицание;
• умножение;
• сложение.

Задача

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

Даны четыре значения числа А: 1) 7, 2) 6, 3) 5, 4) 4. Для какого из них высказывание «инверсия (А меньше 6)+(А меньше 5)» является ложным?

Наш первый столбик будет заполнен значениями 7, 6, 5, 4 обязательно в этой последовательности. В следующем столбце мы должны ответить на вопрос: "А меньше 6?" Третий столбик заполняем аналогично, только теперь отвечаем на вопрос: "А меньше 5?"

Определяемся с последовательностью операций. Вспоминаем, что отрицание имеет приоритет перед дизъюнкцией. Значит, следующий столбик мы заполняем значениями, которые соответствуют условию не(А меньше 6). Четвертый будет отвечать на главный вопрос нашей задачи. Ниже вы видите пример заполнения таблицы.

Обратите внимание на то, что у нас имеются номера ответов, ложным выражение будет при значении А=5, это третий вариант ответа.