Задание 15 ЕГЭ по информатике. Логические операции

Задание 1. Делимость: найти максимальное A

Условие. Обозначим ДЕЛ(n,m) — «n делится на m». Для какого наибольшего натурального A формула
¬ДЕЛ(x,A) → (ДЕЛ(x,6) → ¬ДЕЛ(x,9)) тожд. истинна?

Идея.

Ложь только когда ¬ДЕЛ(x,A) и ДЕЛ(x,6), а при этом ДЕЛ(x,9) (т.е. x кратно 18). Чтобы противоречия не было, все кратные 18 должны делиться на A ⇒ A | 18. Наибольшее — 18.

print(18)

def div (z,y):#Определим функцию "Делится без остатка"
    return z%y==0
def f (xx,aa):#Определим функцию для логического выражения
    return div (xx,aa) or ( not div (xx,6) or not div (xx,9) )
for A in range (1000,0,-1):#Перебираем натуральные числа А от большего к меньшему
    flag=True
    for x in range (1,50000):# Перебираем все Х
        if  not f(x,A):
            flag=False
            break
    if flag:
        print (A)
        break

Задание 2. Линейные неравенства: найти минимальное A

Условие. Найти наименьшее целое A, при котором (5k+6n>57) ∨ ((k≤A) ∧ (n<A)) истинно для всех положительных целых k,n.

Идея.

Опасны только пары с 5k+6n ≤ 57. Для них должно быть k≤A и n<A. Возьмём максимум по этим парам:
max k при n=1 ⇒ k≤10; max n при k=1 ⇒ n≤8. Нужно A ≥ 10 и A > 8 ⇒ A = 10.

print(10)

def f (k,n,A):#Определим функцию для логического выражения
    return (5*k+6*n>57)or(k<=A and n<A)
for A in range(1,10000):
    flag=True
    for k in range(1,10000):
        for n in range(1,10000):
            if not f(k,n,A):
                flag=False
                break
        if not flag: break
    if flag:
        print(A)
        break

Задание 3. Отрезки и импликации: минимальный N

Условие. A=[70;90], B=[40;60], C=[0;N]. Функция
F(x) = (¬(x∈A) → (x∈B)) ∧ (¬(x∈C) → (x∈A)). При каком наименьшем N функция истинна более чем для 30 целых x?

Идея.

U→V ⇔ ¬U ∨ V. Тогда F(x) ⇔ (x∈A ∪ B) ∧ (x∈A ∪ C) = A ∪ (B∩C).
Целых в A — 21. Нужно >30 всего ⇒ в B∩C = [40;min(60,N)] должно быть >9 целых ⇒ min(60,N) ≥ 49. Минимум — N = 49.

print(49)

def f(x,N):
    return ((70<=x<=90)or (40<=x<=60))and(0<=x<=N or (70<=x<=90))
for N in range (1,10000):
    lst=[]
    for x in range (1,10000):
        if f(x,N):
            lst.append(x)
        if len(lst)>30:
            break
    if len(lst)>30:
        print(N)
        break

Задание 4. Побитовые операции: минимальное A

Условие. Для какого наименьшего A формула
(x&29≠0) → ((x&17=0) → (x&A≠0)) тожд. истинна для всех неотрицательных x?

Идея.

Пусть 29=11101₂ (биты 16,8,4,1), 17=10001₂ (16,1). Опасные x: бит 16=0 и 1=0, но хотя бы один из (8,4)=1. Чтобы всегда было x&A≠0, A обязано содержать оба бита 8 и 4 ⇒ A = 8|4 = 12.

print(12)

m = 0
P = {i for i in range(5, 31)}
Q = {i for i in range(14, 24)}

for Amin in range(1, 101):
    for Amax in range(Amin + 1, 101):
        Flag = True
        A = {i for i in range(Amin, Amax)}
        for x in range(1, 101):
            f = not ((x in P) == (x in Q)) or (not(x in A))
            if not f:
                Flag = False
                break
        if Flag:
            m = max(m, len(A))
print(m)

Задание 5. Максимальная длина A для формулы с эквивалентностью

Условие. P=[5;30], Q=[14;23]. Найти наибольшую длину отрезка A, чтобы
((x∈P) ≡ (x∈Q)) → ¬(x∈A) была тожд. истинна.

Идея.

Нужно A ⊆ комплемент к области, где (P≡Q)=1. Эквивалентность равна 1 на
(−∞,5) ∪ [14,23] ∪ (30,∞). Дополнение — [5,14) ∪ (23,30]. Максимум — 9 (интервал [5,14)).

Короткая проверка

def inP(x): return 5 <= x <= 30
def inQ(x): return 14 <= x <= 23
def ok(a1,a2):
    for t in (a1,14,23,a2):
        if a1 <= t <= a2 and (inP(t) == inQ(t)): return False
    return True
print(9, ok(5,14))

m = 0
P = {i for i in range(5, 31)}
Q = {i for i in range(14, 24)}

for Amin in range(1, 101):
    for Amax in range(Amin + 1, 101):
        Flag = True
        A = {i for i in range(Amin, Amax)}
        for x in range(1, 101):
            f = not ((x in P) == (x in Q)) or (not(x in A))
            if not f:
                Flag = False
                break
        if Flag:
            m = max(m, len(A))
print(m)

Задание 6. Минимальная длина A для формулы с дизъюнкцией и импликацией

Условие. P=[10,40], Q=[5,15], R=[35,50]. Найти наименьшую длину промежутка A, чтобы
( (x∈A) ∨ (x∈P) ) ∨ ( (x∈Q) → (x∈R) ) была тожд. истинна.

Идея.

Ложь возможна только там, где одновременно x∉A, x∉P и x∈Q, x∉R. Значит, A должен покрыть (Q \ R) \ P = [5,15]\[10,40] = [5,9].

Ответ: по вещественной длине — 4 (отрезок [5,9]); если в задаче явно сказано «для целых x» и под длиной понимают число целых точек, тогда 5.

def inP(x): return 10 <= x <= 40
def inQ(x): return 5 <= x <= 15
def inR(x): return 35 <= x <= 50
def F(x,a1,a2): return (a1<=x<=a2) or inP(x) or (not inQ(x) or inR(x))
for a1,a2 in [(5,9),(6,8)]:
    bad = [x for x in range(0,51) if not F(x,a1,a2)]
    print(a1,a2, bad[:5])