Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

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

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

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

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

((x1 ≡ x2) → (x3 ≡ x4)) ∧ ((x3 ≡ x4) → ( x5 ≡ x6)) ∧ (( x5 ≡ x6) → (x7 ≡ x8)) = 1

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

Произведём замену: y1 = x1 ≡ x2; y2 = x3 ≡ x4; y3 = x5 ≡ x6; y4 = x7 ≡ x8. Получим уравнение:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1.

Логическое И истинно, только тогда, когда истины все утверждения, поэтому данное уравнение эквивалентно системе уравнений: Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Импликация ложна только в случае, если из истинного следует ложное. Данная система уравнений описывает ряд переменных . Заметим, что если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. То есть решения системы уравнений: 0000; 0001; 0011; 0111; 1111.

Уравнения вида xN ≡ x = 0 имеют два решение, уравнения вида xN ≡ x = 1 также имеет два решения.

Найдём сколько наборов переменных x соответствуют каждому из решений y.

Каждому из решений 0000; 0001; 0011; 0111; 1111 соответствует 2 · 2 · 2 · 2 = 16 решений. Всего 16 · 5 = 80 решений.

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

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

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

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

За­да­ние 3. Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, x3, x4, x5, x6, x7, x8 ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

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

За­пи­шем пе­ре­мен­ные в строч­ку: x1x2x3x4x5x6x7x8. Им­пли­ка­ция ложна толь­ко в том слу­чае, когда из ис­ти­ны сле­ду­ет ложь. Усло­вие не вы­пол­ня­ет­ся, если в ряде после оди­на­ко­вых цифр при­сут­ству­ет дру­гая цифра. На­при­мер, «11101. » что озна­ча­ет не­вы­пол­не­ние вто­ро­го усло­вия.

Рас­смот­рим ком­би­на­ции пе­ре­мен­ных, удо­вле­тво­ря­ю­щие всем усло­ви­ям. Вы­пи­шем ва­ри­ан­ты, при ко­то­рых все цифры че­ре­ду­ют­ся, таких два: 10101010 и 01010101. Те­перь для пер­во­го ва­ри­ан­та, на­чи­ная с конца, будем уве­ли­чи­вать ко­ли­че­ство по­вто­ря­ю­щих­ся под­ряд цифр (на­столь­ко, на­сколь­ко это воз­мож­но). Вы­пи­шем по­лу­чен­ные ком­би­на­ции: «10101011; 10101111. » таких ком­би­на­ций во­семь. Ана­ло­гич­но для вто­ро­го ва­ри­ан­та: «01010101; 01010100. «. Таким об­ра­зом, по­лу­ча­ем 8 + 8 = 16 ре­ше­ний.

За­да­ние 4. Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, x3, x4, x5, x6, x7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

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

За­пи­шем пе­ре­мен­ные в строч­ку: x1x2x3x4x5x6x7. Им­пли­ка­ция ложна толь­ко в том слу­чае, когда из ис­ти­ны сле­ду­ет ложь. Усло­вие не вы­пол­ня­ет­ся, если в ряду после оди­на­ко­вых цифр при­сут­ству­ет дру­гая цифра. На­при­мер, «11101. » что озна­ча­ет не­вы­пол­не­ние вто­ро­го усло­вия.

Рас­смот­рим ком­би­на­ции пе­ре­мен­ных, удо­вле­тво­ря­ю­щие всем усло­ви­ям. Вы­пи­шем ва­ри­ан­ты, при ко­то­рых все цифры че­ре­ду­ют­ся, таких два: 1010101 и 0101010. Те­перь для пер­во­го ва­ри­ан­та, на­чи­ная с конца, будем уве­ли­чи­вать ко­ли­че­ство по­вто­ря­ю­щих­ся под­ряд цифр(на­столь­ко, на­сколь­ко это воз­мож­но). Вы­пи­шем по­лу­чен­ные ком­би­на­ции: «1010111; 1011111. » таких ком­би­на­ций во­семь. Ана­ло­гич­но для вто­ро­го ва­ри­ан­та: «0101011; 0101111. «. Учтём, что при подсчёте ком­би­на­ция для вто­ро­го ва­ри­ан­та ком­би­на­ции 0000000 и 1111111 были учте­ны два­жды. Таким об­ра­зом, по­лу­ча­ем 8 + 8 − 2 = 14 ре­ше­ний.

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

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

По­стро­им древо ре­ше­ний пер­во­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

За­ме­тим, что вы­ра­же­ние (x3 ≡ x4) в двух слу­ча­ях равно 1 и в двух слу­ча­ях равно 0. Таким об­ра­зом, одно урав­не­ние имеет во­семь ре­ше­ний.

Вто­рое урав­не­ние свя­за­но с пер­вым толь­ко через вы­ра­же­ние (x3 ≡ x4). По­стро­им древо ре­ше­ний вто­ро­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x3 ≡ x4) су­ще­ству­ет че­ты­ре на­бо­ра пе­ре­мен­ных x1, x2. x4, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый ри­су­нок). Таким об­ра­зом, си­сте­ма из двух урав­не­ний имеет 4 · 4 = 16 ре­ше­ний.

Тре­тье урав­не­ние свя­за­но со вто­рым толь­ко через вы­ра­же­ние (x5 ≡ x6). По­стро­им древо ре­ше­ний тре­тье­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x5 ≡ x6) су­ще­ству­ет 2 · 4 = 8 на­бо­ров пе­ре­мен­ных x1, x2. x6, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый и вто­рой ри­су­нок). Таким об­ра­зом, си­сте­ма из трёх урав­не­ний имеет 8 · 4 = 32 ре­ше­ния.

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

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

По­стро­им древо ре­ше­ний пер­во­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

За­ме­тим, что вы­ра­же­ние (x3 ≡ x4) в двух слу­ча­ях равно 1 и в двух слу­ча­ях равно 0. Таким об­ра­зом, одно урав­не­ние имеет во­семь ре­ше­ний.

Вто­рое урав­не­ние свя­за­но с пер­вым толь­ко через вы­ра­же­ние (x3 ≡ x4). По­стро­им древо ре­ше­ний вто­ро­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x3 ≡ x4) су­ще­ству­ет че­ты­ре на­бо­ра пе­ре­мен­ных x1, x2. x4, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый ри­су­нок). Таким об­ра­зом, си­сте­ма из двух урав­не­ний имеет 4 · 4 = 16 ре­ше­ний.

Тре­тье урав­не­ние свя­за­но со вто­рым толь­ко через вы­ра­же­ние (x5 ≡ x6). По­стро­им древо ре­ше­ний тре­тье­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x5 ≡ x6) су­ще­ству­ет 2 · 4 = 8 на­бо­ров пе­ре­мен­ных x1, x2. x6, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый и вто­рой ри­су­нок). Таким об­ра­зом, си­сте­ма из трёх урав­не­ний имеет 8 · 4 = 32 ре­ше­ния, си­сте­ма из четырёх — 64.

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

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

По­стро­им древо ре­ше­ний пер­во­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

За­ме­тим, что вы­ра­же­ние (x3 ≡ x4) в двух слу­ча­ях равно 1 и в двух слу­ча­ях равно 0. Таким об­ра­зом, одно урав­не­ние имеет во­семь ре­ше­ний.

Вто­рое урав­не­ние свя­за­но с пер­вым толь­ко через вы­ра­же­ние (x3 ≡ x4). По­стро­им древо ре­ше­ний вто­ро­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x3 ≡ x4) су­ще­ству­ет че­ты­ре на­бо­ра пе­ре­мен­ных x1, x2. x4, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый ри­су­нок). Таким об­ра­зом, си­сте­ма из двух урав­не­ний имеет 4 · 4 = 16 ре­ше­ний.

Тре­тье урав­не­ние свя­за­но со вто­рым толь­ко через вы­ра­же­ние (x5 ≡ x6). По­стро­им древо ре­ше­ний тре­тье­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x5 ≡ x6) су­ще­ству­ет 2 · 4 = 8 на­бо­ров пе­ре­мен­ных x1, x2. x6, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый и вто­рой ри­су­нок). Таким об­ра­зом, си­сте­ма из трёх урав­не­ний имеет 8 · 4 = 32 ре­ше­ния.

Ана­ло­гич­но си­сте­ма из четырёх урав­не­ний будет иметь 64 ре­ше­ния.

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

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

Рас­смот­рим пер­вое урав­не­ние.

При x1 = 1 воз­мож­ны два слу­чая: x2 = 0 и x2 = 1. В пер­вом слу­чае x3 = 1. Во вто­ром — x3 либо 0, либо 1. При x1 = 0 также воз­мож­ны два слу­чая: x2 = 0 и x2 = 1. В пер­вом слу­чае x3 либо 0, либо 1. Во вто­ром — x3 = 0. Таким об­ра­зом, урав­не­ние имеет 6 ре­ше­ний (см. ри­су­нок).

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Рас­смот­рим си­сте­му из двух урав­не­ний.

Пусть x1 = 1. При x2 = 0 воз­мо­жен лишь один слу­чай: x3 = 1, пе­ре­мен­ная x4 = 0. При x2 = 1 воз­мож­но два слу­чая: x3 = 0 и x3 = 1. В пер­вом слу­чае x4 = 1, во вто­ром — x4 либо 0, либо 1. Всего имеем 4 ва­ри­ан­та.

Пусть x1 = 0. При x2 = 1 воз­мо­жен лишь один слу­чай: x3 = 0, пе­ре­мен­ная x4 = 1. При x2 = 0 воз­мож­но два слу­чая: x3 = 0 и x3 = 1. В пер­вом слу­чае x4 либо 1, либо 0, во вто­ром — x4 = 0. Всего имеем 4 ва­ри­ан­та.

Таким об­ра­зом, си­сте­ма из двух урав­не­ний имеет 4 + 4 = 8 ва­ри­ан­тов (см. ри­су­нок).

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Си­сте­ма из трёх урав­не­ний будет иметь 10 ре­ше­ний, из четырёх — 12. От­ри­ца­ние в по­след­нем урав­не­нии дей­ству­ет толь­ко на ком­би­на­цию пе­ре­мен­ных, не свя­зан­ных с с преды­ду­щи­ми урав­не­ни­я­ми. По­это­му, ко­ли­че­ство ре­ше­ний дан­ной в усло­вии си­сте­мы сов­па­да­ет с ко­ли­че­ством ре­ше­ний си­сте­мы из шести од­но­тип­ных урав­не­ний (си­сте­мы, в ко­то­рой в по­след­нем урав­не­нии нет знака от­ри­ца­ния после конъ­юнк­ции), и равно 16.

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

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

По­стро­им древо ре­ше­ний пер­во­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

За­ме­тим, что вы­ра­же­ние (x3 ≡ x4) в двух слу­ча­ях равно 1 и в двух слу­ча­ях равно 0. Таким об­ра­зом, одно урав­не­ние имеет во­семь ре­ше­ний.

Вто­рое урав­не­ние свя­за­но с пер­вым толь­ко через вы­ра­же­ние (x3 ≡ x4). По­стро­им древо ре­ше­ний вто­ро­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x3 ≡ x4) су­ще­ству­ет че­ты­ре на­бо­ра пе­ре­мен­ных x1, x2. x4, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый ри­су­нок). Таким об­ра­зом, си­сте­ма из двух урав­не­ний имеет 4 · 4 = 16 ре­ше­ний.

Тре­тье урав­не­ние свя­за­но со вто­рым толь­ко через вы­ра­же­ние (x5 ≡ x6). По­стро­им древо ре­ше­ний тре­тье­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x5 ≡ x6) су­ще­ству­ет 2 · 4 = 8 на­бо­ров пе­ре­мен­ных x1, x2. x6, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый и вто­рой ри­су­нок). Таким об­ра­зом, си­сте­ма из трёх урав­не­ний имеет 8 · 4 = 32 ре­ше­ния.

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

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

По­стро­им древо ре­ше­ний пер­во­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

За­ме­тим, что вы­ра­же­ние (x3 ≡ x4) в двух слу­ча­ях равно 1 и в двух слу­ча­ях равно 0. Таким об­ра­зом, одно урав­не­ние имеет во­семь ре­ше­ний.

Вто­рое урав­не­ние свя­за­но с пер­вым толь­ко через вы­ра­же­ние (x3 ≡ x4). По­стро­им древо ре­ше­ний вто­ро­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x3 ≡ x4) су­ще­ству­ет че­ты­ре на­бо­ра пе­ре­мен­ных x1, x2. x4, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый ри­су­нок). Таким об­ра­зом, си­сте­ма из двух урав­не­ний имеет 4 · 4 = 16 ре­ше­ний.

Тре­тье урав­не­ние свя­за­но со вто­рым толь­ко через вы­ра­же­ние (x5 ≡ x6). По­стро­им древо ре­ше­ний тре­тье­го урав­не­ния:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Для каж­до­го из зна­че­ний 0 и 1 вы­ра­же­ния (x5 ≡ x6) су­ще­ству­ет 2 · 4 = 8 на­бо­ров пе­ре­мен­ных x1, x2. x6, удо­вле­тво­ря­ю­щих пер­во­му урав­не­нию (см. пер­вый и вто­рой ри­су­нок). Таким об­ра­зом, си­сте­ма из трёх урав­не­ний имеет 8 · 4 = 32 ре­ше­ния.

Ана­ло­гич­но си­сте­ма из четырёх урав­не­ний будет иметь 64 ре­ше­ния, си­сте­ма из пяти урав­не­ний — 128.

За­да­ние 1. Сколь­ко раз­лич­ных ре­ше­ний имеет урав­не­ние 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.

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

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

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

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

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬ K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

где J, K, L, M, N – ло­ги­че­ские пе­ре­мен­ные?

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

Ис­поль­зу­ем фор­му­лы A → B = ¬ A ∨ B и ¬ ( А ∨ В ) = ¬А ∧ ¬В

Рас­смот­рим первую под­фор­му­лу:

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

Рас­смот­рим вто­рую под­фор­му­лу

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

Рас­смот­рим тре­тью под­фор­му­лу

1) M → J = 1 сле ­ до ­ ва ­ тель ­но,

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

(0 ∨ K) ∨ 0 ∨ ¬ N ∨ ¬ L = K ∨ ¬ N ∨ ¬ L;

¬K ∨ N ∧ L ∧ K ∨ ¬ N ∨ ¬ L = 0 ∨ L ∨ 0 ∨ ¬ L = L ∨ ¬ L = 1 сле ­ до ­ ва ­ тель ­ но , 4 ре ­ ше ­ ния .

(J ∧ ¬ K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬ K) ∨ (0 ∧ N ∧ L) = ¬ K;

(¬J ∨ K) ∨ ¬ M ∨ ¬ N ∨ ¬ L = (0 ∨ K) ∨ 1 ∨ ¬ N ∨ ¬ L = K ∨ 1 ∨ ¬ N ∨ ¬ L

K ∨ 1 ∨ ¬ N ∨ ¬ L ∧ ¬ K = 1 ∨ ¬ N ∨ ¬ L сле ­ до ­ ва ­ тель ­ но , 4 ре ­ ше ­ ния .

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

(¬J ∨ K) ∨ ¬ M ∨ ¬ N ∨ ¬ L = (1 ∨ K) ∨ 1 ∨ ¬ N ∨ ¬ L.

За­да­ние 3. Сколь­ко раз­лич­ных ре­ше­ний имеет урав­не­ние:

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

Ис­поль­зу­ем фор­му­лу A → B = ¬ A ∨ B

Рас­смот­рим первую под­фор­му­лу:

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

Учи­ты­вая, что ¬(А ∨ В ) = ¬А ∧ ¬В ,

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

Рас­смот­рим вто­рую под­фор­му­лу

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

При­ме­ним от­ри­ца­ние к левой и пра­вой части урав­не­ния, по­лу­чит­ся

[(J ∧ ¬ K) ∨ (M ∧ N ∧ L)] ∧ [ ¬ L ∨ ¬ M ∨ ¬ N ∨ ¬ J ∨ K] ∧ [ ¬ M ∨ ¬ J] = 1

1) (¬M ∨ ¬ J) = 1, сле ­ до ­ ва ­ тель ­ но ,

0 ∧ ¬ K ∧ ¬ L ∨ ¬ N ∨ K, сле ­ до ­ ва ­ тель ­ но , 0 ре ­ ше ­ ний .

[(0 ∧ ¬ K) ∨ (1 ∧ N ∧ L)] ∧ [ ¬ L ∨ 0 ∨ ¬ N ∨ 1 ∨ K] ∧ [ ¬ M ∨ 1] = N ∧ L ∧ ¬ L ∨ ¬ N ∨ 1 ∨ K = 1 => L=N=1, сле­до­ва­тель­но, 2 ре­ше­ния.

[(1 ∧ ¬ K) ∨ (0 ∧ N ∧ L)] ∧ [ ¬ L ∨ ¬ 0 ∨ ¬ N ∨ ¬ 1 ∨ K] ∧ [ ¬ 0 ∨ ¬ 1] = 1, сле ­ до ­ ва ­ тель ­ но , 4 ре ­ ше ­ ния .

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

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

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

пе­ре­пи­шем урав­не­ние, ис­поль­зуя более про­стые обо­зна­че­ния опе­ра­ций:

((K + L) → (L · M · N)) = 0

1) из таб­ли­цы ис­тин­но­сти опе­ра­ции «им­пли­ка­ция» (см. первую за­да­чу) сле­ду­ет, что это ра­вен­ство верно тогда и толь­ко тогда, когда од­но­вре­мен­но

K + L = 1 и L · M · N = 0

2) из пер­во­го урав­не­ния сле­ду­ет, что хотя бы одна из пе­ре­мен­ных, K или L, равна 1 (или обе вме­сте); по­это­му рас­смот­рим три слу­чая

3) если K = 1 и L = 0, то вто­рое ра­вен­ство вы­пол­ня­ет­ся при любых М и N; по­сколь­ку су­ще­ству­ет 4 ком­би­на­ции двух ло­ги­че­ских пе­ре­мен­ных (00, 01, 10 и 11), имеем 4 раз­ных ре­ше­ния

4) если K = 1 и L = 1, то вто­рое ра­вен­ство вы­пол­ня­ет­ся при М · N = 0; су­ще­ству­ет 3 таких ком­би­на­ции (00, 01 и 10), имеем еще 3 ре­ше­ния

5) если K = 0, то обя­за­тель­но L = 1 (из пер­во­го урав­не­ния); при этом вто­рое ра­вен­ство вы­пол­ня­ет­ся при М · N = 0; су­ще­ству­ет 3 таких ком­би­на­ции (00, 01 и 10), имеем еще 3 ре­ше­ния

6) всего по­лу­ча­ем 4 + 3 + 3 = 10 ре­ше­ний.

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

где 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 ре ­ ше ­ ния .

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

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

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

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

(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>

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

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

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

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬ Y ∧ ¬ Z = 0 => ¬ X ∨ ¬ Y ∧ 1 = 0 =>

¬X ∨ ¬ Y = 0 => X = 1; Y = 1.

Сле­до­ва­тель­но, су­ще­ству­ет толь­ко одно ре­ше­ние урав­не­ния.

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

(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)

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

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

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

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

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

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

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

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

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

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

Ло­ги­че­ское И ис­тин­но толь­ко в одном слу­чае: когда все вы­ра­же­ния ис­тин­ны.

K ∨ L = 1, M ∨ N = 1.

Каж­дое из урав­не­ний дает по 3 ре­ше­ния.

Рас­смот­рим урав­не­ние А ∧ В = 1 если и А и В при ­ ни ­ ма ­ ют ис ­ тин ­ ные зна ­ че ­ ния в трех слу­ча­ях каж­дое, то в целом урав­не­ние имеет 9 ре­ше­ний.

Сле­до­ва­тель­но ответ 9.

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

((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 ре­ше­ний.

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

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

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

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

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

Ло­ги­че­ское ИЛИ ис­тин­но в трех слу­ча­ях.

K ∧ L ∧ M = 1, тогда K, L, M = 1, а ¬ L ∧ M ∧ N = 0. N любое , то есть 2 ре ­ ше ­ ния .

¬L ∧ M ∧ N = 1, тогда N, M = 1; L = 0, K любое , то есть 2 ре ­ ше ­ ния .

Сле­до­ва­тель­но, ответ 4.

Системы логических уравнений, содержащие не однотипные уравнения

За­да­ние 1. Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных 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, x2, x3, x4, x5, y1, y2, y3, y4, y5, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

1) Из по­след­не­го урав­не­ния сле­ду­ет, что гло­баль­но мы имеем три ва­ри­ан­та — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.

2) Ло­ги­че­ское И ис­тин­но, толь­ко тогда, когда ис­ти­ны все утвер­жде­ния, а им­пли­ка­ция ложна толь­ко в слу­чае, если из ис­тин­но­го сле­ду­ет лож­ное.

3) Урав­не­ние (1) опи­сы­ва­ет ряд пе­ре­мен­ных . Так как из пе­ре­мен­ной с более низ­ким но­ме­ром все­гда сле­ду­ет пе­ре­мен­ная с более вы­со­ким, если любую пе­ре­мен­ную из этого ряда при­рав­нять 1, то все сле­ду­ю­щие долж­ны также быть равны 1. Для урав­не­ния (2) су­ще­ству­ет то же самое пра­ви­ло. Иначе го­во­ря, если за­пи­сать пе­ре­мен­ные x (или y) в по­ряд­ке воз­рас­та­ния их но­ме­ров, слева будут нули, а спра­ва — еди­ни­цы.

4) Рас­смот­рим ва­ри­ант x1=1, y1=1. Так как пер­вые числа каж­до­го ряда равны 1, то все сле­ду­ю­щие тоже равны 1. Су­ще­ству­ет толь­ко одна ком­би­на­ция для этого ва­ри­ан­та.

5) Рас­смот­рим ва­ри­ант x1=0, y1=1. Для y-ряда все пе­ре­мен­ные равны 1, для x же су­ще­ству­ет 5 ком­би­на­ций, так как в ряде x может быть от 1 до 5 нолей вклю­чи­тель­но.

6) По­след­ний ва­ри­ант рас­смот­рим ана­ло­гич­но преды­ду­ще­му. Там су­ще­ству­ет всего 5 ком­би­на­ций.

Пра­виль­ный ответ: 5+5+1=11 ком­би­на­ций.

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

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

1) Из по­след­не­го урав­не­ния сле­ду­ет, что гло­баль­но мы имеем x3=1, y3=1.

2) Ло­ги­че­ское И ис­тин­но, толь­ко тогда, когда ис­ти­ны все утвер­жде­ния, а им­пли­ка­ция ложна толь­ко в слу­чае, если из ис­тин­но­го сле­ду­ет лож­ное.

3) Урав­не­ние (1) опи­сы­ва­ет ряд пе­ре­мен­ных . Так как из пе­ре­мен­ной с более низ­ким но­ме­ром все­гда сле­ду­ет пе­ре­мен­ная с более вы­со­ким, если любую пе­ре­мен­ную из этого ряда при­рав­нять 1, то все сле­ду­ю­щие долж­ны также быть равны 1. Для урав­не­ния (2) су­ще­ству­ет то же самое пра­ви­ло, толь­ко на­о­бо­рот: из пе­ре­мен­ной с более вы­со­ким но­ме­ром все­гда сле­ду­ет пе­ре­мен­ная с более низ­ким. Иначе го­во­ря, если за­пи­сать пе­ре­мен­ные x в по­ряд­ке воз­рас­та­ния их но­ме­ров, спра­ва будут еди­ни­цы, а слева — нули, в y — на­про­тив, слева еди­ни­цы, спра­ва — нули.

4) Рас­смот­рим ва­ри­ант x3=1, y3=1. Тогда все сле­ду­ю­щие: x4, x5, y2, y1 тоже равны 1. Оста­ют­ся пе­ре­мен­ные x1, x2, y4, y5. Так как x2 сле­ду­ет из x1, для них мы имеем 3 ва­ри­ан­та, ана­ло­гич­но для y4 и y5. 3 3=9.

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

Конъ­юнк­ция ис­ти­на тогда и толь­ко тогда, когда каж­дое вы­ска­зы­ва­ние ис­тин­но.

Для пер­во­го вы­ра­же­ния это озна­ча­ет, что, если х1 равен 1, то х2, х3 и х4 также равны 1, т. е. для х1. х4 ре­ше­ния су­ще­ству­ют толь­ко в виде «1111», «0111», «0011», «0001» и «0000».

При­ме­нив пре­об­ра­зо­ва­ние им­пли­ка­ции ко вто­ро­му вы­ра­же­нию, уви­дим, что оно ана­ло­гич­но пер­во­му.

В тре­тьем вы­ра­же­нии из «y» сле­ду­ет со­от­вет­ству­ю­щее ему «x», это озна­ча­ет, что если y = 1, то и x = 1.

Сле­до­ва­тель­но, пер­во­му на­бо­ру для x «1111» со­от­вет­ству­ет 5 на­бо­ров y. Вто­ро­му — 4, тре­тье­му — 3, и. т. д.

Сле­до­ва­тель­но, ответ: 5 + 4 + 3 + 2 + 1 = 15.

За­да­ние 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, x2, x3, x4, x5, y1, y2, y3, y4, y5, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

1) Из по­след­не­го урав­не­ния сле­ду­ет, что гло­баль­но мы имеем три ва­ри­ан­та — x1=1, y1=1; x1=0, y1=1; x1=0, y1=0.

2) Ло­ги­че­ское И ис­тин­но, толь­ко тогда, когда ис­ти­ны все утвер­жде­ния, а им­пли­ка­ция ложна толь­ко в слу­чае, если из ис­тин­но­го сле­ду­ет лож­ное.

3) Урав­не­ние (1) опи­сы­ва­ет ряд пе­ре­мен­ных . Так как из пе­ре­мен­ной с более низ­ким но­ме­ром все­гда сле­ду­ет пе­ре­мен­ная с более вы­со­ким, если любую пе­ре­мен­ную из этого ряда при­рав­нять 1, то все сле­ду­ю­щие долж­ны также быть равны 1. Для урав­не­ния (2) су­ще­ству­ет то же самое пра­ви­ло. Иначе го­во­ря, если за­пи­сать пе­ре­мен­ные x (или y) в по­ряд­ке воз­рас­та­ния их но­ме­ров, спра­ва будут еди­ни­цы, а слева — нули.

4) Рас­смот­рим ва­ри­ант x1=1, y1=1. Так как пер­вые числа каж­до­го ряда равны 1, то все сле­ду­ю­щие тоже равны 1. Су­ще­ству­ет толь­ко одна ком­би­на­ция для этого ва­ри­ан­та.

5) Рас­смот­рим ва­ри­ант x1=0, y1=1. Для y-ряда все пе­ре­мен­ные равны 1, для x же су­ще­ству­ет 5 ком­би­на­ций, так как в ряде x может быть от 1 до 5 нолей вклю­чи­тель­но.

6) По­след­ний ва­ри­ант рас­смот­рим ана­ло­гич­но преды­ду­ще­му. Там су­ще­ству­ет всего 25 ком­би­на­ций.

Пра­виль­ный ответ: 25+5+1=31 ком­би­на­ция.

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

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

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

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

1) Из по­след­не­го урав­не­ния сле­ду­ет, что гло­баль­но мы имеем три ва­ри­ан­та — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.

2) Ло­ги­че­ское И ис­тин­но, толь­ко тогда, когда ис­ти­ны все утвер­жде­ния, а им­пли­ка­ция ложна толь­ко в слу­чае, если из ис­тин­но­го сле­ду­ет лож­ное.

3) Урав­не­ние (1) опи­сы­ва­ет ряд пе­ре­мен­ных . Так как из пе­ре­мен­ной с более низ­ким но­ме­ром все­гда сле­ду­ет пе­ре­мен­ная с более вы­со­ким, если любую пе­ре­мен­ную из этого ряда при­рав­нять 1, то все сле­ду­ю­щие долж­ны также быть равны 1. Для урав­не­ния (2) су­ще­ству­ет то же самое пра­ви­ло. Иначе го­во­ря, если за­пи­сать пе­ре­мен­ные x (или y) в по­ряд­ке воз­рас­та­ния их но­ме­ров, спра­ва будут нули, а слева — еди­ни­цы.

4) Рас­смот­рим ва­ри­ант x1=1, y1=1. Так как пер­вые числа каж­до­го ряда равны 1, то все сле­ду­ю­щие тоже равны 1. Су­ще­ству­ет толь­ко одна ком­би­на­ция для этого ва­ри­ан­та.

5) Рас­смот­рим ва­ри­ант x1=0, y1=1. Для y-ряда все пе­ре­мен­ные равны 1, для x же су­ще­ству­ет 6 ком­би­на­ций, так как в ряде x может быть от 1 до 6 нолей вклю­чи­тель­но.

6) По­след­ний ва­ри­ант рас­смот­рим ана­ло­гич­но преды­ду­ще­му. Там су­ще­ству­ет всего 6 ком­би­на­ций.

Пра­виль­ный ответ: 6+6+1=13 ком­би­на­ций.

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

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

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

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

1) Из по­след­не­го урав­не­ния сле­ду­ет, что гло­баль­но мы имеем три ва­ри­ан­та — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.

2) Ло­ги­че­ское И ис­тин­но, толь­ко тогда, когда ис­ти­ны все утвер­жде­ния, а им­пли­ка­ция ложна толь­ко в слу­чае, если из ис­тин­но­го сле­ду­ет лож­ное.

3) Урав­не­ние (1) опи­сы­ва­ет ряд пе­ре­мен­ных . Так как из пе­ре­мен­ной с более низ­ким но­ме­ром все­гда сле­ду­ет пе­ре­мен­ная с более вы­со­ким, если любую пе­ре­мен­ную из этого ряда при­рав­нять 1, то все сле­ду­ю­щие долж­ны также быть равны 1. Для урав­не­ния (2) су­ще­ству­ет то же самое пра­ви­ло. Иначе го­во­ря, если за­пи­сать пе­ре­мен­ные x (или y) в по­ряд­ке воз­рас­та­ния их но­ме­ров, спра­ва будут нули, а слева — еди­ни­цы.

4) Рас­смот­рим ва­ри­ант x1=1, y1=1. Так как пер­вые числа каж­до­го ряда равны 1, то все сле­ду­ю­щие тоже равны 1. Су­ще­ству­ет толь­ко одна ком­би­на­ция для этого ва­ри­ан­та.

5) Рас­смот­рим ва­ри­ант x1=0, y1=1. Для y-ряда все пе­ре­мен­ные равны 1, для x же су­ще­ству­ет 5 ком­би­на­ций, так как в ряде x может быть от 1 до 5 нолей вклю­чи­тель­но.

6) По­след­ний ва­ри­ант рас­смот­рим ана­ло­гич­но преды­ду­ще­му. Там су­ще­ству­ет всего 5 ком­би­на­ций.

Пра­виль­ный ответ: 5+5+1=11 ком­би­на­ций.

За­да­ние 7. Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных 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, x2, x3, x4, x5, y1, y2, y3, y4, y5, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

1) Из по­след­не­го урав­не­ния сле­ду­ет, что гло­баль­но мы имеем три ва­ри­ан­та: x5=1, y5=1; x5=0, y5=0; x5=0, y5=1.

2) Ло­ги­че­ское И ис­тин­но, толь­ко тогда, когда ис­ти­ны все утвер­жде­ния, а им­пли­ка­ция ложна толь­ко в слу­чае, если из ис­тин­но­го сле­ду­ет лож­ное.

3) Урав­не­ние (1) опи­сы­ва­ет ряд пе­ре­мен­ных . Так как из пе­ре­мен­ной с более низ­ким но­ме­ром все­гда сле­ду­ет пе­ре­мен­ная с более вы­со­ким, если любую пе­ре­мен­ную из этого ряда при­рав­нять 1, то все сле­ду­ю­щие долж­ны также быть равны 1. Для урав­не­ния (2) су­ще­ству­ет то же самое пра­ви­ло. Иначе го­во­ря, если за­пи­сать пе­ре­мен­ные x в по­ряд­ке воз­рас­та­ния их но­ме­ров, спра­ва будут нули, а слева — еди­ни­цы, в y — так же.

4) Рас­смот­рим ва­ри­ант x5=1, y5=1. Тогда осталь­ные пе­ре­мен­ные могут при­ни­мать любые зна­че­ния: всего таких ком­би­на­ций 25.

5) Рас­смот­рим ва­ри­ант х5=0, у5=0. Тогда все пе­ре­мен­ные равны 0, сле­до­ва­тель­но, 1 ком­би­на­ция.

6) Рас­смот­рим ва­ри­ант х5=0, у5=1. Тогда все пе­ре­мен­ные х равны 0, а пе­ре­мен­ные у могут при­ни­мать любые зна­че­ния. Всего таких ком­би­на­ций 5.

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

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

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

Най­дем ко­ли­че­ство ре­ше­ний пер­во­го урав­не­ния. Каж­дая из пе­ре­мен­ных x1, . , x5 может при­ни­мать толь­ко два зна­че­ния. Им­пли­ка­ция ложна толь­ко тогда, когда из ис­ти­ны сле­ду­ет ложь. Если за­пи­сать зна­че­ния пе­ре­мен­ных под­ряд, то можно уви­деть, что для того, чтобы ра­вен­ство вы­пол­ня­лось, не­об­хо­ди­мо, чтобы после «1» ни­ко­гда не стоял «0». Сле­до­ва­тель­но, по­лу­ча­ем такие ре­ше­ния: (x1,x2,x3,x4,x5) = 00000, 00001, 00011, 00111, 01111, 11111.

Во вто­ром урав­не­нии не­об­хо­ди­мо, чтобы после «0» ни­ко­гда не сто­я­ла «1». Сле­до­ва­тель­но, по­лу­ча­ем такие ре­ше­ния: (y1,y2,y3,y4,y5) = 00000, 10000, 11000, 11100, 11110, 11111. Таким об­ра­зом, си­сте­ма из двух урав­не­ний имеет 6·6 = 36 ре­ше­ний: для каж­до­го на­бо­ра пе­ре­мен­ных y су­ще­ству­ет 6 на­бо­ров пе­ре­мен­ных x.

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

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

Метод подсчёта количества решений

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Линейные алгебраические уравнения — одни из самых простых уравнений, которые мы можем решить. Если в уравнении только одна переменная, решение тривиально, в то время как для системы линейных уравнений существует множество способов найти уникальные решения.

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

Общая форма интересующего нас уравнения:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

где n и m — положительные целые числа.

Наша задача — найти число решений этого уравнения, предполагая, что xᵢ являются целыми числами. Это предположение значительно снижает число решений заданного уравнения.

Видео:Подготовка к ЕГЭ по информатике: как найти число решений логического уравнения с импликацией?Скачать

Подготовка к ЕГЭ по информатике: как найти число решений логического уравнения с импликацией?

Нам нужен метод

Давайте начнём с частного случая общего уравнения:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Нетрудно найти все решения этого уравнения методом простого счёта. Решения заданы парами (x₁, x₂):

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Мы видим, что уравнение имеет шесть решений. Также нетрудно предположить, что, если мы заменим правую часть определённым положительным целым числом m, решения будут выглядеть так:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

и мы сможем подсчитать число решений — m+1.

Это было просто, верно?

Теперь возьмём немного более сложный вариант с тремя переменными, скажем:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

С несколько большими усилиями, чем в предыдущем примере, находим решения в виде наборов из трёх чисел (x₁, x₂, x₃):

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Число решений в этом случае равно 10.

Легко представить, что метод прямого счёта может стать очень утомительным для уравнения с большим количеством переменных. Он также становится утомительным, если целое число в правой части уравнения становится больше — например, если в правой части у нас будет 8, а не 3, решений будет уже 45. Разумеется, не хотелось бы искать все эти решения методом прямого счёта.

Значит, нужен эффективный метод.

Видео:Задание 23 Система не однотипных логических уравнений_ЕГЭ информатикаСкачать

Задание 23 Система не однотипных логических уравнений_ЕГЭ информатика

Разрабатываем метод

Существует ещё один способ, которым можно решить предыдущие два уравнения. Давайте снова начнём с этого уравнения:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Одним из решений было (5, 0). Давайте преобразуем его в:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Мы разложили решение на нули и единицы, соответствующие каждому числу. Ненулевую часть (в данном случае 5) мы разложили на соответствующее число единиц, а ноль преобразовали в ноль. Таким же образом мы можем разложить и другое решение:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

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

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Записав решения таким образом, видим закономерность. Кажется, все решения — это просто перестановки нулей и единиц. Вопрос о том, сколько существует решений, становится эквивалентным вопросу как много таких перестановок нулей и единиц может быть сделано, начиная с любой из конфигураций.

В данном случае у нас есть 6 местоположений в разложенной конфигурации для размещения нулей и единиц. Мы можем выбрать простейшее решение в качестве начальной конфигурации:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Теперь всё, что нам нужно найти, это общее число способов, которыми можно заполнить шесть местоположений пятью единицами и одним нулём.

Подобные задачи подсчёта мы можем решить различными способами, но наиболее эффективным будет способ, разработанный в такой области математики как комбинаторика, которая даёт нам формулу для числа способов перестановки r объектов в n местоположений:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

где n! (читается как “n факториал”) определяется как произведение всех целых чисел от 1 до n, т.е. n! = 1 × 2 × 3 × ⋅ ⋅ ⋅ × n. Мы также определяем 0! = 1.

Эта формула обычно записывается в компактной форме как:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Теперь, возвращаясь к задаче, мы можем использовать эту формулу для нахождения числа способов перестановки пяти единиц в шести местоположениях:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Это то же самое число, что мы получили методом прямого счёта!

Выглядит многообещающе, поэтому давайте проверим, сможем ли мы найти таким способом число решений второго линейного уравнения:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Некоторые решения можно записать в разложенном виде:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

В этот раз нам нужно заполнить тремя единицами и двумя нулями пять местоположений. Используя формулу мы можем найти число способов расположения чисел:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

И опять то же число, что мы получили методом прямого счёта. Мы можем также найти число решений для нерешённого случая, где в правой части уравнения 8 вместо 3. Одним из решений будет:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

а нам нужно найти число способов разместить 8 единиц в 10 местоположениях, и это будет:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

как и утверждалось выше.

Если мы уверены в том, что этот метод работает для всех случаев, нам нужна общая формула. Напомним, что общее уравнение имеет вид:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Простейшее решение этого уравнения:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

Поскольку существует n переменных, количество нулей в этом решении равно n-1. Таким образом, разложение выглядит так:

Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1

В разложенной конфигурации видим m и n-1 нулей (как утверждалось выше).

Следовательно, общее число местоположений, которые нужно заполнить, равно (m+n-1). Единственное, что остаётся — найти число способов, которыми можно заполнить m+n-1 местоположений m единиц, что определяется по формуле:

🎦 Видео

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

Сколько решений имеет уравнение?

ПОДГОТОВКА К ЕГЭ. ИНФОРМАТИКА. УРОК 2. РЕШЕНИЕ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ ОТОБРАЖЕНИЯСкачать

ПОДГОТОВКА К ЕГЭ. ИНФОРМАТИКА. УРОК 2. РЕШЕНИЕ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ ОТОБРАЖЕНИЯ

Урок 27. Логические уравнения. ИКТ 10 класс по ПоляковуСкачать

Урок 27. Логические уравнения. ИКТ 10 класс по Полякову

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

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

Системы логических уравнений и логические уравнения - ЕГЭ по Информатике - Задание №23Скачать

Системы логических уравнений и логические уравнения - ЕГЭ по Информатике - Задание №23

Системы логических уравнений - 1 тип (метод отображения)Скачать

Системы логических уравнений - 1 тип (метод отображения)

Решение систем логических уравнений. Часть 1. 09042020Скачать

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

Cистемы уравнений. Разбор задания 6 и 21 из ОГЭ. | МатематикаСкачать

Cистемы уравнений. Разбор задания 6 и 21 из ОГЭ.  | Математика

Системы логических уравнений содержащие НЕОДНОТИПНЫЕ УРАВНЕНИЯ [Алгебра логики] #8Скачать

Системы логических уравнений содержащие НЕОДНОТИПНЫЕ УРАВНЕНИЯ [Алгебра логики] #8

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

Сборка ПК под ваши задачи, оценка ваших сборок, ответы на вопросы. Подбор комплектующих для ПК.

Построение таблиц истинностиСкачать

Построение таблиц истинности

Алгебраическое определение количества решений системы линейных уравнений | Алгебра IСкачать

Алгебраическое определение количества решений системы линейных уравнений |  Алгебра I

ЕГЭ информатика. Пример решения заданий. Таблицы истинности и логические схемыСкачать

ЕГЭ информатика. Пример решения заданий.  Таблицы истинности и логические схемы

Интенсив - подготовка к ЕГЭ. Информатика. Решение логических уравненийСкачать

Интенсив - подготовка к ЕГЭ. Информатика. Решение логических уравнений

Все задания №8 (раньше №7) с реального ЕГЭ по профильной математике! Производная на ЕГЭ.Скачать

Все задания №8 (раньше №7) с реального ЕГЭ по профильной математике! Производная на ЕГЭ.
Поделиться или сохранить к себе: