Логические задачи

Особенности решения
Руководствоваться здравым смыслом при решении логических задач.
Задание сложное, его невозможно формализовать, в каждом задании – свой путь решения

Основные знания по теме «Логика»
Базовые логические операции НЕ, И, ИЛИ
Дополнительные логические операции
Исключающее ИЛИ
Импликация
Эквивалентность

Основные знания по теме «Логика»

Приоритет логических операций :
вычисление в скобках
НЕ, И, ИЛИ, исключающее ИЛИ
импликация
эквивалентность
Основные знания по теме «Логика»
Замена операций
⊕ → ↔
через И, ИЛИ и НЕ:
Формулы де Моргана:

I. Простая задача, решаемая с методом рассуждений:
Сколько различных решений имеет уравнение
(K ∨ L ∨ M) ∧ (¬L ∧ ¬M ∧ N) = 1
N-любое (0 или 1)
K-любое, L=0, M=0, N=1, всего два решения
Примеры решения задач
Итого 7 х 2 = 14 решений
Есть только одно совпадающее решение
K=1, L=0, M=0, N=1
Сколько будет решений,
если заменить ∧ → ∨ ?

II. Задача, решаемая с методом рассуждений:
Сколько различных решений имеет уравнение
(X1 → X2)∧(X2 → X3)∧(X3 → X4)∧(X4 → X5) = 1
Все скобки
должны быть равны 1
Операция импликации дает только одно решение = 0, когда 1 → 0,
то есть нельзя, чтобы после 1 был 0
Примеры решения задач
Вывод:
Количество решений на единицу больше количества переменных (6 реш.)
Если X1…X10, то количество решений будет равно 11

III. Задача, решаемая с помощью замены переменных:
Сколько различных решений имеет система уравнений
((x1 ≡ x2) ∨ (x3 ≡ x4)) ∧ (¬(x1 ≡ x2) ∨ ¬(x3 ≡ x4)) =1
((x3 ≡ x4) ∨ (x5 ≡ x6)) ∧ (¬(x3 ≡ x4) ∨ ¬(x5 ≡ x6)) =1
((x5 ≡ x6) ∨ (x7 ≡ x8)) ∧ (¬(x5 ≡ x6) ∨ ¬(x7 ≡ x8)) =1
((x7 ≡ x8) ∨ (x9 ≡ x10)) ∧ (¬(x7 ≡ x8) ∨ ¬(x9 ≡ x10)) =1
Примеры решения задач
t1 = (x1 ≡ x2)
t2 = (x3 ≡ x4)
t3 = (x5 ≡ x6)
t4 = (x7 ≡ x8)
t5 = (x9 ≡ x10)
Произведем замену:
Перепишем уравнения, заметим, что уравнения = 1, когда t1 ≠ t2
( t1 ∨ t2 ) ∧ ( ¬ t1 ∨ ¬ t2) =1
( t2 ∨ t3 ) ∧ ( ¬ t2 ∨ ¬ t3) =1
( t3 ∨ t4 ) ∧ ( ¬ t3 ∨ ¬ t4) =1
( t4 ∨ t5 ) ∧ ( ¬ t4 ∨ ¬ t5) =1

Поскольку значения переменных в скобках должны быть разными, они будут чередоваться:
Примеры решения задач
t1 = (x1 ≡ x2)
t2 = (x3 ≡ x4)
t3 = (x5 ≡ x6)
t4 = (x7 ≡ x8)
t5 = (x9 ≡ x10)
Для каждой комбинации из 5-ти значений t1 … t5 существует по 2 решения:
если t1 = 0, то x1 =1, x2 =0
или x1 =0, x2 =1
если t1 = 1, то x1 =1, x2 =1
или x1 =0, x2 =0
( t1 ∨ t2 ) ∧ ( ¬ t1 ∨ ¬ t2) =1
( t2 ∨ t3 ) ∧ ( ¬ t2 ∨ ¬ t3) =1
( t3 ∨ t4 ) ∧ ( ¬ t3 ∨ ¬ t4) =1
( t4 ∨ t5 ) ∧ ( ¬ t4 ∨ ¬ t5) =1
Получим 2 решения:
То есть 2 варианта по 5 переменным дают 25=32 решения, 32+32=64