Основные законы алгебры логики

Виды заданий:

• задачи с отрезками;

• задачи на множества чисел;

• задачи с делителями;

• задачи с битовыми логическими операциями;

• анализ неравенств на плоскости;

• смешанные задачи.

Что нужно знать для решения 15 задания?

1. Основные логические операции, их обозначения, таблицы истинности (все это можно посмотреть в предыдущем занятии №14).

2. Тождественные преобразования логических выражений.

В алгебре логики выполняются основные законы, позволяющие производить тождественные преобразования логических выражений.

Критерий истинности. 

AB (Если А, то В). Что нужно помнить об импликации? 1→0

Поэтому если А = 1, то В должно = 1.

Какой порядок действий при решении задачи №15 при решении ручным методом?

1. Ввести обозначения для краткой записи выражения.

2. Преобразовывать выражение до «читаемой» импликации.

3. Писать критерий истинности и находить ответ.

Пример 1. Задачи на ДЕЛ

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

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

Решение

• Ввести обозначения для краткой записи выражения

• Преобразовывать выражение до «читаемой» импликации

• Писать критерий истинности и находить ответ

Если значение x делится на A, то оно должно делиться на 23 и на 17. НОК(23,17)=391

Ответ: 391 

Пример 2. Задачи на побитовую конъюнкцию

Определи наименьшее натуральное число A, такое, что выражение

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

Решение

• Ввести обозначения для краткой записи выражения

•  Преобразовывать выражение до «читаемой» импликации

• Писать критерий истинности и находить ответ

чтобы это выражение было истинным, нужно, чтобы множество единичных битов числа 233 or А перекрывало множество единичных битов числа 135; с помощью А можно добавить недостающие биты:

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

Ответ: 6

Пример 3. Множества

Известно, что выражение

истинно (то есть принимает значение = 1 при любом значении переменной х). 

Определи наименьшее возможное значение произведения элементов множества А. Элементами множества А являются натуральные числа. 

Решение.

• Введем обозначения a, b, c для краткой записи выражения. (х ∈ 1,3,5,7,9,11) обозначим b, (х∈3,6,9,12) обозначим c, (х∈А) обозначим a

• Преобразовывать выражение до «читаемой» импликации:

  • используя закон исключения импликации, заменим ее отрицанием и дизъюнкцией: b ⋁ ¬c ⋁ a

  • используя правило Де Моргана, вынесем отрицание за скобку: ¬(b ∧ c) ⋁ a

  • заменяем на импликацию: (b ∧ c) → a

• Писать критерий истинности и находить ответ: если x b И x a, то x должен ∈а. Находим числа из множеств b = 1,3,5,7,9,11 и c=3,6,9,12, которые есть и там, и там. Это числа 3,9, поэтому Amin=3,9. Указываем минимальное множество А, так как в нем могут содержаться и другие числа, кроме 3 и 9. Требовалось найти произведение элементов множества А: 3*9=27

• Ответ: 27

Пример 4. Отрезки

На числовой прямой даны два отрезка: P=[43;49] и Q=[44;53]. Укажи наибольшую возможную длину такого отрезка А, что формула

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

Решение.

• Введем обозначения A, P, Q для краткой записи выражения. (х ∈ A) обозначим A, х ∈ P обозначим P, х∈Qобозначим Q:

• Преобразовывать выражение до «читаемой» импликации:

  • используя закон исключения импликации, заменим ее отрицанием и дизъюнкцией: A⋁P ⋁ Q

  • заменяем на импликацию: A → P ⋁ Q

• Писать критерий истинности и находить ответ: если x A , то x должен ∈P ИЛИ x∈Q

Делаем вывод, что А = [43;53]. Найти нужно длину А, для этого вычитаем из одного конца отрезка другой: 53-43=10

Ответ: 10

Задачи на отрезки программным способом

from itertools import *
def f(x):
    p=15<=x<=25 #записать отрезок 
    q=51<=x<=66 #записать отрезок Q
    A=a1<=x<=a2 # концы отрезка A неизвестны
    return (not q) <= ((p==q) or ((not p) <= A)) # записать формулу, быть осторожным со скобками  
Ox = [i/4 for i in range(24*4,76*4)]
m=[] # перебор значений с шагом 0,25 
for a1,a2 in combinations(Ox,2):
    if all(f(x)==1 for x in Ox): # функция истинна или ложна по условию задачи
        m.append(a2-a1)
print(min(m)) # написать min или max в зависимости от условия задачи