Построение таблиц истинности логических выражений

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

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

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,,¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Поэтому иногда операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение). В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (,,¬), что еще раз подчеркивает проблему.

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

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

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

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

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

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

A  B эквивалентность (равносильность)

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

A → B = ¬ A  B

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

¬ (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 (выражение ложно)
  
• 
  логическое следование (импликация) А→В равна 0 тогда и только тогда, когда из A (посылка) истинна, а B (следствие) ложно
  
• 
  эквивалентность АB равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1
  

П

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

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

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

1) ¬X  ¬Y  ¬Z 2) X  Y  Z 3) X  Y  Z 4) ¬X  ¬Y  ¬Z

Решение:

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

(красный крестик показывает, что значение функции не совпадает с F, а знак «–» означает, что вычислять оставшиеся значения не обязательно).

З

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

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

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

1) X  ¬Y  Z 2) X  Y  Z 3) X  Y  ¬Z 4) ¬X  Y  ¬Z

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

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

1) ¬X  Y  ¬Z 2) X  Y  ¬Z 3) ¬X  ¬Y  Z 4) X  ¬Y  Z

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

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

1) X  Y  Z 2) ¬X  ¬Y  Z 3) X  Y  ¬Z 4) ¬X  ¬Y  ¬Z

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

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

1) ¬X  ¬Y  Z 2) ¬X  ¬Y  Z 3) X  Y  ¬Z 4) X  Y  Z

A	B	F
0	0	1
0	1	1
1	0	1
1	1	0

5. 
   Символом F обозначена логическая функция от двух аргументов (A и B), заданная таблицей истинности. Какое выражение соответствует F?
   

1) A → (¬A  ¬B) 2) A  B 3) ¬A → B 4) ¬A  ¬B

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

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

1) X  Y  Z 2) ¬X  Y  ¬Z 3) X  (Y  Z) 4) (X  Y)  ¬Z

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

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

1) X  Y  Z 2) X  Y  Z 3) X  Y  Z 4) ¬X  ¬Y  ¬Z

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

1

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

1) ¬(X  Y)  Z 2) ¬(X  ¬Y)  Z 3) ¬(X  Y)  Z 4) (X  Y)  Z

9. 
   С

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

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

1) X  Y  Z 2) ¬X  Y  ¬Z 3) X  Y  Z 4) X  Y  ¬Z

10. 
    

    A	B	F
    0	0	0
    0	1	1
    1	0	1
    1	1	1

    Символом F обозначена логическая функция от двух аргументов (A и B), заданная таблицей истинности. Какое выражение соответствует F?
    

1) A → (¬(A  ¬B)) 2) A  B 3) ¬A → B 4) ¬A  B

11. 
    Дан фрагмент таблицы истинности выражения F.
    

x1	x2	x3	x4	x5	x6	x7	F
0	1	0	1	1	1	1	1
1	0	1	0	1	1	0	0
0	1	0	1	1	0	1	1

Какое выражение соответствует F?

1) x1  ¬x2  x3  ¬x4  x5  x6  ¬x7

2) ¬x1  x2  ¬x3  x4  ¬x5  ¬x6  x7

3) ¬x1  x2  ¬x3  x4  x5  x6  x7

4) x1  ¬x2  x3  ¬x4  ¬x5  ¬x6  ¬x7

12. 
    Дан фрагмент таблицы истинности выражения F.
    

x1	x2	x3	x4	x5	x6	x7	F
0	1	0	1	1	1	1	1
1	0	1	0	1	1	1	0
0	1	0	1	1	0	1	1

Какое выражение соответствует F?
1) ¬x1  ¬x2  x3  x4  x5  x6  ¬x7

2) x1  x2  x3  ¬x4  ¬x5  ¬x6  x7

3) x1  x2  ¬x3  ¬x4  x5  x6  x7

4) ¬x1  x2  ¬x3  x4  ¬x5  ¬x6  ¬x7