Логические уравнения и системы. Методы решений

Логические уравнения, системы В4 ЕГ-2009,2010: В10-ЕГ-2011 В15

Задачи на вычисл числовых значений переменных

Пр1. A, B и С — целые числа, для кот истин высказывание

¬ (А = B) /\ ((A B)→(B C)) /\ ((B A)→(С B)). Чему равно В, если A = 45 и C = 43?

Обр вн, что это сложное выск состоит из трех простых
1) ¬(А = B); (A B)→(B C); (B A)→(С B)
2) эти простые выск связаны оп ∧ (И, конъюнкw), т е, они д вып одновременно
3) из ¬(А = B)=1 сразу следует, что А B
4) предп, что A B, тогда из 2 усл 1→(B C)=1; это выр м б истин только тогда, когда B C = 1
5) поэтому имеем A B C, этому условию соотв только число 44
6) на всякий сл пров и вар A C)=1;это выр истинно при любом B; теперь см 3 усл получ 1→(С B)=1;это выр м б истинно тогда и только тогда, когда C B, и тут мы получ противор, потому что нет такого числа B, для кот C B A.

B15 № 2210. Изв, что для X, Y и Z ист выск (Z Чему равно Z, если X=25 и Y=48?

3)A,B,C – целые , для кот истинно высказывание

Ка­ко­во наи­боль­шее целое по­ло­жи­те X, при ко­т высказывание

B15 № 2206. Сост табл ист для логич фу X = (А ↔ B) \/ ¬(A → (B \/ C)) в кот столбец зн арг А предст двоич запись числа 27, столбец зн арг В — числа 77, ст-ц зн арг С — числа 120. Число в столбце запис сверху вниз от ст разряда к младш. Перев получ двоич запись зн ф X в 10-чн систему счисления.

Решение 1 уравнения

Ука­жи­те зн пе­ре­м, при ко­т ло­гическое вы­р- ложно Ответ запиш в виде строки из 4 симв: зн перем К, L, М и N (в указ порядке). Так, н, строка 1101 соотв тому, что К=1, L=1, M=0, N=1.

А) (¬(М ∨ L) ∧ К) → (¬К ∧ ¬М ∨ N) б) (¬K ∨ M) → (¬L ∨ M ∨ N)

в) (¬(M ∨ L) ∧ K) →((¬K ∧ ¬M) ∨ N) г) (Р ∨ ¬Q) ∨ (Q → (S∨Т)) д) (K → M) ∨ (L ∧ K) ∨ ¬N

Ука­жи­те зн пе­ре­м, при ко­т ло­гическое вы­р-е истинно

А) (K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

А)

б)

б) ¬((J → K) → (L ∧ M ∧ N)) ∨ ¬((L ∧ M ∧ N) → (¬J ∨ K)) ∨ (M ∧ J) = 0

В) ((K ∨ L) → (L ∧M ∧ N))=0 г) (K ∧ L) ∨ (M ∧ N)=1 д) (X ∧ Y ∨ Z) → (Z ∨ P) = 0

и) (¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0 е) (X ∨ Y ∨ Z) → (X ∧ P) = 1

ж) (K ∨ L) ∧ (M ∨ N) = 1 з) ((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

Системы логических уравнений

Способ 1. Сведение к одному уравнению

преобр ур так, чтоб пр ч = 1 (истинно). Для этого применим инверсию

предст импликацию и “исклИЛИ” через базовые оп (“И”, “ИЛИ”, “НЕ”)

и можно объед их с пом оп “И” в одно уравнение,

единств реш: A =1, B=0 и C=1.

Метод таблиц истинности

Недостаток метода — трудоемкость при большом кол перем ( 4)

0) 1)Кто из подозреваемых участвовал в преступлении, если известно:

1) если Иванов не участвовал или Петров участвовал, то Сидоров участвовал;

2) если Иванов не участвовал, то Сидоров не участвовал.

Реш. И - Иванов участв в преступл; П - Петров участв\ в преступл; С - Сидоров участв в преступ.

Соед оба утв в 1 выск:

Составим таблицу истинности на полученное высказывание:

видим, что только у Иванова в получ строках "ИСТИНА" совп с его участ в прес. Зн он и есть преступ.

Способ 3. Декомпозиция

Идея чтобы зафикс зн одной из перем (полож ее= 0 или 1) и за счет этого упростить уравн. Затем м зафикс зн 2 перем и т.д

А)при A =0 получаем импликац ложна только в 1

сл — когда посылка истинна, а следствие ложно система реш не имеет

б) A =1 Из 1 ура в силу свойств импликац следует,

из 2-го т к означ что т е реш

Метод Преобразования уравнений

пр1 Найти единств решение системы логических уравнений

Отв запиш в виде строки из 4 симв: зн пер A, B, C, D (в указ пор). Т, н, строка 1101 соотв тому, что А = 1, В = 1, С = 0, D = 1. Реш упрощ 1 ур с-мы л ч

пр ч

Преобр 2 ур смы: итак

подст 2-е в 1-е

или откуда C=1 Тогда из 1 ур B=1

Пр2)Определить, кто из четырех студентов сдал экзамен, если известно, что:

а) если 1й сдал, то и 2й сдал;б) если 2й сдал, то 3й сдал или 1й не сдал;

в) если 4й не сдал, то 1й сдал, а 3й не сдал;г) если 4й сдал, то и 1й сдал

A — 1й студ сдал B — «2й с сдал C — 3й сдал E — 4й сдал

экз сдали все 4 студ

пр) какой корабль вышел в море если

А)Неверно, что если корабль A вышел в море, то корабль C — нет.

(б). В море вышел корабль B или корабль C, но не оба вместе.

. Реш. A — “корабль A вышел в море”,B — “корабль B вышел в море”,C — “корабл C вышел в море”.

Способ 1. Сведение к 1 уравнению.

преобр уравнения так, что правые части= 1 (истинн зн). Для этого

Последнее ур, равносильн исх системе, имеет единств реш: A=1, B=0 и C=1.

Способ 4. Последовательное решение уравнений дерево решений

В нек сл м решать ур последоват, на каждом шаге доб по 1 перем в рассм набор.

1-е ур 2 пары (A=0,B=1) и (A=1,B=0)

Подкл 2ур из кот н опред доп знач C

При A =0 импликац не м б ложна, т е 1 строка предыд табл не дает ни 1 реш смы 2 уравн

При A =1 единственное реш, для кот C=1:

Задачи на решение с-мы уравнений

1)(x1 → х2) ∧ (х2 →хЗ) ∧ (хЗ → х4) ∧ (х4 → х5 )=1

(y1 → y2) ∧ (у2→уЗ) ∧ (уЗ →у4) ∧ (у4 → у5 )=1

x1 ∨ y1 = 1

2)

3)

Задачи на кол-во решений с-мы уравнений

1. возм решать противоп задачу, определив общее число наборов, 

2. в з-ти от необх превр в конъюнк = 1 или дизъюнкцию = 0

3. разбить на систему согл табл истин описать наборы реш для каждой части системы

4. по возможности выбрать ту, где меньше решений

5. посмотреть какие реш совп, т.е. протестир решения одной части для др части

6. выкинуть из 2 части то, что не явл реш первой части.

7. для системы из 2 легко восп формулой колич пересечений.

8. иногда до легко подсч комб по их плу образ", иногда нагл и проще выпис их списком (если это в предел десятка)

Пр1)Ск разл реш имеет ур: (X\/Y\/Z)=(X/\P)=1, где X, Y, Z, P — логич переменные?

Это ур имеет последнюю оп импликацию, реш которой м б такие варианты:

Итого, для всего исходного уравнения получаем 2+4=6 решений.

Пр2.Сколько разл реш имеет уравн ((J→K)→(M \N/\L)) /\ ((J/\¬K)→¬(M /\ N /\ L))/\(M→J)=1,

Реш. Сначала преобразуем: (JΛ¬K) → ¬(MΛNΛL).

(JΛ¬K) → ¬(M Λ N Λ L)=¬(¬JVK)→ ¬(M Λ N Λ L)-вынесли отрицание за скобки

замену: (J → K)=P (M Λ N Λ L)=Q Получ : (P→Q) Λ (¬P→¬Q) это лог оп эквиваленц:P↔Q.

Проведем обратную замену:P↔Q=(J → K)↔(M Λ N Λ L).

Выпишем ур с учетом преобр:((J → K)↔(M Λ N Λ L)) Λ (M → J) = 1.

Ур= 1,когда (J → K)↔(M Λ N Λ L)=1 и (M → J)=1-логич умн дает 1,когда оба лог операнда равны 1.

(J → K)↔(M Λ N Λ L) дает 2 решения:

и Получ 2 с-мы ур: и

1-я имеет 1 реш. 2-я 7 реш всего 8 реш

1.Ск разл реш имеет уравн где A,B,C,D,E или J K L M N –логич перем. В отв не перечисл все разл наборы зн А, В, С, D, Е, явл реш, а только указать кол таких наборов

В отв не н перечис все разл наборы зн перем x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при кот вып данная система равенств. В кач отв н указать количество таких наборов.

Проверим, явл ли найд зн решен 2 уравнения

В ответе не н перечисл все разл наборы знач x1, x2, ... x9, x10, при кот вып данн система Ответ: 64

B15. Ск сущ разл наборов зн логич перем x1,x2,x3,x4,y1,y2,y3,y4, удовл всем перечисл ниже усло?

А) (x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1
(¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1 отв 15

1. Сколько решений имеет система уравнений:

(A  E)  (B  D) = B  B  C  (E  B  C  D), отв 5

C = 1.

В отв не н перечисл все разл наборы зн А, В, С, D, Е, явл реш, а только указ кол таких наборов.

2. Укаж зн пер А, В, С, D, при кот лв (А  С)  (А   (В   D)) ложно. Отв запиш в виде строки из 4 симв: зн перем A, B, C, D (в указ поряд). Т, н, строка 1101 соотв, А = 1, В = 1, С = 0, D = 1. Отв 0110

B15 № 2201. Ск разл реш имеет ур J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логиче перем? В отв не н перечис все разл наборы зн J, K, L, M и N, при кот вып данное рав В кач ответа н указать кол таких наборов.

Сколько различных решений имеет уравнение

Метод построения бинарного дерева решений

1а)Сколько разл реш имеет система логич ур:а) б)

1а)_Получив одну 1, все ост зн перем также стан 1, получив же 0, возм два вар: 0 и 1. Для одного ур дерево состоит из 2 уровней, для 2 ур доб одна перем и соотв один уровень дерева. Кол возм реш – кол разл ветвей постр дерева. Легко видеть, что оно равно m+1 На рис дерево на 5 уровней.

Реш. замена:(x1 ≡ x2)=y1 (x3 ≡ x4)=y2 (x5 ≡ x6)=y3 (x7 ≡ x8)=y4 (x9 ≡ x10)=y5

…

это инверсия эквиваленции: имеет 2 реш:y1=1,y2=0 или y1=0,y2=1.

Решим с-му из 2 уравн: и заменим одним

или по з-ну двойств вып, только когда и

пусть получаем пусть получаем т.е 2 реш

при доб 1 ур к самому 1му ур не меняется число реш=2. След, доб ост ур не изм общее кол реш=2

Теперь перейдем к поиску кол реш, исп обр подст для y. : y1 =(x1 ≡ x2) для каждого из зн y1 есть 2 реш. Анал и для ост:y3,y4,y5. Пары реш (x1,x2),(x3,x4),(x5,x6),(x7,x8),(x9,x10) - не зависят др от др, поэтому комб реш р 2⁵=32. не учли, что и y1,y2,y3,y4,y5 дают в 2 р больше реш. Общ кол реш: 32*2=64 реш.

1б) похожая з-ча при m=2 – 5 реш ,при m=3 – 8 решений пусть - кол решений при k уравн

-кол решений при x1=0, -кол реш при x1=1, тогда где

- число Фибоначчи. при n=7 при n=10

----------------------------------------------------------------------------------------------------------------------

Прим1. Сколько различных реш имеет система уравн: где X1-X10 — логич перем?

……………….

X1 =0 X10= 0

В отв не н перечисл все разл наборы знач X1, X2, X3, …, X10, при кот вып данная с-ма ур. нужно указать количество таких наборов.

Реш.прив ур к б удобн виду. В частн, в 1й скобке кажд ур нах лв, равносильн эквивал. Во 2й скобке нах логич выр, равносиль искл или. Заменив выр в первых скобках на эквивал, а во 2х на искл или получим:

(X1≡ X2) +(X2  X3) = 1

(X2 ≡ X3) +(X3  X4) = 1

(X3 ≡ X4) _(X4  X5) = 1

…………………………………………………

(X8  ≡X9) +(X9  X10) = 1

X1 =0 X10= 0

Дальн реш построим на принципе рассужд и постр дерева решения. По условию X1= 0

Пусть X2 = 1.Тогда 1е усл 1го уравн не вып (Xl≡X2) и тогда д вып 2е усл 1го ур (X2  X3), т е, X3 = 0. Тогда получ, что X2  X3 (не вып 1е усл 2го уравн), значит, д вып 2е условие 2го уравн X3  X4, Зн, X4 = 1. Анал рассуждая, получ, что знач последую перем д чередоваться:
Х5 = 0, Х6 = 1, Х7 = 0, Х8 = 1, Х9 = 0, Х10 = 1. Эта ветка рассужд (X2 = 1) привела нас к единств реш, но оно нам не подходит, т к мы получ Х10 = 1, а по усл задачи Х10 = 0. (Правая ветка дерева).

Пусть X2 = 0. Тогда 1е усл 1го уравн вып (Xl≡X2). Это зн, что 2е усл 1го уравн (X2  X3), не обязат д выполняться. То есть, X3 может быть любым.

Пусть X3= 1. Тогда 1е усл 2го ур (X2  X3) не вып. Зн, д вып 2е усл 2го ур (X3  X4), т е, Х4 = 0. Ситуация анал уже рассм нами для X2 = 1 — зн послед перем д чередоваться:
Х5 = 1, Х6 = 0, Х7 = 1, Х8 = 0, Х9 = 1, Х10 = 0. Это одно их решений.

Пусть X3=0. Тогда 1е усл 2го ур вып (X2 ≡ X3), это з, что 2е усл 2го ур (X3  X4) не обязат д вып. То есть, X4  может быть любым. Мы пришли к. повторяющ ситуации. Для каждой послед перем если она будет = 1, это б давать единств реш, а если 0, то н будет рассм 2 вар зн след перем. Всего б иметь 10 реш, но 5 из них нам не подх, так какХ10 = 1.Представим дерево решений:

ответ: 5.

Прим2 Рассм следующ систему уравн. Она отличается от предыдущей последним уравнением.

Сколько различных решений имеет система уравнений:

……………….

где X1, X2, X3, …, X10 — логич перем?

Реш. Необх рассм две ситуации: X1 = 0 и X1 = 1.

При X1 = 0 реш будет такое же, как в предыдущей задаче. Дерево решений то же

При выборе реш н учесть, что X1 ≡ X10= 0 вып, когда X1 и X10 имеют разные зн. Поэтому при X1 =0 выбир X10= 1.Решений будет 5. Столько же решений будет при X1 =1.

Всего решений будет 10. Ответ: 10.

Задачи на дерево решений

B15 № 3822. Сколько сущ разл наборов зн логич перем x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовл всем перечис ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5 ) = 1
x1\/y1 =1
B15 № 3854. Сколько сущ разл наборов зн лог перем x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовл всем перечисл ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1
(y5→y4) /\ (y4→y3) /\ (y3→y2) /\ (y2→y1 ) = 1
x3/\y3 =1
В15-2012 Сколько существ разл наборов зн логич перем x1,x2, ... x9, x10, кот удовл системе?

((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) =1
((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) =1
...
((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) =1

В ответе не н перечисл все разл наборы зн x1, x2, ... x9, x10, при кот выполн данная система

РЕШЕНИЕ СИСТЕМ УРАВНЕНИЙ Метод Сеток

метод прозрачных таблиц (метод сеток) – аналог графич способа для реш алгебраич систем, кот позво быстро решать с-му уравн, содерж не более 4 перем.Этот метод осн на скал произвед векторов. Систему уравнений

м записать в векторном виде:

Отлож вдоль оси ох все знач перем , а вдоль оси оу все зн вектора . Постр сетку на плоскости, прямые кот прох через указ знач и в узлах сетки выч скал произв векторов, т.е. левую часть 1 ур смы.Заполн такой табл требует врем, но она заполн быстро, т.к. в ней много закономерн. Например:

Если 2 вектора имеют на одном и том же месте коорд,= 1, то скал произв вект=1. Как следствие этого факта в табл 1 правая верхняя четверть заполнена единицами.

Если коорд одного вектора явл инверсными знач для коорд др вектора, то = 0.

Если хотя один из векторов явл нулевым, то скалярное произвед=0.

После заполн табл реш любой системы ур легко найти. Рассм метод сеток на примере.

С-ма: где (х₁; х₂; х₃) – вектор неизв, (1;1;0), (1;0;1), (0;1;1),

(1;0;1) – вектор своб членов.

По оси Оу нах вектор с коорд (1;1;0). Н налож 3 таб так, чтобы строки с вект (1;1;0), (1;0;1), (0;1;1), совмест. Нах узлы со з (1;0;1). Опуск перпенд на Ох из данных узлов и видим, что сма имеет единств решения: (0;1;0), т.е. х₁ = 0, х₂ = 1, х₃ = 0.

Зад3 (один учащ работает у доски под рук-вом учителя). Постр сетку для реш систем с 4 неизвестны.

1)Решить  систему   логических   уравнений  методом сеток

А) б) в)

Зад 3. 6 прозрач стаканов с водой расст в 2 паралл ряда по 3 стакана в каждом. На риспредст вид спереди и вид с правой стороны. Через прозр стенки стаканов видны уровни воды в каждом стакане и во всех стаканах, стоящих за ними. Опр, сколько воды налито в каждый стакан.

По рис видно, что стаканы либо полные, либо пустые. Мн-во стаканов, кот м оказ на указ 6 местах, обр алфа, кот сост из 2 элем.Обозн пустой стакан – 0, а полный – 1. тогда мн-во сост из 0 и 1, т.е. = {0,1} .Занум проекции на рис числами от 1 до 5. Занум ряды стаканов след обраи укажем эл, кот м оказ в этих рядах

1я проекция показ, что в первом столбце нет полных стаканов, т.е. х₁₁ = 0, х₂₁ = 0.

Из 5 проекции видно, что х₂₃ = 0, х₂₂ = 0. Ост элем легко опр: х₁₂ = 1, х₁₃ = 1.

Аналитич постановка задачи сводится к решению системы уравнений

Имеем систему ур, в кот опер “+” –  дизъюнкция, “^. ” –   конъюнкция.
Из 2 ур с-мы и истин таблиц конъюнкции и дизъюнкции получ х₂₁ + х₂₂ + х₂₃ = 0 = х₂₁ = х₂₂ = х₂₃ = 0.
Из 3 ура = х₁₁ = 0. Подст найден зн неизв в 4 и 5 урав системы:

=

Все свобод и неизв члены прин зн 0 или 1, а ур удовл логич опер, т.е. получ систему логиче уравн.
Таким образом, если в задаче даны 2 вида стаканов, то она легко реш путем реш системы логич уравнений. Это позв сэкономить время, дает более короткий и простой путь решения.