Пропозициональная формула - противоречие

Пропозициональная формула - тавтология.

Лекция 2.

Логика высказываний.

Переменная, допустимыми значениями которой являются произвольные высказывания, называется пропозициональной переменной. В качестве пропозициональных переменных мы будем использовать большие латинские буквы P,Q,R,... (возможно с индексами; например, P₃,Q₇,R_n).

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

1) любая пропозициональная переменная является пропозициональной формулой;

2) если А и В — пропозициональные формулы, то ¬А, (А & В), (А ∨ В), (A⊃B), (A ≡ В) — пропозициональные формулы.

Например, выражения

(P ⊃ Q), (P ⊃ (Q ⊃ R)), (P⊃ (Q⊃ (P&Q)))

являются пропозициональными формулами.

Если в пропозициональную формулу А, построенную из пропозициональных переменных P₁,... ,Р_п, вместо этих переменных подставить конкретные высказывания, то получится некоторое высказывание.

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

(Р ∨ ¬P) — закон исключенного третьего;

(¬¬Р ≡ Р) — закон двойного отрицания;

¬ (P ∧ ¬ P) — закон противоречия;

(((Р ⊃ Q) ⊃ P) ⊃ Р) — закон Пирса.

Очевидно, что истинностное значение высказывания, полученного подстановкой в пропозициональную формулу конкретных высказываний вместо пропозициональных переменных, зависит только от истинностных значений подставляемых высказываний. Поэтому довольно легко можно проверить, является ли данная пропозициональная формула тавтологией. Для этого достаточно перебрать всевозможные подстановки в эту формулу значений И и Л вместо пропозициональных переменных (таких подстановок ровно 2ⁿ, где п — число переменных в формуле), и для каждой такой подстановки вычислить соответствующее значение формулы, пользуясь истинностными таблицами для логических операций. Формула является тавтологией тогда и только тогда, когда при любой подстановке она принимает значение И.

Упражнение.

1. Доказать интерполяционную теорему: если пропозициональная формула A ⊃ В — тавтология, и формулы ¬А и В не являются тавтологиями, то существует пропозициональная формула С, содержащая только те переменные, которые входят как в А, так и в В, такая, что формулы А ⊃ С и С ⊃ В суть тавтологии.

Пропозициональная формула является противоречием, если при подстановке в формулу вместо пропозициональных переменных Р ₁,…, Р_п любых значений, получим конкретное высказывание являющееся ложью. Например:

P & ¬ P - противоречие

Дата добавления: 2014-01-20