Таблицы истинности для логических функций. Определение числа логических функций

Тема: таблицы истинности для логических функций. Определение числа логических функций.

Холдаров Темур 075-21

План:
1) Понятие таблиц истинности
2) Правила того, как следует проводить построение таблицы истинности
3) Порядок действий при построении таблицы истинности для логических выражений
4) О порядке логических операций
5) Построения функции, если известна её таблица истинности

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

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

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

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

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

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

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

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

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

Определение
Логические операции — построение из одного или нескольких высказываний нового высказывания.

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

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

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

Определение
Логическое выражение — это запись, принимающая логическое значение «истина» или «ложь».

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

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

вычисляется существующие функциональные зависимости;

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

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

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

Конъюнкция

Определение
Конъюнкция — это логическое умножение. Эта операция, для которой требуются два и более логических величины. Конъюнкция соединяет логические высказывания при помощи связки «и». Связка изображается символом ∧.

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

Дизъюнкция
Определение
Дизъюнкция — логическое сложение. Эта логическая операция соединяет два и более высказываний с помощью связки «или». Эта связка обозначается как ∨.

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

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

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

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

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

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

А В А∨В ¬А ¬В ¬А∨¬В (A∨B)∧(¬A∨¬B)

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

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

Задача

Построим еще одну таблицу истинности и решим выражение F=X∨Y∧¬Z

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

X Y Z ¬Z Y∧¬Z X∨Y∧¬Z

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

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

Логические операции и таблицы истинности

1) Логическое умножение или конъюнкция:

Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.
Обозначение: F = A & B.

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

A B F
1 1 1
1 0 0
0 1 0
0 0 0

2) Логическое сложение или дизъюнкция:

Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.
Обозначение: F = A + B.

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

A B F
1 1 1
1 0 1
0 1 1
0 0 0

3) Логическое отрицание или инверсия:

Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

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

A неА
1 0
0 1

4) Логическое следование или импликация:

Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. Тоесть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.

Таблица истинности для импликации

A B F
1 1 1
1 0 0
0 1 1
0 0 1

5) Логическая равнозначность или эквивалентность:

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

Таблица истинности для эквивалентности

A B F
1 1 1
1 0 0
0 1 0
0 0 1