Таблицы истинности элементы теории множеств и алгебры логики

Ключевые слова
таблицы истинности
логическая функция
равносильные (эквивалентные) логические выражения

Таблица истинности
Таблицу значений, которые принимает логическое выражение при всех сочетаниях значений (наборах) входящих в него переменных, называют таблицей истинности логического выражения.
!
Таблицы истинности логических операций
Функцию от n переменных, аргументы которой и сама функция принимают только два значения – 0 и 1, называют логической функцией.
Таблица истинности может рассматриваться как способ задания логической функции.
!

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

Пример построения таблицы истинности
Построим таблицу истинности для логического выражения
Сколько строк будет в таблице?
Сколько столбцов будет в таблице?
В этом выражении две переменные – А и В.
В таблице будет 5 строк (22 плюс строка заголовка).
В логическом выражении две логические переменные и пять логических операций. Итого 7 столбцов.
1
4
2
5
3
1
2
3
4
5
Строим таблицу из 5 строк и 7 столбцов.
Заполним заголовок таблицы с учётом приоритета логических операций (поря-док выполнения операций: инверсия, конъюнкция, дизъюнкция).
Заполним наборы входных переменных с учётом того, что они представляют собой ряд целых двухразрядных двоичных чисел от 0 до 3.
Заполним столбцы таблицы согласно правилам определения истинности логических операций.
Обратите внимание на последний стол-бец, содержащий конечный результат. Какой из рассмотренных логических операций он соответствует?
А
В
1
0
0
0
1
0
1
1
0
0
1
0
0
0
0
1
0
0
1
1

Эквивалентные выражения
Логические выражения, зависящие от одних и тех же логических переменных, называются равносильны-ми или эквивалентными, если для всех наборов входящих в них переменных значения выражений в таблицах истинности совпадают.
!
Ответ
?

Анализ таблиц истинности
№ 1. Известен фрагмент таблицы истинности для логичес-кой функции F (А, В, С). Сколько из приведённых ниже логических выражений соответствуют этому фрагменту?
а) (A ∨ С) & В
б) (A ∨ В) & (C → A)
в) (A & В ∨ С) & (В → A & С)
г) (A → В) ∨ (С ∨ A → В)
Ответить на поставленный вопрос можно, вычислив значение каждого логического вы-ражения на заданном наборе переменных и сравнив его с имеющимся значением F.
Вычисления будем производить построчно.
Таблица
Таблица
Таблица
Таблица
Ответ
Ответ: 2 (а, г)

а) (A ∨ С) & В
б) (A ∨ В) & (C → A)
в) (A & В ∨ С) & (В → A & С)
г) (A → В) ∨ (С ∨ A → В)
Анализ таблиц истинности
№ 1. Известен фрагмент таблицы истинности для логичес-кой функции F (А, В, С). Сколько из приведённых ниже логических выражений соответствуют этому фрагменту?
а) (A ∨ С) & В
1
1
1
1
1
0
1
2

а) (A ∨ С) & В
б) (A ∨ В) & (C → A)
в) (A & В ∨ С) & (В → A & С)
г) (A → В) ∨ (С ∨ A → В)
Анализ таблиц истинности
№ 1. Известен фрагмент таблицы истинности для логичес-кой функции F (А, В, С). Сколько из приведённых ниже логических выражений соответствуют этому фрагменту?
б) (A ∨ В) ∧ (C → A)
1
1
1
2
3
1

а) (A ∨ С) & В
б) (A ∨ В) & (C → A)
в) (A & В ∨ С) & (В → A & С)
г) (A → В) ∨ (С ∨ A → В)
Анализ таблиц истинности
№ 1. Известен фрагмент таблицы истинности для логичес-кой функции F (А, В, С). Сколько из приведённых ниже логических выражений соответствуют этому фрагменту?
в) (A ∧ В ∨ С) ∧ (В → A ∧ С)
0
1
1
2
3
1
4
5
1
1

а) (A ∨ С) & В
б) (A ∨ В) & (C → A)
в) (A & В ∨ С) & (В → A & С)
г) (A → В) ∨ (С ∨ A → В)
Анализ таблиц истинности
№ 1. Известен фрагмент таблицы истинности для логичес-кой функции F (А, В, С). Сколько из приведённых ниже логических выражений соответствуют этому фрагменту?
г) (A → В) ∨ (С ∨ A → В)
0
1
1
2
3
0
4
0
1
1
1
1
1
1
1
1

Анализ таблиц истинности
№ 2. Дана логическая функция:
Справа приведён фрагмент таблицы истинности, содержащий все наборы переменных, на которых F истинна. Определите, какому столбцу таблицы соответствует каждая из переменных.
Ответ
Существуют разные подходы к решению подобных задач:
1) построение полной таблицы истинности
2) методом рассуждений
Решение
Решение

Анализ таблиц истинности
№ 2.
Решение:
Сколько строк в полной таблице истинности для данной функции?
Данная функция зависит от 3 логических переменных. Полная таблица истинности для нее должна состоять из 8 (23) строк.
При каких наборах переменных x, y, z функция F (x, y, z) = 0?
Наборы переменных, на которых функция ложна - 001, 101 и 110.

= 0
Анализ таблиц истинности
№ 2.
Решение:
Выясним, при каких значениях x, y, z функция F(x, y, z) = 0.
= 0
=0
Дизъюнкция («или») ложна только в случае равенства нулю каждого из операндов, входящих в нее.
Конъюнкция («и») ложна, если хотя бы один из операндов равен нулю.
Сравним эту таблицу с восстановленным фрагментом исходной таблицы истин-ности.
x
x
y
z
y
Ответ: z, y, x

В данном примере два логических выра-жения связаны операцией «и».
Анализ таблиц истинности
Тогда в строках, где x = 1 значение y = 1.
№ 2.
Решение:
= 1
=1
0
1
x не 2-я переменная
x не 1-я переменная
y - 2-я переменная
z - 1-я переменная
Конъюнкция («и») истинна тогда и только тогда, когда каждый из операндов, входящих в нее, равен истине.
= 1
х не может быть
2-й переменной
х не может быть
1-й переменной
x
x
y – не может быть
1-й переменной
y
z
z
y
или
Ответ: z, y, x

Самое главное
Таблицу значений, которые принимает логическое выражение при всех сочетаниях значений (наборах) входящих в него переменных, называют таблицей истинности логического выражения.
Истинность логического выражения можно доказать путём построения его таблицы истинности.
Функцию от n переменных, аргументы которой и сама функция принимают только два значения – 0 и 1, называют логической функцией.
Таблица истинности может рассматриваться как способ задания логической функции.

Вопросы и задания
№ 3. Проверьте правильность решения задания №2. Для этого составьте таблицу истинности.

Вопросы и задания
№ 4. Составлена таблица истинности для логического выражения, содержащего n переменных. Известно m — количество строк, в которых выражение принимает значение истина. Требуется выяснить, в скольких случаях логическое выражение примет значение ложь при следующих значениях n и m:
1) n = 4, m = 9
2) n = 8, m = 156
3) n = 12, m = 1596
Решение / Ответ
24 – 9 = 16 – 9 = 7
28 – 156 = 256 – 156 = 100
212 – 1596 = 4096 – 1596 = 2500