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

ТАБЛИЦЫ ИСТИННОСТИ

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ И АЛГЕБРЫ ЛОГИКИ

Ключевые слова

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

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

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

!

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

А

0

В

A & B

0

0

1

0

А ∨ B

1

1

A → B

0

0

0

1

1

0

1

A  ⊕ B

1

1

A ↔ B

0

1

0

1

1

1

1

0

1

0

0

1

А

0

A

1

1

0

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

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

!

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

Определить количество строк таблицы m = 2 n , где n - количество переменных в логическом выражении

Определить число столбцов таблицы - сумма количест-ва логических переменных и операций в выражении

Установить последовательность выполнения логичес-ких операций с учётом скобок и приоритетов операций

Заполнить строку с заголовками столбцов таблицы истинности (имена переменных, номера операций)

Выписать наборы входных переменных (ряд целых n -разрядных двоичных чисел от 0 до 2 n – 1 )

Провести заполнение таблицы истинности по столбцам, выполняя логические операции

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

Построим таблицу истинности для логического выражения

1

4

2

5

3

A & B ∨ A & B

Сколько строк будет в таблице?

5

В

А

4

3

2

1

В этом выражении две переменные – А и В .

В таблице будет 5 строк (2 2 плюс строка заголовка).

1

0

1

1

1

0

0

0

0

0

0

1

1

0

Сколько столбцов будет в таблице?

В логическом выражении две логические переменные и пять логических операций. Итого 7 столбцов.

1

0

0

0

0

1

0

1

1

0

1

0

0

1

Заполним наборы входных переменных с учётом того, что они представляют собой ряд целых двухразрядных двоичных чисел от 0 до 3.

Строим таблицу из 5 строк и 7 столбцов.

Заполним заголовок таблицы с учётом приоритета логических операций (поря-док выполнения операций: инверсия, конъюнкция, дизъюнкция).

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

Обратите внимание на последний стол-бец, содержащий конечный результат. Какой из рассмотренных логических операций он соответствует?

5

Эквивалентные выражения

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

!

?

А

А

В

В

0

0

0

0

A → B

А ∧ В ∨ A ∧ В

0

0

1

1

А ∨ B

A ↔ B

1

1

1

1

1

0

0

1

0

0

1

1

0

0

1

1

1

1

1

1

Ответ

0

0

1

1

С помощью таблиц истинности докажите равносильность выражений A → B и А ∨ B.

Анализ таблиц истинности

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

а) (A ∨ С) & В

б) (A ∨ В) & (C → A)

в) (A & В ∨ С) & (В → A & С)

г) (A → В) ∨ (С ∨ A → В)

Таблица

А

В

1

0

С

1

1

1

F

1

0

1

0

1

1

1

Таблица

Таблица

Таблица

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

Ответ: 2 (а, г)

Вычисления будем производить построчно.

Комментарии.

Можно сразу посмотреть ответ (кнопка «Ответ»)

Или провести вычисления для всех (или нескольких) выражений – кнопки «Таблица». Для удобства они расположены на разных слайдах

Ответ

Анализ таблиц истинности

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

а) (A ∨ С) & В

б) (A ∨ В) & (C → A)

в) (A & В ∨ С) & (В → A & С)

г) (A → В) ∨ (С ∨ A → В)

А

1

В

0

1

С

1

1

F

1

0

1

0

1

1

1

1

2

а) (A ∨ С) & В

А

А

1

В

1

С

0

1

1

1

1

2

0

1

F

1

0

1

1

0

1

1

1

1

1

Анализ таблиц истинности

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

а) (A ∨ С) & В

б) (A ∨ В) & (C → A)

в) (A & В ∨ С) & (В → A & С)

г) (A → В) ∨ (С ∨ A → В)

А

1

В

0

С

1

1

1

F

1

0

1

0

1

1

1

3

1

2

б) (A ∨ В) ∧ (C → A)

Б

А

1

В

0

1

С

1

1

1

1

2

1

0

3

1

F

0

1

1

1

1

1

Анализ таблиц истинности

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

а) (A ∨ С) & В

б) (A ∨ В) & (C → A)

в) (A & В ∨ С) & (В → A & С)

г) (A → В) ∨ (С ∨ A → В)

А

В

1

0

1

С

1

1

F

1

0

1

0

1

1

1

4

3

1

5

2

в) (A ∧ В ∨ С) ∧ (В → A ∧ С)

в

А

1

В

1

С

0

1

1

1

1

0

2

1

1

3

4

5

F

0

1

1

0

1

1

1

1

Анализ таблиц истинности

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

а) (A ∨ С) & В

б) (A ∨ В) & (C → A)

в) (A & В ∨ С) & (В → A & С)

г) (A → В) ∨ (С ∨ A → В)

А

В

1

0

1

С

1

1

F

1

0

1

0

1

1

1

3

1

4

2

г) (A → В) ∨ (С ∨ A → В)

Г

А

1

В

1

С

0

1

1

1

1

2

0

1

3

1

4

F

0

1

1

0

0

0

1

1

1

1

1

1

1

1

1

Анализ таблиц истинности

№ 2. Дана логическая функция:

?

?

0

0

?

0

0

F

1

0

1

1

1

0

1

1

1

0

0

1

1

1

1

1

x

z

y

F (x, y, z) = (x ∨ y ∨ z ) & (x ∨ y).

Справа приведён фрагмент таблицы истинности, содержащий все наборы переменных, на которых F истинна. Определите, какому столбцу таблицы соответствует каждая из переменных.

Существуют разные подходы к решению подобных задач:

1) построение полной таблицы истинности

2) методом рассуждений

Решение

Решение

Ответ

Анализ таблиц истинности

№ 2.

Решение:

?

0

?

?

0

0

0

1

F

0

1

0

1

1

1

0

1

1

0

1

1

1

1

1

F (x, y, z) = (x ∨ y ∨ z ) & (x ∨ y)

2 = 0 10

Выясним, при каких значениях x, y, z функция F(x, y, z) = 0.

Подберём подходящие значения x, y и z, заполняя следующую таблицу:

Конъюнкция («и») ложна, если хотя бы один из операндов равен нулю.

Дизъюнкция («или») ложна только в случае равенства нулю каждого из операндов, входящих в нее.

2 = 2 10

Сколько строк в полной таблице истинности для данной функции?

2 = 3 10

2 = 4 10

Данная функция зависит от 3 логических переменных. Полная таблица истинности для нее должна состоять из 8 ( 2 3 ) строк.

(x ∨ y ∨ z )

(x ∨ y ∨ z )

1

1

0

2 = 7 10

(x ∨ y)

(x ∨ y)

0

0

0

2 = 1 10

1

0

0

0

1

1

При каких наборах переменных x , y , z функция F (x, y, z) = 0 ?

2 = 5 10

1

1

0

2 = 6 10

Наборы переменных, на которых функция ложна - 001 , 101 и 110 .

Анализ таблиц истинности

№ 2.

Решение:

x

y

?

0

?

0

?

0

F

0

1

0

1

1

1

0

1

0

1

1

1

0

1

1

1

1

y

x

z

F (x, y, z) = (x ∨ y ∨ z ) & (x ∨ y)

= 0

=0

= 0

Выясним, при каких значениях x, y, z функция F(x, y, z) = 0 .

Дизъюнкция («или») ложна только в случае равенства нулю каждого из операндов, входящих в нее.

Конъюнкция («и») ложна, если хотя бы один из операндов равен нулю.

Сравним эту таблицу с восстановленным фрагментом исходной таблицы истин-ности.

0

0

1

1

1

0

0

1

1

0

0

0

x

x

0

y

y

z

1

z

F

F

1

0

0

0

0

0

1

1

0

(x ∨ y ∨ z )

(x ∨ y ∨ z )

1

0

0

(x ∨ y)

Ответ: z, y, x

(x ∨ y)

1

0

1

Анализ таблиц истинности

№ 2.

Решение:

x

y

z

?

0

?

0

?

0

0

0

F

1

1

1

0

1

0

1

1

1

0

1

1

1

1

1

x

y

z

=1

= 1

F (x, y, z) = (x ∨ y ∨ z ) & (x ∨ y)

= 1

В данном примере два логических выра-жения связаны операцией «и».

х не может быть 2-й переменной

Конъюнкция («и») истинна тогда и только тогда, когда каждый из операндов, входящих в нее, равен истине.

y – не может быть 1-й переменной

х не может быть 1-й переменной

• x не 2-я переменная

(x ∨ y) = 1

Ответ: z, y, x

• x не 1-я переменная

0

1

или

Тогда в строках, где x = 1 значение y = 1.

• y - 2-я переменная

• z - 1-я переменная

Самое главное

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

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

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

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

Вопросы и задания

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

z

y

0

0

0

x

F

0

1

0

1

1

0

1

0

1

1

1

1

0

1

1

1

1

F (x, y, z) = (x ∨ y ∨ z ) & (x ∨ y).

Вопросы и задания

№ 4. Составлена таблица истинности для логического выражения, содержащего n переменных. Известно m — количество строк, в которых выражение принимает значение истина . Требуется выяснить, в скольких случаях логическое выражение примет значение ложь при следующих значениях n и m :

1) n = 4 , m = 9

2) n = 8 , m = 156

3) n = 12 , m = 1596

2 4 – 9 = 16 – 9 = 7

2 8 – 156 = 256 – 156 = 100

2 12 – 1596 = 4096 – 1596 = 2500

Решение / Ответ

Информационные источники

• http://xn--80aanlrjbcx2b7fsb.xn--p1ai/wp-content/uploads/2015/07/156.jpg
• http://iq230.com/images/sampledata/1/teacher-desk.jpg
• http://www.s.0512.com.ua/s/8/section/doska/upload/pers/8/img/doska/000/000/123/1172305_blogjpg_20131007062226902_144205923264.jpg

17