Построение таблиц истинности
учебно-методический материал на тему

Лекция 13

Тема : «Построение таблиц истинности»

Цель: закрепить умение строить истинные сложные высказывания из простых с использованием логических операций, сформировать навыки построения таблиц истинности

Ход урока

1. Орг. момент

2. Решение задач

Упражнение 1

Запишите следующие высказывания в виде логических выражений

1. Число 17 нечетное и двузначное
2. Неверно, что корова – хищное животное
3. На уроке физики ученики выполняли лабораторную работу и сообщали результаты исследований учителю
4. Если число делится на 2, то – нечетное.
5. Переходи улицу только на зеленый свет
6. На уроке информатики необходимо соблюдать особые правила поведения
7. При замерзании воды выделяется тепло
8. Если Маша – сестра Саши, то Саша – брат маши
9. если компьютер включен, то можно на нем работать
10. Водительские права можно получить тогда и только тогда, когда тебе исполниться 18 лет
11. Компьютер выполняет вычисления, если он включен
12. ты можешь купить в магазине продукты, если у тебя есть деньги
13. Тише едешь – дальше будешь

Упражнение 2

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

1. Неверно, что  и  

2. Z является min(Z,Y)

3. А является max(A,B,C)

4.Любое из чисел А,В,С положительно

5. Любое из чисел А,В,С отрицательно

6. Хотя бы одно из чисел А,В,С не отрицательно

7. Хотя бы одно из чисел А,В,С не меньше 12

8. Все числа А,В,С равны 12

9. Если Х делится на 9 то Х делится на 3

10. если Х делится на 2, то оно четное.

Упражнении 3.

Найдите значения логических выражений:

1. F=(00)(11)
2. F=(11)(10)
3. F=(0^0) ^(1^1)
4. F= ¬1^(11) (¬0^1)
5. F=(¬11) ^(1¬1) ^(¬10)

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

Приоритет логических операций

1) инверсия   2) конъюнкция   3) дизъюнкция  4) импликация и эквивалентность

 Как составить таблицу истинности?

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

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:

(0, 0),     (0, 1),     (1, 0),     (1, 1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь       (0, 0, 0),     (0, 0, 1),     (0, 1, 0),     (0, 1, 1),     (1, 0, 0),     (1, 0, 1),     (1, 1, 0),     (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

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

Для составление таблицы истинности необходимо (алгоритм записать в тетрадь)

1. выяснить количество сток в таблице (вычисляется как 2n, где n- количество переменных)
2. выяснить количество столбцов = количеству переменных + количество логических операций
3. установить последовательность логических операций
4. построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных.
5. заполнить таблицу истинности

Пример: В классе оказалось разбито стекло. Учитель объясняет директору: это сделал Коля или Саша. Но Саша этого на делал, т.к. в это время сдавал мне зачет. Следовательно, это сделал Коля.

 Решение: 

Формализуем данное сложное высказывание.

                      К – это сделал Коля

                      С – это сделал Саша

Кол-во простых высказываний n = 2.

Форма высказывания:  Е  =  ( К ∨ C ) & ¬ С  ⇒ К

1. Определить количество строк и столбцов в таблице истинности.

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

Количество строк в таблице =  2 n   +  строка на заголовок.

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

В нашем примере:  количество строк  -   22  + 1 = 5 ,            

                                             столбцов –     2 + 4  = 6

2. Начертить таблицу и заполнить заголовок

Первая строка – номера столбцов.

Вторая строка промежуточные формулы и соответствующие им условные записи операций над значениями .

3. Заполнить первые n столбцов.

В нашем примере сначала заполняем 1-й и 2-й столбцы.

4. Заполнить остальные столбцы.

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

     Итак,  вычисляем значения 3-го столбца по значениям 2-го, потом значения 4-го – по значениям 1-го и 2-го…

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

Примеры.

1. Составим таблицу истинности для формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.

2. Таблица истинности для формулы :

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.

3. Таблица истинности для формулы :

Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.

4. Решение задач

1. Построить таблицу истинности для выражения F=(A B) ^( ¬A B), определить количество строк, столбцов и указать порядок действий

2. Построить таблицу истинности для выражения F=X Y ^ ¬Z

5. Подведение итогов