3. Построить логическую схему для заданной таблицы истинности (таблица задана для трех переменных).

Построить логическую схему для заданной таблицы истинности:

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

Анализируя таблицу истинности, замечаем, что количество нулей и единиц в результате (значения переменной F) одинаково, поэтому выбор конкретного способа построения может быть любым. Выберем дизъюнктивный многочлен.

Получаем (для сокращения записи знак конъюнкции пропущен, отрицание переменной обозначено горизонтальной черточкой сверху):

При преобразовании выражения использовались законы логики (см. билет № 8).

Построим соответствующую логическую схему:

 Варианты заданий

Построить логическую схему для заданной таблицы истинности:

Билет № 3

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

Информация является важнейшим понятием и основным объектом изучения в информатике (см. билет № 1). Неудивительно поэтому, что проблема измерения информации имеет фундаментальное значение1.

На бытовом уровне информация является синонимом слов сведения, знания, данные, новость, известие, сообщение и аналогичным им. При этом неявно подразумевается, что тот, кто получает информацию, выделяет из нее некоторый смысл (содержание).

Смысловая составляющая информации во многом индивидуальна. Большинство россиян не способны извлечь никакой информации из текста на японском языке. Многие взрослые, взяв учебник для начальных классов, также не сочтут его заслуживающей своего внимания информацией, хотя, в отличие от предыдущего случая, понимают (слишком хорошо!), что там написано. Химика редко интересуют сообщения об археологических открытиях, а большая часть литераторов активно игнорирует любые сведения из области математики. Наконец, многие образованные люди не верят в статьи, опубликованные в бульварной прессе, заранее считая их недостоверными. Таким образом, информативность любых сведений и сообщений существенно зависит от воспринимающего их человека, его предыдущих знаний, опыта, интересов, отношения к источнику информации и множества других факторов личного характера, т.е. по своей сути является субъективной.

Дополнительное пояснение. Во всех наиболее распространенных школьных учебниках подобными описаниями и несколькими несвязанными примерами неинформативных сообщений дело и ограничивается. Но на самом деле вопрос о соотношении между информативностью и предыдущими знаниями человека имеет самостоятельное значение. Например, в недавно вышедших учебниках [1, 2] приведен следующий весьма наглядный и любопытный качественный график зависимости воспринимаемой пользователем информации I от предварительно известных ему сведений S (для обозначения совокупности сведений, которыми располагает пользователь или любая другая система, принят специальный научный термин — тезаурус).

Из графика отчетливо видно, что воспринимаемая из фиксированного сообщения информация зависит от познаний пользователя неоднозначно. При малых S (тезаурус мал, пользователь неквалифицирован) воспринимаемая информация близка к нулю — человек ее просто не понимает. По мере роста S ситуация улучшается, и количество воспринятой из данного сообщения информации растет (невежественный пользователь быстро прогрессирует). Но лишь до определенного предела, а затем величина I начинает постепенно уменьшаться. Здесь вступает в действие другой фактор: при больших S (большой объем знаний, мы имеем дело с образованным пользователем) многие сообщения не могут добавить к тезаурусу ничего нового и их информативность вновь устремляется к нулю. Выражаясь житейским языком, когда человек много знает, его ничем не удивишь.

Таким образом, график количества воспринимаемой информации имеет максимум (на рисунке он обозначен Sопт), соответствующий вполне определенному соотношению между содержащейся в сообщении информацией и уже имеющимися у субъекта знаниями2.

Если задуматься над сутью рассмотренного графика, то можно получить целый ряд практически интересных выводов. Например, что передаваемая информация должна определенным образом соотноситься с уже имеющимися в ее приемнике сведениями, иначе данные могут оказаться бесполезными и только напрасно будут загружать каналы связи и узлы обработки. Между прочим, учащиеся после этих рассуждений должны проникнуться еще большим уважением к учителю, который постоянно вынужден “подстраивать” степень информативности своего рассказа, интуитивно оценивая разнообразные объемы тезаурусов сидящих в классе учеников, причем с учетом возможности их интеллектуального роста по мере освоения материала.

Несколько иная трактовка измерения смысла сообщений по способу А.Н. Колмогорова весьма просто и интересно обсуждается в школьном учебнике [3].

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

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

Действительно, в целом ряде важных практических задач смысл информации и даже ее вид (числа, текст, видео) несущественен. Например, при передаче информации по каналам связи, при распределении объемов ОЗУ для хранения различных типов данных, при записи информации на внешние носители, при архивации и многих других компьютерных применениях содержание передаваемой и обрабатываемой информации особого значения не имеет.

Нечто похожее наблюдается и в “некомпьютерных” областях. Так, книги хранятся и ищутся не по содержанию, а по другим, часто весьма формальным признакам; в библиотеке нашего университета, в частности, книги расставлены на стеллажах в том числе с учетом размера обложки, который явно слабо связан с содержанием книги. Аналогично почтальону должно быть все равно, что именно находится внутри доставляемого им конверта, а диктор телевидения не может пропускать отдельные новости или их фрагменты в соответствии со своими личными убеждениями.

Примечание. Подобно тому, как в физике при полном игнорировании трения можно установить фундаментальные законы движения, можно надеяться, что изучение “информации без смысла” позволит понять наиболее важные закономерности протекания информационных процессов.

На этих и многочисленных подобных примерах мы видим, что информация перестает зависеть от человека при абстрагировании от ее смысла. Следовательно, появляется возможность объективного измерения количества информации. При этом используется два подхода: вероятностный или алфавитный.