Основные понятия математической логики



Pdf көрінісі
Дата09.03.2019
өлшемі180.45 Kb.

 

 



 

 

A15



 (повышенный уровень, время – 2 мин) 

Тема:  Основные понятия математической логики. 

Про обозначения 

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» 

математической логике (

,



,

¬

), неудобны, интуитивно непонятны и никак не проявляют 

аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает  

 и 


. Поэтому 

на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку 

это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).  

В разных  учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ 

приводится расшифровка закорючек (





,

¬

), что еще раз подчеркивает проблему. Далее во 

всех решениях приводятся два варианта записи. 

Что нужно знать

 



условные обозначения логических операций 

¬ A, 

A

 

 

не A (отрицание, инверсия)



 

 B, 

B

A



 

A и B (логическое умножение, конъюнкция)

 

 B, 



B

A

+

 

 A или B (логическое сложение, дизъюнкция) 



 B 



 

 импликация (следование) 

 

таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация» (см. презентацию 



«Логика») 

 



операцию «импликация» можно выразить  через «ИЛИ» и «НЕ»: 



 B = ¬ A  B 

или в других обозначениях  



 B = 



B

A

+

 

 

если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем  – 



«ИЛИ», и самая последняя – «импликация» 

 



иногда полезны формулы де Моргана

1



¬ (A  B) = ¬ A  ¬ B  

B

A

B

A

+

=



 

¬ (A  B) = ¬ A  ¬ B  



B

A

B

A

=



+

 

Пример задания: 

Для какого из указанных значений X истинно высказывание     

¬((X

 

>

 

2)→(X

 

>

 

3))? 

 1)  1  

2) 2 


3) 3 

4) 4 


Решение (вариант 1, прямая подстановка): 

1)

 



определим порядок действий: сначала вычисляются результаты отношений в скобках, затем 

выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция 

«НЕ») для выражения в больших скобках 

2)

 



выполняем операции для всех приведенных возможных ответов (1 обозначает истинное 

условие, 0 – ложное); сначала определяем результаты сравнения в двух внутренних  скобках: 





X

 

>

 



X

 

>

 



 (X

 

>

 

2)→(X

 

>

 

3) 

¬((X

 

>

 

2)→(X

 

>

 

3)) 



 

 





 

 



 



 



 

 



                                                            

1

 Огастес (Август) де Морган – шотландский  математик и логик. 



 

 



 

 

3)



 

по таблице истинности операции «импликация» находим третий столбец (значение 

выражения в больших скобках), применив операцию «импликация» к значениям второго и 

третьего столбцов (в каждой строке): 





X

 

>

 



X

 

>

 



 (X

 

>

 

2)→(X

 

>

 

3) 

¬((X

 

>

 

2)→(X

 

>

 

3)) 



 





 





 



 



4)

 

значение выражения равно инверсии третьего столбца (меняем 1 на 0 и наоборот): 





X

 

>

 



X

 

>

 



 (X

 

>

 

2)→(X

 

>

 

3) 

¬((X

 

>

 

2)→(X

 

>

 

3)) 















5)

 

таким образом, ответ – 3. 



Возможные ловушки и проблемы

 



можно «забыть» отрицание (помните, что правильный ответ – всего один!) 

 



можно перепутать порядок операций (скобки, «НЕ», «И», «ИЛИ», «импликация») 

 



нужно помнить таблицу истинности операции «импликация», которую очень любят 

составители тестов

2

 



 

этот метод проверяет только заданные числа и не дает общего решения, то есть не 

определяет все множество значений X, при которых выражение истинно 

Решение (вариант 2, упрощение выражения): 

1)

 



обозначим простые высказывания буквами: 

A

 

=

 

X

 

>

 

2, B

 

=

 

X

 

>

 

2)

 



тогда можно записать все выражение в виде  

     


¬(A

 



 

B)  

или  


B

A

  



3)

 

выразим импликацию через «ИЛИ» и «НЕ» (см. выше): 



¬(A

 



 

B)= ¬(¬A

 



 



B) или  

B

A

B

A

+

=



 

4)



 

раскрывая по формуле де Моргана операцию «НЕ» для всего выражения, получаем 



¬(¬A

 



 



B)= A

 



 



¬B

   


или  

B

A

B

A

=



+

 

5)



 

таким образом, данное выражение истинно только тогда, когда A истинно (



X

 

>

 

2), а B – 

ложно (


X

 



 

3), то есть для всех X, таких что

 

2



 

<

 

X

 



 

3 

6)

 



из приведенных чисел только 3 удовлетворяет этому условию, 

7)

 



таким образом, ответ – 3. 

Возможные проблемы

 



нужно помнить законы логики (например, формулы де Моргана) 

 



при использовании формул де Моргана нужно не забыть заменить «И» на «ИЛИ» и 

наоборот 

 

нужно не забыть, что инверсией (отрицанием) для выражения  



X

 

>

 

3

 

является 



X

 



 

3, а не 

X

 

<

 

3 

 

                                                            

2

 … но которая, к сожалению, почти не нужна на практике. ☺ 



 

 



 

 

Решение (вариант 3, использование свойств импликации): 

1)

 

обозначим простые высказывания буквами: 



A

 

=

 

X

 

>

 

2, B

 

=

 

X

 

>

 

2)

 



тогда исходное выражение можно переписать в виде   

¬(A→B)=1 или A→B=0 

3)

 



импликация 

A→B ложна в одном единственном случае, когда A = 1 и B = 0; поэтому 

заданное выражение истинно для всех X, таких что 



X

 

>

 

2 и X

 



 

3 

4)

 



из приведенных чисел только 3 удовлетворяет этому условию, 

5)

 



таким образом, ответ – 3. 

 

Выводы: 

1)

 



в данном случае, наверное, проще третий вариант решения, однако он основан на том, что 

импликация ложна только для одной комбинации исходных данных; не всегда этот прием 

применим 

2)

 



второй и третий варианты позволяют не только проверить заданные значения, но и 

получить общее решение – все множество X, для которых выражение истинно; это более 

красиво для человека, обладающего математическим складом ума. 


 

 



 

 

Задачи для тренировки



3

1)

 



Для какого из указанных значений числа X истинно высказывание 

  

((X



 

<

 

5)→(X

 

<

 

3)) 



 ((X



 

<

 

2)→(X

 

<

 

1)) 

 

1)  1  



2) 2 

3) 3 


4) 4 

2)

 



Для какого числа X истинно высказывание 

 

((X



 

>

 

3)



(X



 

<

 

3)) →(X

 

<

 

1) 

 

1) 1 



2) 2 

3) 3 


4) 4 

3)

 



Для какого числа X истинно высказывание     

X

 

>

 



 ((X



 

<

 

5)→(X

 

<

 

3)) 

  1) 1 


2) 2 

3) 3 


4) 4 

4)

 



Для какого имени истинно высказывание: 

¬

 (Первая буква имени гласная  → Четвертая буква имени согласная)? 

1) ЕЛЕНА 

2) ВАДИМ 

3) АНТОН 

4) ФЕДОР 

5)

 

Для какого символьного выражения неверно высказывание: 



Первая буква гласная → 

¬

 (Третья буква согласная)? 

1)abedc 

2)becde 


3) babas     4) abcab 

6)

 



Для какого числа X истинно высказывание     

(X

 

>

 

2)



(X



 

>

 

5)→(X

 

<

 

3) 

  1) 5   

2) 2 

3) 3 


4) 4 

7)

 



Для какого из значений числа Z высказывание 

((Z

 

>

 

2)



(Z



 

>

 

4)) →(Z

 

>

 

3) будет ложным? 

1) 1 


2) 2 

3) 3 


4) 4 

8)

 



Для какого имени истинно высказывание: 

¬

 (Первая буква имени согласная  → Третья буква имени гласная)? 

1) ЮЛИЯ 

2) ПЕТР 


3) АЛЕКСЕЙ 

4) КСЕНИЯ 

9)

 

Для какого из значений числа Y высказывание 



(Y

 

<

 

5)

 



 



((Y

 

>

 

1)

 



 

(Y

 

>

 

5)) будет истинным? 

1) 1 


2) 2 

3) 3 


4) 4 

                                                            

3

 Источники заданий:  



1.

 

Демонстрационные варианты ЕГЭ 2004‐2011 гг. 



2.

 

Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. — СПб: Тригон, 2009. 



3.

 

Якушкин П.А., Лещинер В.Р., Кириенко Д.П.  ЕГЭ 2010. Информатика. Типовые тестовые задания. — М: 



Экзамен, 2010. 

4.

 



Крылов С.С., Ушаков Д.М.  ЕГЭ 2010. Информатика. Тематическая рабочая тетрадь.  — М.: Экзамен, 2010. 

5.

 



Якушкин П.А., Ушаков Д.М.  Самое полное издание типовых вариантов реальных заданий ЕГЭ 2010. 

Информатика.  — М.: Астрель, 2009. 

6.

 

М.Э. Абрамян, С.С. Михалкович, Я.М. Русанова, М.И. Чердынцева. Информатика. ЕГЭ шаг за шагом. – М.: 



НИИ школьных технологий, 2010. 

7.

 



Самылкина Н.Н., Островская Е.М. ЕГЭ 2011. Информатика. Тематические тренировочные задания. — М.: 

Эксмо, 2010. 

8.

 

Крылов С.С., Лещинер В.Р., Якушкин П.А. ЕГЭ 2011. Информатика. Универсальные материалы для подготовки 



учащихся. — М.: Интеллект‐центр, 2011. 

9.

 



Чуркина Т.Е. ЕГЭ 2011. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2010. 

 

 



 

 

10)



 

Для какого символьного выражения верно высказывание:  

 

¬

 (Первая буква согласная)  

 

¬



  (Вторая буква гласная)? 

1) abcde     

2) bcade      

3) babas  

4) cabab 

11)


 

Для какого имени истинно высказывание: 

(Вторая буква гласная  → Первая буква гласная)

 

 

  Последняя  буква согласная



1) ИРИНА 

2) МАКСИМ 

3) МАРИЯ 

4) СТЕПАН 

12)

 

Для какого имени истинно высказывание: 



¬

 (Первая буква согласная  → Последняя буква гласная)



 

 

  Вторая буква согласная



1) ИРИНА 

2) СТЕПАН 

 

3) МАРИНА 



4) ИВАН 

13)


 

Для какого имени истинно высказывание: 

(Первая буква согласная  → Вторая буква согласная)

 

 

  Последняя  буква гласная



1) КСЕНИЯ 

2) МАКСИМ 

3) МАРИЯ 

4) СТЕПАН 

14)

 

Для какого имени истинно высказывание: 



¬

 (Вторая буква гласная  → Первая буква гласная)



 

 

  Последняя  буква согласная



1) ИРИНА 

2) МАКСИМ 

3) МАРИЯ 

4) СТЕПАН 

15)

 

Для какого имени истинно высказывание: 



¬

 (Первая буква согласная  → Последняя буква согласная)



 

 

  Вторая буква согласная



1) ИРИНА 

2) СТЕПАН 

 

3) МАРИЯ 



4) КСЕНИЯ 

16)


 

Для какого имени истинно высказывание: 



¬

 (Первая буква гласная  → Вторая буква гласная)



 

 

  Последняя буква гласная



1) ИРИНА 

2) МАКСИМ 

 

3) АРТЕМ 



4) МАРИЯ 

17)


 

Для какого названия животного ложно высказывание: 



Заканчивается на согласную  

  В слове 7 букв  →



 

  

¬



(Третья буква согласная)

1) Верблюд 

2) Страус 

 

3) Кенгуру 



4) Леопард 

18)


 

Для какого названия животного ложно высказывание: 



В слове 4 гласных буквы  

  



¬

 (Пятая буква гласная)  

 

  В слове 5 согласных букв



1) Шиншилла 

2) Кенгуру 

 

3) Антилопа 



4) Крокодил 

19)


 

Для какого названия животного ложно высказывание: 



Четвертая буква гласная  →  

¬

 (Вторая буква согласная)? 

1) Собака 

2) Жираф 

 

3) Верблюд 



4) Страус 

20)


 

Для какого слова ложно высказывание: 



Первая буква слова согласная  → (Вторая буква имени гласная 



 Последняя буква слова 



согласная)? 

1) ЖАРА 


2) ОРДА 

3) ОГОРОД 

4) ПАРАД 


 

 



 

 

21)



 

Для какого числа X истинно высказывание 

 

(X(X-16)

 

>

 

-64) →(X

 

>

 

8

) 

 

1) 5 


2) 6 

3) 7  


4) 8 

22)


 

Для какого числа X истинно высказывание 

 

(X(X-8)

 

>

 

-25 + 2X) →(X

 

>

 

7

) 

 

1) 4 


2) 5 

3) 6  


4) 7 

23)


 

Для какого символьного набора истинно высказывание: 



Вторая буква согласная

 

 

  (В слове 3 гласных буквы  



 

Первая буква согласная)? 

1) УББОШТ 

2) ТУИОШШ 

 

3) ШУБВОИ 



4) ИТТРАО 

24)


 

Для какого имени ложно высказывание: 

(Первая буква гласная  

  Последняя буква согласная)  →



 

  

¬



(Третья буква согласная)

1) ДМИТРИЙ 

2) АНТОН 

 

3) ЕКАТЕРИНА 



4) АНАТОЛИЙ 

25)


 

Для какого имени истинно высказывание: 



Первая буква гласная  

  Четвертая буква согласная



 

 

  В слове четыре буквы



1) Сергей 

2) Вадим 

 

3) Антон 



4) Илья 

26)


 

Для какого числа X истинно высказывание 

  

       (


(X < 4) →(X < 3))  

 

(

(X < 3) →(X < 1)) 

 

1) 1 



2) 2 

3) 3  


4) 4 

27)


 

Для какого имени истинно высказывание: 



¬

 (Первая буква согласная  → Вторая буква согласная)



 

 

  Последняя буква согласная



1) ИРИНА 

2) МАКСИМ 

 

3) СТЕПАН 



4) МАРИЯ 

28)


 

Для какого имени истинно высказывание: 



¬

 (Первая буква согласная  → Последняя буква согласная)



 

 

  Вторая буква согласная



1) ИРИНА 

2) СТЕПАН 

 

3) КСЕНИЯ 



4) МАРИЯ 

29)


 

Для какого имени истинно высказывание: 

 (Первая буква согласная  → Вторая буква согласная)

 

 

  Последняя буква гласная



1) КСЕНИЯ 

2) МАКСИМ 

 

3) СТЕПАН 



4) МАРИЯ 

30)


 

Для какого имени истинно высказывание: 



¬

 (Последняя буква гласная  → Первая буква согласная)



 

 

  Вторая буква согласная



1) ИРИНА 

2) АРТЁМ 

 

3) СТЕПАН 



4) МАРИЯ 

31)


 

Для какого слова истинно высказывание: 



¬

 (Первая буква согласная  → (Вторая буква согласная



 

 

  Последняя буква гласная))? 



1) ГОРЕ 

2) ПРИВЕТ 

 

3) КРЕСЛО 



4) ЗАКОН 

32)


 

Для какого имени истинно высказывание: 

 (Первая буква согласная  → Вторая буква гласная)

 

 

  Последняя буква согласная



 

 



 

 

1) АЛИСА 



2) МАКСИМ 

 

3) СТЕПАН 



4) ЕЛЕНА 

33)


 

Для какого имени истинно высказывание: 

 (Вторая буква гласная  → Первая буква гласная)

 

 

  Последняя буква согласная



1) АЛИСА 

2) МАКСИМ 

 

3) СТЕПАН 



4) ЕЛЕНА 

34)


 

Для какого названия реки ложно высказывание: 

 (Вторая буква гласная  → Предпоследняя буква согласная)

 

 

  Первая буква стоит в  



     алфавите раньше третьей

1) ДУНАЙ 

2) МОСКВА 

 

3) ДВИНА 



4) ВОЛГА 

35)


 

Для каких значений X и Y истинно высказывание: 

 

(Y+1 > X) 

 



(Y+X < 0) 

 



(X > 1)

1) 


X = 0,5; Y = -1,1 

 

2) 



X = 1,1; Y = -4 

 

 



3) 

X = -1; Y = -4 

 

4) 



X = -1/10; Y = -1,1 

36)


 

Для какого слова истинно высказывание: 

 (Вторая буква согласная  

 



  Последняя буква гласная) → Первая буква гласная)? 

1) ГОРЕ 


2) ПРИВЕТ 

 

3) КРЕСЛО 



4) ЗАКОН 

37)


 

Для какого имени истинно высказывание: 

 Первая буква согласная 

 (



¬

 Вторая буква согласная 

 

 Четвертая буква гласная)? 



1) ИВАН 

2) ПЕТР 


 

3) ПАВЕЛ 

4) ЕЛЕНА 

38)


 

Для какого названия станции метро истинно высказывание: 

(Первая буква согласная 

 

Вторая буква согласная) ~

 

 Название содержит букву «л»)? 



Знаком ~ обозначается операция эквивалентности (результат X ~ Y – истина, если значения X и Y 

совпадают). 

1) Маяковская  2) Отрадное 

 

3) Волжская 



4) Комсомольская 

39)


 

Для какого названия города истинно высказывание: 

(Первая буква гласная 

 



Последняя буква гласная) ~

 

 Название содержит букву «м»)? 



Знаком ~ обозначается операция эквивалентности (результат X ~ Y – истина, если значения X и Y 

совпадают). 

1) Москва 

2) Дюссельдорф 

3) Амстердам 

4) Атланта 



 



Достарыңызбен бөлісу:


©stom.tilimen.org 2019
әкімшілігінің қараңыз

    Басты бет