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

1 Теоретические основы математической логики

2 Высказывания Высказывание – это повествовательное (декларативное) предложение, которое является истинным (И или 1) или ложным (Л или 0). Примеры : 2+2=4 (И) Москва – столица Белоруссии (Л). Х – целое число (не является высказыванием). Можно войти? (не является высказыванием). Ложность или истинность высказывания называется истинностным значением высказывания или просто значением, А, b, c, … – пропозициональные переменные, или просто переменные, принимающими значения И или Л.

3 Логические операции: конъюнкция дизъюнкция отрицание Логическое умножение или конъюнкция Обозначение:A B (A и B, A&B) Конъюнкция двух высказываний истинна только в случае, когда истинны оба высказывания. Логическое сложение или дизъюнкция Обозначение:A B (A или B) Дизъюнкция двух высказываний истинна в случае, когда истинно хотя бы одно из двух высказываний. Логическое отрицание или инверсия Обозначение: A Если А – истинно, то A – ложно и наоборот.

4 Логические операции: импликация, эквивалентность Импликация или следование Обозначение: А В (А В) Импликация ложна только в случае, когда из истинного высказывания следует ложное. В импликации А и В не переставляются местами. Здесь А – условие, В – следствие, тогда если условие истинно и условие – ложно, то их импликация – ложна. Эквивалентность (эквиваленция) Обозначение: А В (А В) Эквиваленция истинна в случае, когда оба высказывания истинны, или оба высказывания ложны.

5 Предложение, полученное путем увязывания двух и более высказываний логическими операциями и записанное с помощью математических символов, называется логическим выражением или формулой. Равносильными логическими выражениями называются такие выражения, у которых совпадают последние столбцы истинности. Приоритеты логических операций: 1)отрицание; 2)конъюнкция; 3)дизъюнкция; 4)импликация. Логические выражения

6 Таблица истинности определяет значение логического выражения при всех возможных комбинациях значений логических переменных. Правила построения таблицы истинности: 1)Количество строк в таблице истинности равно количеству возможных комбинаций значений n логических переменных, то есть 2 n. 2)Количество столбцов в таблице истинности равно количеству логических переменных плюс количество логических операций. 3)В построенный шаблон таблицы истинности вписываются все значения исходных переменных. 4)Таблица истинности заполняется по столбцам, в соответствии с правилами логических операций. Таблицы истинности

7 Таблицы истинности основных операций АВ А В A ИИИИИИЛ ИЛИЛЛЛЛ ЛИИЛИЛИ ЛЛЛЛИИИ

8 Таблицы истинности (в бинарном виде) АВ А В A

9 Основные законы логики Название законаФормулировка Переместительный закон (коммутативность) А В= В А Сочетательный закон (ассоциативность) (А В) С= А (В С) Распределительный закон (дистрибутивность) А (В С)=(А В) (А С) Закон противоречия (высказывание не может быть одновременно истинным и ложным) А ¬А=0 Закон исключения третьего (либо высказывание, либо его отрицание должно быть истинным) А ¬А= 1 Закон двойного отрицания ¬ (¬А)=А Закон де Моргана ¬ (А В)= ¬ А ¬ В Выражение импликации через отрицание и логическое сложение А В = ¬ А В

10 Пример 1. Упростить логическое выражение: F=(А В) ( ¬А В). Примеры решения задач Решение. Сначала по закону дистрибутивности выносится за скобки В, далее используется закон исключения третьего: F=(А В) ( ¬А В)=В (А ¬А )=В 1=В. Ответ: F=В.

11 Пример 2. Составить таблицу истинности логического выражения: F=(А В) ( ¬А ¬ В). Примеры решения задач Решение. АВ А В ¬А¬А¬В¬В ¬А ¬ В F

12 Пример 3. Доказать равносильность (эквивалентность) выражений: F1=А В и F2=(А В) А. Примеры решения задач Решение. Равносильность выражений доказывается путем сравнения их таблиц истинности. АВ А В А F2F

13 Пример 4. Задана таблица истинности выражения F. Записать для него формулу. Примеры решения задач ABF Решение. В данной таблице единица находится только в последней строке, поэтому истинным будет выражение А ¬В. Составим для него таблицу истинности и сравним с исходной. AB ¬А¬А ¬В¬В А ¬В

14 Пример 5. Трое судей используют электрическую схему тайного голосования. Решение принимается в том случае, если за него проголосовало большинство. Составить данную схему и соответствующее логическое выражение. Примеры решения задач Решение. Пусть А1 – первый судья проголосовал «за», А2 – второй судья проголосовал «за», А3 – третий судья проголосовал «за». Тогда искомое выражение примет вид: (А1 А2 А3) (А1 А2 А3) ( А1 А2 А3).

15 Решение. Если в каждом ответе только одно утверждение истинно, то и дизъюнкция этих утверждений, тоже буде истинной. Обозначим высказывания: Сергей – 1 через С1, Роман – 2 через Р2 и т.д. В таких обозначениях ответы записываются в виде: 1) F1=С1 Р2; 2) F2=С2 В3; 3) F3=Ю2 В4. Так как конъюнкция истинных высказываний будет истинной, то истинным должно быть выражение F=F1 F2 F3=(С1 Р2) (С2 В3) (Ю2 В4). Примеры решения задач

16 Пример 6. Виктор, Юрий, Сергей и Роман заняли на олимпиаде по информатике первые четыре места. Когда их спросили о распределении мест, они дали три таких ответа: 1) Сергей – 1, Роман – 2; 2) Сергей – 2, Виктор – 3; 3) Юрий – 2, Виктор – 4. Как распределены места, если в каждом ответе только одно утверждение истинно? Примеры решения задач

17 Производим преобразование первой конъюнкции, представив ее в виде дизъюнкции простейших конъюнкций: (С1 Р2) (С2 В3)=[(С1 Р2) С2] [(С1 Р2) B3]= =[(С1 С2) (Р2 С2)] [(С1 B3) (Р2 B3)] В этом выражении (С1 С2) – ложно, (Р2 С2) – ложно, поэтому их дизъюнкция тоже – ложь. Поэтому: (С1 Р2) (С2 В3)=[(С1 B3) (Р2 B3)]. Таким образом: F=[(С1 B3) (Р2 B3)] (Ю2 В4). Примеры решения задач

18 Производим далее аналогичные преобразования: F={[(С1 B3) (Р2 B3)] Ю2)} {[(С1 B3) (Р2 B3)] В4)}= =(С1 B3 Ю2) (Р2 B3 Ю2) (С1 B3 В4) (Р2 B3 В4). В этом выражении ложны высказывания: (Р2 B3 Ю2), (С1 B3 В4) и (Р2 B3 В4), поскольку они являются конъюнкциями или одинаковых букв с разными номерами, или разных букв с одинаковыми номерами, чего не может быть. Следовательно, истинной является только высказывание (С1 B3 Ю2), которое означает, что Сергей – 1, Виктор – 3, Юрий – 2. Ответ: Сергей – 1, Юрий – 2, Виктор – 3, Роман – 4. Примеры решения задач

19 В ЕГЭ по данной теме содержат задания : с выбором ответа (А) с кратким ответом (В) Эти задания включали в себя проверку умения: решать логические уравнения; строить таблицы истинности; строить логические формулы; преобразовывать логические выражения; определять эквивалентность логических выражений. Задачи в ЕГЭ по теме «Основы логики»

20 Задача А7. (2009) Для какого из указанных значений Х истинно высказывание: ¬((Х>2) (Х>3))? 1) 1; 2) 2; 3) 3; 4) 4. 1 тип задач на следование Решение. Решается методом подстановки: 1) ¬ ((1>2) (1>3)) = ¬ (Л Л)= ¬ (И) = Л 2) ¬ ((2>2) (2>3)) = ¬ (Л Л)= ¬ (И) = Л 3) ¬ ((3>2) (3>3)) = ¬ (И Л)= ¬ (Л) = И 4)¬ ((4>2) (4>3)) = ¬ (И И)= ¬ (И) = Л Ответ: 3.

21 Задача B4. (2009) Каково наибольшее целое число Х, при котором истинно высказывание: (50 (X+1)(X+1))? 1 тип задач на следование Решение. Решается методом подстановки с учетом того, что следование становится ложным только, если из истины следует ложь. Легко установить, что при X=8 первая скобка становится истинной, а вторая продолжает быть ложью. При дальнейшем увеличении X истинность скобок не меняется. Ответ: 7.

22 Задача А8. (2009) Какое логическое выражение равносильно выражению ¬ (А В) ¬ С? 1) ¬ А В ¬ С; 2) (¬ А ¬ В) ¬ С; 3) (¬ А ¬ В) С; 4) ¬ А ¬ В ¬ С. 2 тип задач на определение равносильного выражения Решение. 1 способ – воспользоваться законом Моргана, т.е. раскрыть скобки: ¬ (А В) ¬ С = (¬ А ¬В) ¬ С. Ответ: 2.

23 АВС¬А¬А ¬B¬C ¬(А В) ¬С¬А В ¬С(¬А ¬В) ¬C(¬А ¬В) С¬А ¬В ¬ С тип задач 2 способ – построить таблицу истинности всех выражений и определить одинаковые результаты в столбцах

24 XYZF тип задач по фрагменту таблицы истинности определить соответствующее F выражение из предложенных в ответе Задача А9. (2009) Дан фрагмент таблицы истинности выражения F Какое выражение соответствует F? 1) X Y Z; 2) X Y Z; 3) X Y Z; 4) X Y Z.

25 XYZF¬X¬Y¬Z X Y Z тип задач Решение. Составим фрагмент таблицы истинности всех перечисленных в ответах логических выражений для различных наборов переменных X, Y, Z: Заметим, что значения истинности одинаковы для логических выражений F и при любых значениях аргументов X, Y, Z из данного фрагмента, следовательно, эти логические выражения равносильны. Ответ: 3.

26 4 тип задач: решение логических уравнений Пример 4. Сколько различных решений имеет уравнение (K L M) ( L M N)=1. В качестве ответа нужно указать только количество таких наборов: 1) 1; 2) 2; 3) 3; 4) 4. Решение. Дизъюнкция истина в случаях, когда хотя бы одна из скобок в уравнении истинна. В скобках содержатся конъюнкции, которые истинны только в том случае, когда все ее переменные истинны. При этом следует учитывать, что часть переменных входят как в первую, так и во вторую скобку в дизъюнкции, поэтому их значения должны обеспечивать фиксированную истинность.

27 4 тип задач: решение логических уравнений Следует учесть, что значения L и M должны быть одинаковыми. Руководствуясь этим, проверяем наборы: 1) (K L M)=0 или ( L M N)=1; Первая скобка – ложь, например, если K=1, L=0, M=0, или K=0, L=0, M=0, причем, вторая скобка должна быть истинной, что обеспечивается L=0, M=0, N=1. Отсюда уже следует два набора различных решений: 1001, ) (K L M)=1 или ( L M N)=0; Первая скобка – истина, только если K=1, L=1, M=1,тогда, вторая скобка должна быть ложью, что обеспечивается L=1, M=1, N=0 или L=1, M=1, N=1. Отсюда уже следует еще два набора различных решений: 1111, ) (K L M)=1 или ( L M N)=1; Этот случай не привносит нового набора. Ответ: 4.

28 5 тип задач на анализ логических цепочек Решение. Методом разглядывания легко установить, что: первому требованию не удовлетворяет цепочка (3); второму требованию удовлетворяет только (1) из оставшихся, она же удовлетворяет третьему требованию. Ответ: 1. Задача А12. (2009) Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин А, В, С. На первом месте – одна из бусин В, D, С, которой нет на третьем месте. В средине – одна из бусин A, C, E, B, не стоящая на первом месте. Какая из перечисленных цепочек создана по этому правилу? 1) CBB 2) EAC 3) BCD 4) BCB

29 Задача В6. (2009) Кто из 4-х мальчиков разбил вазу, если Саша, Ваня, Коля и Олег делают вид, что происшедшее к ним не относится. Их ответы: Саша: Коля не бил по мячу. Это сделал Ваня. Ваня: Разбил Коля, Саша не играл в футбол. Коля: Я знаю, что Ваня не мог этого сделать, а я сегодня еще не делал уроки. Олег: А меня не было в комнате. Я был в библиотеке. Оказалось, что один из мальчиков оба раза солгал, а трое в каждом их своих заявлений говорили правду. Кто разбил вазу? 1) Коля; 2) Ваня; 3) Саша; 4) Олег. 5 тип задач на установление истины

30 5 тип задач Решение. Необходимо выдвинуть предположение, о том, к то солгал оба раза и найти противоречия в оставшихся показаниях. Если противоречий не будет, то автоматически получится правильный ответ. Предположение 1: Саша солгал обо раза. Тогда его фраза должна трактоваться как: «К – разбил, В – не разбивал». Остальные показания записываются виде: «К – разбил, С – не разбивал»; «В – не разбивал»; «О – не разбивал». В указанных показаниях нигде нет противоречий, и утверждение «К – разбил» поэтому истинно. Ответ: 1.

31 Решение задач такого типа иногда удобно представлять схематически, если количество элементов ее условия не превышает трех. В этом случае: элементы условия задачи отображают символами (буквами); соответствие между элементами отображают сплошной линией; если между элементами нет соответствия, то они соединяются пунктирной линией. 5 тип задач на установление истины: решение с помощью схем

32 Задача 5.1. В классе три девочки (Аня, Женя, Нина) получили различные оценки по контрольной работе. «Двоек» в классе нет, у Ани не «3», у Нины не «3» и не «5». Какие оценки получили каждая из учениц? 5 тип задач на установление истины Решение. Можно нарисовать схему решения, обозначив на ней А – Аня, Н – Нина, Ж – Женя: А3 Ж4 Н5

33 Рассуждения: 1) По условию у Нины не «3» и не «5» – проводим пунктирные линии от «Н» к «3» и к «5». 2) Так как у Нины «4», то а Ани и у Жени не «4» – проводим сплошную линию от «Н» к «4» и пунктирные – от «А» и «Ж» к «4». 3) Так как у Ани не «3» и не «4», то «5» – проводим сплошную линию от «А» к «5» и пунктирные – от «А» к «3» и к «4». 4) Так как у Ани «5», а у Нины «4», то у Жени «3» – проводим сплошную линию от «Ж» к «3» и пунктирные – от «Ж» к «5» и к «4». Ответ: у Ани «5», Нины «4», Жени «3». А3 Ж4 Н5

34 Задача 5.2. У трех мальчиков – Алеши, Сережи и Дениса – щенки разных пород – колли, ротвейлер и овчарка. Им дали клички – Блек, Джек и Ванда. Щенок Алеши темнее овчарки, Блека и Джека. Щенок Сережи старше Джека, ротвейлера и овчарки. Какой породы щенок и с какой кличкой у каждого из мальчиков? 5 тип задач на установление истины Решение. Можно нарисовать схему решения, обозначив на ней А – Алеша, С – Сережа, Д – Денис, К – колли, Р – ротвейлер, О – овчарка.

35 Рассуждения: 1) По условию у Алеши не овчарка и не Блек и не Джек, а у Сережи – не Джек, не ротвейлер и не овчарка. Отсутствие таких соответствий отмечаем пунктирными линиями на схеме. 2) Теперь видно, что у Сережи колли, значит, овчарка у Дениса. Следовательно, у Алеши ротвейлер. Эти соответствия отмечаем сплошными линиями. 3) Из схемы видно, что Джек кличка собаки Дениса, а кличка собаки Алеши Ванда. Значит у Сережи Блек. Ответ: у Дениса овчарка Джек, у Сережи колли Блек, у Алеши ротвейлер Ванда. КДБлек РСДжек ОАВанда

36 Задача А7. (2010) Какое из приведенных имен удовлетворяет логическому условию: (первая буква гласная вторая буква гласная) последняя буква гласная 1) Ирина; 2) Максим; 3) Артем; 4) Мария. Задачи из Демо КИМ 2010 по теме «основы логики» Решение. Последняя буква должна быть гласной, поэтому варианты (2) и (3) – отбрасываем. Первая гласна только в (1). Ответ: 1

37 Задача А8. (2010) Какое логическое выражение равносильно выражению ( A B) C: 1) A B C; 2)A B C; 3)(A B) C; 4)( A B) C. Решение. Первая скобка преобразуется по закону Моргана ( A B)=A B. Тогда ясно, что равносильным является выражение (2). Ответ: 2

38 XYZF Задача А9. (2010) Дан фрагмент таблицы истинности выражения F Какое выражение соответствует F? 1) X Y Z; 2) X Y Z; 3) X Y Z; 4) X Y Z.

39 XYZF¬X¬Y¬Z X Y Z Решение. Составим фрагмент таблицы истинности всех перечисленных в ответах логических выражений для различных наборов переменных X, Y, Z: Заметим, что значения истинности одинаковы для логических выражений F и при любых значениях аргументов X, Y, Z из данного фрагмента, следовательно, эти логические выражения равносильны. Ответ: 3.

40 В4. (2010) Сколько различных решений имеет уравнение J K L M (N N) = 0. В качестве ответа нужно указать только количество таких наборов. Решение. Конъюнкция принимает значение 0, когда хотя бы один из сомножителей 0. Всего 5 переменных могут принимать два значения, поэтому число возможных комбинаций 2 5 =32. Но так как последняя скобка принимает значение 1 при любых N, то следует отбросить два значения переменной N. Поэтому количество решений уравнения 32-2=30. Ответ: 30.

41 Задача В6. (2010) На одной улице стоят в ряд 4 дома, в которых живут 4 человека: Алексей, Егор, Виктор и Михаил. Известно, что каждый из них владеет ровно одной из следующих профессий: Токарь, Столяр, Хирург и Окулист, но неизвестно, кто какой и неизвестно, кто в каком доме живет. Однако, известно, что: 1) Токарь живет левее Столяра 2) Хирург живет правее Окулиста 3) Окулист живет рядом со Столяром 4) Токарь живет не рядом со Столяром 5) Виктор живет правее Окулиста 6) Михаил не Токарь 7) Егор живет рядом со Столяром 8) Виктор живет левее Егора Выясните, кто какой профессии, и кто где живет, и дайте ответ в виде заглавных букв имени людей, в порядке слева направо. Например, если бы в домах жили (слева направо) Константин, Николай, Роман и Олег, ответ был бы: КНРО

42 Решение. Обозначим: токарь – Т, столяр – С, хирург – Х, окулист – О, Алексей – А, Виктор – В, Михаил – М. 1) Т С; 2) Х О; 3) О С или С О; 4) ТОС. Из этого получается последовательность профессий – ТОСХ. Далее удобно использовать схему рассуждений: ТОСХ ¬М¬М¬А¬А¬А¬А¬А¬А ¬В¬В¬В¬ВВЕ ¬Е¬ЕМ А АМВЕ Ответ: АМВЕ.

43 XYZF Задача А9. (2011) Дан фрагмент таблицы истинности выражения F Какое выражение соответствует F? 1) X Y Z; 2) X Y Z; 3) X Y Z; 4) X Y Z. Задачи из Демо КИМ 2011 по теме «основы логики»

44 XYZF¬X¬Y¬Z X Y Z Решение. Составим фрагмент таблицы истинности всех перечисленных в ответах логических выражений для различных наборов переменных X, Y, Z: Заметим, что значения истинности одинаковы для логических выражений F и при любых значениях аргументов X, Y, Z из данного фрагмента, следовательно, эти логические выражения равносильны. Ответ: 4.

45 Задача А10. (2011) Какое логическое выражение равносильно выражению A ( B C): 1) A B C; 2)A (B C); 3)A B C; 4)A B C. Решение. Вторая скобка преобразуется по закону Моргана ( В С)=В С. Тогда ясно, что равносильным является выражение (2). Ответ: 2

46 Задача В7. (2011) Девять школьников, оставшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы: Володя: «Это сделал Саша». Аня: «Володя лжет!» Егор: «Маша разбила». Саша: «Аня говорит не правду!» Рома: «Разбила либо Маша, либо Нина…» Маша: «Это я разбила!» Нина: «Маша не разбивала». Коля: «Ни Маша, ни Нина этого не делали». Олег: «Нина не разбивала!» Кто разбил окно, если известно, что из девяти высказываний истинны только три. Ответ запишите в виде первой буквы имени.

47 Решение. Составляем таблицу Так как истинны только три высказывания, то разбила Нина. Ответ: Н. Имена разбили CМН В100 А010 Е010 С101 Р011 М010 Н101 К100 О110 итог553

48 В10. (2011) Сколько различных решений имеет уравнение ((J K) (M N L)) ((J N) (M N L)) (M J) = 1. В качестве ответа нужно указать только количество таких наборов. Ответ: 8.

49 Спасибо за внимание!