Сколько различных решений имеет система логических уравнений x1 y1 (3 видео)

Содержание

Сколько различных решений имеет система логических уравнений x1 y1
Сколько различных решений имеет система логических уравнений x1 y1
Задача №23. Решение систем логических уравнений.
📸 Видео

Видео:КАК РЕШАТЬ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ. ЕГЭ по информатике. Задание 23Скачать

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

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

где x₁, x₂, . x₈, y₁, y₂, . y₈ — логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

x₁y₁	x₂y₂
00	00
01	01
10	10
11	11

Для первой строки x₁y₁ истина возможна тогда и только тогда, когда пара x₂y₂ будет принимать значение 11.

Для второй строки x₁y₁ истина возможна тогда и только тогда, когда пара x₂y₂ будет принимать значение 11.

Для третей строки x₁y₁ истина возможна тогда и только тогда, когда пара x₂y₂ будет принимать значение 11.

Для четвёртой строки x₁y₁ истина возможна тогда и только тогда, когда пара x₂y₂ будет принимать значения 00, 01 и 10.

Применим это для остальных пар:

x₁y₁	x₂y₂	x₃y₃	x₄y₄	x₅y₅	x₆y₆	x₇y₇	x₈y₈
00	1	1	3	3	9	9	27	27
01	1	1	3	3	9	9	27	27
10	1	1	3	3	9	9	27	27
11	1	3	3	9	9	27	27	81

Таким образом, количество решений будет равно

Видео:Сколько решений имеет лог. уравнение (!(A *B) + C) IMP (!A * !B + D) = 1. Информатика, ЕГЭ, логикаСкачать

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

Представляем (не x2 + не y2) как не(x2 * y2) по закону де Моргана.
Тогда система пример вид

(x1 * y1) = не(x2 * y2)
(x2 * y2) = не(x3 * y3)
.
(x6 * y6) = не(x7 * y7)

Скобки не связаны между собой, мы можем их заменить своими переменными
a = не b
b = не c
c = не d
d = не e
e = не f
f = не g

Для этой системы возможны только два решения:
a 0 1
b 1 0
c 0 1
d 1 0
e 0 1
f 1 0
g 0 1

Каждая переменная является конъюнкцией икса и игрика, то есть если переменная истинна, то она принимает один вариант, если ложна — три варианта.
Таким образом, на первый столбец решения приходится 3^3=27 решений, на второй — 3^4 = 81 решение.
27+81 = 108.

Видео:Сколько решений имеет логическое уравнение: (A импликация В) ИЛИ (C импликация D). ЕГЭ(информатика)Скачать

Задача №23. Решение систем логических уравнений.

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

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

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

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, х2, х3, х4, х5, х6, х7, х8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Сделаем замену переменных:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно записать систему в виде одного уравнения:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

Кол-во наборов на x1…x8

Сложим количество наборов: 1 + 3 + 9 + 27 + 81 = 121.

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

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

Сделаем замену переменных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 — два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

Решение систем логических уравнений методом визуального определения рекурсии.

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

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

где x1, x2, … x10 — логические переменные?

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

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 ( 0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 ( 0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N_i₊₁ = N_i + 1. Тогда для десяти переменных получим 11 наборов.

Решение систем логических уравнений различного типа

Сколько существует различных наборов значений логических переменных x₁, . x₄, y₁. y₄, z₁. z₄, которые удовлетворяют всем перечисленным ниже условиям?

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

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

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

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):