Исчисление высказываний

Высказывание Под высказыванием понимается утвердительное предложение, которое может быть либо истинным, либо ложным, но не то и другое одновременно. x: земля круглая, y 4 : плотность воды составляет 0.5т/м3, z: идет дождь.

Построение формальных теорий Выбирается алфавит теории, т. е совокупность разрешимых символов. Указывается правило составления «правильных» выражений – формул. Из множества формул делается выделение формулы или аксиомы. Указываются правила вывода, т. е правила получения теорем.

Пропозициональная переменная и формула Пропозициональная переменная переменная, значением которой может быть логическое высказывание. 1. Если P пропозициональная переменная, то P формула. 2. Если A формула, то ¬А формула. 3. Если A и B формулы, то (AB), (A B ) и (A B) формулы. 4. Других соглашений нет. Знаки ¬,, и (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками.

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

Аксиомы ФИВ

Правила вывода

Теоремы A A, A A (закон двойного отрицания) A (A B) (из ложного, что угодно) ( B A) (A B), (A B) ( B A) (закон противоположности) A ( B (A B))

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

Предикаты Местностью предиката называется количество различных предикатных переменных, входящих в предикат. Одноместный предикат - x впадает в Каспийское море Двухместный предикат - x впадает в y.

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

Множество истинности Множество истинности P+ предиката P(x), определенного на базовом множестве M (xM), называется множество тех элементов xM, для которых P(x) истинно.

Равносильность и следствие

Теоремы Пусть из P Q, т.е. Q следствие P, тогда если P – тождественно-истинно (выполнимо), то и Q – тождественно- истинно (выполнимо). Если Q – тождественно-ложный (опровержимый) предикат, то и P – тождественно-ложный (опровержимый) предикат.

Кванторы Квантор общее название для логических операций, ограничивающих область истинности какого-либо предиката. Квантор всеобщности (обозначение:, читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»). Квантор существования (обозначение:, читается: «существует…» или «найдётся…»).

Квантификация x P(x) x y P(x,y,z)