Решение задачи 23 (2015 г.)
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

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

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


Решение задачи 23 на примере официальной демо-версии КИМ ЕГЭ 2015 г.


Payeer

Решение задачи 23 на примере официальной демо-версии КИМ ЕГЭ 2015 г.

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

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


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

Заметим, что во всех уравнениях с выражениями, показанными в скобках, выполняется конъюнкция (последнее уравнение содержит одно такое выражение, поэтому с ним конъюнкцию по понятным причинам записывать не надо). Это указывает на возможность представления каждого отдельно взятого уравнения в виде системы соответствующих выражений (ведь конъюнкция и система — одно и то же, см. Теоретическое введение). Если так, то исходное условие есть система систем, в которой отдельные их выражения можно перегруппировать:

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

(1)
(1)

Работать с полученными уравнениями будем именно в таком порядке, потому что:

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

совместное решение первых двух уравнений даёт общее представление о конечном числе решений;

третье уравнение тоже определяет правило отбора решений (у него, как и у первого, слишком много собственных решений), но в нём содержатся не упомянутые в первых двух уравнениях переменные y1, y2, … y8, так что этим правилом наиболее удобно воспользоваться в самом конце, — для того, чтобы записать окончательный ответ.

Подробно о назначении и применении правил отбора решений см. Теоретическое введение.

Представим первое уравнение системы (1) в виде системы совокупностей (2):

(2)
(2)

Составим обратное ему уравнение, которое представляет собой совокупность семи систем:

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

(3)
(3)

Применяя правило (3) позже, мы будем отбрасывать не интересующие нас решения второго уравнения системы (1) для определения совместных решений первых двух её уравнений.

Каждое выражение конъюнкта второго уравнения системы (1) можно записать в виде совокупности (см. о записи импликации в виде совокупности в Теоретическом введении). В ней конъюнкция, равная нулю, превращается во вложенную совокупность, а знаки вложенных совокупностей в этом случае, как известно, можно опустить:

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

Затем последовательно выполним такие переходы (преобразования) с применением Правила (9) — см. Теоретическое введение:

    • Ещё раз акцентируем внимание на том, что после проведённых преобразований решения второго уравнения системы (1) будут именно непересекающимися. Это сделано, чтобы при формировании окончательного ответа можно было просто сложить число частных решений вложенных в совокупность систем.

Вот теперь совокупность содержит только непересекающиеся частные решения, что и требовалось получить. Каждая импликация второго уравнения системы (1) записывается только что полученной совокупностью. А всё целиком второе уравнение системы (1) выглядит как система (4); для удобства последующих преобразований в ней соседние пары совокупностей уже пересечены системами:

(4)
(4)

Каждая из трёх вложенных систем системы (4) пересекает две совокупности с учётом правила (3). Механизм получения совокупности решений из каждой такой вложенной системы приведён ниже:

Тогда совместные решения первых двух уравнений системы (1) описываются системой (5):

(5)
(5)

Пересечём первые две вложенные совокупности системы (5):

Теперь, наконец, пересечём полученную совокупность с последней вложенной совокупностью системы (5):

    • Выведенная совокупность содержит восемь систем. Каждая из них, кстати, имеет по одному частному решению для своих переменных. Подробнее о том, как можно записывать систему логических переменных в одну строку, см. Теоретическое введение.

Обратим пристальное внимание на первую и пятую системы полученной только что совокупности.

В первой отсутствует переменная x8 при том, что x7 = 0. Правило (3) запрещает, чтобы x8 = 0. Следовательно, потребуется дописать, что переменная x8 может быть равна только единице.

В пятой системе отсутствуют переменные x7 и x8 при том, что x6 = 0. Следовательно, x7 в ней должна быть равна единице, а x8 может иметь любое значение, поэтому её всё-таки допускается не указывать. Итак, совместные решения первых двух уравнений системы (1) после упрощения, заключающегося в очередном применении правила (3), описываются совокупностью (6):

(6)
(6)

Другими словами, система (5) и совокупность (6) — одно и то же!

Последнее, третье, уравнение системы (1), есть система, пересекающая восемь совокупностей, — см. (7):

(7)
(7)

В начале настоящей статьи было упомянуто о том, что третье уравнение системы (1) есть правило отбора решений. Система (7) имеет очень много частных решений, которых всех вместе невозможно описать проще, чем системой (7), поэтому поступим с ней так, как с первым уравнением системы (1) — проанализируем обратное ему. Вот как выглядит совокупность (8), обратная системе (7):

(8)
(8)

Совокупность (8) как уравнение, обратное уравнению системы (1), и как правило говорит о следующем: во всех решениях системы (1) не может быть таких, в которых встречается хотя бы одна пара переменных x и y с равными индексами при том, что xi = 1 и одновременно yi = 0. В процессе отсеивания решений от результата, описываемого совокупностью (6), применим это правило.

Построим таблицу, содержащую конкретные решения совокупности (6):

Номер системы в совокупностиx1x2x3x4x5x6x7x8
101010101
201010111
301011111
401111111
51010101 
610101111
710111111
811111111

Допишем к ней справа столбцы возможных значений переменных y1 … y8:

Номер системы в совокупностиx1x2x3x4x5x6x7x8
101010101
201010111
301011111
401111111
51010101 
610101111
710111111
811111111
y1y2y3y4y5y6y7y8
        
        
        
        
        
        
        
        

Заполним присоединённые столбцы в соответствии с правилом (8) таким способом: если переменная xi = 1, то yi = 1 (иначе быть не может). Если же xi = 0, то в соответствующей строке столбца yi указывать ничего не будем (ведь тогда yi может быть и истинной, и ложной). Вот что получилось:

Номер системы в совокупностиx1x2x3x4x5x6x7x8
101010101
201010111
301011111
401111111
51010101 
610101111
710111111
811111111
y1y2y3y4y5y6y7y8
 1 1 1 1
 1 1 111
 1 11111
 1111111
1 1 1 1 
1 1 1111
1 111111
11111111

Каждая строка в полученной таблице — система. Вследствие действий, которые были выполнены для получения системы (4), никакие решения, содержащиеся в строках таблицы, не пересекаются. Значит, достаточно просто суммировать число решений от каждой такой системы. Посчитаем решения для систем таблицы, для этого добавим к ней столбец "Число решений":

Номер системы в совокупностиx1x2x3x4x5x6x7x8
101010101
201010111
301011111
401111111
51010101 
610101111
710111111
811111111
y1y2y3y4y5y6y7y8
 1 1 1 1
 1 1 111
 1 11111
 1111111
1 1 1 1 
1 1 1111
1 111111
11111111
Число решений
 
 
 
 
 
 
 
 

В первой строке имеется 4 незаполненные клетки (т. е. 4 логические переменные могут иметь одно любое из двух возможных значений), следовательно, первая система таблицы имеет 24 = 16 общих решений.

Вторая строка имеет 3 незаполненные клетки, число решений второй системы таблицы — 23 = 8.

Заполним по аналогии данные для ещё двух строк:

Номер системы в совокупностиx1x2x3x4x5x6x7x8
101010101
201010111
301011111
401111111
51010101 
610101111
710111111
811111111
y1y2y3y4y5y6y7y8
 1 1 1 1
 1 1 111
 1 11111
 1111111
1 1 1 1 
1 1 1111
1 111111
11111111
Число решений
16
8
4
2
 
 
 
 

С пятой системой (строкой) сложнее. Если x8 = 0, то решений 16, а если x8 = 1, то 8. Итого — 24:

Номер системы в совокупностиx1x2x3x4x5x6x7x8
101010101
201010111
301011111
401111111
51010101 
610101111
710111111
811111111
y1y2y3y4y5y6y7y8
 1 1 1 1
 1 1 111
 1 11111
 1111111
1 1 1 1 
1 1 1111
1 111111
11111111
Число решений
16
8
4
2
16 + 8 = 24
 
 
 

Наконец, заполним столбец "Число решений" до конца:

Номер системы в совокупностиx1x2x3x4x5x6x7x8
101010101
201010111
301011111
401111111
51010101 
610101111
710111111
811111111
y1y2y3y4y5y6y7y8
 1 1 1 1
 1 1 111
 1 11111
 1111111
1 1 1 1 
1 1 1111
1 111111
11111111
Число решений
16
8
4
2
24
4
2
1

Если теперь просуммировать все значения столбца "Число решений", то получим ответ на вопрос задачи: 61 решение имеет система (1), а, значит, и исходная система логических уравнений.

Ответ. 61.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика