Geum.ru

Методические указания для подготовительных курсов Ростов-на-Дону

Вид материалаМетодические указания

Содержание


Пример Л5.
Пример Л6.
В является логическим следствием А
Пример Л9.
Пример Л10.
А  вс)св(в  а)  ( а  вс)  св (в  а) 
Подобный материал:
1   2   3

Пример Л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

1
0
1
1
0
0
1

0
1
0
0
1
0
0

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


Пример Л5. Определить истинность формулы   (xy)  xyz  xyz для всех значений переменных x, y, z.


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


x
y
z
xy
(xy)  1
x
y
z
xyz

 2
xyz

 3
12

 4
4  3

 

0
0
0
0
1
1
1
1
1
0
1
0

0
0
1
0
1
1
1
0
1
1
1
1

0
1
0
0
1
1
0
1
1
1
1
1

0
1
1
0
1
1
0
0
1
1
1
1

1
0
0
0
1
0
1
1
1
1
1
1

1
0
1
0
1
0
1
0
1
1
1
1

1
1
0
1
0
0
0
1
1
1
1
1

1
1
1
1
0
0
0
0
0
1
1
1


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


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


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


1) А  В  В  А

2) (А  В)  С  А  (В  С)

3) А  А  А

4) АВ  ВА

5) (АВ)С  А(ВС)

6) А  А  А

7) А(В  С)  АВ  АС

8) А  (ВС)  (А  В)  (А  С)

9)   А  А

10)  (А  В)  А  В

11)  (АВ)  А  В

12) А  В   А  В

13) А  В   В  А

14) (А  В)  (В  А)

15) А  (АВ)  А

16) А(А  В)  А

17) (АВ)  В  А  В

18) А (В  С)  АВ  С

19) А  В   В  В   В

20) А  В  В  А

21) А(В В)  А

22) А  (В   В)  В   В


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


Пример Л6. Упростить формулу: (xy)(x  y)x.

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

(xy)(x  y)x  (12)  (xy)( x  y)x  (11)   x   y  ( x  y)x  (9, 4, 7)  x  y   xx  yx  (20)  x  y  yx  (15)  x  y. 


Пример Л7. Определить, является ли формула (xy)(x  y)x противоречием?

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


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

Решение. Упростим формулу: x  ((y  z) x)  (11)  x  (y  z)   x  (1)  x  x  (y  z)  (19)  x   x. Ответ – да. 


2.6. Решение логических задач


Решение логических задач сводится к построению логической формулы и последующему ее упрощению. При этом можно получить ответы на вопросы: является ли рассуждение логически правильным, является ли рассуждение В логическим следствием рассуждения А, совместны ли рассуждения А, В, С, …? Для понимания решения таких задач рассмотрим подробнее эти понятия.

Говорят, что В является логическим следствием А, или А логически влечет В, если формула А  В является тавтологией. Из таблицы истинности для операции  и определения тавтологии следует, что это условие равносильно следующему: если истинно А, то истинно и В.

Для выяснения, являются ли рассуждения логически правильными, нужно представить каждое предложение в виде логической формулы и проверить, является ли заключение логическим следствием конъюнкции посылок.

Говорят, что множество утверждений совместно, если конъюнкция формул, соответствующих этим утверждениям, не является противоречием.


Пример Л9. Правильно ли рассуждение:

Если Джонс – коммунист, то Джонс – атеист. Джонс – атеист. Следовательно, Джонс – коммунист.

Решение. Обозначим утверждения: А – «Джонс – коммунист», В – «Джонс – атеист». Тогда исходное рассуждение можно представить формулой: (АВ)ВА. Упростим формулу и определим, является ли она тавтологией. Упрощение: избавимся от импликаций, скобок и отрицания по правилам 12, 7, 11, 15: (АВ)В  А   ((АВ) В))  А  В  А. Полученная формула тавтологией не является, следовательно, исходное рассуждение логически неверно. 


Пример Л10. Совместны ли утверждения: 1) Если инфляция растет, то увеличивается зарплата и увеличиваются налоги. 2) Налоги растут. 3) Зарплата снижается. 4) Если растет зарплата, то инфляция также растет.

Решение. Обозначим простые высказывания: инфляция растет – А, зарплата увеличивается – В, налоги увеличиваются – С. Запишем утверждения в виде формул: 1) А  ВС; 2) С; 3)  В; 4) В  А. Построим их конъюнкцию, упростим и проверим, будет ли окончательная формула противоречием:

(А  ВС)СВ(В  А)  ( А  ВС)  СВ (В  А) 

 ( А  ВС)(СВ  СВА)   АСВ  ВСВ  СВАА  ВСВА   АСВ. Полученная формула непротиворечива, следовательно, исходные утверждения совместны. 


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


Записать с помощью формул:
  1. Данное отношение есть отношение эквивалентности тогда и только тогда, когда оно рефлексивно, симметрично и транзитивно.
  2. Для того чтобы число делилось на три, достаточно, чтобы оно делилось на девять.
  3. Если влажность так высока, то либо после полудня, либо вечером будет дождь.
  4. Чтобы быть избранным в конгресс, необходимо приложить много усилий.
  5. Чтобы цены упали, достаточно, чтобы спроса не было и предложение было велико и необходимо, чтобы этого захотел продавец.


Проверить истинность формул:
  1. Известно, что эквивалентность x  y истинна. Что можно сказать о значении x  y и x  y ?
  2. Заполнить истинностную таблицу для формулы (PQ)( (PQ)).
  3. Известно, что x имеет значение 1. Что можно сказать о значениях импликации xy  z?
  4. Проверить истинность формулы ((xy)(yz)) (xz) при x=0, y=1, z=0 и при x=1, y=1, z=0.
  5. Построить таблицу истинности для функции Ф(x, y, z)   ( x y)  (x y)x. Является ли она тавтологией?


Преобразование (упрощение) формул:
  1. Противоречива ли формула P  P  РР ?
  2. Является ли тавтологией формула (PQ)  P  QQ ?
  3. Пусть Ф – тождественно ложная формула. Доказать, что xyФ 

x y.
  1. Упростить формулу (xy)(x  y)x.
  2. Найти x, если (x  a)  (x  a)  b.
  3. Проверить эквивалентность формул, преобразовав формулы слева и справа от знака  к одной и той же формуле: (PQ)(PR)  (PQR).
  4. Противоречива, тавтология или ни то, ни другое формула (PQ) (Q  P)  QQ ?
  5. Не строя таблицы истинности, доказать эквивалентность (хy)  xy.
  6. Упростить формулу (x(xx  yy) z)  x  yz  (yz).
  7. Не строя таблицы истинности, доказать эквивалентность x(yz)  xy  z .
  8. Построить таблицу истинности: F = А  ( В  А  В).
  9. Построить таблицу истинности: F = (В   А) ( ВА  АВ).
  10. Построить таблицу истинности: F = (А  В)  (В  А)  (В  А).
  11. На каких наборах переменных А и В истинна функция F = (А  В)  (В  А)  В  А (Ответ: <1, 0> , <1, 1>).
  12. Упростить логическую формулу ( А  В) (В  С)  С  А (Ответ: А ).
  13. Упростить логическую формулу АВС С В (Ответ: А В  С).
  14. Упростить логическую формулу (АВ  С)СВ D (Ответ: D).
  15. Истинность высказываний: «из двух фирм В и С проводит рекламную акцию только одна» и «фирма А проводит рекламную компанию, а фирма С не проводит – означает проведение рекламных акций какими фирмами? (Ответ: Фирмы A и B проводят рекламную акцию (Логическая формула для первого высказывания : , второго – . Тогда из истинности обоих высказываний следует, что ()  (). Упростим формулу и получим )).



Задания для самостоятельного решения


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

а) 3204; б) 5100.

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

а) 0,755; б) 0,787.

3. Переведите смешанное десятичное число в двоичную систему счисления 323,95.

4. Переведите целые числа из десятичной в восьмеричную систему счисления: а) 9080; б) 3090.
  1. Переведите целые числа из десятичной в шестнадцатеричную систему счисления: а) 2180; б) 4201.
  2. Переведите числа из десятичной системы счисления в восьмеричную:

а) 9326; б) 814, 562.
  1. Переведите двоичные числа в восьмеричную систему счисления: а) 1011010011111; б) 111000000100.
  2. Вычислите сумму чисел x и y, если . Результат представьте в виде восьмеричного числа и в виде шестнадцатеричного числа.
  3. Вычислить значение суммы в десятичной системе счисления: .
  4. B шестнадцатеричной системе счисления сумма чисел 12F16 и 10102 равна?
  5. Проверить истинность формулы ((xy)(yz)) (xz) при x=0, y=0, z=1 и при x=1, y=0, z=1.
  6. Является ли тавтологией формула (PQ)  P  QQ ?
  7. Упростить формулу (x(xx  yy) z)  x  yz  (yz).
  1. Упростить логическую формулу (А ВС)СА  С.
  2. Упростить логическую формулу (АВ)  (АВ)А.
  3. Упростить логическую формулу АВ(С  D) ВСА В ВА.
  4. Упростить логическую формулу (АВС С) В С.
  5. Упростить логическую формулу (А В (АВ)) С((АС) С)



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

  1. Найти произведение чисел 10110(2)и 4B(16). Результат перевести в восьмеричную систему счисления

1)97
2) 4B4FB0
3) 1650
4) 3162
5) 324
6) 10001
7) 4A45
8) 1029
9) 456
  1. На каких наборах логическая функция принимает значение Истина:

1) (0,0); (1,1)
2) (1,1); (0,1)
3) (0,0); (0,1); (1,0)
4) (1,1)
5) (0,0); (0,1)
6) на всех наборах
7) нет наборов
8) (0,0); (1,0);
9) (0,1); (1,0);
  1. После упрощения операций логическое выражение преобразуется к виду

1) A  B
2) ABC
3) CC
4) BC
5) CC

6) Нет варианта ответа
7) ABC
8) ABC
9) A  B
  1. Для чисел X=33(8), Y=1С(16), Z=11110(2), заданных в различных системах счисления, справедливо соотношение

1) x
2) y
3) z
4) z
5) x
6) y
7) x=y=z
8)x< y, y=z

9) Нет варианта ответа
  1. На каких наборах логическая функция принимает значение Истина:

1) (0,1); (1,1); (1,0)
2) (1,1); (0,1)
3) (0,0); (0,1); (1,0)
4) (1,1)
5) (0,0); (0,1)
6) на всех наборах
7) нет наборов
8) (0,0); (1,0);
9) (0,1); (1,0);
  1. После упрощения операций логическое выражение преобразуется к виду

1) C
2) ABC
3) A  B
4) BC
5) CC

6) Нет варианта ответа
7) B
8) ABC
9) A  B