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, была наименьшей.
Кодирование должно быть таким, чтобы при передаче его не было искажения информации.
Простота (сложность) декодирования. И т.д.