Некоторые общезначимые формулы с кванторами.

1. ()Р (х) ( х) .

2. ()Р (х) ( х) .

3. ( х) Р (х) () .

4. ( х) Р (х) () .

5. ( х) Р (х) ( х) Q(х) ( х) (Р (х) Q(х)).

6. ( х) Р (х) ( х) Q(х) ( х) (Р (х) Q(х)).

7. ( х) ( у) Р (х, у) у х Р (х, у).

8. ( х) ( у) Р (х, у) ( у) ( х) Р (х, у).

9. ( х) ( у) Р (х, у)  ( у) ( х) Р (х, у).

10. ( х) Р (х) ( х) Q(х)  ( х) (Р (х) Q(х)).

11. ( х) (Р (х) Q(х))  ( х) Р (х) ( х) Q(х).

12. ( х) (Р (х) Q(х))  (( х) Р (х) ( х) Q(х)).

13. ( х) Р (х)  Р (у).

14. Р (у)  ( х) Р (х).

Мы ранее  установили равносильность левой и правой частей формул 1-8, следовательно, эквиваленциии будут общезначимыми формулами.

Идея доказательства формул 9-12 заключается в том, что область истинности левой части включается в область истинности правой части. Рассмотрим на примере формулы 10:

( х) Р (х) ( х) Q(х)  ( х) (Р (х) Q(х)).

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

Пусть области истинности предикатов Р (х) и Q(х) не совпадают с А. Тогда левая часть импликации ложна, следовательно, импликация истинна.

Если одна из областей истинности совпадает с А, например М_р = А, но тогда ( х) Р (х) = 1, значит вся левая часть импликации истинна. Так как область истинности Р (х)  Q(х) является объединением областей истинности предикатов, то она совпадает с А, следовательно, правая часть импликации истинна, и импликация истина. Тем самым доказана общезначимость формулы 10.

Докажем теперь формулу 13 - ( х) Р (х)  Р (у):

Предикат Р задан на некотором множестве U.

Пусть Р (у) (у из U) – ложно, но тогда ложно ( х) Р (х) (х из U), так как импликация истинна. Если Р (у) – истина, то и импликация – истина.

Докажем формулу 14:

Р (у)  ( х) Р (х).

Пусть М = Ø, тогда ( х) Р (х) - ложно. Но тогда и Р (у) ложно. Следовательно, импликация истинна. Если М Ø, то ( х) Р (х). - истина, следовательно, импликация истина.

Рассуждения.

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

Рассуждение считается правильным, если из истинности посылок , ,…,  не может следовать ложного заключения.

, ,…, ^├         (1)

Рассмотрим формулу  (к=1,…,n)        (2)

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

Необходимость.

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

Достаточность.

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

Пример.

На множестве рациональных чисел  рассмотрим рассуждение:

Если число целое, то оно рациональное. Число 3 – целое, следовательно, оно рациональное.

Введем обозначения:

С (х), х – целое. R(x). х – рациональное.

Рассуждение принимает вид

( х) (С (х)  R(x)), С(3) ^├ R(3).

Рассмотрим формулу х (С (х) R(x)). Значит при х -3 получим С(3) R(3)=1, тогда С(3) R(3), С(3) ^├ R(3) по ПЗ.

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

другие правила вывода, основанные на общезначимых формулах:

, - ввод единичного (ВЕ).

 - правило ввода логической функции (ВЛ).

Вывод.

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

Пример.

Если в параллелограмме все стороны равны, то он – ромб. В параллелограмме ABCD все стороны равны, следовательно, он – ромб.

Введем обозначения:

Р (х), х – параллелограмм с равными сторонами.

R(x), x – ромб.

Рассуждение выглядит так:

 ( х) (Р (х) R(x)), Р(ABCD) ^├ R(ABCD).

Построим вывод:

1) ( х) (Р (х) R(x)) – посылка.

2) Р (у) R(у), ВЛ.(1).

3) Р(ABCD) – посылка.

4) R (ABCD), ВЕ (2, 3).

Можно рассмотреть и другие правила вывода, и другие примеры рассуждений.

 

 

 

Кодирование информации.

Задача кодирования.

Пусть имеется некоторое множество А = { , ,…, }. Будем называть это множество алфавитом, а объекты – буквами. Кортеж из букв = , ,…,  будем называть словом. Последовательность слов – S называется сообщением. Множество сообщений над алфавитом А будем обозначать А ..

Пусть имеется алфавит В= { , ,…, }.

 Задача кодирования заключается в том, что сообщение S, заданное над алфавитом А, преобразуется в сообщение S , заданное над алфавитом В (код). Функция f(), переводящая сообщение S в S , называется кодированием. Последовательность символов , ,…, , соответствующая букве алфавита А, называется элементарным кодом этой буквы.

Общее количество символов  - длина кода.

Замечание: в качестве буквы алфавита А, могут выступать и сообщения.

Функция, обратная функции кодирования F  (), называется декодированием.

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

Примеры:

 Кодирование должно допускать декодирование.

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

Кодирование должно быть таким, чтобы при передаче его не было искажения информации.

Простота (сложность) декодирования. И т.д.

Равномерное кодирование.

Равномерное кодирование – это кодирование, при котором каждый элементарный код имеет одинаковую длину.

Например, если выбрать в качестве алфавита В цифры, то одноразрядным кодом можно закодировать 10 символов, а двухразрядными числами – 100.

Пусть алфавит В содержит к букв, а длина элементарного кода n букв. Сколько символов (m) при равномерном кодировании можно закодировать?

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

m = к ⁿ (1)

Поставим обратную задачу. Имеется m букв алфавита А. Сколько букв должны содержать элементарные коды при равномерном кодировании?

Из формулы (1), логарифмируя, получим

n = logк m   (2)

 Если же алфавит В={0,1} – двоичный, то закодировать n – битным кодом можно в силу формулы (1)

m = 2 ⁿ (3) букв.

Пусть имеется алфавит А, состоящий из m символов. Сколько бит должен содержать каждый элементарный код при равномерном кодировании?

Из формулы (2) получим

n = log ₂ m    (4), если m – степень 2

и по формуле

n =\ log   m | + 1 (5),

  где |log  m | - целая часть log  m..

Формулы (4) - (5) называются формулами Хартли.

Если в качестве алфавита А взять русский алфавит, который содержит 33 символа и пробел, то для 34 символов: по формуле Хартли

n =|log  34 | +1=5+1- 6 бит. При этом мы можем 6-битным кодом закодировать еще 30 символов. Такое кодирование называется избыточным. В компьютерах применяется 1-байтовое кодирование (256 символов) и оно также является избыточным.

Задача: Дано сообщение S. Производится равномерное кодирование длиной k – бит. Найти общую длину кода.

Решение: Если длина сообщения |S|= , то длина кода L=k .

Алфавитное кодирование.

Алфавитное кодирование – это кодирование, при котором каждой букве алфавита А соответствует элементарный код алфавита В.

Если некоторое слово  может быть представлено в виде двух частей = , то  называется префиксом, а  - постфиксом. Естественно разбиение слова на префикс и постфикс чаще всего неоднозначно. Например, в слове 00110 префиксом может быть 0, или 00, или 001, или 0011.