Учебно-методический комплекс уфа 2009 удк 007 ббк 32. 81

Вид материала

Учебно-методический комплекс

Содержание Принцип Кирхгоффа Количество информации Логической (булевой) функцией Задача упрощения логического выражения Задача доказательства равенства двух логических выражений (функций) Тема 4. Теоретические основы правовой информатики Принцип Кирхгоффа Количество информации Логической (булевой) функцией Задача упрощения логического выражения Задача доказательства равенства двух логических выражений (функций)

Подобный материал:

• Учебно-методический комплекс уфа 2009 удк 004 ббк, 598.63kb.
• Учебно-методический комплекс Москва, 2009 удк 338(47 + 57)(091) ббк 63., 11843.89kb.
• Учебно-методический комплекс удк ббк а рекомендовано к изданию Учебно-методическим, 1479.59kb.
• Учебно-методический комплекс удк ббк а рекомендовано к изданию учебно-методическим, 1848.18kb.
• Учебно-методический комплекс удк ббк п рекомендовано к изданию Учебно-методическим, 1762.72kb.
• Учебно-методический комплекс уфа 2008 удк 330 ббк 65., 1042.22kb.
• Учебно-методический комплекс удк ббк Х рекомендовано к изданию методическим советом, 1869.11kb.
• Учебно-методический комплекс удк ббк к рекомендовано к изданию методическим советом, 2586.47kb.
• Учебно-методический комплекс автор-составитель: Н. Н. Спиридонов удк ббк м рекомендовано, 1327.83kb.
• Учебно-методический комплекс удк ббк м печатается по решению Учебно-методического совета, 2773.77kb.

Тема 3. Введение в правовую информатику

В лекции рассматриваются основы теоретической правовой информатики, в частности, базовые понятия "код", "шифр", "количество информации", меры информации, логические высказывания и инфологические задачи, понятия алгоритма и данных для алгоритмов.

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

Сообщения измеряются в байтах, килобайтах, мегабайтах, гигабайтах, терабайтах, петабайтах и эксабайтах, реализуются в ЭВМ в битах.

Основные соотношения между единицами измерения сообщений: 1 бит (binary digit – двоичная единица) = 0 или 1; 1 байт = 8 битов; 1 килобайт (1К) = 213 бит; 1 мегабайт (1М) = 223 бит; 1 гигабайт (1Г) = 233 бит; 1 терабайт (1Т) = 243 бит; 1 петабайт (1П) = 253 бит; 1 эксабайт (1Э) = 263 бит.

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

Кодирование – процесс преобразования букв (слов) алфавита  в буквы (слова) алфавита .

При представлении сообщений в ЭВМ все символы кодируются байтами (например, стандарт кодирования ASCII) или двумя байтами (стандарт UNICOD).

Сообщение, которое мы хотим передать адресату, назовем открытым сообщением. Зашифрованное сообщение – закрытое сообщение.

Процесс преобразования открытого сообщения в закрытое сообщение и есть шифрование. Если  – открытое сообщение,  – закрытое сообщение (шифр),  – правило шифрования, то имеется зависимость вида: .

Правила шифрования должны быть выбраны так, чтобы зашифрованное сообщение можно было бы расшифровать. Однотипные правила объединяются в классы правил и внутри класса определяется некоторый параметр, позволяющий перебирать все такие правила.

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

При кодировании нет такого секретного ключа, так как кодирование ставит целью лишь более сжатое, компактное представление сообщения.

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

Принцип Кирхгоффа: секретность зашифрованных сообщений определяется секретностью ключа.

Это означает, что если даже алгоритм шифрования будет известен криптоаналитику, тот, тем не менее, не в состоянии будет расшифровать закрытое сообщение, если не располагает соответствующим ключом.

В российских и американских шифрах часто используется -битовый ключ, а число различных ключей (пространство ключей) составляет при этом .

Для измерения количества информации используются различные подходы и методы.

Количество информации – число, адекватно характеризующая структурированность, определенность в оцениваемой системе.

Количество информации часто оценивается в битах.

Рассмотрим меру информации по Р. Хартли.

Пусть известны  состояний системы  ( опытов с различными, равновозможными, последовательными состояниями системы). Мера разнообразия множества состояний системы задается формулой Р. Хартли:



Если во множестве  искать произвольный элемент, то для его нахождения (по Хартли) необходимо иметь не менее  (бит) информации.

Уменьшение  говорит об уменьшении разнообразия состояний  системы. Увеличение  говорит об увеличении разнообразия состояний  системы.

Мера Хартли подходит лишь для идеальных систем, так как в реальных системах состояния системы обычно не одинаково осуществимы (не равновероятны).

Для реальных систем используют более подходящую меру К. Шеннона. Мера Шеннона оценивает информацию отвлеченно от ее смысла:



где  – число состояний системы;  – вероятность (относительная частота) перехода системы в -ое состояние, а сумма всех  должна равняться .

Если все состояния рассматриваемой системы равновозможны, равновероятны, то есть , то из формулы Шеннона можно получить (как частный случай) формулу Хартли:



.

В термодинамике известен так называемый коэффициент Больцмана  (эрг/град) и формула Больцмана для энтропии или меры хаоса в термодинамической системе:



Сравнивая выражения для  и  можно заключить, что величину I можно понимать как энтропию из-за нехватки информации в системе (о системе).

Основное функциональное соотношение между энтропией и информацией имеет вид:



Из этой формулы следуют важные выводы:

1. увеличение меры Шеннона свидетельствует об уменьшения энтропии системы;
   
2. уменьшение меры Шеннона свидетельствует об увеличении энтропии системы.
   

Утверждение – основная единица, неделимая с точки зрения отражения смысла информации (семантики).

Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать, истинно оно или ложно.

Эти два значения всевозможных высказываний обозначаются  и ,  и  или  и .

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

Предикат – выражение, формула с логическими переменными, имеющая смысл при любых допустимых значениях этих переменных.

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

Множество логических переменных  с определенными над ним операциями:

•  – отрицания или инверсии,
  
•  – логического сложения или дизъюнкции,
  
•  – логического умножения или конъюнкции
  

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

1. Аксиома двойного отрицания:.
   
2. Аксиомы ассоциативности:, .
   
3. Аксиомы переместительности:, .
   
4. Аксиомы одинаковых операндов:, .
   
5. Аксиомы поглощения: , .
   
6. Аксиомы распределения: , .
   
7. Аксиомы де Моргана:, .
   
8. Аксиомы нейтральности:, .
   
9. Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем: , , , .
   

Из этих аксиом следует ряд полезных соотношений, например,

, , , , , .

Такая таблица всех значений некоторой логической функции называется таблицей истинности этой функции.

Кроме указанных трех базовых операций можно с их помощью ввести еще следующие важные операции алгебры предикатов:

1. импликации: ;
   
2. эквиваленции: .
   

Операции импликации и эквиваленции имеют важное значение в правовой сфере, при решении задач, связанных с умозаключениями, выводами.

Всегда истинные формулы называют тавтологиями.

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

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

Задача доказательства равенства двух логических выражений (функций) состоит в установлении эквивалентности этих функций.

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

Рассмотрим пример формализации и решения правовой информационно–логической задачи.

Пусть Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем "Бьюике", Джонс сказал, что это был черный "Крайслер", Смит утверждал, что это был "Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определим истинный цвет и истинную марку автомобиля.

Рассмотрим простые высказывания вида: , ,, , . На их основе, высказывание Брауна можно записать в виде сложного логического выражения вида , высказывание Джонса – в виде , а высказывание Смита – в виде . Так как в каждом из этих выражений одна из переменных принимает значение "истина", то истинны и дизъюнкции вида: , , . По определению конъюнкции, . Упростим это выражение:



Мы использовали тот факт, что одновременно не могут быть истинными два высказывания относительно цвета или два высказывания относительно марки машины. Так как конъюнкция истинна только тогда, когда , , , то заключаем, что автомобиль был черным "Бьюиком".

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

Любая актуализация информации опирается на какие–то данные, любые данные могут быть каким–то образом актуализированы.

Данные – это некоторые сообщения, слова в некотором заданном алфавите.

Данные актуализируются, хранятся с помощью некоторых алгоритмов, процедур. В свою очередь, процедуры, алгоритмы существенно зависят от типа и структуры обрабатываемых ими данных.


Тема 4. Теоретические основы правовой информатики

В лекции рассматриваются основы теоретической правовой информатики, в частности, базовые понятия "код", "шифр", "количество информации", меры информации, логические высказывания и инфологические задачи, понятия алгоритма и данных для алгоритмов.

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

Сообщения измеряются в байтах, килобайтах, мегабайтах, гигабайтах, терабайтах, петабайтах и эксабайтах, реализуются в ЭВМ в битах.

Основные соотношения между единицами измерения сообщений: 1 бит (binary digit – двоичная единица) = 0 или 1; 1 байт = 8 битов; 1 килобайт (1К) = 213 бит; 1 мегабайт (1М) = 223 бит; 1 гигабайт (1Г) = 233 бит; 1 терабайт (1Т) = 243 бит; 1 петабайт (1П) = 253 бит; 1 эксабайт (1Э) = 263 бит.

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

Кодирование – процесс преобразования букв (слов) алфавита  в буквы (слова) алфавита .

При представлении сообщений в ЭВМ все символы кодируются байтами (например, стандарт кодирования ASCII) или двумя байтами (стандарт UNICOD).

Сообщение, которое мы хотим передать адресату, назовем открытым сообщением. Зашифрованное сообщение – закрытое сообщение.

Процесс преобразования открытого сообщения в закрытое сообщение и есть шифрование. Если  – открытое сообщение,  – закрытое сообщение (шифр),  – правило шифрования, то имеется зависимость вида: .

Правила шифрования должны быть выбраны так, чтобы зашифрованное сообщение можно было бы расшифровать. Однотипные правила объединяются в классы правил и внутри класса определяется некоторый параметр, позволяющий перебирать все такие правила.

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

При кодировании нет такого секретного ключа, так как кодирование ставит целью лишь более сжатое, компактное представление сообщения.

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

Принцип Кирхгоффа: секретность зашифрованных сообщений определяется секретностью ключа.

Это означает, что если даже алгоритм шифрования будет известен криптоаналитику, тот, тем не менее, не в состоянии будет расшифровать закрытое сообщение, если не располагает соответствующим ключом.

В российских и американских шифрах часто используется -битовый ключ, а число различных ключей (пространство ключей) составляет при этом .

Для измерения количества информации используются различные подходы и методы.

Количество информации – число, адекватно характеризующая структурированность, определенность в оцениваемой системе.

Количество информации часто оценивается в битах.

Рассмотрим меру информации по Р. Хартли.

Пусть известны  состояний системы  ( опытов с различными, равновозможными, последовательными состояниями системы). Мера разнообразия множества состояний системы задается формулой Р. Хартли:



Если во множестве  искать произвольный элемент, то для его нахождения (по Хартли) необходимо иметь не менее  (бит) информации.

Уменьшение  говорит об уменьшении разнообразия состояний  системы. Увеличение  говорит об увеличении разнообразия состояний  системы.

Мера Хартли подходит лишь для идеальных систем, так как в реальных системах состояния системы обычно не одинаково осуществимы (не равновероятны).

Для реальных систем используют более подходящую меру К. Шеннона. Мера Шеннона оценивает информацию отвлеченно от ее смысла:



где  – число состояний системы;  – вероятность (относительная частота) перехода системы в -ое состояние, а сумма всех  должна равняться .

Если все состояния рассматриваемой системы равновозможны, равновероятны, то есть , то из формулы Шеннона можно получить (как частный случай) формулу Хартли:



.

В термодинамике известен так называемый коэффициент Больцмана  (эрг/град) и формула Больцмана для энтропии или меры хаоса в термодинамической системе:



Сравнивая выражения для  и  можно заключить, что величину I можно понимать как энтропию из-за нехватки информации в системе (о системе).

Основное функциональное соотношение между энтропией и информацией имеет вид:



Из этой формулы следуют важные выводы:

1. увеличение меры Шеннона свидетельствует об уменьшения энтропии системы;
   
2. уменьшение меры Шеннона свидетельствует об увеличении энтропии системы.
   

Утверждение – основная единица, неделимая с точки зрения отражения смысла информации (семантики).

Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать, истинно оно или ложно.

Эти два значения всевозможных высказываний обозначаются  и ,  и  или  и .

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

Предикат – выражение, формула с логическими переменными, имеющая смысл при любых допустимых значениях этих переменных.

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

Множество логических переменных  с определенными над ним операциями:

•  – отрицания или инверсии,
  
•  – логического сложения или дизъюнкции,
  
•  – логического умножения или конъюнкции
  

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

1. Аксиома двойного отрицания:.
   
2. Аксиомы ассоциативности:, .
   
3. Аксиомы переместительности:, .
   
4. Аксиомы одинаковых операндов:, .
   
5. Аксиомы поглощения: , .
   
6. Аксиомы распределения: , .
   
7. Аксиомы де Моргана:, .
   
8. Аксиомы нейтральности:, .
   
9. Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем: , , , .
   

Из этих аксиом следует ряд полезных соотношений, например,

, , , , , .

Три базовые операции определяются таблицей их значений вида:

Такая таблица всех значений некоторой логической функции называется таблицей истинности этой функции.

Кроме указанных трех базовых операций можно с их помощью ввести еще следующие важные операции алгебры предикатов:

1. импликации: ;
   
2. эквиваленции: .
   

Операции импликации и эквиваленции имеют важное значение в правовой сфере, при решении задач, связанных с умозаключениями, выводами.

Всегда истинные формулы называют тавтологиями.

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

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

Задача доказательства равенства двух логических выражений (функций) состоит в установлении эквивалентности этих функций.

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

Рассмотрим пример формализации и решения правовой информационно–логической задачи.

Пусть Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем "Бьюике", Джонс сказал, что это был черный "Крайслер", Смит утверждал, что это был "Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определим истинный цвет и истинную марку автомобиля.

Рассмотрим простые высказывания вида: , ,, , . На их основе, высказывание Брауна можно записать в виде сложного логического выражения вида , высказывание Джонса – в виде , а высказывание Смита – в виде . Так как в каждом из этих выражений одна из переменных принимает значение "истина", то истинны и дизъюнкции вида: , , . По определению конъюнкции, . Упростим это выражение:



Мы использовали тот факт, что одновременно не могут быть истинными два высказывания относительно цвета или два высказывания относительно марки машины. Так как конъюнкция истинна только тогда, когда , , , то заключаем, что автомобиль был черным "Бьюиком".

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

Любая актуализация информации опирается на какие–то данные, любые данные могут быть каким–то образом актуализированы.

Данные – это некоторые сообщения, слова в некотором заданном алфавите.

Данные актуализируются, хранятся с помощью некоторых алгоритмов, процедур. В свою очередь, процедуры, алгоритмы существенно зависят от типа и структуры обрабатываемых ими данных.