Логические операции учитель математики и информатики Чистопрудова Е.В. - презентация

1 Логические операции учитель математики и информатики Чистопрудова Е.В.

2 КОНЪЮНКЦИЯ ЛОГИЧЕСКОЕ УМНОЖЕНИЕ ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ СОЮЗА В прямоугольнике противоположные стороны равны и параллельны В прямоугольнике противоположные стороны равны и пересекаются

3 ABF = A ^ B КОНЪЮНКЦИЯ ЛОГИЧЕСКОЕ УМНОЖЕНИЕ

4 ДИЗЪЮНКЦИЯ ЛОГИЧЕСКОЕ СЛОЖЕНИЕ ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ СОЮЗА Все положительные числа больше отрицательных или больше 0 Все положительные числа больше 1 или больше нуля

5 ABF = A ν B ДИЗЪЮНКЦИЯ ЛОГИЧЕСКОЕ СЛОЖЕНИЕ

6 ОТРИЦАНИЕ (ИНВЕРСИЯ) ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ ЧАСТИЦЫ А А - «На улице идет дождь» ¬А Тогда ¬А - А А - «На улице нет дождя»

7 A¬ А¬ А ОТРИЦАНИЕ (ИНВЕРСИЯ)

8 ИМПЛИКАЦИЯ (логическое следование) Если будет дождь, то мы не пойдем на улицу. Если я поленюсь, то получу двойку. Если на траве роса, то скоро настанет вечер.

9 ИМПЛИКАЦИЯ (логическое следование) ABA => B

10 ИМПЛИКАЦИЯ (логическое следование) ABA => B

11 ЭКВИВАЛЕНТНОСТЬ (равнозначность) Чайник греет воду тогда и только тогда, когда он включен. Мы дышим воздухом тогда и только тогда, когда гуляем в парке.

12 ЭКВИВАЛЕНТНОСТЬ (равнозначность) ABA B

13 Как составлять таблицу истинности сложных выражений 1. Необходимо определить количество строк в таблице истинности. количество строк = 2 n, где n – количество логических переменных 2. Необходимо определить количество столбцов в таблице истинности, которое равно количеству логических переменных плюс количество логических операций. 3. Необходимо построить таблицу истинности с указанным количеством строк и столбцов, ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов; 4. Заполнить столбцы входных переменных наборами значений 5. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью. F = (A ^ B) & (A v B)

14 Как составлять таблицу истинности сложных выражений 1. Необходимо определить количество строк в таблице истинности. количество строк = 2 n, где n – количество логических переменных F = (AvB) & (A^B)F = (A ^ B) & (A v B)

15 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) 2. Необходимо определить количество столбцов в таблице истинности, которое равно количеству логических переменных плюс количество логических операций. F = (A ^ B) & (A v B)

16 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) 3. Необходимо ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов; F = (A ^ B) & (A v B)

17 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) 3. Необходимо ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов; ABA ^ BA v B(A^B) & (AvB) F = (A ^ B) & (A v B)

18 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) 4. Заполнить столбцы входных переменных наборами значений ABA ^ BA v B(A^B) & (AvB) F = (A ^ B) & (A v B)

19 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) 4. Заполнить столбцы входных переменных наборами значений ABA ^ BA v B(A^B) & (AvB) F = (A ^ B) & (A v B)

20 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) 5. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью. ABA ^ BA v B(A^B) & (AvB) F = (A ^ B) & (A v B)

21 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) 5. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью. ABA ^ BA v B(A^B) & (AvB) F = (A ^ B) & (A v B)

22 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) ABA ^ BA v B(A^B) & (AvB) Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью. F = (A ^ B) & (A v B)

23 Как составлять таблицу истинности сложных выражений F = (AvB) & (A^B) ABA ^ BA v B(A^B) & (AvB) Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью. F = (A ^ B) & (A v B)

24 Закон двойного отрицания Двойное отрицание исключает отрицание. ¬( ¬A) = А ¬( ¬ A) = А

25 Законы де Моргана. Называют законами общей инверсии. Отрицание дизъюнкции является конъюнкцией отрицаний. ¬(A V B) = ¬A /\ ¬B Отрицание конъюнкции является дизъюнкцией отрицаний. ¬(A /\B) = ¬A V ¬B

26 Закон идемпотентности Дословно переводится (равносильный) A V A = A A & A = A

27 Закона исключения третьего (операция переменной с ее инверсией) Из двух противоречащих высказываний об одном и том же одно всегда истинно, второе ложно, третьего не дано. A V ¬А= 1 A V ¬ А= 1

28 Закон непротиворечия (операция переменной с ее инверсией) Не могут быть одновременно истинны утверждение и его отрицание. A & ¬А= 0 A & ¬ А= 0

29 Закон исключения констант (операция с константами) Для логического сложения: A V 1 = 1 A V 0 = A A & 1 = A A & 0 = 0 A & 1 = A A & 0 = 0 Для логического умножения:

30 Задание 1. (Задание А11 демоверсии 2004 г.) Для какого имени истинно высказывание: ¬ (Первая буква имени гласная -> Четвертая буква имени согласная)? 1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР Решение. Сложное высказывание состоит из двух простых высказываний: А - первая буква имени гласная, В - четвертая буква имени согласная. ¬ (А В) = ¬ (¬A V В) = (¬ (¬А) /\ ¬B) = A /\ ¬B Применяемые формулы: 1. Импликация через дизъюнкцию А В = ¬A V В 2. Закон де Моргана ¬(A V B) = ¬A /\ ¬B 3. Закон двойного отрицания. (Первая буква имени гласная /\ Четвертая буква имени гласная) Ответ: 3) АНТОН

31 Задание 2. (Задание А12 демоверсии 2004 г.) Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)? 1) A \/ B 2) A /\ B 3) ¬A \/ ¬B 4) ¬A /\ B Решение. ¬ (А \/ ¬B)= ¬ А \/ ¬ (¬B)= ¬ А \/ B Ответ: 4

32 Задание 3. (Задание А9 демоверсий 2005 г., 2006 г.) Для какого числа X истинно высказывание X>1 ((X<5)(X<3)) (*) 1) 1 2) 2 3) 3 4) 4 Решение. Заменим импликацию, входящую в исходное выражение, воспользовавшись тождеством (1): (1) (X>5)(X<3) = ¬ (X<5) (X<3) Подставим получившееся выражение в (*): (X>1) ((X 1) (¬ (X 1) ((X>=5) (X<3)) (**) Найдем значение выражения (**) при заданных значениях X (=1; 2; 3; 4) X=1: (1>1) ((1>=5) (1<3)) = 0 (1 1) = 0 1=0 X=2: (2>1) ((2>=5) (2<3)) = 1 (0 1) = 1 1=1 X=3: (3>1) ((3>=5) (3<3)) = 1 (0 0) = 1 0=0 X=4: (4>1) ((4>=5) (4<3)) = 1 (0 0) = 1 0=0 Верный вариант ответа 2. Ответ: 2.

33 Задание 4. (Задание А10 демоверсий 2005 г., 2006 г.) Укажите, какое логическое выражение равносильно выражению ¬(¬A B) 1) A ¬B 2) ¬A B 3) B ¬A 4) A ¬B Решение. Воспользуемся равенствами (6) и (12): (6) (12) ¬(¬A B) = ¬(¬A) ¬B = A ¬B Верный вариант ответа 1. Ответ: 1.

34 Задание 5. (Задание А13 демоверсий 2005 г., 2006 г.) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице: Определить, какой набор букв закодирован двоичной строкой ) EBCEA 2) BDDEA 3) BDCEA 4) EBAEA Решение. Строка может начинаться только с двух букв: 01(В) или 011(Е). При этом, если первая буква В, то для второй буквы имеется две возможности: 10(D) и 101(-) – нет соответствующей буквы и т.д. При этом результативным является один вариант из двух – BDCEA, что соответствует варианту ответа 3. Верный вариант ответа 3. Ответ: 3. ABCDE

35 Задание 6. (Задание В2 демоверсий 2005 г., 2006 г.) Сколько различных решений имеет уравнение (K L M) (¬L ¬M N)=1 где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. Решение. Поскольку исходное уравнение представляет собой объединение двух логических выражений, то оно равносильно совокупности (объединению) уравнений, состоящих из этих выражений: ¬K L M=1 (*) L ¬M N=1 (**) При этом уравнение (*) представляет собой пересечение трех логических выражений, и потому оно принимает значение, равное 1, тогда и только тогда, когда каждое из них истинно, т.е. К=L=M=1. На выражение N условий не накладывается, поэтому возможны два варианта решений: 1) К=L=M=1, N=1; 2) К=L=M=1, N=0.

36 Уравнение (**) также представляет собой пересечение трех логических выражений, и потому оно принимает значение, равное 1, тогда и только тогда, когда ¬L=¬M=N=1. Откуда: L=M=0, N=1. На выражение K условий не накладывается, поэтому у уравнения (18) – также два решения: 1) К=M=0, N=1, K=1; 2)К=M=0, N=1,k=0. Таким образом, уравнение (*) имеет 2 решения и уравнение (18) имеет два решения. Поскольку исходное уравнение представляет собой объединение этих двух уравнений, то количество его решений равно сумме решений уравнений (*) и (**), т.е. равно 4. Ответ: 4.

37 Задание 9. (Задание В2 демоверсии 2004 г.) Укажите значения переменных K, L, M, N, при которых логическое выражение (¬K M) (¬L M N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

38 Решение. Преобразуем данное выражение, используя равенства (1), (6), (12): (1) (6), (12) (¬K M) (¬L M N) = ¬ (¬K M) (¬L M N) = (K ¬M) (¬L M N) =0 Поскольку получившееся выражение представляет собой логическое сложение двух выражений (K ¬M) и (¬L M N), то оно равно тогда и только тогда, когда K ¬M =0 (*) ¬L M N =0 (**) Из (**) следует, что ¬L= M= N =0, значит L=1, M=0, N=0. Подставим M=0 в уравнение (*): K 1 =0, откуда K=0. В итоге получим: K=0, L=1, M=0, N=0 Ответ: 0100.

39 Задание 10. (Задание В4 демоверсии 2006 г.) Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном. Кто это сделал? спросила мама. Коля не бил по мячу, сказал Саша. Это сделал Ваня. Ваня ответил: Разбил Коля, Саша не играл в футбол дома. Так я и знала, что вы друг на дружку сваливать будете, рассердилась мама. Ну, а ты что скажешь? спросила она Колю. Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, сказал Коля. Оказалось, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду. Кто разбил вазу?

40 Решение. Введем обозначения для высказываний: А = «Коля не бил по мячу» = «¬Коля» = ¬C; В = «Это сделал Ваня»= «Ваня»; С = «Разбил Коля» = «Коля»; D = «Саша не играл в футбол дома» = «¬Саша»; E = «Ваня не мог этого сделать» = «¬Ваня» = ¬B; F = «Я сегодня еще не сделал уроки» - не имеет отношения к вопросу «Кто разбил вазу?». Из условия задачи известно, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду.

41 Решение. Предположим, что солгал первый мальчик, тогда: A=0 B=0 C=1 D=1 E=1 F=1. Поскольку A= ¬C и E=¬B, имеем: ¬C=0, B=0, C=1, D=1, ¬B=1, F=1, – противоречий не получили, этот вариант является решением задачи: ¬B=1, C=1, F=1, осталось лишь вспомнить обозначения: В= «Ваня», значит: ¬B = не «Ваня»; C=«Коля»; F=1 – не имеет отношения к вопросу. Значит, вазу разбил Коля.

42 Решение. На всякий случай рассмотрим два других варианта (когда солгал второй или третий мальчики). Если солгал второй мальчик, то: С=0 D=0 A=1 B=1 E=1 F=1. Поскольку A= ¬C и E=¬B, имеем: C=0, D=0, ¬C=1, B=1, ¬B=1, F=1 – получили противоречие: B=1 и ¬B=1, значит, этот вариант нам не подойдет. Если солгал третий мальчик, то: E=0 F=0 A=1 B=1 C=1 D=1. Заменим: A= ¬C и E=¬B, тогда: E=0, F=0, ¬C=1, B=1, C=1, D=1– получили противоречие: C=1 и ¬C=1, значит, этот вариант нам не подойдет. Ответ: Коля.