Таблица истинности

Что такое таблицы истинности

Таблица истинности необходима для совершения логических операций. Она включает в себя n+1 столбцы и 2ⁿ строки, где n - число используемых переменных. В первых n столбцах представлены разные значения аргументов функции, а в n+1 столбце представлены значения функции, которые она принимает на данном наборе аргументов.

Набором называется совокупность значений переменных. А = 0, В = 1. В случае, когда количество переменных n, число различных наборов будет равно 2^N. Например, для трех переменных число разных наборов будет равно 2³ = 8.

Для создания таблиц истинности используются обозначения логических значений 0 (ложь) и 1 (истина).

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

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

Логические операции

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

К логическим операциям относятся конъюнкция, дизъюнкция, импликация, разделительная дизъюнкция, эквиваленция, антиконъюнкция, антидизъюнкция.

Логические выражения

Их можно разделить на два типа:

• выражения, использующие операции сравнения и принимающие логические значения. Например, выражение a < b, где a = 12, а b = 9, равно значению «ложь»;
• логические выражения, которые связаны с логическими величинами и операциями. Например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина.

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

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

Инверсия

Если данное высказывание обозначается буквой A, то отрицание исходного высказывания обозначается следующим образом \([\overline{A}]\). Кроме этого возможно использование условного обозначения \(\neg A\). Читаться это будет как «не А», «А ложно», «неверно, что А», «отрицание А».

Унарной в данном случае называется операция, которая используется относительно одной величины.

Конъюнкция

Конъюнкция может быть истинной только в том случае, если оба высказывания истинны. Например, A ∧ B, если A = ложь, а B = истина, является ложным.

Дизъюнкция

Логическое высказывание будет истинным, если истинно хотя бы одно из условий. Например, A ∨ B истинно, даже если А = истина, а В = ложь. Высказывание будет ложным только в том случае, если ложны и А, и В.

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

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

Строить таблицы истинности необходимо по следующему алгоритму:

1. Вычислить число переменных в выражении (n).
2. Вычислить общее количество логических операций в выражении.
3. Определить последовательность, в которой будут выполняться логические операции.
4. Установить количество столбцов в таблице — количество переменных и количество операций.
5. Внести в шапку таблицы переменные и операции, соблюдая последовательность, определенную в пункте 3.
6. Высчитать количество строк в таблице, используя формулу m = 2ⁿ
7. Занести в таблицу наборы входных переменных. Они представляют собой целый ряд n-разрядных двоичных чисел от 0 до 2ⁿ−1.
8. Заполнить таблицу, совершая логические операции.

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

Задача

Построим таблицу истинности и решим выражение\( F = (A \vee B) \wedge (¬A \vee ¬B)\). Будем пользоваться приведенным выше алгоритмом.

1. Число переменных в выражении n = 2.
2. Общее количество логических операций в выражении — 5.
3. Последовательность выполнения логических операций — 1, 5, 2, 4, 3.
4. Количество столбцов — 7. Логические переменные (А и В) + логические операции \(\vee\), \(\wedge\), \(¬\), \(\vee\) , \(¬\) = 2 +5 = 7.
5. Количество строк — 5, исходя из m =2ⁿ, таким образом 2² = 4, 4+1 (строка заголовков столбцов) = 5.
6. Заполним таблицу.

Решение

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

F = 0 при A = B = 0 и A = B = 1

Задача

Построим еще одну таблицу истинности и решим выражение \(F = X \vee Y \wedge ¬Z\)

1. Число переменных в выражении n = 3.
2. Общее количество логических операций в выражении — 3.
3. Последовательность выполнения логических операций — 3, 2, 1.
4. Количество столбцов — 6. Логические переменные (X, Y, Z) + логические операции\( \vee\), \(\wedge\), ¬ = 3 + 3 = 6.
5. Количество строк — 9, исходя из m =2ⁿ, таким образом 2³ = 8, 8+1 (строка заголовков столбцов) = 9.
6. Заполним таблицу.

Решение

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

F = 0, при X = Y = Z = 0; при X = Y = 0 и Z = 1.