Логика. Построение таблиц истинности логических выражений. Проверка истинности логического выражения. Что нужно знать

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

,

,

,

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

=

• 
  иногда для упрощения выражений полезны формулы де Моргана:
  

¬ (A  B) = ¬ A  ¬ B

¬ (A  B) = ¬ A  ¬ B

• 
  если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
  
• 
  таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных
  
• 
  если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);
  
• 
  количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 2³=8 строчек, если заданы только 6 из них, то можно найти 2^8-6=2²=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)
  
• 
  логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
  
• 
  логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)
  

З

X	Y	Z	F
1	0	0	1
0	0	0	1
1	1	1	0

адание 1: Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

1. 
   нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных
   
2. 
   если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F
   
3. 
   перепишем ответы в других обозначениях:
   1) 2) 3) 4)
   
4. 
   первое выражение, , равно 1 только при , поэтому это неверный ответ (первая строка таблицы не подходит)
   
5. 
   второе выражение, , равно 1 только при , поэтому это неверный ответ (первая и вторая строки таблицы не подходят)
   
6. 
   третье выражение,, равно нулю при , поэтому это неверный ответ (вторая строка таблицы не подходит)
   
7. 
   наконец, четвертое выражение, равно нулю только тогда, когда , а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности
   
8. 
   таким образом, правильный ответ – 4 ; частичная таблица истинности для всех выражений имеет следующий вид:
   

X	Y	Z	F
1	0	0	1	0 ×	0 ×	1	1
0	0	0	1	–	–	0 ×	1
1	1	1	0	–	–	–	0

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

1. 
   часто правильный ответ – это самая простая функция, удовлетворяющая частичной таблице истинности, то есть, имеющая единственный нуль или единственную единицу в полной таблице истинности
   
2. 
   в этом случае можно найти такую функцию и проверить, есть ли она среди данных ответов
   
3. 
   в приведенной задаче в столбце F есть единственный нуль для комбинации
   
4. 
   выражение, которое имеет единственный нуль для этой комбинации, это , оно есть среди приведенных ответов (ответ 4)
   
5. 
   таким образом, правильный ответ – 4
   

Возможные проблемы: метод применим не всегда, то есть, найденная в п. 4 функция может отсутствовать среди ответов

З

X	Y	Z	F
1	0	0	1
0	0	0	0
1	1	1	0

адание 2:

1. 
   перепишем ответы в других обозначениях:
   

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

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

¬((X > 2)→(X > 3))?

1. 
   определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках
   
2. 
   выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); сначала определяем результаты сравнения в двух внутренних скобках:
   

   X	X > 2	X > 3	(X > 2)→(X > 3)	¬((X > 2)→(X > 3))
   1	0	0
   2	0	0
   3	1	0
   4	1	1

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

   X	X > 2	X > 3	(X > 2)→(X > 3)	¬((X > 2)→(X > 3))
   1	0	0	1
   2	0	0	1
   3	1	0	0
   4	1	1	1

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

   X	X > 2	X > 3	(X > 2)→(X > 3)	¬((X > 2)→(X > 3))
   1	0	0	1	0
   2	0	0	1	0
   3	1	0	0	1
   4	1	1	1	0

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

Возможные ловушки и проблемы: можно «забыть» отрицание (помните, что правильный ответ – всего один!) можно перепутать порядок операций (скобки, «НЕ», «И», «ИЛИ», «импликация») нужно помнить таблицу истинности операции «импликация», которую очень любят составители тестов этот метод проверяет только заданные числа и не дает общего решения, то есть не определяет все множество значений X, при которых выражение истинно

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

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

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

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

5. 
   таким образом, данное выражение истинно только тогда, когда A истинно (X > 2), а B – ложно (X ≤ 3), то есть для всех X, таких что 2 < X ≤ 3
   
6. 
   из приведенных чисел только 3 удовлетворяет этому условию,
   
7. 
   таким образом, ответ – 3.
   

Возможные проблемы: нужно помнить законы логики (например, формулы де Моргана) при использовании формул де Моргана нужно не забыть заменить «И» на «ИЛИ» и наоборот нужно не забыть, что инверсией (отрицанием) для выражения X > 3 является X ≤ 3, а не X < 3

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

2. 
   тогда исходное выражение можно переписать в виде ¬(A→B)=1 или A→B=0
   
3. 
   импликация A→B ложна в одном единственном случае, когда A = 1 и B = 0; поэтому заданное выражение истинно для всех X, таких что X > 2 и X ≤ 3
   
4. 
   из приведенных чисел только 3 удовлетворяет этому условию,
   
5. 
   таким образом, ответ – 3.