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


Интерактивный тренажер 18 ЕГЭ ДЕМО 2017
"Основные понятия математической логики"


Нашли ошибку, возникли вопросы или появились замечания, пишите...


Разбор решения задания 18 демоверсии ЕГЭ 2016
Основные понятия математической логики.

 

Пример:

 

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 1110&0101 = 0100 = 4.

Для какого наименьшего неотрицательного целого числа А формула

 x&25 <> 0 -> (x&17 = 0 -> x&А <> 0)

тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

 

Введем обозначения: P = x&25 = 0, Q = x&17 = 0, A = x&А = 0

 

Запишем данное выражение с помощью нашего обозначения

 

!P -> (Q ->!A)


и преобразуем, используя свойство импликации

 

!A + !B = !(A & B) и закон де Моргана A -> B = !A + B

 

!P -> (Q -> !A) = P + !Q +!A = !(P & Q) + A

 

окончательно получаем:


P & !Q -> A


чтобы это выражение было истинным, нужно, чтобы множество единичных битов числа (P or a) перекрывало множество единичных битов числа Q, а с помощью (a) можно добавить недостающие биты.

 

25 = 11001
(a) = *1***
17 = 10001

 

чтобы выбрать минимальное a, биты, обозначенные звездочками, примем равными нулю; получаем число 010002 = 8

 


Задача №18 на основные понятия математической логики

Примеры задач, генерируемых интерактивным тренажером на основные понятия математической логики с развернутым решением

Задание №1

На числовой прямой даны два отрезка: P=[13,28] и Q=[6,23]. Укажите наименьшую возможную длину такого отрезка A, что формула:

((x принадлежит A) > (x принадлежит P)) | (x принадлежит Q)

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

РЕШЕНИЕ:

   Для упрощения записи обозначим простые высказывания соответствующими буквами, тогда заданное выражение можно будет записать так:

          (A->P) + Q = 1,

но импликацию можно выразить через операции ИЛИ и НЕ поэтому можем записать, что

          ¬A + P + Q = 1

   Если рассматривать все значения x на числовой прямой, то логические значения формул могут измениться только при переходе через граничные точки заданных промежутков, следовательно, для упрощения записи можно не рассматривать значения формул на концах отрезков, так как это не повлияет на решение

   Исходя из заданных значений отрезков P = [13, 28] и Q = [6, 23], разбиваем числовой диапазон (Д) на несколько интервалов, определяемых точками (6,13,23 и 28)

   (Д)----6------13---------23----28--------> X

1-й интервал - x<6
2-й интервал - 6<x<13
3-й интервал - 13<x<23
4-й интервал - 23<x<28
5-й интервал - x>28

   Для определения истинности P и Q воспользуемся схематическим отображением данных отрезков и исследуемого числового диапазона Д, где цифрами 1,2,3 и 4 обозначим границы соответствующих промежутков

(Д)----1------2---------3----4--------

(P)-----------################-------

(Q)----##################------------

   Откуда становится понятным, что

P = 1 только внутри третьего и четвертого интервалов, т.е. между границами 2 и 4, а в остальных случаях - 0

Q = 1 только внутри второго и третьего интервалов, т.е. между границами 1 и 3, а в остальных случаях - 0

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

   Используя полученные значения, последовательно заполняем таблицу истинности

___X___|_P_|_Q_|P+Q|!A_|_A_|

  x<6  |_0_|_0_|_0_|_1_|_0_|

 6<x<13|_0_|_1_|_1_|_л_|_л_|

13<x<23|_1_|_1_|_1_|_л_|_л_|

23<x<28|_1_|_0_|_1_|_л_|_л_|

  x>28 |_0_|_0_|_0_|_1_|_0_|

   Из таблицы находим, что область возможного ответа, назовем ее 'О' лежит в диапазоне [6<x<28], сформированном значениями А = л, где символ 'л' от слова 'любое', указывающий на то, что переменная А может принимать значения равные 0 или 1

   Таким образом  наименьшая возможная длина отрезка А = 22

   Ответ: 22

 

Задание №2

На числовой прямой даны два отрезка: P=[5,35] и Q=[16,67]. Укажите наименьшую возможную длину такого отрезка A, что формула

P -> ((Q&!A) -> !P)

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

РЕШЕНИЕ:

   Для упрощения записи обозначим простые высказывания соответствующими буквами, тогда заданное выражение можно будет записать так:

          P->(Q&!A) -> !P = 1,

но импликацию можно выразить через операции ИЛИ и НЕ поэтому распишем первую импликацию:

          !P + (Q & !A) -> !P = 1

аналогично распишем и вторую импликацию:

          !P + !(Q & !A) + !P = 1

раскрывая скобку получаем:

          !P + !Q + !!A + !P = !P + !Q + A  =  1

   Если рассматривать все значения x на числовой прямой, то логические значения формул могут измениться только при переходе через граничные точки заданных промежутков, следовательно, для упрощения записи можно не рассматривать значения формул на концах отрезков, так как это не повлияет на решение

   Исходя из заданных значений отрезков P = [5, 35] и Q = [16, 67], разбиваем числовой диапазон (Д) на несколько интервалов, определяемых точками (5,16,35 и 67)

1-й интервал - x<5
2-й интервал - 5<x<16
3-й интервал - 16<x<35
4-й интервал - 35<x<67
5-й интервал - x>67

   Откуда становится понятным, что

P = 1 только внутри третьего и четвертого интервалов, т.е. между границами 2 и 4, в остальных случаях - 0

Q = 1 только внутри второго и третьего интервалов, т.е. между границами 1 и 3, а в остальных случаях - 0

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

___X___|_P_|_Q_|!P_|!Q_|!P+!Q|_A_|

  x<5  |_0_|_0_|_1_|_ 1_|__1__|_л_|

 5<x<16|_0_|_1_|_1_|_ 0_|__1__|_л_|

16<x<35|_1_|_1_|_0_|_ 0_|__0__|_1_|

35<x<67|_1_|_0_|_0_|_ 1_|__1__|_л_|

  x>67 |_0_|_0_|_1_|_ 1_|__1__|_л_|

   Из таблицы находим, что область возможного ответа лежит в диапазоне 16 < x < 35, сформированном значениями А = 1, а, в обозначеннии - 'л' от слова 'любое', указывающее на то, что переменная А может принимать значения равные 0 или 1

   Таким образом  наименьшая возможная длина отрезка А = 19

   Ответ: 19

 

 
© Северобайкальск, Russia
Александр Козлов, 2017

  Рейтинг@Mail.ru