Определение истинности формул с помощью таблиц истинности

Пример Л4. Определить, истинна или нет формула Ø (x Ú Ø y) ® xÙ y, если а) x=1, y=0; б) x=0, y=1.

Решение. Для решения задачи нужно подставить данные значения x и y в формулу и использовать интерпретацию операций, учитывая их приоритет. Так, для а): Ø (1 Ú Ø 0) ® 1Ù 0 º Ø 1 ® 0 º 0 ® 0 º 1. Ответ: при x=1, y=0 данная формула истинна. Для б): Ø (0 Ú Ø 1) ® 0Ù 1 º Ø (0 Ú 0) ®0 º Ø 0 ® 0 º 1 ® 0 º 0. Ответ: при x=0, y=1 данная формула ложна. Этот процесс можно представить таблицей:

x	y	Ø y	x Ú Ø y	Ø (x Ú Ø y)	xÙ y	Ø (x Ú Ø y) ® xÙ y

Такими таблицами удобно пользоваться, если формула сложная и требуется определить ее истинность для всех возможных значений переменных.<

Пример Л5. Определить истинность формулы j º Ø (xÙ y) ® Ø xÚ Ø yÚ Ø z ® xÚ yÚ z для всех значений переменных x, y, z.

Решение. Решаем задачу с помощью таблицы, разбивая исходную формулу на подформулы:

x	y	z	xÙ y	Ø (xÙ y) º j₁	Ø x	Ø y	Ø z	Ø xÚ Ø yÚ Ø z º j₂	xÚ yÚ z º j₃	j₁®j₂ º j₄	j₄® j₃ º j

Создав такую таблицу, можно ответить на вопрос: является ли данная формула тавтологией? Ответ – нет, т.к. при x=0, y=0, z=0 ее значение есть 0, а тавтология истинна при любых x, y, z. Является ли эта формула противоречием? Нет, т.к. есть наборы переменных, при которых она истинна. Из таблицы видно, что, например, «усеченная» формула Ø (xÙ y) ® Ø xÚ Ø yÚ Ø z является тавтологией (все ее значения истинны), а, соответственно, ее отрицание Ø (Ø (xÙ y) ® Ø xÚ Ø yÚ Ø z ) будет противоречием (все значения ложны). <

Упрощение формул

Следующая важная задача в приложениях логики высказываний – упрощение формул. Под упрощением понимается получение более простой (например, более короткой, не содержащей знаков ®, скобок, отрицаний над составными формулами) формулы, эквивалентной данной. Для этого используются эквивалентные преобразования формул, основанные на следующих известных тождествах (правилах):

1) Ø (А Ú В) º Ø А Ù Ø В

2) Ø (АÙ В) º Ø А Ú Ø В

3) АÙ (В Ú С) º АÙ В Ú АÙ С

4) А Ú (ВÙ С) º (А Ú В) Ù (А Ú С)

5) А Ú (АÙ В) º А

6) АÙ (А Ú В) º А

7) (АÙ В) Ú Ø В º А Ú Ø В

8) Ø Ø А º А

9) А ® В º Ø А Ú В

10) А ® В º Ø В ® Ø А

11) АÙ В º ВÙ А

12) А Ú В º В Ú А

13) (АÙ В)Ù С º АÙ (ВÙ С)

14) (А Ú В) Ú С º А Ú (В Ú С)

15) (А º В) º (В º А)

16) А® (В ® С) º АÙ В ® С

17) А Ú А º А

18) АÙ А º А

19) А Ú В Ú Ø В º В Ú Ø В

20) А Ú В Ù Ø В º А

21) АÙ (ВÚ Ø В) º А

Здесь А, В, С – (под)формулы, в частности, логические переменные. Обычно, при преобразованиях вначале избавляются от импликаций с помощью правила 9, затем от отрицаний над составными формулами (правила 1, 2, 8) и скобок. Если в конечном результате преобразований получена тавтология, например, хÚ Ø х, то исходная формула также является тавтологией, т.к. она эквивалентна полученной. Аналогично, результат xÙ Ø x говорит о противоречивости исходной формулы. Правило 19 говорит о том, что в дизъюнкции подформула-тавтология и будет результатом, т.к. она всегда истинна, а для истинности дизъюнкции достаточно истинности хотя бы одного операнда. Правило 20 говорит о том, что противоречие не влияет на результат дизъюнкции, т.к. оно всегда ложно и результат определяется истинностью или ложностью оставшейся формулы. Соответственно тавтология не влияет на результат конъюнкции (правило 21), т.к. она всегда истинна и окончательный результат зависит только от значения оставшейся формулы.

Пример Л6. Упростить формулу: Ø (Ø xÙ Ø y)Ú (x ® y)Ù x.

Решение. Проводим цепочку преобразований (в скобках указывается номер применяемого правила):

Ø (Ø xÙ Ø y)Ú (x ® y)Ù x º (9) º Ø (Ø xÙ Ø y)Ú (Ø x Ú y)Ù x º (2) º Ø Ø x Ú Ø Ø y Ú (Ø x Ú y)Ù x º (8, 11, 3) º x Ú y Ú Ø xÙ x Ú yÙ x º (20) º x Ú y Ú yÙ x º (5) º x Ú y. <

Пример Л7. Определить, является ли формула Ø (Ø xÙ Ø y)Ú (x ® y)Ù x противоречием?

Решение. Проделав упрощения, приведенные в примере 1, получим, что исходная формула эквивалентна формуле x Ú y, которая противоречием не является. Ответ – нет.

Пример Л8. Определить, является формула xÚ Ø ((y Ú z) Ù x) тавтологией?

Решение. Упростим формулу: x Ú Ø ((y Ú z) Ù x) º (2) º x Ú Ø (y Ú z) Ú Ø x º (12) º x Ú Ø x Ú Ø (y Ú z) º (19) º x Ú Ø x. Ответ – да. <

3.6. Упражнения по теме для самостоятельного решения

1. Переведите целые числа из десятичной системы счисления в двоичную:

а) 513 ( Ответ: 1000000001); б) 600 ( Ответ: 1001011000).

2. Переведите десятичные дроби в двоичную систему счисления (ответ записать с шестью двоичными знаками):

а) 0, 4622 ( Ответ: 0, 011101); б) 0, 5198 ( Ответ: 0, 100001);

3. Переведите целые числа из десятичной в восьмеричную систему счисления: а) 8700 ( Ответ: 20774); б) 8888 ( Ответ: 21270).

4. Переведите целые числа из десятичной в шестнадцатеричную систему счисления: а) 266 ( Ответ: 10A); б) 1023 ( Ответ: 3FF).

5. Переведите двоичное число 1010001001011 в восьмеричную систему счисления ( Ответ: 12113).

6. Вычислите сумму чисел x и y, если . Результат представьте в виде восьмеричного числа. (Ответ: 320).

7. Вычислить значение суммы в десятичной системе счисления: (Ответ: 26).

8. B шестнадцатеричной системе счисления сумма чисел F₁₆ и 1011₂ равна? (Ответ: 1A)

9. Записать с помощью логических формул: если влажность так высока, то либо после полудня, либо вечером будет дождь. (Ответ: обозначим высказывания: А – «влажность высока», В – «дождь после полудня», С – «дождь вечером». Тогда формула: А ® (В Ú С) ).

10. Проверить истинность формул: известно, что x имеет значение 1. Что можно сказать о значениях импликации: Ø xÙ y ® z? (Ответ: импликация истинна независимо от значений y и z, т.к. ее посылка всегда ложна при x=1).

11. Противоречива ли формула: P ® Ø P Ú РÙ Ø Р? (Ответ: Нет: упростив формулу, получим формулу Ø Р, которая противоречием не является).

12. Упростить формулу: Ø (Ø xÙ Ø y)Ú (x ® y)Ù x. (Ответ: x Ú y)

13. Не строя таблицы истинности доказать эквивалентность: Ø (х®y) º x& Ø y (Ответ: Упростив формулу слева от знака тождества, получим формулу xÙ Ø y, что и требовалось).

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒