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

Тема: Преобразование логических выражений.

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

,

,

,

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

=

• 
  если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
  
• 
  логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
  
• 
  логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
  
• 
  правила преобразования логических выражений (слайд из презентации «Логика»):
  

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

21. 
    это операция импликации между двумя отношениями и
    
22. 
    попробуем сначала решить неравенства
    

23. 
    обозначим эти области на оси X:
    

24. 
    вспомним таблицу истинности операции «импликация»:
    

    A	B	A → B
    0	0	1
    0	1	1
    1	0	0
    1	1	1

25. 
    согласно таблице, заданное выражение истинно везде, кроме областей, где и ; область истинности выделена зеленым цветом
    
26. 
    поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее , то есть, 7
    
27. 
    таким образом, верный ответ – 7 .
    

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

2. 
   это значит, что выражение истинно там, где или
   
3. 
   дальнейшие действия точно такие же, как и в варианте 1.
   

Еще пример задания:

1. 
   перепишем уравнение, используя более простые обозначения операций:
   

2. 
   из таблицы истинности операции «импликация» (см. первую задачу) следует, что это равенство верно тогда и только тогда, когда одновременно
   

3. 
   из первого уравнения следует, что хотя бы одна из переменных, K или L равна 1 (или обе вместе); поэтому рассмотрим три случая
   
4. 
   если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения
   
5. 
   если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения
   
6. 
   если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения
   
7. 
   таким образом, всего получаем 4 + 3 + 3 = 10 решений.
   

Еще пример задания:

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

2. 
   из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных
   
3. 
   из таблицы истинности операции «импликация» (см. первую задачу) следует, что это выражение ложно тогда и только тогда, когда одновременно
   

4. 
   первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда и ; отсюда следует (логическая сумма равна нулю), что может быть только при ; таким образом, три переменных мы уже определили
   
5. 
   из второго условия, , при и получаем
   
6. 
   таким образом, правильный ответ – 1000.
   

1. 
   запишем уравнение, используя более простые обозначения операций:
   

2. 
   заменим импликацию по формуле :
   

3. 
   раскроем инверсию сложного выражения по формуле де Моргана :
   

4. 
   упростим выражение :
   

5. 
   мы получили уравнение вида «сумма = 0», в нем все слагаемые должны быть равны нулю
   
6. 
   поэтому сразу находим
   
7. 
   таким образом, правильный ответ – 1000.
   

Замечание: этот способ работает всегда и дает более общее решение; в частности, можно легко обнаружить, что уравнение имеет несколько решений (тогда оно не сведется к форме «сумма = 0» или «произведение = 1»)

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

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

41. 
    Каково наибольшее целое число X, при котором истинно высказывание
    

42. 
    Сколько различных решений имеет уравнение
    

43. 
    Укажите значения переменных K, L, M, N, при которых логическое выражение
    

44. 
    Каково наименьшее целое положительное число X, при котором высказывание:
    

45. 
    Каково наибольшее целое положительное число X, при котором истинно высказывание:
    

46. 
    Укажите значения переменных K, L, M, N, при которых логическое выражение
    

47. 
    Каково наименьшее натуральное число X, при котором высказывание
    

48. 
    Укажите значения логических переменных Р, Q, S, Т, при которых логическое выражение
    

49. 
    Каково наибольшее целое положительное число X, при котором высказывание:
    

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