Интерпретация и свойства высказываний

Виды интерпретации:

1. внутренняя (логическая) – осуществляется с помощью таблиц истинности.

2. внешняя (физическая) – связана с трактовкой формул на естественном языке.

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

· (a → b) – если a, то b; в случае а имеет место b; для b необходимо а;

· (a b) – a и b; не только а, но и b; b несмотря на а; а вместе с b;

· (a b) – а или b; a или b или вместе;

· а – не а; а не имеет места; а неверно.

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

1. Исчисление высказываний как формальная система

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

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

1. Базовые элементы (алфавит) Т:

· пропозициональные буквы a, b, c, …, A, B, C, … с индексами и без них;

· логические операторы и пропозициональные связки ();

· скобки.

Зависимость значения истинности новых высказываний определяется таблицей истинности.

X	Y	X Y	X Y	X	X Y	X Y

2. Синтаксические правила S:

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

· если а есть формула, то и (а) также является формулой;

· если а есть формула, то и отрицание а также является формулой;

· если а и b являются формулами, то и выражения (a b, a b, a b) также являются формулами.

3. Аксиомы А:

Существует несколько систем аксиом.

Система аксиом Гильберта:

· (А 1) ((а а) а) – закон сокращения;

· (А 2) (а (а b)) – закон расширения;

· (А 3) ((a b) (b a)) – закон коммутативности.

4. Правила вывода B.

a) Правило «modus ponens» (правило отделения):

Если а и (а b) являются теоремами, то b есть следствие а, т.е. выводимо из а.

(а) и (a b) b

Если истинно утверждение а и истинно, что а следует из b, то истинно b.

b) Правило подстановки:

Букву можно заменять формулой (для всех вхождений).

 

В исчислении высказываний выводимая формула называется теоремой.

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

 

1. Нормальные формы в логике высказываний. Алгоритм преобразования формулы в дизъюнктивную нормальную форму (ДНФ)

Литерал – атомарная формула (кроме логических 1 и 0) или ее отрицание.

Элементарной конъюнкцией называется литерал или конъюнкция литералов.