Индивидуальная работа по информатике (стр. 2 из 2)

Важную роль в Алгебра логики и её приложениях играет т. н. сокращённая днф. Днф называется сокращённой, если выполнены следующие условия: 1) в ней нет таких пар слагаемых Ái и Áj, что всякий сомножитель из Ái имеется и в ÁI; 2) для всяких двух таких слагаемых Ái и Ái ,из которых один содержит сомножителем некоторое переменное, а другой — отрицание этого переменного (при условии, что в данной паре слагаемых нет другого переменного, для которого это же имеет место), имеется (в этой же днф) слагаемое Ái, равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая днф при помощи равенства (1) — (7) может быть приведена к равной ей сокращённой днф.

Кроме днф, употребляются также конъюнктивные нормальные формы (кнф). Так называют выражения, которые можно получить из днф путём замены в них знаков Ú на &, а & на Ú.

Следствия. Гипотезы. Минимизация.

Совершенные и сокращённые днф и кнф используются для решения задачи обзора всех гипотез и всех следствий заданной формулы. Под гипотезой формулы Á понимается такая формула Â, что (®Á) = 1, а под следствием формулы Á — такая формула Â, что (Á®Â) = 1. Гипотеза формулы Á называется простой, если она есть конъюнкция переменных или их отрицаний и после отбрасывания любого из её сомножителей перестаёт быть гипотезой формулы Á. Аналогично, следствие формулы называется простым, если оно есть дизъюнкция переменных или их отрицаний и после отбрасывания любого из её слагаемых перестаёт быть следствием формулы Á. Решение задачи обзора гипотез и следствий основано на указании алгоритма, строящего все простые гипотезы и следствия для заданной формулы и в получении из них при помощи законов (2) — (7) всех остальных гипотез и следствий.

Сокращённая днф имеет важные приложения. Следует отметить прежде всего задачу минимизации функций Алгебра логики, являющуюся частью т. н. задачи синтеза управляющих систем. Минимизация функций Алгебра логики состоит в построении такой днф для заданной функции Алгебра логики, которая реализует эту функцию и имеет наименьшее суммарное число сомножителей в своих слагаемых, т. е. имеет минимальную «сложность». Такие днф называются минимальными. Каждая минимальная днф для заданной отличной от константы функции Алгебра логики получается из сокращённой днф любой формулы, реализующей эту функцию, выбрасыванием некоторых слагаемых Ái, из этой сокращённой днф.Существует алгоритм, который по произвольной конечной системе функций Алгебра логики устанавливает её полноту или неполноту. Рассматриваются и такие языки, в основе которых лежат системы операций, не являющихся функционально полными, и таких языков бесконечно много. Среди них имеется бесконечно много попарно неравносильных языков (в смысле отсутствия переводимости при помощи тождественных преобразований с одного языка на другой). Однако для всякого языка, построенного на основе тех или иных операций Алгебра логики, существует такая конечная система равенств этого языка, что всякое равенство этого языка выводимо при помощи тождественных преобразований из равенств этой системы. Такая система равенств называется дедуктивно полной системой равенств (п. с. р.) языка.

Решение задач ЕГЭ.

Пример решения задачи B7 из ЕГЭ по информатике.

Скорость передачи данных через ADSL-соединение составляет 256 000 бит / c. Через данное соединение передают файл размером 500 Кбайт. Определите время передачи файла в секундах.

- СКОРОСТЬ: 256 000 бит / с = 28 *103 бит / с = 28 * 103 / 23 байт / с = 25 * 103 байт / с = 1000 * 25 байт / с

- РАЗМЕР: 500 Кбайт = 5 * 102 Кбайт = 5 * 102 * 210 байт = 500 * 210 байт

- применяем формулу: время = размер / скорость = (500 * 210 байт) / (1000 * 25 байт / с) = 25 / 2 с = 16 с.

Ответ: 16.

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

J /\ ¬K /\ L /\ ¬M /\ (N \/ ¬N) = 0

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

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

Решение: Обратите внимание на то, что выражение (N \/ ¬N) - истинно при любом N. Из максимально возможного числа наборов логических переменных исключите те, при которых уравнение не имеет смысла.

Ответ: 30.

Задача части А:

1. Дано:

V=1 Мб

M * N= 800 * 600

2 стр.

Найти к-?

Решение:

V=n* M* N

n

= = ≈8,7

k=

, k= , k=256

Ответ: 256

Заключение

Информатика – чрезвычайно нужная и интересная наука. Сфера ее практического применения очень обширна: сегодня тяжело представить отрасль деятельности человека, в которой не применялись бы компьютеры. Знание информатики – один из залогов профессионального успеха.

Мне бы хотелось, что бы на занятиях информатики мы больше решали задач, научились создавать различные веб - сайты, программы. Информатику, я считаю, очень интересной и увлекательной наукой.