Примеры решения задания В15

1)Сколько существует различных наборов значений логических переменных 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, при которых выполнена данная система

Решение:

Проведем замену:

(x1 ≡ x2)=y1

(x3 ≡ x4)=y2

(x5 ≡ x6)=y3

(x7 ≡ x8)=y4

(x9 ≡ x10)=y5

Перепишем систему уравнений с учетом замены:

(y1Vy2)Λ(¬y1V¬y2)=1

(y2Vy3)Λ(¬y2V¬y3)=1

....

(y4Vy5)Λ(¬y4V¬y5)=1

Решим первое уравнение (y1Vy2)Λ(¬y1V¬y2)=1.Преобразуем логическое выражение (y1Vy2)Λ(¬y1V¬y2):

(y1Vy2)Λ(¬y1V¬y2)=(y1Λ¬y1)V(y1Λ¬y2)V(y2Λ¬y1)V(y2Λ¬y2)=0V(y1Λ¬y2)V(y2Λ¬y1)V0=(y1Λ¬y2)V(y2Λ¬y1).

Отобразим логическое выражение (y1Λ¬y2)V(y2Λ¬y1) с помощью диаграммы Эйлера-Венна:

Видно по рисунку,что это инверсия эквиваленции: ¬(y1≡y2) или ¬(y1↔y2).

Перепишем уравнение: ¬(y1≡y2)=1. Отсюда (y1≡y2)=0. Такое уравнение имеет 2 решения:y1=1,y2=0 или y1=0,y2=1.

Рассмотрим 2-ое уравнение. С учетом преобразований оно становится таким:¬(y2≡y3)=1.

Решим систему из двух уравнений:

¬(y1≡y2)=1

¬(y2≡y3)=1

Перепишем систему в одно уравнение:¬(y1≡y2)Λ¬(y2≡y3)=1.

Преобразуем ¬(y1≡y2)Λ¬(y2≡y3):

¬(y1≡y2)Λ¬(y2≡y3)=¬( (y1≡y2)V(y2≡y3) )-выносим отрицание за скобки.

Уравнение примет вид:¬( (y1≡y2)V(y2≡y3) )=1. Отсюда (y1≡y2)V(y2≡y3)=0.

Логическое выражение выполняется, только когда (y1≡y2)=0 и (y2≡y3)=0.

Пусть y2=0.

y1≡0=0-выполняется при y1=1.

0≡y3=0-выполняется при y3=1.

Получаем одно решение:y2=0,y1=1,y3=1.

Пусть y2=1.

y1≡1=0-выполняется при y1=0.

0≡y3=0-выполняется при y3=0.

Получаем одно решение:y2=1,y1=0,y3=0.

Общее число решений при двух уравнениях системы:1+1=2 решения.

Таким образом,при добавлении одного уравнения к самому первому уравнению не меняется число решений, остается равным двум. Следовательно, добавление остальных уравнений не изменит общее количество решений. Остается два решения.

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

y1=(x1 ≡ x2)-для каждого из значений y1 есть два решения. Например,если y=0,то x1=0,x2=1 или x1=1,x2=0.

y2=(x3 ≡ x4)-для каждого из значений y2 есть два решения.

Аналогично и для остальных:y3,y4,y5. Пары решений (x1,x2),(x3,x4),(x5,x6),(x7,x8),(x9,x10) - не зависят друг от друга, поэтому комбинаций решений равно 25=32.(основание равно 2,т.к. каждая пара дает два решения, а степень равна 5,т.к. у нас есть 5 пар).

В данном случае мы не учли, что и y1,y2,y3,y4,y5 дают нам в два раза больше решений.

Общее количество решений:32*2=64 решения.

2) Сколько существует различных наборов значений логических переменных 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

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

В качестве ответа Вам нужно указать количество таких наборов

Решение:

Преобразуем систему уравнений к виду:

(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1 (1)

(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1 (2)

(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1 (3)

Красным выделено уравнение, которое было преобразовано. ¬y1 \/ y2=y1 → y2. Аналогично и для остальных частей данного уравнения.

Решим уравнение (1).

Уравнение (1) содержит импликации (→), связанные конъюнкцией (/\). Соответственно, чтобы уравнение было истинно, все входящие импликации должны быть истинны:

x1 → x2=1,

x2 → x3=1,

x3 → x4=1.

Таблица истинности для импликации на примере x1 → x2:

x1

x2

x1->x2

0

0

1

0

1

1

1

0

0

1

1

1

 

Красным выделена комбинация, когда импликация ложна. Видно, что в ней идут подряд "1" и "0". Выпишем комбинации для x1x2x3x4, в которых не встречается подряд "1" и "0", чтобы импликации x1 → x2, x2 → x3, x3 → x4 не были равны 0.

x1

x2

x3

x4

0

0

0

0

0

0

0

1

0

0

1

1

0

1

1

1

1

1

1

1

 

Получили 5 комбинаций

3) Сколько существует различных наборов значений логических переменных 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

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

Решение. Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k]  = 1 . Поэтому первое уравнение имеет 6 решений (1-я цифра в наборе – значение x1, 2-я цифра в наборе – значение x2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Второе уравнение имеет 6 аналогичных решений (1-я цифра в наборе – значение y1, 2-я цифра в наборе – значение y2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Решение системы – пара таких наборов. Ввиду третьего уравнения, один наборов в паре должен быть набором 11111. Таких пар – 11: {11111, 11111}, 5 пар вида {11111, R} и 5 пар вида {R, 11111}, здесь R – один из наборов 00000, 00001, 00011, 00111, 01111. Пара {11111, 11111} встретилась 2 раза.

Ответ: 11

4) Сколько существует различных наборов значений логических переменных 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

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

Решение. Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k]  = 1 . Поэтому  первое уравнение имеет 6 решений (1-я цифра в наборе – значение x1, 2-я цифра в наборе – значение x2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Второе уравнение имеет 6 аналогичных решений (1-я цифра в наборе – значение y1, 2-я цифра в наборе – значение y2 и т.д.):

00000, 10000, 11000, 11100, 11110, 11111

Решение системы – пара таких наборов. Ввиду третьего уравнения, первый набор в паре должен принадлежать множеству {00111, 01111, 11111},  а второй - множеству  {11100, 11110, 11111}.  При этом любой из перечисленных наборов может образовывать пару с любым другим. Поэтому система имеет 3*3 = 9 решений.

Ответ: 9

4) Сколько существует различных наборов значений логических переменных 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

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

Решение. Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k]  = 1 . Поэтому первое уравнение имеет 6 решений (1-я цифра в группе – значение x1, 2-я цифра в группе – значение x2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Второе уравнение имеет 6 аналогичных решений (1-я цифра в группе – значение y1, 2-я цифра в группе – значение y2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Решение системы – пара таких наборов. Ввиду третьего уравнения, если первый набор в паре – это набор 11111, то и второй набор – 11111. Любой из остальных пяти наборов значений для переменных x1, x2, x3, x4, x5 может образовать решение системы с любым из 6 возможных  решений для  переменных y1, y2, y3, y4, y5. Таким образом, система имеет 1+5*6 = 31 решение.

Ответ: 31

5) Сколько существует различных наборов значений логических переменных x1, x2, ..., x5, которые удовлетворяют всем перечисленному ниже условию?

(x1 → x2) /\  (x2 → x3) /\ (x3 → x4) /\ (x4 → x5) = 1

В ответе не нужно перечислять все различные наборы значений x1, x2, ..., x5, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Решение. Очевидно, выполнены следующие соотношения:

 (x1 → x2) = 1

 (x2 → x3) = 1

 (x3 → x4) = 1

 (x4 → x5) = 1

Допустим, что набор {a1, a2, a3. a4, a5} – решение нашего уравнения. Допустим, что  a4 = 1. Тогда, из уравнения

(x4 → x5) = 1

следует, что a5 = 1 (напомним: 1 → 0  ложно!). Допустим теперь, что а3=1. Из условия

(x3 → x4) = 1

следует, что a4=1 и, значит, по доказанному, a5 = 1.

Аналогично можно показать (проверьте сами!), что если в решении встречается 1, то далее идут только единицы.

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

!!! Важно не забыть про «особые» наборы – 00000 и 11111. Они тоже годятся.

Таким образом, вот все решения уравнения:

00000, 00001, 00011, 00111, 01111, 11111

Каждое решение полностью описывается количеством единиц в нем. Это количество может быть от 0 до 5. Количество решений – 6.

Ответ: 6

6) Сколько существует различных наборов значений логических переменных x1, x2, ..., x5, z1, ..., z4, которые удовлетворяют всем перечисленному ниже условию?

(x1 → x2) /\  (x2 → x3) /\ (x3 → x4) /\ (x4 → x5) = 1 (1)

(z1 → z2) /\  (z2 → z3) /\ (z3 → z4)  = 1(2)

В ответе не нужно перечислять все различные наборы значений x1, x2, ..., x5, , z1, ..., z4 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Решение. Про такие системы говорят, что переменные в них «разделенные»: x1, …, x5 встречаются только в уравнении (1), а z1, …, z4  - только в уравнении (2). Из решения задачи 3 следует, что уравнению (1) удовлетворяют 6 наборов значений переменных x1, x2, ..., x5, а уравнению (2) – 5 наборов значений переменных z1, …, z4  Каждый из этих наборов для {xi } может образовать решение с любым из наборов для {zi }. Поэтому общее количество решений равно 6∙5 = 30.

Ответ: 30

 

7)Сколько существует различных наборов значений логических переменных  x1,x2x3,x4,у1,у2,у3,у4,которые удовлетворяют всем перечисленным ниже условиям?

X1-> X2-> X3-> X4=0

Y1-> Y2-> Y3-> Y4=0

 

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

Решение:

1) Уравнения независимы: находим решения первого уравнения, затем второго, далее множество решений первого и второго уравнений.

2) Выполним преобразование первого уравнени

 

((X1-> X2 )-> X3)-> X4 =((¬ X1V X2)-> X3->) X4 =

(¬( ¬X1V X2)V X3-> X4=( X1 ^¬X2 V X3->) X4=

¬(X1^¬ X2V X3)V X4=(¬ X1V X2)^ X3V X4=

=¬X1^ X3V X2^ ¬X3V X4=0

 

3) Полученное уравнение имеет пять наборов логических переменных x1,x2,x3,x4,удовлетворяющих условию.

4) Для набора из 4 независимых переменных существует 24 разных комбинаций значений этих переменных.

Второе уравнение преобразовывается аналогично первому, имеет 16- 5 = 11 наборов логических переменных у1,у2,у3,у4,удовлетворяющих условию.

5) Каждому из пяти наборов переменных x1,x2,x3,x4,соответствует 11 наборов переменных у1,у2,у3,у4,, т.е. 5 * 11 = 55

Ответ: 55

 

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

В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение.

Выражение (N ∨ ¬N) истинно при любом N, поэтому J ∧ ¬K ∧ L ∧ ¬M = 0.

 

Применим отрицание к обеим частям логического уравнения и используем закон де Моргана ¬(А∧В)=¬А∨¬В. Получим 

¬J ∨ K ∨ ¬L ∨ M = 1.

Логическая сумма равна 1, если хотя бы одно из составляющих ее высказываний равно 1. Поэтому полученному уравнению удовлетворяют любые комбинации логических переменных кроме случая, когда все входящие в уравнение величины равны 0. Каждая из 4 переменных может быть равна либо 1, либо 0, поэтому всевозможных комбинаций 2·2·2·2=16. Следовательно, уравнение имеет 16−1=15 решений.

Осталось заметить, что найденные 15 решений соответствуют любому из двух возможных значений значений логической переменной N, поэтому исходное уравнение имеет 30 решений.

Ответ:30

 

8)Укажите значения переменных K, L, M, N, при которых логическое выражение

(¬K ∨ M) → (¬L ∨ M ∨ N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1. 

Решение.

Применим преобразование импликации:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Применим отрицание к обоим частям уравнения:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Преобразуем:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.

Следовательно, M = 0, N = 0, рассмотрим теперь (¬K ∧ L ∨ M ∧ L):

из того, что M = 0, N = 0 следует, что M ∧ L = 0, тогда ¬K ∧ L = 1, то есть K = 0, L = 1.

Ответ:0100

 

9) Известно, что для целых чисел X, Y и Z истинно высказывание

(Z < X ∨ Z < Y) ∧ ¬(Z+1 < X) ∧ ¬(Z+1 < Y)

Чему равно Z, если X=25 и Y=48?

Решение.

(Z < X ∨ Z < Y) ∧ ¬(Z+1 < X) ∧ ¬(Z+1 < Y) = 1.

Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.

Подставим значения чисел в выражение:

1) (Z < X ∨ Z < Y) = (Z < 25 ∨ Z < 48) = 1.

2) ¬(Z+1 < X) = ¬(Z+1 < 25) = (Z => 24) = 1

3) ¬(Z+1 < Y) = (Z => 47) = 1.

Посмотрим на 1): если Z < 25 = 1, то неверно Z => 47, следовательно из 1) => Z < 48.

Из 3) и 1) следует, что Z = 47.

Ответ:47

 

10)Укажите значения переменных K, L, M, N, при которых логическое выражение

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

истинно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Решение.
Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.

1) (K → M) = 1 Применим преобразование импликации: ¬K ∨ M = 1

2) (K → ¬M) = 1 Применим преобразование импликации: ¬K ∨ ¬M = 1

Отсюда следует, что K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Применим преобразование импликации: K ∨ (M ∧ ¬L ∧ N) = 1 из того что K= 0 получаем:

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Ответ:0011

 

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

(K ∧ L) ∨ (M ∧ N) = 1

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.Выражение истинно в трех случаях, когда (K ∧ L) и (M ∧ N) равны соответственно 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N равны 1, а K и L любые, кроме как одновременно 1. Следовательно 3 решения.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 решение.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 решения.

Ответ:7

 

12) Каково наибольшее целое положительное число X, при котором истинно высказывание:

(X•X - 1 > 100) → (X•(X-1)< 100)

Решение.

Применим преобразование импликации:

¬(X•X - 1 > 100) ∨ (X•(X-1)< 100) => X•X - 1 < 100 ∨ (X•(X-1)< 100) => 
X•X < 101 ∨ (X•(X-1)< 100)

Если X•X < 101 = 1, то т. к.корень из 101 чуть больше 10 (меньше чем на 1), ответ 10.

Если X•(X-1)< 100, то нам необходимо решить неравенство: X•X - X - 100 < 0.

Корни этого квадратного уравнения:

Воспользовавшись методом интервалов, получаем, что наибольшее целое положительное число, удовлетворяющее неравенству, это 10.

В качестве ответа берем наибольшее из решений.

Ответ:10

 

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

(X ∨ Y ∨ Z) → (X ∧ P) = 1

где X, Y, Z, P – логические переменные? В ответе не нужно перечислять все различные наборы значений, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.

Применим преобразование импликации:

(X ∨ Y ∨ Z) → (X ∧ P) = 1;

¬(X ∨ Y ∨ Z) ∨ (X ∧ P) = 1;

(¬X ∧ ¬Y ∧ ¬Z) ∨ (X ∧ P) = 1; (1)

Логическое "ИЛИ" ложно , когда ложны оба утверждения.

Логическое "И" истинно только тогда, когда истинны оба утверждения.

Вариант 1.

(¬X ∧ ¬Y ∧ ¬Z) = 1 тогда X = 0, Y = 0, Z = 0.

Тогда из (1) следует, что P может быть как 1, так и 0, то есть 2 набора решений.

Вариант 2.

(¬X ∧ ¬Y ∧ ¬Z) = 0, (X ∧ P) = 1.

Тогда P = 1, X = 1.

(0 ∧ ¬Y ∧ ¬Z) = 0 => есть 4 решения.

В итоге 6 решений.

Ответ:6

 

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

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

где A, B, C, D – логические переменные?

В ответе не нужно перечислять все различные наборы значений A, B, C, D, при которых выполнено данное равенство. В качестве ответа вам нужно указать количество таких наборов.

Пояснение.Логическое "ИЛИ" истинно , когда истинно хотя бы одно из утверждений.

(D ∧ ¬D)= 0 при любых D.

Следовательно,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, что дает нам 3 варианта решений при каждом D.

(D ∧ ¬ D)= 0 при любых D, что дает нам два варианта решений (при D = 1, D = 0).

Следовательно: всего решений 2*3 = 6.

Итого 6 решений.

Ответ:6

 

15) Сколько существует целых значений X, при которых истинно высказывание:

¬(|X| > 5) ∧ (|X| > 1) ∧ (|X| > 10)

Решение.

Логическое "И" истинно, когда истинны все утверждения.

¬ (|X| > 5) = (|X| < 5) решение неравенства: (-5;5).

|X| > 1 решение неравенства: (-∞;-1) и (1;+∞).

|X| > 10 решение неравенства: (-∞;-10) и (10;+∞).

Найдем пересечение всех интервалов и посчитаем количество целых значений X.

Их будет 0.

Ответ:0